Warning

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

networkx.algorithms.minors.contracted_edge

contracted_edge(G, edge, self_loops=True)[source]

Returns the graph that results from contracting the specified edge.

Edge contraction identifies the two endpoints of the edge as a single node incident to any edge that was incident to the original two nodes. A graph that results from edge contraction is called a minor of the original graph.

Parameters:
  • G (NetworkX graph) – The graph whose edge will be contracted.
  • edge (tuple) – Must be a pair of nodes in G.
  • self_loops (Boolean) – If this is True, any edges (including edge) joining the endpoints of edge 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 endpoints of edge identified in a single node. The right node of edge will be merged into the left one, so only the left one will appear in the returned graph.

Return type:

Networkx graph

Raises:

ValueError – If edge is not an edge in G.

Examples

Attempting to contract two nonadjacent nodes yields an error:

>>> import networkx as nx
>>> G = nx.cycle_graph(4)
>>> nx.contracted_edge(G, (1, 3))
Traceback (most recent call last):
  ...
ValueError: Edge (1, 3) does not exist in graph G; cannot contract it

Contracting two adjacent nodes in the cycle graph on n nodes yields the cycle graph on n - 1 nodes:

>>> import networkx as nx
>>> C5 = nx.cycle_graph(5)
>>> C4 = nx.cycle_graph(4)
>>> M = nx.contracted_edge(C5, (0, 1), self_loops=False)
>>> nx.is_isomorphic(M, C4)
True