Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2007
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2007

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

Search the Archive

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
>


  • 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