Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Union of two network diagrams

Can anyone point me to the right data structures / algorithms to accomplish the following?

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

Thanks!

enter image description here

like image 582
Brian Rice Avatar asked Mar 05 '14 19:03

Brian Rice


2 Answers

Short answer

  1. Union the node sets.
  2. Union the edge sets.

Long answer

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

Let's call your two graphs G and H, where a graph is a list<Node>.

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

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

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

For each Node u in this new graph M, compute 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 name in NextNames, add MLookup[name] to u.Next.

M is now your merged 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
like image 84
Timothy Shields Avatar answered Oct 06 '22 17:10

Timothy Shields


Typically graphs can be represented as either adjacency matrices or adjacency lists. Either way to union them isn't hard.

From the adjacency list perspective, you have

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

so all you would have to do is union the sublist per node in your adjacency lists

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

For the adjacency matrix, it is trivial. Simply loop 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:

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

and graph 2 had something like:

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

then graph 3 would end up with

    A   B   C
A   1   1   0
B   0   1   1
C   0   1   1
like image 4
C.B. Avatar answered Oct 06 '22 19:10

C.B.