Merge nodes that share attributes

Question

EDITED

I really need help from Networkx/graph experts.

Let us say I have the following data frames and I would like to convert these data frames to graphs. Then I would like to map the two graphs with corresponding nodes based on description and priority attributes.

df1

From   description    To         priority 
10        Start      20, 50         1
20        Left       40             2 
50        Bottom     40             2
40        End        -              1

df2

From   description    To      priority 
60        Start      70,80       1
70        Left       80, 90      2 
80        Left       100         2
90        Bottom     100         2
100        End        -          1

I just converted the two data frames and created a graph (g1, and g2).

And then I am trying to match the nodes based on their description and priority for only once. for example 10/60, 40/100, 50/90 but not 20/70, 20/80, and 70/80. 20 has three conditions to be mapped which are not what I want. Because I would like to map nodes for only once unless I would like to put them as a single node and mark the node as red to differentiate.

A node should only be mapped for only once means, for example, if I want to map 10, it has priority 1 and description Start on the first graph and then find the same priority and description on the second graph. For this, 60 is there. There are no other nodes other than 60. But if we take 20 on the first graph, it has priority 2 and description left. On the second graph, there are two nodes with priority 2 and description left which is 70 and 80. This creates confusion. I cannot map 20 twice like 20/70 and 20/80. But I would like to put them as a single node as shown below on the sample graph.

I am expecting the following result.

To get the above result, I tried it with the following python code.

mapped_list= []

for node_1, data_1 in g1.nodes(data=True):
    for node_2, data_2 in g2.nodes(data=True):

        if (((g1.node[node_1]['priority']) == (g2.node[node_2]['priority'])) & 
                    ((g1.node[node_1]['description']) == (g2.node[node_2]['description']))
                   ):
                    if (node_1 in mapped_list) & (node_2 in mapped_list): // check of if the node exist on the mapped_list
                        pass
                    else:    
                        name = str(node_1) + '/' + str(node_2)
                        mapped_list.append((data_1["priority"], data_1["descriptions"], node_1, name))
                        mapped_list.append((data_2["priority"], data_2["descriptions"], node_2, name))

Can anyone help me to achieve the above result shown on the figure /graph/? Any help is appreciated.

user_9698684 · Answer

The way I'd go about this instead, is to build a new graph taking the nx.union of both graphs, and then "combine" together the start and end nodes that share attributes using contracted_nodes.

Let's start by creating both graphs from the dataframes:

df1 = df1.drop('To',1).join(df1.To.str.replace(' ','').str.split(',').explode())
df2 = df2.drop('To',1).join(df2.To.str.replace(' ','').str.split(',').explode())

g1 = nx.from_pandas_edgelist(df1.iloc[:-1,[0,3]].astype(int), 
                             source='From', target='To', create_using=nx.DiGraph)
g2 = nx.from_pandas_edgelist(df2.iloc[:-1,[0,3]].astype(int), 
                             source='From', target='To', create_using=nx.DiGraph)

df1_node_ix = df1.assign(graph='graph1').set_index('From').rename_axis('nodes')
nx.set_node_attributes(g1, values=df1_node_ix.description.to_dict(), 
                       name='description')
nx.set_node_attributes(g1, values=df1_node_ix.priority.to_dict(), 
                       name='priority')
nx.set_node_attributes(g1, values=df1_node_ix.graph.to_dict(), 
                       name='graph')

df2_node_ix = df2.assign(graph='graph2').set_index('From').rename_axis('nodes')
nx.set_node_attributes(g2, values=df2_node_ix.description.to_dict(), 
                       name='description')
nx.set_node_attributes(g2, values=df2_node_ix.priority.to_dict(), 
                       name='priority')
nx.set_node_attributes(g2, values=df2_node_ix.graph.to_dict(), 
                       name='graph')

Now by taking the nx.union of both graphs, we have:

g3 = nx.union(g1,g2)

from networkx.drawing.nx_agraph import graphviz_layout
plt.figure(figsize=(8,5))
pos=graphviz_layout(g3, prog='dot')
nx.draw(g3, pos=pos, 
        with_labels=True, 
        node_size=1500, 
        node_color='red', 
        arrowsize=20)

What we can do now is come up with some data structure which we can later use to easily combine the pairs of nodes that share attributes. For that we can sort the nodes by their description. Sorting them will enable us to use itertools.groupby to group consecutive equal pairs of nodes, which we can then easily combine using nx.contrated_nodes, and then just overwrite on the same previous graph. The nodes can be relabeled as specified in the question with nx.relabel_nodes:

from itertools import groupby

g3_node_view = g3.nodes(data=True)
sorted_by_descr = sorted(g3_node_view, key=lambda x: x[1]['description'])
node_colors = dict()
colors = {'Bottom':'saddlebrown', 'Start':'lightblue', 
          'Left':'green', 'End':'lightblue'}
all_graphs = {'graph1', 'graph2'}

for _, grouped_by_descr in groupby(sorted_by_descr, 
                                   key=lambda x: x[1]['description']):
    for _, group in groupby(grouped_by_descr, key=lambda x: x[1]['priority']):
        grouped_nodes = list(group)
        nodes = [i[0] for i in grouped_nodes]
        graphs = {i[1]['graph'] for i in grouped_nodes}

        # check if there are two nodes that share attributes
        # and both belong to different graphs
        if len(nodes)==2 and graphs==all_graphs:
            # contract both nodes and update graph
            g3 = nx.contracted_nodes(g3, *nodes)
            # define new contracted node name and relabel
            new_node = '/'.join(map(str, nodes))
            g3 = nx.relabel_nodes(g3, {nodes[0]:new_node})
            node_colors[new_node] = colors[grouped_nodes[0][1]['description']]
        else:
            for node in nodes:    
                node_colors[node] = 'red'

Which would give:

plt.figure(figsize=(10,7))
pos=graphviz_layout(g3, prog='dot')
nx.draw(g3, pos=pos, 
        with_labels=True, 
        node_size=2500, 
        nodelist=node_colors.keys(),
        node_color=node_colors.values(), 
        arrowsize=20)

Merge nodes that share attributes

1 Answers