Union of two network diagrams

Question

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!

Answer 1

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