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