Union of two network diagrams

Question

Can someone point me to the correct data structures / algorithms to do the following?

I would like to combine (Union?) The following two sets of nodes to get the third set.

Thanks!

Answer 1

Short answer

• Combine the node set.
• Combine the ribs.

Long answer

I assume that you are using a graph data structure in which there are Node instances, where each Node has a string Name and list<Node> Next .

Let me call your two graphs G and H , where the graph is list<Node> .

Let GNames and HNames be the node name sets in each of the graphs. Let MNames be a union of GNames and HNames .

Create a new schedule for list<Node> M , where there is a new Node for each name in MNames .

Build map<string, Node> GLookup, HLookup, MLookup as a mapping from node name to Node for each of list<Node> G, H, M

For each Node u in this new column M calculate NextNames as the union of GLookup[u.Name].Next.Select(v => v.Name) and HLookup[u.Name].Next.Select(v => v.Name) , then for each name in NextNames add MLookup[name] to u.Next .

M is now your combined graph.

pseudo code

 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

Typically, graphs can be represented as adjacency matrices and adjacency lists. Any way to combine them is not difficult.

In terms of adjacency list you have

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

so all you have to do is merge the sublist into node in your adjacency lists

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

For the adjacency matrix, it is trivial. Just swipe through each aij in the matrix, and if it is 0, and the corresponding entry in the other matrix is ​​1, set it to 1.

If graph 1 had something like:

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

and Count 2 had something like:

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

then count 3 would end with

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