Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.minors.contracted_nodes

contracted_nodes(G, u, v, self_loops=True)[source]

Returns the graph that results from contracting u and v.

Node contraction identifies the two nodes as a single node incident to any edge that was incident to the original two nodes.

Parameters:
  • G (NetworkX graph) – The graph whose nodes will be contracted.
  • u, v (nodes) – Must be nodes in G.
  • self_loops (Boolean) – If this is True, any edges joining u and v in G become self-loops on the new node in the returned graph.
Returns:

A new graph object of the same type as G (leaving G unmodified) with u and v identified in a single node. The right node v will be merged into the node u, so only u will appear in the returned graph.

Return type:

Networkx graph

Notes

For multigraphs, the edge keys for the realigned edges may not be the same as the edge keys for the old edges. This is natural because edge keys are unique only within each pair of nodes.

Examples

Contracting two nonadjacent nodes of the cycle graph on four nodes C_4 yields the path graph (ignoring parallel edges):

>>> G = nx.cycle_graph(4)
>>> M = nx.contracted_nodes(G, 1, 3)
>>> P3 = nx.path_graph(3)
>>> nx.is_isomorphic(M, P3)
True

>>> G = nx.MultiGraph(P3)
>>> M = nx.contracted_nodes(G, 0, 2)
>>> M.edges
MultiEdgeView([(0, 1, 0), (0, 1, 1)])

>>> G = nx.Graph([(1,2), (2,2)])
>>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)
>>> list(H.nodes())
[1]
>>> list(H.edges())
[(1, 1)]

Notes

This function is also available as identified_nodes.