Networkx Edge Contraction

contract_edges.py

#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

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

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!