maximum_spanning_edges(G, algorithm='kruskal', weight='weight', keys=True, data=True, ignore_nan=False)
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.
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/
An undirected graph. If G is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.
The algorithm to use when finding a maximum spanning tree. Valid choices are 'kruskal', 'prim', or 'boruvka'. The default is 'kruskal'.
Edge data key to use for weight (default 'weight').
Whether to yield edge key in multigraphs in addition to the edge. If G is not a multigraph, this is ignored.
If True yield the edge data along with the edge.
If a NaN is found as an edge weight normally an exception is raised. If :None:None:`ignore_nan is True` then that edge is ignored instead.
An iterator over edges in a maximum spanning tree of G. Edges connecting nodes :None:None:`u` and :None:None:`v` are represented as tuples: :None:None:`(u, v, k, d)` or :None:None:`(u, v, k)` or :None:None:`(u, v, d)` or :None:None:`(u, v)`
If G is a multigraph, keys
indicates whether the edge key k will be reported in the third position in the edge tuple. :None:None:`data` indicates whether the edge datadict d will appear at the end of the edge tuple.
If G is not a multigraph, the tuples are :None:None:`(u, v, d)` if :None:None:`data` is True or :None:None:`(u, v)` if :None:None:`data` is False.
Generate edges in a maximum spanning forest of an undirected weighted graph.
>>> from networkx.algorithms import tree
Find maximum spanning edges by Kruskal's algorithm
>>> G = nx.cycle_graph(4)
... G.add_edge(0, 3, weight=2)
... mst = tree.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 = nx.cycle_graph(4)See :
... G.add_edge(0, 3, weight=2) # assign weight 2 to edge 0-3
... mst = tree.maximum_spanning_edges(G, algorithm="prim", data=False)
... edgelist = list(mst)
... sorted(sorted(e) for e in edgelist) [[0, 1], [0, 3], [2, 3]]
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them