networkx.algorithms.minors.contracted_edge¶
- contracted_edge(G, edge, self_loops=True, copy=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
- GNetworkX graph
The graph whose edge will be contracted.
- edgetuple
Must be a pair of nodes in
G
.- self_loopsBoolean
If this is True, any edges (including
edge
) joining the endpoints ofedge
inG
become self-loops on the new node in the returned graph.- copyBoolean (default True)
If this is True, a the contraction will be performed on a copy of
G
, otherwise the contraction will happen in place.
- Returns
- Networkx graph
A new graph object of the same type as
G
(leavingG
unmodified) with endpoints ofedge
identified in a single node. The right node ofedge
will be merged into the left one, so only the left one will appear in the returned graph.
- Raises
- ValueError
If
edge
is not an edge inG
.
See also
Examples
Attempting to contract two nonadjacent nodes yields an error:
>>> 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:
>>> 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