I'm not sure what a topological search is, I understand a topological
sort.
AFAIK a topological sort is not a solution to my problem since it does
not work if there are cycles.
I'm not sure how I can be clearer with the problem, I can give another
example.
Given one sequence where
a) V -> W -> X -> Y -> Z (V comes before W which comes before X
etc)
and another where
b) W -> Y -> Z -> X -> V (W comes before Y which comes before Z
etc)
and
c) T -> U -> W-> Z -> X (T comes before U which comes before W
etc)
an ordering of the points which supports all the sequences would be
a b c
T /
U /
V /
W / / /
X /
Y / /
Z / / /
X / /
V /
where points V and X occur twice in the sequence because V occurs
before Z in sequence 'a' and after Z in sequence 'b'
and X occurs before Z in sequence 'a' and after Z in sequence 'c'.
I'd like to be able to extend that to arbitrary lengths and numbers of
sequences, minimizing the number of repeated points and keeping the
original sequences together as much as possible.
for example V T U W X Y Z X V is another ordering which satisfies the
all original sequences, but T U V W X Y Z X V
is better because it keeps all the points in sequence 'a' together.
Hope that helps.
On May 30, 1:21 pm, Chandrasekhar <[EMAIL PROTECTED]> wrote:
> Hi
>
> you problem is not very clear. But as far as i get it, it is somewhat like
> topological search.
>
> jus see what toplogical search is and chk if tht is wat u want.
>
> if not plz give a clearer picture of the prob.
>
> all the best
>
> bbye
>
> On 5/30/07, Edward <[EMAIL PROTECTED]> wrote:
>
>
>
>
>
>
>
> > I'm afraid I don't really know the correct teminology do describe this
> > problem, so I'm having trouble looking for generalised solutions.
>
> > I have a set of sequences of points I must traverse in order and and I
> > want to combine the set into one long sequence possibly with some
> > points repeated so that it still satisfies the original sequences.
>
> > So
> > 1) A -> B -> C -> D
> > 2) A -> C -> B -> D
> > 3) B -> C -> A -> D
>
> > combined together could create a sequence of
>
> > A -> C -> B -> C -> A -> D
>
> > 1 1 1 1
> > 2 2 2 2
> > 3 3 3 3
>
> > Can anyone advise me what this problem is called, or give me pointers
> > as to a solution?
> > I expect its a part of graph theory or something, but without knowing
> > the right terms its hard to look it up.
>
> --
> Chandrasekhar
> Final Year CSE
> NIT Allahabad- Hide quoted text -
>
> - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
