Rule-based branching construction of lists

Question

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!

Answer 1

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

Answer 2

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