Re: find all paths

*To*: mathgroup at smc.vnet.net*Subject*: [mg78109] Re: find all paths*From*: "Matt Enlow" <mattenlow at gmail.com>*Date*: Sat, 23 Jun 2007 07:06:08 -0400 (EDT)*References*: <359434a80706220910j5e34db0q9e364ebef7061b1e@mail.gmail.com>*Reply-to*: mattenlow at gmail.com

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 >