MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: find all paths


I've cobbled something together that works, but I still feel there
ought to be an easier way.

Here's what I came up with:

addV[g_Graph, p_List] := Union[Flatten[
    Outer[
      If[OutDegree[g, Last[#1]] == 0,
        #1,
        If[Last[#1] == First[#2], Join[#1, Drop[#2, 1]]]
      ]&, p, Edges[g], 1
    ] /. Null -> Sequence[],
  1]
];

allPaths[g_Graph] := FixedPoint[
    addV[g, #] &,
    List /@ Select[Range[V[g]], InDegree[g, #] == 0 &]
]

So, for example, if in a given graph g, we have

In[1] := Edges[g]
Out[1] := {{1, 8}, {3, 5}, {4, 2}, {4, 6}, {5, 7}, {6, 1}, {6, 7}, {9,
2}, {9, 4}, {9, 6}, {10, 9}}

then the "allPaths" function yields

In[2] := allPaths[g]
Out[2] := {{3, 5, 7}, {10, 9, 2}, {10, 9, 4, 2}, {10, 9, 6, 7}, {10,
9, 4, 6, 7}, {10, 9, 6, 1, 8}, {10, 9, 4, 6, 1, 8}}

as desired. (I don't think I mentioned before that I was only
interested in the function returning "maximal" paths.)

I'd love to see something cleaner...

- Matt

On 6/22/07, Matt Enlow <mattenlow at gmail.com> wrote:
> Calling all Combinatorica pros! This is driving me nutty.
>
> I'd like to find a way to get a list of all paths through a given
> directed, acyclic graph. This would presumably be a list of lists of
> integers, each list indicating a sequence of vertices.
>
> I thought this might be something that would come up often enough to
> warrant its own built-in function, but I couldn't find one. (There are
> functions that will give you the "shortest" path, but not all paths.)
> I also feel as though there must be certain built-in functions that
> would make creating my own such "list all paths" function relatively
> simple, but I don't know what they are either. It seems to me that
> someone with more Mathematica programming experience than I have would
> most likely look at this problem and come up with an idea for writing
> such a function rather quickly. Any takers?
>
> Thank you very much in advance,
>
> Matt Enlow
>


  • Prev by Date: Re: Re: PrimePi and limit of argument
  • Next by Date: Demonstrations and other Mathematica 6 Training
  • Previous by thread: find all paths
  • Next by thread: Parallel Computing Toolkit 2.1 now available