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
>