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.recognition for 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.