Skip to content

Instantly share code, notes, and snippets.

@aanastasiou
Forked from Zulko/nx_merge_nodes.py
Last active March 26, 2024 17:18
Show Gist options
  • Save aanastasiou/7639465 to your computer and use it in GitHub Desktop.
Save aanastasiou/7639465 to your computer and use it in GitHub Desktop.
Networkx Edge Contraction
#Edge contraction as per http://en.wikipedia.org/wiki/Edge_contraction
def contract_edges(G,nodes, new_node, attr_dict=None, **attr):
'''Contracts the edges of the nodes in the set "nodes" '''
#Add the node with its attributes
G.add_node(new_node, attr_dict, **attr)
#Create the set of the edges that are to be contracted
cntr_edge_set = G.edges(nodes, data = True)
#Add edges from new_node to all target nodes in the set of edges that are to be contracted
#Possibly also checking that edge attributes are preserved and not overwritten,
#especially in the case of an undirected G (Most lazy approach here would be to return a
#multigraph so that multiple edges and their data are preserved)
G.add_edges_from(map(lambda x: (new_node,x[1],x[2]), cntr_edge_set))
#Remove the edges contained in the set of edges that are to be contracted, concluding the contraction operation
G.remove_edges_from(cntr_edge_set)
#Remove the nodes as well
G.remove_nodes_from(nodes)
#Return the graph
return G
@Zulko
Copy link

Zulko commented Dec 1, 2013

Cool, I didn't know that was called edge contraction. Do you think you could commit that to the networkx people ? That would be great to have this feature in the module.

@wladston
Copy link

Thanks for this, neat and clean. It should be in networkx itself imho.

@garcia
Copy link

garcia commented Mar 28, 2015

Worth noting that this only works on undirected graphs. For digraphs you'd need to handle the in-edges on nodes as well. That aside, thank you for this!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment