easygraph.functions.path.bridges module#
- easygraph.functions.path.bridges.bridges(G, root=None)[source]#
Generate all bridges in a graph.
A bridge in a graph is an edge whose removal causes the number of connected components of the graph to increase. Equivalently, a bridge is an edge that does not belong to any cycle.
- Parameters:
G (undirected graph) –
root (node (optional)) – A node in the graph G. If specified, only the bridges in the connected component containing this node will be returned.
- Yields:
e (edge) – An edge in the graph whose removal disconnects the graph (or causes the number of connected components to increase).
- Raises:
NodeNotFound – If root is not in the graph G.
Examples
>>> list(eg.bridges(G)) [(9, 10)]
Notes
This is an implementation of the algorithm described in _[1]. An edge is a bridge if and only if it is not contained in any chain. Chains are found using the
chain_decomposition()function.Ignoring polylogarithmic factors, the worst-case time complexity is the same as the
chain_decomposition()function, $O(m + n)$, where $n$ is the number of nodes in the graph and $m$ is the number of edges.References
- easygraph.functions.path.bridges.has_bridges(G, root=None)[source]#
Decide whether a graph has any bridges.
A bridge in a graph is an edge whose removal causes the number of connected components of the graph to increase.
- Parameters:
G (undirected graph) –
root (node (optional)) – A node in the graph G. If specified, only the bridges in the connected component containing this node will be considered.
- Returns:
Whether the graph (or the connected component containing root) has any bridges.
- Return type:
bool
- Raises:
NodeNotFound – If root is not in the graph G.
Examples
>>> eg.has_bridges(G) True
Notes
This implementation uses the
easygraph.bridges()function, so it shares its worst-case time complexity, $O(m + n)$, ignoring polylogarithmic factors, where $n$ is the number of nodes in the graph and $m$ is the number of edges.