easygraph.functions.path package
Submodules
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.
easygraph.functions.path.mst module
- easygraph.functions.path.mst.maximum_spanning_edges(G, algorithm='kruskal', weight='weight', data=True, ignore_nan=False)[source]
Generate edges in a maximum spanning forest of an undirected weighted graph.
A maximum spanning tree is a subgraph of the graph (a tree) with the maximum possible sum of edge weights. A spanning forest is a union of the spanning trees for each connected component of the graph.
- Parameters
G (undirected Graph) – An undirected graph. If G is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.
algorithm (string) – The algorithm to use when finding a maximum spanning tree. Valid choices are ‘kruskal’, ‘prim’, or ‘boruvka’. The default is ‘kruskal’.
weight (string) – Edge data key to use for weight (default ‘weight’).
data (bool, optional) – If True yield the edge data along with the edge.
ignore_nan (bool (default: False)) – If a NaN is found as an edge weight normally an exception is raised. If ignore_nan is True then that edge is ignored instead.
- Returns
edges – An iterator over edges in a maximum spanning tree of G. Edges connecting nodes u and v are represented as tuples: (u, v, k, d) or (u, v, k) or (u, v, d) or (u, v)
- Return type
iterator
Examples
>>> from easygraph.functions.basic import mst
Find maximum spanning edges by Kruskal’s algorithm
>>> G.add_edge(0, 3, weight=2) >>> mst = mst.maximum_spanning_edges(G, algorithm="kruskal", data=False) >>> edgelist = list(mst) >>> sorted(sorted(e) for e in edgelist) [[0, 1], [0, 3], [1, 2]]
Find maximum spanning edges by Prim’s algorithm
>>> G.add_edge(0, 3, weight=2) # assign weight 2 to edge 0-3 >>> mst = mst.maximum_spanning_edges(G, algorithm="prim", data=False) >>> edgelist = list(mst) >>> sorted(sorted(e) for e in edgelist) [[0, 1], [0, 3], [2, 3]]
Notes
For Borůvka’s algorithm, each edge must have a weight attribute, and each edge weight must be distinct.
For the other algorithms, if the graph edges do not have a weight attribute a default weight of 1 will be used.
Modified code from David Eppstein, April 2006 http://www.ics.uci.edu/~eppstein/PADS/
- easygraph.functions.path.mst.maximum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False)[source]
Returns a maximum spanning tree or forest on an undirected graph G.
- Parameters
G (undirected graph) – An undirected graph. If G is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.
weight (str) – Data key to use for edge weights.
algorithm (string) – The algorithm to use when finding a maximum spanning tree. Valid choices are ‘kruskal’, ‘prim’, or ‘boruvka’. The default is ‘kruskal’.
ignore_nan (bool (default: False)) – If a NaN is found as an edge weight normally an exception is raised. If ignore_nan is True then that edge is ignored instead.
- Returns
G – A maximum spanning tree or forest.
- Return type
EasyGraph Graph
Examples
>>> G.add_edge(0, 3, weight=2) >>> T = eg.maximum_spanning_tree(G) >>> sorted(T.edges(data=True)) [(0, 1, {}), (0, 3, {'weight': 2}), (1, 2, {})]
Notes
For Borůvka’s algorithm, each edge must have a weight attribute, and each edge weight must be distinct.
For the other algorithms, if the graph edges do not have a weight attribute a default weight of 1 will be used.
There may be more than one tree with the same minimum or maximum weight. See
easygraph.tree.recognitionfor more detailed definitions.Isolated nodes with self-loops are in the tree as edgeless isolated nodes.
- easygraph.functions.path.mst.minimum_spanning_edges(G, algorithm='kruskal', weight='weight', data=True, ignore_nan=False)[source]
Generate edges in a minimum spanning forest of an undirected weighted graph.
A minimum spanning tree is a subgraph of the graph (a tree) with the minimum sum of edge weights. A spanning forest is a union of the spanning trees for each connected component of the graph.
- Parameters
G (undirected Graph) – An undirected graph. If G is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.
algorithm (string) – The algorithm to use when finding a minimum spanning tree. Valid choices are ‘kruskal’, ‘prim’, or ‘boruvka’. The default is ‘kruskal’.
weight (string) – Edge data key to use for weight (default ‘weight’).
data (bool, optional) – If True yield the edge data along with the edge.
ignore_nan (bool (default: False)) – If a NaN is found as an edge weight normally an exception is raised. If ignore_nan is True then that edge is ignored instead.
- Returns
edges – An iterator over edges in a maximum spanning tree of G. Edges connecting nodes u and v are represented as tuples: (u, v, k, d) or (u, v, k) or (u, v, d) or (u, v)
- Return type
iterator
Examples
>>> from easygraph.functions.basic import mst
Find minimum spanning edges by Kruskal’s algorithm
>>> G.add_edge(0, 3, weight=2) >>> mst = mst.minimum_spanning_edges(G, algorithm="kruskal", data=False) >>> edgelist = list(mst) >>> sorted(sorted(e) for e in edgelist) [[0, 1], [1, 2], [2, 3]]
Find minimum spanning edges by Prim’s algorithm
>>> G.add_edge(0, 3, weight=2) >>> mst = mst.minimum_spanning_edges(G, algorithm="prim", data=False) >>> edgelist = list(mst) >>> sorted(sorted(e) for e in edgelist) [[0, 1], [1, 2], [2, 3]]
Notes
For Borůvka’s algorithm, each edge must have a weight attribute, and each edge weight must be distinct.
For the other algorithms, if the graph edges do not have a weight attribute a default weight of 1 will be used.
Modified code from David Eppstein, April 2006 http://www.ics.uci.edu/~eppstein/PADS/
- easygraph.functions.path.mst.minimum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False)[source]
Returns a minimum spanning tree or forest on an undirected graph G.
- Parameters
G (undirected graph) – An undirected graph. If G is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.
weight (str) – Data key to use for edge weights.
algorithm (string) – The algorithm to use when finding a minimum spanning tree. Valid choices are ‘kruskal’, ‘prim’, or ‘boruvka’. The default is ‘kruskal’.
ignore_nan (bool (default: False)) – If a NaN is found as an edge weight normally an exception is raised. If ignore_nan is True then that edge is ignored instead.
- Returns
G – A minimum spanning tree or forest.
- Return type
EasyGraph Graph
Examples
>>> G.add_edge(0, 3, weight=2) >>> T = eg.minimum_spanning_tree(G) >>> sorted(T.edges(data=True)) [(0, 1, {}), (1, 2, {}), (2, 3, {})]
Notes
For Borůvka’s algorithm, each edge must have a weight attribute, and each edge weight must be distinct.
For the other algorithms, if the graph edges do not have a weight attribute a default weight of 1 will be used.
Isolated nodes with self-loops are in the tree as edgeless isolated nodes.
easygraph.functions.path.path module
- easygraph.functions.path.path.Dijkstra(G, node, weight='weight')[source]
Returns the length of paths from the certain node to remaining nodes
- Parameters
G (graph) – weighted graph
node (int) –
- Returns
result_dict – the length of paths from the certain node to remaining nodes
- Return type
dict
Examples
Returns the length of paths from node 1 to remaining nodes
>>> Dijkstra(G,node=1,weight="weight")
- easygraph.functions.path.path.Floyd(*args, **kwargs)
- easygraph.functions.path.path.Kruskal(*args, **kwargs)
- easygraph.functions.path.path.Prim(*args, **kwargs)
- easygraph.functions.path.path.Spfa(*args, **kwargs)