Boost Graph Library, Algorithmus um alle Pfade von den Inputs zu den Outputs enumerieren

[Ku-Klux-Klowns]

Hallo Leute,

ich habe benutze die Boost Graph Library um digitale Schaltungen abzubilden,
in digitalen Schaltungen gibt es Inputs und Outputs.
Logik-Gatter sind Nodes in meinem Graphen und Kanten sind die Kabel zwischen den Gattern.
Ich moechte jetzt alle Pfade von den Inputs zu den Outputs ausgeben, gibt es da einen schoenen eleganten Algorithmus in der BGL der das kann oder allgemein
gibt es einen Algorithmus der alle Pfade in einem Graph enumerieren kann. In der Doku finde ich viele Algorithmen aber keinder schint genau zu passen.
Meine Graphen sind immer Directed Acylic Graphs (DAG)

Besten Dank,

[dfs]

Im Prinzip DFS ohne den Check ob ein Knoten bereits gesucht wurde.

void visit_all_paths(node n, node to, std::vector<int>& callstack)
{
  if (n == to) {
    output(callstack);
    return;
  }
  for (node m : n.adjacent_nodes) {
    callstack.push_back(n);
    visit_all_paths(m, to, callstack);
    callstack.pop_back();
  }
}

(ich kenne BGL nicht, da geht das aber sicher ganz einfach)

Die Performance ist sowieso im A... weil das unter Umständen sehr viele Wege sein können, O(N!) um genau zu sein. Willst du wirklich alle ausgeben?

[dfs]

Oh, wenn das ein DAG ist, dann hast du "nur" O(exp(N)).

[Ku-Klux-Klowns]

Zu Beginn moechte ich alle ausgeben. Spaeter kann ich evtl. einschraenken.