CODEWITHSUNDEEP
pythonnetworkx
moritz
moritz

Reputation: 314

Aggregate edge attributes in MultiGraph

I have a Graph with multiple edges between two nodes as in the example below. I want to aggregate all edges that meet a condition into one edge. In the example: if an edge belongs to the same group, then I want to merge that edge into one and add 1 to the 'freq' attribute.

G = nx.MultiGraph()
G.add_edge(1,2, group=1)
G.add_edge(1,2, group=1)
G.add_edge(1,2, group=2)
G.add_edge(1,2, group=2)
G.add_edge(1,2, group=3)
G.add_edge(1,2, group=3)
G.add_edge(1,2, group=4)

G.edges(data=True)
OUT: MultiEdgeDataView([(1, 2, {'group': 1, 'freq': 1}), (1, 2, {'group': 1, 'freq': 1}), (1, 2, {'group': 2, 'freq': 1}), (1, 2, {'group': 2, 'freq': 1}), (1, 2, {'group': 3, 'freq': 1})])

The outcome I want should be:

OUT: MultiEdgeDataView([(1, 2, {'group': 1, 'freq': 2}), (1, 2, {'group': 2, 'freq': 2}), (1, 2, {'group': 3, 'freq': 1})])

Upvotes: 2

Views: 1138

Answers (1)

Gambit1614
Gambit1614

Reputation: 8801

This code basically works for arbitrary number of edge attributes and updates the frequency accordingly. I have added the comments for more clarity

import networkx as nx

G = nx.MultiGraph()
G.add_edge(1,2, group=1)
G.add_edge(1,2, group=1)
G.add_edge(1,2, group=2)
G.add_edge(1,2, group=2)
G.add_edge(1,2, group=3)
G.add_edge(1,2, group=3)
G.add_edge(1,2, group=4)
G.edges(data=True)

def get_same_attrib_key(u, v, data, G1, G2):

    # First check if edge exists in new Graph
    if G2.has_edge(u, v) is None:
      return None

    # Get data for all edges between u and v
    new_edge_data = G2.get_edge_data(u, v)


    if new_edge_data:

      # This index will be used to update frequency in new graph
      idx = 0

      # For each edge between u and v, check the attributes
      for dict_attrs in new_edge_data:

        # Example 1: If G1 has edge from 1-->2 with data {'group': 1}
        # and G2 has edge from 1-->2 with data {'group': 1, 'freq': 2},
        # this if statement will return True
        #
        # Example 2: If G1 has edge from 1-->2 with data {'group': 1}
        # and G2 has edge from 1-->2 with data {'group': 1, 'freq': 2, 'xyz':3},
        # this if statement will return False
        if len(new_edge_data[dict_attrs].items()-data.items())==1:
          return idx
        idx +=1

    # No match found, hence return None
    return None

G_agg = nx.MultiGraph()
for u, v, data in G.edges(data=True):

    # Check if the current edge with same attribute dictionary 
    # exists in new Graph. This key is used for accessing data 
    # in Multigraphs. 
    key = get_same_attrib_key(u, v, data, G, G_agg)

    # Update frequency if same edge exists
    if key is not None:
        G_agg[u][v][key]['freq'] += 1

    # Else create a new edge with same data and a new key `freq` set to 1
    else:
        G_agg.add_edge(u, v, **dict({'freq': 1}, **data))

This will return the following edges: MultiEdgeDataView([(1, 2, {'freq': 2, 'group': 1}), (1, 2, {'freq': 2, 'group': 2}), (1, 2, {'freq': 2, 'group': 3}), (1, 2, {'freq': 1, 'group': 4})])

Now, suppose you want to add arbitrary number of edge-attribute keys and get the frequencies, then the this code still works, for example for the following graph:

G = nx.MultiGraph()
G.add_edge(1,2, group=1, other=5)  #<------This edge attribute is diff. from others
G.add_edge(1,2, group=3)
G.add_edge(1,2, group=1)
G.add_edge(1,2, group=1)
G.add_edge(1,2, group=2)
G.add_edge(1,2, group=2)
G.add_edge(1,2, group=2)
G.add_edge(1,2, group=3)
G.add_edge(1,2, group=4)
G.add_edge(1,2, group=2)
G.add_edge(1,2, group=2)
G.edges(data=True)

This code will output the following edges: MultiEdgeDataView([(1, 2, {'group': 1, 'other': 5}), (1, 2, {'group': 3}), (1, 2, {'group': 1}), (1, 2, {'group': 1}), (1, 2, {'group': 2}), (1, 2, {'group': 2}), (1, 2, {'group': 2}), (1, 2, {'group': 3}), (1, 2, {'group': 4}), (1, 2, {'group': 2}), (1, 2, {'group': 2})])

Notice how the edge with the key 'other':5 has frequency 1., since this attribute is not present in any other combination of edge between 1 and 2 with 'group':1

You can check the code in this Google Colab notebook here.

Upvotes: 1

Related Questions