Encoding gerichteten Graphen als Zahlen

Question

Sagen wir, dass ich einen gerichteten Graphen mit einer einzigen Wurzel und ohne Zyklen habe. Ich möchte eine Art auf jedem Knoten (zum Beispiel als eine ganze Zahl mit einem gewissen benutzerdefinierten Reihenfolge) hinzuzufügen, mit der folgenden Eigenschaft:

if Node1.type <= Node2.type then there exists a path from Node1 to Node2 

anzumerken, dass topologische Sortierung genügt tatsächlich die umgekehrte Eigenschaft:

if there exists a path from Node1 to Node2 then Node1.type <= Node2.type 

also kann es hier nicht verwendet werden.

Nun beachten Sie, dass Ganzzahlen mit natürlicher Ordnung hier nicht verwendet werden können, weil alle 2 ganzen Zahlen verglichen werden können, d. H. Die Reihenfolge der ganzen Zahlen ist linear, während der Baum nicht sein muss.

Also hier ist ein Beispiel. Es sei angenommen, dass der Graph hat 4 Knoten A, B, C, D und 4 Pfeile:

A->B, A->C, B->D, C->D 

So ist es ein Diamant. Jetzt können wir setzen

A.type = 00 
B.type = 01 
C.type = 10 
D.type = 11 

wo auf der rechten Seite haben wir Ganzzahlen im Binärformat. Der Vergleich ist bitweise definiert:

(X <= Y) if and only if (n-th bit of X <= n-th bit of Y for all n) 

Also ich denke, solche Reihenfolge könnte verwendet werden, die Frage ist, wie man Werte aus einem gegebenen Diagramm zu konstruieren? Ich bin mir nicht einmal sicher, ob die Lösung immer existiert. Irgendwelche Hinweise?

UPDATE: Da es einige Missverständnisse über Terminologie ich benutze lassen Sie mich mehr explicite sein: Ich habe Interesse an gerichteten azyklischen Graphen, so dass es ohne Vorgänger genau ein Knoten ist (auch bekannt als die Wurzel) und es gibt auf der eine Pfeil zwischen zwei Knoten. Der Diamant wäre ein Beispiel. Es nicht muss ein Blatt (d. H. Der Knoten ohne Nachfolger) haben. Jeder Knoten kann mehrere Vorgänger und mehrere Nachfolger haben. Man könnte sagen, dass dies eine teilweise geordnete Menge mit einem kleinsten Element ist (d. H. Ein eindeutiges global minimales Element).

Answer 1

Für jede DAG können Sie definieren als "es gibt einen Pfad von X nach Y". Diese Beziehung ist eine Teilaufordnung. Ich nehme an, dass die Frage ist, wie man diese Beziehung effizient darstellt.

Definieren Sie für jeden Knoten X ¡X als die Menge der von X erreichbaren Knoten (einschließlich X selbst). Die beiden Aussagen

• ¡X ist eine Teilmenge von ¡Y
• X erreichbar ist aus Y

sind äquivalent.

Codieren Sie diese Sätze als Bitsets (N-Bit-Binärzahlen), und Sie sind festgelegt.

Answer 2

Sie rufen die Beziehung <=, aber es ist nicht unbedingt vollständig (dh: es, dass für ein gegebenes Paar sein kann a und b, weder a <= b noch b <= a).

Hier ist eine Idee, wie man es definiert.

Wenn die Knoten 0 nummeriert, 1 ..., N-1, dann können Sie type wie folgt definieren:

type(i) = (1 << i) + sum(1 << (N + j), for j such that Path(i, j)) 

Und <= wie folgt definieren:

type1 <= type2 if (type1 >> N) & type2 != 0 

Das heißt type(i) kodiert den Wert i in den niedrigsten N Bits und die Menge aller erreichbaren Knoten in den höchsten N Bits. Die <=-Beziehung sucht nach dem Zielknoten im codierten Satz erreichbarer Knoten.

Diese Definition funktioniert unabhängig davon, ob Zyklen im Diagramm vorhanden sind oder nicht, und kodiert nur eine beliebige Beziehung auf Ihrer Knotengruppe.

Sie könnten die Definition ein wenig effizienter machen, indem Sie ceil(log2(N)) Bits verwenden, um die Knotennummer zu codieren (für eine Gesamtzahl von N + ceil(log2(N)) Bits pro type).

Answer 3

Die Frage besagt (und fährt fort zu sagen), dass die Eingabe ein Baum ist, aber eine spätere Bearbeitung widerspricht dem mit einem Beispiel einer Diamant-Grafik. In solchen Nicht-Baum-Fällen wird mein Algorithmus unten nicht angewendet.

Die vorhandenen Antworten funktionieren für allgemeine Beziehungen auf allgemeinen gerichteten Graphen, die ihre Repräsentationsgrößen auf O (n) Bits für n Knoten aufblähen. Da Sie einen Baum haben, ist eine kürzere O (log n) -Bit-Darstellung möglich.

In einem Baum, der von der Wurzel weggerichtet ist, müssen für zwei beliebige Vertices u und v die von u bzw. v erreichbaren Sätze von Blättern L (u) und L (v) entweder disjunkt sein oder man muss Sei eine Untermenge der anderen. Wenn sie disjunkt sind, ist u nicht von v aus erreichbar (und umgekehrt); Wenn man eine richtige Teilmenge der anderen ist, ist die eine mit der kleineren Menge von der anderen zu erreichen (und in diesem Fall wird diejenige mit der kleineren Menge notwendigerweise eine strengere Tiefe haben). Wenn L (u) = L (v), dann ist u von v aus erreichbar, wenn und nur wenn depth (v) < depth (u), wobei depth (u) die Anzahl der Kanten auf dem Pfad von der Wurzel zu u ist. (Insbesondere, wenn L (u) = L (v) und Tiefe (u) = Tiefe (v), dann u = v.)

Wir können diese Beziehung prägnant kodieren, indem wir bemerken, dass alle Blätter von einem gegebenen erreichbar sind Vertex v besetzt ein zusammenhängendes Segment der Blätter, das durch eine inverse Durchquerung des Baums ausgegeben wird. Für jeden gegebenen Knoten v kann diese Menge von Blättern daher durch ein Paar von Ganzzahlen (first, last) dargestellt werden, wobei first das erste Blatt (in der Reihenfolge des Durchlaufs) und last das letzte Blatt kennzeichnet. Der Test, ob ein Pfad existiert von i nach j ist dann sehr einfach - in pseudo-C++:

bool doesPathExist(int i, int j) { 
    return x[i].first <= x[j].first && x[i].last >= x[j].last && depth[i] <= depth[j]; 
} 

Beachten Sie, dass, wenn jeder Nicht-Blatt Scheitel im Baum mindestens zwei Kinder haben, man dann don‘ t müssen sich mit Tiefen beschäftigen, da L (u) = L (v) in diesem Fall u = v impliziert. (Meine ursprüngliche Version des Posts hat diese Annahme gemacht; ich habe es jetzt repariert, auch wenn dies nicht der Fall ist.)