Vereinigung von zwei Netzwerkdiagrammen

Question

Kann mir jemand auf die richtigen Datenstrukturen/Algorithmen hinweisen, um folgendes zu erreichen?

Ich möchte (Union?) Die folgenden zwei Sätze von Knoten kombinieren, um den dritten Satz zu erhalten.

Danke!

Answer 1

Kurze Antwort Ende

1. Verbinden Sie die Knotensätze.
2. Verbinden Sie die Kantensätze.

Lange Antwort

Ich nehme es eine Graphdatenstruktur verwenden, in denen es Node Fällen, in denen jeder Node eine string Name und eine list<Node> Next.

Nennen wir Ihre beiden Graphen G und H, wobei ein Graph eine list<Node> ist.

Lassen Sie GNames und HNames die Sätze der Knotennamen in jedem der Graphen sein. Lassen Sie MNames die Union von GNames und HNames sein.

Erstellen Sie ein neues Diagramm list<Node> M, wo es einen neuen Node für jeden Namen in MNames gibt.

Build map<string, Node> GLookup, HLookup, MLookup als Zuordnungen von Knotenname zu Node für jede der list<Node> G, H, M.

Für jeden Node u in diesem neuen Graphen M berechnen NextNames als die Vereinigung von GLookup[u.Name].Next.Select(v => v.Name) und HLookup[u.Name].Next.Select(v => v.Name), dann für jeden Namen name in NextNames, fügen MLookup[name]-u.Next.

M ist jetzt Ihr zusammengeführter Graph.

Pseudocode

list<Node> merge(list<Node> G, list<Node> H) 
    GNames = G.Select(u => u.Name) 
    HNames = H.Select(u => u.Name) 
    MNames = union(GNames, HNames) 
    M = MNames.Select(name => new Node(name)) 
    GLookup = G.ToMap(u => u.Name) 
    HLookup = H.ToMap(u => u.Name) 
    MLookup = M.ToMap(u => u.Name) 
    foreach u in M 
     NextNames = union(
         GLookup[u.Name].Next.Select(v => v.Name), 
         HLookup[u.Name].Next.Select(v => v.Name)) 
     foreach name in NextNames 
      u.Next.Add(MLookup[name]) 
    return M 

Answer 2

Typischerweise Graphen können entweder als Adjazenzmatrizen oder Adjazenzlisten dargestellt werden. So oder so, um sie zu vereinigen, ist nicht schwer.

Aus der Sicht Adjazenzliste Sie

list1 = [[A,[B,K]],[B,[C,D,E]],...] 
list2 = [[A,[B]],[B,[C,D,E]],...] 

haben so alles, was Sie tun müssen, würde ist die Vereinigung der Unterliste pro Knoten in Ihrer Adjazenzlisten

list3 = [[A,UNION([B,K],[B])]...] 

Für die Adjazenzmatrix ist es trivial. Einfach eine Schleife durch jede Aij in der Matrix, und wenn es 0 ist, und der entsprechende Eintrag in der anderen Matrix gleich 1 ist, auf 1 setzen

Wenn Grafik 1 etwas wie hatte:

A B C 
A 1 1 0 
B 0 1 0 
C 0 1 1 

und Graph

2 hatte so etwas wie:

A B C 
A 1 1 0 
B 0 1 1 
C 0 0 1 

dann graph 3 würde sich mit

A B C 
A 1 1 0 
B 0 1 1 
C 0 1 1