5
$\begingroup$

I would like to efficiently construct all lists subject to certain relations. For example, I have the following "root objects" and rules:

{a,b}
{a->{c,d},b->{e}}
{c->{f},d->{g,h},e->{i}}

and would like to get

{{a,c,f},{a,d,g},{a,d,h},{b,e,i}}

If the pattern isn't clear, I'm essentially looking for all three-element lists such that successive elements are "allowed" by the rules. You may think of it as all length 2 traversals of a rooted tree of height 2.

This is a very simple toy example. I would like to be able to deploy this algorithm on "root objects" and rules which will lead to several dozen millions of lists, through perhaps 8-10 bouts of rules (the example above had only 2). I have an algorithm that can do this, but it scales very poorly and I'd like to rewrite it.

Is there a built-in Mathematica function that can handle this efficiently? I've been playing with Distribute and Thread, but couldn't quite get them to work.

Thanks for your help!

$\endgroup$
7
$\begingroup$

Dirty,but work well. :)

Construct a graph

rule1 = {a -> {c, d}, b -> {e}};
rule2 = {c -> {f}, d -> {g, h}, e -> {i}};
graph = Graph[Flatten[Thread /@ # & /@ {rule1, rule2}],VertexLabels -> "Name"]

Find all path from source vertex to sink vertex

Catenate[FindPath @@@Catenate[Tuples[{{#},GraphComputation`SourceVertexList[#], 
       GraphComputation`SinkVertexList[#]}]&/@WeaklyConnectedGraphComponents[graph]]]

{{a,d,g},{a,d,h},{a,c,f},{b,e,i}}

$\endgroup$
3
$\begingroup$

In version 10.1 I do not have WeaklyConnectedGraphComponents so here is a try without it:

roots = {a, b};
rule1 = {a -> {c, d}, b -> {e}};
rule2 = {c -> {f}, d -> {g, h}, e -> {i}};

graph = Graph[Join @@ Thread /@ Join[rule1, rule2]];

find[g_Graph] := find[g, VertexList@g]

find[g_, v_][root_] := (
  GraphDistance[g, root]
    // Pick[v, #, Max[# /. ∞ -> -1]] &
    // Map[FindPath[g, root, #] &]
    // Catenate
 )

find[graph] /@ roots
{{{a, c, f}, {a, d, g}, {a, d, h}}, {{b, e, i}}}
$\endgroup$
  • $\begingroup$ You even have no GraphComputation`SinkVertexList?If so,that mean the WR is expanding the package GraphComputation` still? $\endgroup$ – yode Apr 2 '17 at 12:26
  • $\begingroup$ @yode I was mistaken; I do have the GraphComputation functions but their names were shown in blue so I thought I did not. However what I do not have is WeaklyConnectedGraphComponents which is what prevented your code from working on my system. $\endgroup$ – Mr.Wizard Apr 3 '17 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.