contracted_edge(G, edge, self_loops=True)¶
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.
- G (NetworkX graph) – The graph whose edge will be contracted.
- edge (tuple) – Must be a pair of nodes in
- self_loops (Boolean) – If this is True, any edges (including
edge) joining the endpoints of
Gbecome self-loops on the new node in the returned graph.
A new graph object of the same type as
Gunmodified) with endpoints of
edgeidentified in a single node. The right node of
edgewill be merged into the left one, so only the left one will appear in the returned graph.
edgeis not an edge in
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