# Rule-based branching construction of lists

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!

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[{{#},GraphComputationSourceVertexList[#],
GraphComputationSinkVertexList[#]}]&/@WeaklyConnectedGraphComponents[graph]]]


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

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}}}

• You even have no GraphComputationSinkVertexList?If so,that mean the WR is expanding the package GraphComputation  still? – yode Apr 2 '17 at 12:26
• @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. – Mr.Wizard Apr 3 '17 at 1:51