Re: longest chain! is that a DFS?
- To: mathgroup at smc.vnet.net
- Subject: [mg78793] Re: longest chain! is that a DFS?
- From: Peter Pein <petsie at dordos.net>
- Date: Tue, 10 Jul 2007 06:20:51 -0400 (EDT)
- References: <f6siaj$86s$1@smc.vnet.net>
Hi Chekad,
I took the data from the Bi (which differ from S):
S := {{{1, 2}, {2, 3}, {2, 4}, {5, 6}},
{{1, 4}, {2, 8}, {4, 5}, {6, 7}},
{{8, 1}, {8, 5}, {7, 8}},
{{5, 2}, {8, 5}},
{{7, 3}}}
I added B5={{7,3}} to justify the use of
Last[DeleteCases[FoldList[....],{}]] instead of Fold, which is
sufficient if there are no "roads to nowhere".
B1 is obviously our set to start with. For each chain found so far,
replace those elements of the next B which start with the end of the
chain with its second element appended to the chain. *phew*
maximalPath :=
Last[DeleteCases[FoldList[Function[{p, q},
Flatten[(Cases[q, {Last[#1], y_} :> Join[#1, {y}]] & ) /@ p, 1]],
First[#1], Rest[#1]], {}]] &
maxPath2[S]
{{1, 2, 8, 5, 2}, {5, 6, 7, 8, 5}}
Regards,
Peter
mumat schrieb:
> Hi there Everyone,
>
> Here is my question.
>
> Assume S is the set {B1,B2,...,Bn} where Bi's are non-empty sets of
> ordered pairs of A={1,2,3,...,8} ( <--- for simplicity).
>
> our goal is to list all sequences of the form
>
> X_1,X2,X3,X_4,...,X_m over A
>
> of m, the longest possible length for which
>
>
> for every i: (X_i, X_(i+1)) is in B_i AND (X_(i+1),X_(i
> +2)) is in B_(i+1).
>
>
> For instance, ( with Notation: ab:={a,b})
>
> S={ {12,23,24,56}, {14,28,45,67},{81,15,78}, {56,85} }, so
>
>
> B1={12,23,24,56},B2={14,28,45,67},B3={81,85,78},B4={52,85}.
>
>
> seq: 1,2,8,5,2 is of longest possible length 5.
>
> 2,4,8,5,2 is another sequence of longest length.
>
>
> Any help would be greatly appreciated.
>
> Best regards,
>
> chekad sarami
>
>