Generieren aller DAGs mit n Vertices

Ich möchte alle DAGs mit n Vertices, bis zu Isomorphie generieren - das heißt, unbenannte DAGs ohne Duplikate. Ja, ich weiß, dass es eine Lot von diesen gibt, aber ich bin hauptsächlich mit kleinen Zahlen betroffen (z. B. n weniger als 10), wo Zeug noch handhabbar ist.Generieren aller DAGs mit n Vertices

Offensichtliche Ansätze wie alle möglichen Kombinationen von Kanten hinzugefügt haben zwei Hauptnachteile:

Eine solche mehr Duplikate (Isomorphen) als einzigartige grafische Darstellungen erzeugt, vor allem als n wächst.
Jedes generierte Diagramm muss überprüft werden, um festzustellen, ob es Zyklen enthält.

Quelle

2016-07-09 BeeOnRope

Siehe http://cs.stackexchange.com/questions/29552/enumerate-all-non-isomorphic-graph-of-a-certain-size –

Ich habe. Soweit ich weiß, ist Nauty nur für ungerichtete Graphen effektiv. Es ist theoretisch möglich, alle ungerichteten Graphen und dann alle nicht-isomorphen Orientierungen solcher Graphen zu erzeugen, aber dieser Ansatz ist nicht praktikabel, wenn Beschränkungen wie keine Zyklen gegeben sind. – BeeOnRope

Sie können mit einem simple complete graph Kn beginnen, wobei n die Ordnung des Graphen ist und dann alle seine spanning trees aufzuzählen. The algorithm ist ein modifiziertes DFS, indem es Backtracking verwendet und bridges vermeidet (um weiterhin verbundene Bäume zu erzeugen), während es alle möglichen unterschiedlichen Kombinationen untersucht.

Nach Cayley's formula gibt es n^(n-2) (wo ^ zu einer Potenzierung bezeichnet) Spanning Bäume auf einem Kn, so dass Ihr schlimmster Fall wahrscheinlich wie 9^7=4782969 aussieht und schließt Duplikate.

Dies erinnert auch an einem „Teilproblem“ in Motif Detection wo das Ziel, für some algorithms (oder this one) ist all simple connected graphs (not limited to trees) of order n (motifs) zu erzeugen, um eine Zersetzung des Graphen in diese n Motive dann zu erzeugen. Diese Literatur könnte dir also auch von Nutzen sein.

Hoffe, das hilft.

Quelle

2016-07-24 21:04:05

Das Hauptproblem ist "mit Duplikaten". Ich war nicht klar genug in meiner Frage (ich habe jetzt eine Klarstellung hinzugefügt), aber der Haupttrick besteht darin, die Duplikate (d. H. Die Erzeugung von DAGs, die isomorph sind) zu vermeiden, die den meisten naiven Ansätzen innewohnen. Auch Ihre Schätzung für 'n = 9' scheint nicht zu stimmen - tatsächlich gibt es (ohne Duplikate) 20.286.025 unmarkierte DAGs für 'n = 9' - bereits mehr als Ihre 4.782.969 (die Duplikate hat) - siehe [A003087] (https : //oeis.org/A003087). – BeeOnRope

In der Tat scheint es, dass der Spanning-Tree-Ansatz nicht funktionieren kann. Zum Beispiel, wie gehst du vom (ungerichteten) aufspannenden Baum zu einer DAG? Wie würde dann das Richten der Kanten eines aufspannenden Baums jemals die triviale "Diamant-DAG" erzeugen, in der Sie "a -> {b, c}, {b, c} -> d" haben? Solch ein DAG hat einen Zyklus in seinem ungerichteten Skelett, so dass ich nicht sehe, wie die Kanten eines Baumes (der keine Zyklen hat) erzeugt werden könnten. – BeeOnRope

Es ist nicht meine Schätzung, alles, was ich tat, war Cayleys Formel zu verwenden und es zählt bestimmte Bäume zweimal. Aber ja, ich habe mich nicht an "gerichtet" gehalten. Sie könnten Duplikate mit einer Metrik markieren und sie während der Erkennung ablehnen, aber das ist nur ein Mittel. Für das DAG-Problem, siehe Motive. Viele mehr, weil jede Kante drei Zustände hat. Darf ich fragen, an was für einem Problem du arbeitest? –

Antwort

Verwandte Themen