aboutsummaryrefslogtreecommitdiff
path: root/.venv/lib/python3.12/site-packages/networkx/algorithms/tree
diff options
context:
space:
mode:
authorS. Solomon Darnell2025-03-28 21:52:21 -0500
committerS. Solomon Darnell2025-03-28 21:52:21 -0500
commit4a52a71956a8d46fcb7294ac71734504bb09bcc2 (patch)
treeee3dc5af3b6313e921cd920906356f5d4febc4ed /.venv/lib/python3.12/site-packages/networkx/algorithms/tree
parentcc961e04ba734dd72309fb548a2f97d67d578813 (diff)
downloadgn-ai-master.tar.gz
two version of R2R are hereHEADmaster
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/algorithms/tree')
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/__init__.py6
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/branchings.py1042
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/coding.py413
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/decomposition.py88
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/mst.py1284
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/operations.py105
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/recognition.py273
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/__init__.py0
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_branchings.py624
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_coding.py114
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_decomposition.py79
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_mst.py918
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_operations.py53
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_recognition.py174
14 files changed, 5173 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/__init__.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/__init__.py
new file mode 100644
index 00000000..7120d4bc
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/__init__.py
@@ -0,0 +1,6 @@
+from .branchings import *
+from .coding import *
+from .mst import *
+from .recognition import *
+from .operations import *
+from .decomposition import *
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/branchings.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/branchings.py
new file mode 100644
index 00000000..cc9c7cf1
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/branchings.py
@@ -0,0 +1,1042 @@
+"""
+Algorithms for finding optimum branchings and spanning arborescences.
+
+This implementation is based on:
+
+ J. Edmonds, Optimum branchings, J. Res. Natl. Bur. Standards 71B (1967),
+ 233–240. URL: http://archive.org/details/jresv71Bn4p233
+
+"""
+
+# TODO: Implement method from Gabow, Galil, Spence and Tarjan:
+#
+# @article{
+# year={1986},
+# issn={0209-9683},
+# journal={Combinatorica},
+# volume={6},
+# number={2},
+# doi={10.1007/BF02579168},
+# title={Efficient algorithms for finding minimum spanning trees in
+# undirected and directed graphs},
+# url={https://doi.org/10.1007/BF02579168},
+# publisher={Springer-Verlag},
+# keywords={68 B 15; 68 C 05},
+# author={Gabow, Harold N. and Galil, Zvi and Spencer, Thomas and Tarjan,
+# Robert E.},
+# pages={109-122},
+# language={English}
+# }
+import string
+from dataclasses import dataclass, field
+from operator import itemgetter
+from queue import PriorityQueue
+
+import networkx as nx
+from networkx.utils import py_random_state
+
+from .recognition import is_arborescence, is_branching
+
+__all__ = [
+ "branching_weight",
+ "greedy_branching",
+ "maximum_branching",
+ "minimum_branching",
+ "minimal_branching",
+ "maximum_spanning_arborescence",
+ "minimum_spanning_arborescence",
+ "ArborescenceIterator",
+]
+
+KINDS = {"max", "min"}
+
+STYLES = {
+ "branching": "branching",
+ "arborescence": "arborescence",
+ "spanning arborescence": "arborescence",
+}
+
+INF = float("inf")
+
+
+@py_random_state(1)
+def random_string(L=15, seed=None):
+ return "".join([seed.choice(string.ascii_letters) for n in range(L)])
+
+
+def _min_weight(weight):
+ return -weight
+
+
+def _max_weight(weight):
+ return weight
+
+
+@nx._dispatchable(edge_attrs={"attr": "default"})
+def branching_weight(G, attr="weight", default=1):
+ """
+ Returns the total weight of a branching.
+
+ You must access this function through the networkx.algorithms.tree module.
+
+ Parameters
+ ----------
+ G : DiGraph
+ The directed graph.
+ attr : str
+ The attribute to use as weights. If None, then each edge will be
+ treated equally with a weight of 1.
+ default : float
+ When `attr` is not None, then if an edge does not have that attribute,
+ `default` specifies what value it should take.
+
+ Returns
+ -------
+ weight: int or float
+ The total weight of the branching.
+
+ Examples
+ --------
+ >>> G = nx.DiGraph()
+ >>> G.add_weighted_edges_from([(0, 1, 2), (1, 2, 4), (2, 3, 3), (3, 4, 2)])
+ >>> nx.tree.branching_weight(G)
+ 11
+
+ """
+ return sum(edge[2].get(attr, default) for edge in G.edges(data=True))
+
+
+@py_random_state(4)
+@nx._dispatchable(edge_attrs={"attr": "default"}, returns_graph=True)
+def greedy_branching(G, attr="weight", default=1, kind="max", seed=None):
+ """
+ Returns a branching obtained through a greedy algorithm.
+
+ This algorithm is wrong, and cannot give a proper optimal branching.
+ However, we include it for pedagogical reasons, as it can be helpful to
+ see what its outputs are.
+
+ The output is a branching, and possibly, a spanning arborescence. However,
+ it is not guaranteed to be optimal in either case.
+
+ Parameters
+ ----------
+ G : DiGraph
+ The directed graph to scan.
+ attr : str
+ The attribute to use as weights. If None, then each edge will be
+ treated equally with a weight of 1.
+ default : float
+ When `attr` is not None, then if an edge does not have that attribute,
+ `default` specifies what value it should take.
+ kind : str
+ The type of optimum to search for: 'min' or 'max' greedy branching.
+ seed : integer, random_state, or None (default)
+ Indicator of random number generation state.
+ See :ref:`Randomness<randomness>`.
+
+ Returns
+ -------
+ B : directed graph
+ The greedily obtained branching.
+
+ """
+ if kind not in KINDS:
+ raise nx.NetworkXException("Unknown value for `kind`.")
+
+ if kind == "min":
+ reverse = False
+ else:
+ reverse = True
+
+ if attr is None:
+ # Generate a random string the graph probably won't have.
+ attr = random_string(seed=seed)
+
+ edges = [(u, v, data.get(attr, default)) for (u, v, data) in G.edges(data=True)]
+
+ # We sort by weight, but also by nodes to normalize behavior across runs.
+ try:
+ edges.sort(key=itemgetter(2, 0, 1), reverse=reverse)
+ except TypeError:
+ # This will fail in Python 3.x if the nodes are of varying types.
+ # In that case, we use the arbitrary order.
+ edges.sort(key=itemgetter(2), reverse=reverse)
+
+ # The branching begins with a forest of no edges.
+ B = nx.DiGraph()
+ B.add_nodes_from(G)
+
+ # Now we add edges greedily so long we maintain the branching.
+ uf = nx.utils.UnionFind()
+ for i, (u, v, w) in enumerate(edges):
+ if uf[u] == uf[v]:
+ # Adding this edge would form a directed cycle.
+ continue
+ elif B.in_degree(v) == 1:
+ # The edge would increase the degree to be greater than one.
+ continue
+ else:
+ # If attr was None, then don't insert weights...
+ data = {}
+ if attr is not None:
+ data[attr] = w
+ B.add_edge(u, v, **data)
+ uf.union(u, v)
+
+ return B
+
+
+@nx._dispatchable(preserve_edge_attrs=True, returns_graph=True)
+def maximum_branching(
+ G,
+ attr="weight",
+ default=1,
+ preserve_attrs=False,
+ partition=None,
+):
+ #######################################
+ ### Data Structure Helper Functions ###
+ #######################################
+
+ def edmonds_add_edge(G, edge_index, u, v, key, **d):
+ """
+ Adds an edge to `G` while also updating the edge index.
+
+ This algorithm requires the use of an external dictionary to track
+ the edge keys since it is possible that the source or destination
+ node of an edge will be changed and the default key-handling
+ capabilities of the MultiDiGraph class do not account for this.
+
+ Parameters
+ ----------
+ G : MultiDiGraph
+ The graph to insert an edge into.
+ edge_index : dict
+ A mapping from integers to the edges of the graph.
+ u : node
+ The source node of the new edge.
+ v : node
+ The destination node of the new edge.
+ key : int
+ The key to use from `edge_index`.
+ d : keyword arguments, optional
+ Other attributes to store on the new edge.
+ """
+
+ if key in edge_index:
+ uu, vv, _ = edge_index[key]
+ if (u != uu) or (v != vv):
+ raise Exception(f"Key {key!r} is already in use.")
+
+ G.add_edge(u, v, key, **d)
+ edge_index[key] = (u, v, G.succ[u][v][key])
+
+ def edmonds_remove_node(G, edge_index, n):
+ """
+ Remove a node from the graph, updating the edge index to match.
+
+ Parameters
+ ----------
+ G : MultiDiGraph
+ The graph to remove an edge from.
+ edge_index : dict
+ A mapping from integers to the edges of the graph.
+ n : node
+ The node to remove from `G`.
+ """
+ keys = set()
+ for keydict in G.pred[n].values():
+ keys.update(keydict)
+ for keydict in G.succ[n].values():
+ keys.update(keydict)
+
+ for key in keys:
+ del edge_index[key]
+
+ G.remove_node(n)
+
+ #######################
+ ### Algorithm Setup ###
+ #######################
+
+ # Pick an attribute name that the original graph is unlikly to have
+ candidate_attr = "edmonds' secret candidate attribute"
+ new_node_base_name = "edmonds new node base name "
+
+ G_original = G
+ G = nx.MultiDiGraph()
+ G.__networkx_cache__ = None # Disable caching
+
+ # A dict to reliably track mutations to the edges using the key of the edge.
+ G_edge_index = {}
+ # Each edge is given an arbitrary numerical key
+ for key, (u, v, data) in enumerate(G_original.edges(data=True)):
+ d = {attr: data.get(attr, default)}
+
+ if data.get(partition) is not None:
+ d[partition] = data.get(partition)
+
+ if preserve_attrs:
+ for d_k, d_v in data.items():
+ if d_k != attr:
+ d[d_k] = d_v
+
+ edmonds_add_edge(G, G_edge_index, u, v, key, **d)
+
+ level = 0 # Stores the number of contracted nodes
+
+ # These are the buckets from the paper.
+ #
+ # In the paper, G^i are modified versions of the original graph.
+ # D^i and E^i are the nodes and edges of the maximal edges that are
+ # consistent with G^i. In this implementation, D^i and E^i are stored
+ # together as the graph B^i. We will have strictly more B^i then the
+ # paper will have.
+ #
+ # Note that the data in graphs and branchings are tuples with the graph as
+ # the first element and the edge index as the second.
+ B = nx.MultiDiGraph()
+ B_edge_index = {}
+ graphs = [] # G^i list
+ branchings = [] # B^i list
+ selected_nodes = set() # D^i bucket
+ uf = nx.utils.UnionFind()
+
+ # A list of lists of edge indices. Each list is a circuit for graph G^i.
+ # Note the edge list is not required to be a circuit in G^0.
+ circuits = []
+
+ # Stores the index of the minimum edge in the circuit found in G^i and B^i.
+ # The ordering of the edges seems to preserver the weight ordering from
+ # G^0. So even if the circuit does not form a circuit in G^0, it is still
+ # true that the minimum edges in circuit G^0 (despite their weights being
+ # different)
+ minedge_circuit = []
+
+ ###########################
+ ### Algorithm Structure ###
+ ###########################
+
+ # Each step listed in the algorithm is an inner function. Thus, the overall
+ # loop structure is:
+ #
+ # while True:
+ # step_I1()
+ # if cycle detected:
+ # step_I2()
+ # elif every node of G is in D and E is a branching:
+ # break
+
+ ##################################
+ ### Algorithm Helper Functions ###
+ ##################################
+
+ def edmonds_find_desired_edge(v):
+ """
+ Find the edge directed towards v with maximal weight.
+
+ If an edge partition exists in this graph, return the included
+ edge if it exists and never return any excluded edge.
+
+ Note: There can only be one included edge for each vertex otherwise
+ the edge partition is empty.
+
+ Parameters
+ ----------
+ v : node
+ The node to search for the maximal weight incoming edge.
+ """
+ edge = None
+ max_weight = -INF
+ for u, _, key, data in G.in_edges(v, data=True, keys=True):
+ # Skip excluded edges
+ if data.get(partition) == nx.EdgePartition.EXCLUDED:
+ continue
+
+ new_weight = data[attr]
+
+ # Return the included edge
+ if data.get(partition) == nx.EdgePartition.INCLUDED:
+ max_weight = new_weight
+ edge = (u, v, key, new_weight, data)
+ break
+
+ # Find the best open edge
+ if new_weight > max_weight:
+ max_weight = new_weight
+ edge = (u, v, key, new_weight, data)
+
+ return edge, max_weight
+
+ def edmonds_step_I2(v, desired_edge, level):
+ """
+ Perform step I2 from Edmonds' paper
+
+ First, check if the last step I1 created a cycle. If it did not, do nothing.
+ If it did, store the cycle for later reference and contract it.
+
+ Parameters
+ ----------
+ v : node
+ The current node to consider
+ desired_edge : edge
+ The minimum desired edge to remove from the cycle.
+ level : int
+ The current level, i.e. the number of cycles that have already been removed.
+ """
+ u = desired_edge[0]
+
+ Q_nodes = nx.shortest_path(B, v, u)
+ Q_edges = [
+ list(B[Q_nodes[i]][vv].keys())[0] for i, vv in enumerate(Q_nodes[1:])
+ ]
+ Q_edges.append(desired_edge[2]) # Add the new edge key to complete the circuit
+
+ # Get the edge in the circuit with the minimum weight.
+ # Also, save the incoming weights for each node.
+ minweight = INF
+ minedge = None
+ Q_incoming_weight = {}
+ for edge_key in Q_edges:
+ u, v, data = B_edge_index[edge_key]
+ w = data[attr]
+ # We cannot remove an included edge, even if it is the
+ # minimum edge in the circuit
+ Q_incoming_weight[v] = w
+ if data.get(partition) == nx.EdgePartition.INCLUDED:
+ continue
+ if w < minweight:
+ minweight = w
+ minedge = edge_key
+
+ circuits.append(Q_edges)
+ minedge_circuit.append(minedge)
+ graphs.append((G.copy(), G_edge_index.copy()))
+ branchings.append((B.copy(), B_edge_index.copy()))
+
+ # Mutate the graph to contract the circuit
+ new_node = new_node_base_name + str(level)
+ G.add_node(new_node)
+ new_edges = []
+ for u, v, key, data in G.edges(data=True, keys=True):
+ if u in Q_incoming_weight:
+ if v in Q_incoming_weight:
+ # Circuit edge. For the moment do nothing,
+ # eventually it will be removed.
+ continue
+ else:
+ # Outgoing edge from a node in the circuit.
+ # Make it come from the new node instead
+ dd = data.copy()
+ new_edges.append((new_node, v, key, dd))
+ else:
+ if v in Q_incoming_weight:
+ # Incoming edge to the circuit.
+ # Update it's weight
+ w = data[attr]
+ w += minweight - Q_incoming_weight[v]
+ dd = data.copy()
+ dd[attr] = w
+ new_edges.append((u, new_node, key, dd))
+ else:
+ # Outside edge. No modification needed
+ continue
+
+ for node in Q_nodes:
+ edmonds_remove_node(G, G_edge_index, node)
+ edmonds_remove_node(B, B_edge_index, node)
+
+ selected_nodes.difference_update(set(Q_nodes))
+
+ for u, v, key, data in new_edges:
+ edmonds_add_edge(G, G_edge_index, u, v, key, **data)
+ if candidate_attr in data:
+ del data[candidate_attr]
+ edmonds_add_edge(B, B_edge_index, u, v, key, **data)
+ uf.union(u, v)
+
+ def is_root(G, u, edgekeys):
+ """
+ Returns True if `u` is a root node in G.
+
+ Node `u` is a root node if its in-degree over the specified edges is zero.
+
+ Parameters
+ ----------
+ G : Graph
+ The current graph.
+ u : node
+ The node in `G` to check if it is a root.
+ edgekeys : iterable of edges
+ The edges for which to check if `u` is a root of.
+ """
+ if u not in G:
+ raise Exception(f"{u!r} not in G")
+
+ for v in G.pred[u]:
+ for edgekey in G.pred[u][v]:
+ if edgekey in edgekeys:
+ return False, edgekey
+ else:
+ return True, None
+
+ nodes = iter(list(G.nodes))
+ while True:
+ try:
+ v = next(nodes)
+ except StopIteration:
+ # If there are no more new nodes to consider, then we should
+ # meet stopping condition (b) from the paper:
+ # (b) every node of G^i is in D^i and E^i is a branching
+ assert len(G) == len(B)
+ if len(B):
+ assert is_branching(B)
+
+ graphs.append((G.copy(), G_edge_index.copy()))
+ branchings.append((B.copy(), B_edge_index.copy()))
+ circuits.append([])
+ minedge_circuit.append(None)
+
+ break
+ else:
+ #####################
+ ### BEGIN STEP I1 ###
+ #####################
+
+ # This is a very simple step, so I don't think it needs a method of it's own
+ if v in selected_nodes:
+ continue
+
+ selected_nodes.add(v)
+ B.add_node(v)
+ desired_edge, desired_edge_weight = edmonds_find_desired_edge(v)
+
+ # There might be no desired edge if all edges are excluded or
+ # v is the last node to be added to B, the ultimate root of the branching
+ if desired_edge is not None and desired_edge_weight > 0:
+ u = desired_edge[0]
+ # Flag adding the edge will create a circuit before merging the two
+ # connected components of u and v in B
+ circuit = uf[u] == uf[v]
+ dd = {attr: desired_edge_weight}
+ if desired_edge[4].get(partition) is not None:
+ dd[partition] = desired_edge[4].get(partition)
+
+ edmonds_add_edge(B, B_edge_index, u, v, desired_edge[2], **dd)
+ G[u][v][desired_edge[2]][candidate_attr] = True
+ uf.union(u, v)
+
+ ###################
+ ### END STEP I1 ###
+ ###################
+
+ #####################
+ ### BEGIN STEP I2 ###
+ #####################
+
+ if circuit:
+ edmonds_step_I2(v, desired_edge, level)
+ nodes = iter(list(G.nodes()))
+ level += 1
+
+ ###################
+ ### END STEP I2 ###
+ ###################
+
+ #####################
+ ### BEGIN STEP I3 ###
+ #####################
+
+ # Create a new graph of the same class as the input graph
+ H = G_original.__class__()
+
+ # Start with the branching edges in the last level.
+ edges = set(branchings[level][1])
+ while level > 0:
+ level -= 1
+
+ # The current level is i, and we start counting from 0.
+ #
+ # We need the node at level i+1 that results from merging a circuit
+ # at level i. basename_0 is the first merged node and this happens
+ # at level 1. That is basename_0 is a node at level 1 that results
+ # from merging a circuit at level 0.
+
+ merged_node = new_node_base_name + str(level)
+ circuit = circuits[level]
+ isroot, edgekey = is_root(graphs[level + 1][0], merged_node, edges)
+ edges.update(circuit)
+
+ if isroot:
+ minedge = minedge_circuit[level]
+ if minedge is None:
+ raise Exception
+
+ # Remove the edge in the cycle with minimum weight
+ edges.remove(minedge)
+ else:
+ # We have identified an edge at the next higher level that
+ # transitions into the merged node at this level. That edge
+ # transitions to some corresponding node at the current level.
+ #
+ # We want to remove an edge from the cycle that transitions
+ # into the corresponding node, otherwise the result would not
+ # be a branching.
+
+ G, G_edge_index = graphs[level]
+ target = G_edge_index[edgekey][1]
+ for edgekey in circuit:
+ u, v, data = G_edge_index[edgekey]
+ if v == target:
+ break
+ else:
+ raise Exception("Couldn't find edge incoming to merged node.")
+
+ edges.remove(edgekey)
+
+ H.add_nodes_from(G_original)
+ for edgekey in edges:
+ u, v, d = graphs[0][1][edgekey]
+ dd = {attr: d[attr]}
+
+ if preserve_attrs:
+ for key, value in d.items():
+ if key not in [attr, candidate_attr]:
+ dd[key] = value
+
+ H.add_edge(u, v, **dd)
+
+ ###################
+ ### END STEP I3 ###
+ ###################
+
+ return H
+
+
+@nx._dispatchable(preserve_edge_attrs=True, mutates_input=True, returns_graph=True)
+def minimum_branching(
+ G, attr="weight", default=1, preserve_attrs=False, partition=None
+):
+ for _, _, d in G.edges(data=True):
+ d[attr] = -d.get(attr, default)
+ nx._clear_cache(G)
+
+ B = maximum_branching(G, attr, default, preserve_attrs, partition)
+
+ for _, _, d in G.edges(data=True):
+ d[attr] = -d.get(attr, default)
+ nx._clear_cache(G)
+
+ for _, _, d in B.edges(data=True):
+ d[attr] = -d.get(attr, default)
+ nx._clear_cache(B)
+
+ return B
+
+
+@nx._dispatchable(preserve_edge_attrs=True, mutates_input=True, returns_graph=True)
+def minimal_branching(
+ G, /, *, attr="weight", default=1, preserve_attrs=False, partition=None
+):
+ """
+ Returns a minimal branching from `G`.
+
+ A minimal branching is a branching similar to a minimal arborescence but
+ without the requirement that the result is actually a spanning arborescence.
+ This allows minimal branchinges to be computed over graphs which may not
+ have arborescence (such as multiple components).
+
+ Parameters
+ ----------
+ G : (multi)digraph-like
+ The graph to be searched.
+ attr : str
+ The edge attribute used in determining optimality.
+ default : float
+ The value of the edge attribute used if an edge does not have
+ the attribute `attr`.
+ preserve_attrs : bool
+ If True, preserve the other attributes of the original graph (that are not
+ passed to `attr`)
+ partition : str
+ The key for the edge attribute containing the partition
+ data on the graph. Edges can be included, excluded or open using the
+ `EdgePartition` enum.
+
+ Returns
+ -------
+ B : (multi)digraph-like
+ A minimal branching.
+ """
+ max_weight = -INF
+ min_weight = INF
+ for _, _, w in G.edges(data=attr, default=default):
+ if w > max_weight:
+ max_weight = w
+ if w < min_weight:
+ min_weight = w
+
+ for _, _, d in G.edges(data=True):
+ # Transform the weights so that the minimum weight is larger than
+ # the difference between the max and min weights. This is important
+ # in order to prevent the edge weights from becoming negative during
+ # computation
+ d[attr] = max_weight + 1 + (max_weight - min_weight) - d.get(attr, default)
+ nx._clear_cache(G)
+
+ B = maximum_branching(G, attr, default, preserve_attrs, partition)
+
+ # Reverse the weight transformations
+ for _, _, d in G.edges(data=True):
+ d[attr] = max_weight + 1 + (max_weight - min_weight) - d.get(attr, default)
+ nx._clear_cache(G)
+
+ for _, _, d in B.edges(data=True):
+ d[attr] = max_weight + 1 + (max_weight - min_weight) - d.get(attr, default)
+ nx._clear_cache(B)
+
+ return B
+
+
+@nx._dispatchable(preserve_edge_attrs=True, mutates_input=True, returns_graph=True)
+def maximum_spanning_arborescence(
+ G, attr="weight", default=1, preserve_attrs=False, partition=None
+):
+ # In order to use the same algorithm is the maximum branching, we need to adjust
+ # the weights of the graph. The branching algorithm can choose to not include an
+ # edge if it doesn't help find a branching, mainly triggered by edges with negative
+ # weights.
+ #
+ # To prevent this from happening while trying to find a spanning arborescence, we
+ # just have to tweak the edge weights so that they are all positive and cannot
+ # become negative during the branching algorithm, find the maximum branching and
+ # then return them to their original values.
+
+ min_weight = INF
+ max_weight = -INF
+ for _, _, w in G.edges(data=attr, default=default):
+ if w < min_weight:
+ min_weight = w
+ if w > max_weight:
+ max_weight = w
+
+ for _, _, d in G.edges(data=True):
+ d[attr] = d.get(attr, default) - min_weight + 1 - (min_weight - max_weight)
+ nx._clear_cache(G)
+
+ B = maximum_branching(G, attr, default, preserve_attrs, partition)
+
+ for _, _, d in G.edges(data=True):
+ d[attr] = d.get(attr, default) + min_weight - 1 + (min_weight - max_weight)
+ nx._clear_cache(G)
+
+ for _, _, d in B.edges(data=True):
+ d[attr] = d.get(attr, default) + min_weight - 1 + (min_weight - max_weight)
+ nx._clear_cache(B)
+
+ if not is_arborescence(B):
+ raise nx.exception.NetworkXException("No maximum spanning arborescence in G.")
+
+ return B
+
+
+@nx._dispatchable(preserve_edge_attrs=True, mutates_input=True, returns_graph=True)
+def minimum_spanning_arborescence(
+ G, attr="weight", default=1, preserve_attrs=False, partition=None
+):
+ B = minimal_branching(
+ G,
+ attr=attr,
+ default=default,
+ preserve_attrs=preserve_attrs,
+ partition=partition,
+ )
+
+ if not is_arborescence(B):
+ raise nx.exception.NetworkXException("No minimum spanning arborescence in G.")
+
+ return B
+
+
+docstring_branching = """
+Returns a {kind} {style} from G.
+
+Parameters
+----------
+G : (multi)digraph-like
+ The graph to be searched.
+attr : str
+ The edge attribute used to in determining optimality.
+default : float
+ The value of the edge attribute used if an edge does not have
+ the attribute `attr`.
+preserve_attrs : bool
+ If True, preserve the other attributes of the original graph (that are not
+ passed to `attr`)
+partition : str
+ The key for the edge attribute containing the partition
+ data on the graph. Edges can be included, excluded or open using the
+ `EdgePartition` enum.
+
+Returns
+-------
+B : (multi)digraph-like
+ A {kind} {style}.
+"""
+
+docstring_arborescence = (
+ docstring_branching
+ + """
+Raises
+------
+NetworkXException
+ If the graph does not contain a {kind} {style}.
+
+"""
+)
+
+maximum_branching.__doc__ = docstring_branching.format(
+ kind="maximum", style="branching"
+)
+
+minimum_branching.__doc__ = (
+ docstring_branching.format(kind="minimum", style="branching")
+ + """
+See Also
+--------
+ minimal_branching
+"""
+)
+
+maximum_spanning_arborescence.__doc__ = docstring_arborescence.format(
+ kind="maximum", style="spanning arborescence"
+)
+
+minimum_spanning_arborescence.__doc__ = docstring_arborescence.format(
+ kind="minimum", style="spanning arborescence"
+)
+
+
+class ArborescenceIterator:
+ """
+ Iterate over all spanning arborescences of a graph in either increasing or
+ decreasing cost.
+
+ Notes
+ -----
+ This iterator uses the partition scheme from [1]_ (included edges,
+ excluded edges and open edges). It generates minimum spanning
+ arborescences using a modified Edmonds' Algorithm which respects the
+ partition of edges. For arborescences with the same weight, ties are
+ broken arbitrarily.
+
+ References
+ ----------
+ .. [1] G.K. Janssens, K. Sörensen, An algorithm to generate all spanning
+ trees in order of increasing cost, Pesquisa Operacional, 2005-08,
+ Vol. 25 (2), p. 219-229,
+ https://www.scielo.br/j/pope/a/XHswBwRwJyrfL88dmMwYNWp/?lang=en
+ """
+
+ @dataclass(order=True)
+ class Partition:
+ """
+ This dataclass represents a partition and stores a dict with the edge
+ data and the weight of the minimum spanning arborescence of the
+ partition dict.
+ """
+
+ mst_weight: float
+ partition_dict: dict = field(compare=False)
+
+ def __copy__(self):
+ return ArborescenceIterator.Partition(
+ self.mst_weight, self.partition_dict.copy()
+ )
+
+ def __init__(self, G, weight="weight", minimum=True, init_partition=None):
+ """
+ Initialize the iterator
+
+ Parameters
+ ----------
+ G : nx.DiGraph
+ The directed graph which we need to iterate trees over
+
+ weight : String, default = "weight"
+ The edge attribute used to store the weight of the edge
+
+ minimum : bool, default = True
+ Return the trees in increasing order while true and decreasing order
+ while false.
+
+ init_partition : tuple, default = None
+ In the case that certain edges have to be included or excluded from
+ the arborescences, `init_partition` should be in the form
+ `(included_edges, excluded_edges)` where each edges is a
+ `(u, v)`-tuple inside an iterable such as a list or set.
+
+ """
+ self.G = G.copy()
+ self.weight = weight
+ self.minimum = minimum
+ self.method = (
+ minimum_spanning_arborescence if minimum else maximum_spanning_arborescence
+ )
+ # Randomly create a key for an edge attribute to hold the partition data
+ self.partition_key = (
+ "ArborescenceIterators super secret partition attribute name"
+ )
+ if init_partition is not None:
+ partition_dict = {}
+ for e in init_partition[0]:
+ partition_dict[e] = nx.EdgePartition.INCLUDED
+ for e in init_partition[1]:
+ partition_dict[e] = nx.EdgePartition.EXCLUDED
+ self.init_partition = ArborescenceIterator.Partition(0, partition_dict)
+ else:
+ self.init_partition = None
+
+ def __iter__(self):
+ """
+ Returns
+ -------
+ ArborescenceIterator
+ The iterator object for this graph
+ """
+ self.partition_queue = PriorityQueue()
+ self._clear_partition(self.G)
+
+ # Write the initial partition if it exists.
+ if self.init_partition is not None:
+ self._write_partition(self.init_partition)
+
+ mst_weight = self.method(
+ self.G,
+ self.weight,
+ partition=self.partition_key,
+ preserve_attrs=True,
+ ).size(weight=self.weight)
+
+ self.partition_queue.put(
+ self.Partition(
+ mst_weight if self.minimum else -mst_weight,
+ (
+ {}
+ if self.init_partition is None
+ else self.init_partition.partition_dict
+ ),
+ )
+ )
+
+ return self
+
+ def __next__(self):
+ """
+ Returns
+ -------
+ (multi)Graph
+ The spanning tree of next greatest weight, which ties broken
+ arbitrarily.
+ """
+ if self.partition_queue.empty():
+ del self.G, self.partition_queue
+ raise StopIteration
+
+ partition = self.partition_queue.get()
+ self._write_partition(partition)
+ next_arborescence = self.method(
+ self.G,
+ self.weight,
+ partition=self.partition_key,
+ preserve_attrs=True,
+ )
+ self._partition(partition, next_arborescence)
+
+ self._clear_partition(next_arborescence)
+ return next_arborescence
+
+ def _partition(self, partition, partition_arborescence):
+ """
+ Create new partitions based of the minimum spanning tree of the
+ current minimum partition.
+
+ Parameters
+ ----------
+ partition : Partition
+ The Partition instance used to generate the current minimum spanning
+ tree.
+ partition_arborescence : nx.Graph
+ The minimum spanning arborescence of the input partition.
+ """
+ # create two new partitions with the data from the input partition dict
+ p1 = self.Partition(0, partition.partition_dict.copy())
+ p2 = self.Partition(0, partition.partition_dict.copy())
+ for e in partition_arborescence.edges:
+ # determine if the edge was open or included
+ if e not in partition.partition_dict:
+ # This is an open edge
+ p1.partition_dict[e] = nx.EdgePartition.EXCLUDED
+ p2.partition_dict[e] = nx.EdgePartition.INCLUDED
+
+ self._write_partition(p1)
+ try:
+ p1_mst = self.method(
+ self.G,
+ self.weight,
+ partition=self.partition_key,
+ preserve_attrs=True,
+ )
+
+ p1_mst_weight = p1_mst.size(weight=self.weight)
+ p1.mst_weight = p1_mst_weight if self.minimum else -p1_mst_weight
+ self.partition_queue.put(p1.__copy__())
+ except nx.NetworkXException:
+ pass
+
+ p1.partition_dict = p2.partition_dict.copy()
+
+ def _write_partition(self, partition):
+ """
+ Writes the desired partition into the graph to calculate the minimum
+ spanning tree. Also, if one incoming edge is included, mark all others
+ as excluded so that if that vertex is merged during Edmonds' algorithm
+ we cannot still pick another of that vertex's included edges.
+
+ Parameters
+ ----------
+ partition : Partition
+ A Partition dataclass describing a partition on the edges of the
+ graph.
+ """
+ for u, v, d in self.G.edges(data=True):
+ if (u, v) in partition.partition_dict:
+ d[self.partition_key] = partition.partition_dict[(u, v)]
+ else:
+ d[self.partition_key] = nx.EdgePartition.OPEN
+ nx._clear_cache(self.G)
+
+ for n in self.G:
+ included_count = 0
+ excluded_count = 0
+ for u, v, d in self.G.in_edges(nbunch=n, data=True):
+ if d.get(self.partition_key) == nx.EdgePartition.INCLUDED:
+ included_count += 1
+ elif d.get(self.partition_key) == nx.EdgePartition.EXCLUDED:
+ excluded_count += 1
+ # Check that if there is an included edges, all other incoming ones
+ # are excluded. If not fix it!
+ if included_count == 1 and excluded_count != self.G.in_degree(n) - 1:
+ for u, v, d in self.G.in_edges(nbunch=n, data=True):
+ if d.get(self.partition_key) != nx.EdgePartition.INCLUDED:
+ d[self.partition_key] = nx.EdgePartition.EXCLUDED
+
+ def _clear_partition(self, G):
+ """
+ Removes partition data from the graph
+ """
+ for u, v, d in G.edges(data=True):
+ if self.partition_key in d:
+ del d[self.partition_key]
+ nx._clear_cache(self.G)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/coding.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/coding.py
new file mode 100644
index 00000000..f33089f7
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/coding.py
@@ -0,0 +1,413 @@
+"""Functions for encoding and decoding trees.
+
+Since a tree is a highly restricted form of graph, it can be represented
+concisely in several ways. This module includes functions for encoding
+and decoding trees in the form of nested tuples and Prüfer
+sequences. The former requires a rooted tree, whereas the latter can be
+applied to unrooted trees. Furthermore, there is a bijection from Prüfer
+sequences to labeled trees.
+
+"""
+
+from collections import Counter
+from itertools import chain
+
+import networkx as nx
+from networkx.utils import not_implemented_for
+
+__all__ = [
+ "from_nested_tuple",
+ "from_prufer_sequence",
+ "NotATree",
+ "to_nested_tuple",
+ "to_prufer_sequence",
+]
+
+
+class NotATree(nx.NetworkXException):
+ """Raised when a function expects a tree (that is, a connected
+ undirected graph with no cycles) but gets a non-tree graph as input
+ instead.
+
+ """
+
+
+@not_implemented_for("directed")
+@nx._dispatchable(graphs="T")
+def to_nested_tuple(T, root, canonical_form=False):
+ """Returns a nested tuple representation of the given tree.
+
+ The nested tuple representation of a tree is defined
+ recursively. The tree with one node and no edges is represented by
+ the empty tuple, ``()``. A tree with ``k`` subtrees is represented
+ by a tuple of length ``k`` in which each element is the nested tuple
+ representation of a subtree.
+
+ Parameters
+ ----------
+ T : NetworkX graph
+ An undirected graph object representing a tree.
+
+ root : node
+ The node in ``T`` to interpret as the root of the tree.
+
+ canonical_form : bool
+ If ``True``, each tuple is sorted so that the function returns
+ a canonical form for rooted trees. This means "lighter" subtrees
+ will appear as nested tuples before "heavier" subtrees. In this
+ way, each isomorphic rooted tree has the same nested tuple
+ representation.
+
+ Returns
+ -------
+ tuple
+ A nested tuple representation of the tree.
+
+ Notes
+ -----
+ This function is *not* the inverse of :func:`from_nested_tuple`; the
+ only guarantee is that the rooted trees are isomorphic.
+
+ See also
+ --------
+ from_nested_tuple
+ to_prufer_sequence
+
+ Examples
+ --------
+ The tree need not be a balanced binary tree::
+
+ >>> T = nx.Graph()
+ >>> T.add_edges_from([(0, 1), (0, 2), (0, 3)])
+ >>> T.add_edges_from([(1, 4), (1, 5)])
+ >>> T.add_edges_from([(3, 6), (3, 7)])
+ >>> root = 0
+ >>> nx.to_nested_tuple(T, root)
+ (((), ()), (), ((), ()))
+
+ Continuing the above example, if ``canonical_form`` is ``True``, the
+ nested tuples will be sorted::
+
+ >>> nx.to_nested_tuple(T, root, canonical_form=True)
+ ((), ((), ()), ((), ()))
+
+ Even the path graph can be interpreted as a tree::
+
+ >>> T = nx.path_graph(4)
+ >>> root = 0
+ >>> nx.to_nested_tuple(T, root)
+ ((((),),),)
+
+ """
+
+ def _make_tuple(T, root, _parent):
+ """Recursively compute the nested tuple representation of the
+ given rooted tree.
+
+ ``_parent`` is the parent node of ``root`` in the supertree in
+ which ``T`` is a subtree, or ``None`` if ``root`` is the root of
+ the supertree. This argument is used to determine which
+ neighbors of ``root`` are children and which is the parent.
+
+ """
+ # Get the neighbors of `root` that are not the parent node. We
+ # are guaranteed that `root` is always in `T` by construction.
+ children = set(T[root]) - {_parent}
+ if len(children) == 0:
+ return ()
+ nested = (_make_tuple(T, v, root) for v in children)
+ if canonical_form:
+ nested = sorted(nested)
+ return tuple(nested)
+
+ # Do some sanity checks on the input.
+ if not nx.is_tree(T):
+ raise nx.NotATree("provided graph is not a tree")
+ if root not in T:
+ raise nx.NodeNotFound(f"Graph {T} contains no node {root}")
+
+ return _make_tuple(T, root, None)
+
+
+@nx._dispatchable(graphs=None, returns_graph=True)
+def from_nested_tuple(sequence, sensible_relabeling=False):
+ """Returns the rooted tree corresponding to the given nested tuple.
+
+ The nested tuple representation of a tree is defined
+ recursively. The tree with one node and no edges is represented by
+ the empty tuple, ``()``. A tree with ``k`` subtrees is represented
+ by a tuple of length ``k`` in which each element is the nested tuple
+ representation of a subtree.
+
+ Parameters
+ ----------
+ sequence : tuple
+ A nested tuple representing a rooted tree.
+
+ sensible_relabeling : bool
+ Whether to relabel the nodes of the tree so that nodes are
+ labeled in increasing order according to their breadth-first
+ search order from the root node.
+
+ Returns
+ -------
+ NetworkX graph
+ The tree corresponding to the given nested tuple, whose root
+ node is node 0. If ``sensible_labeling`` is ``True``, nodes will
+ be labeled in breadth-first search order starting from the root
+ node.
+
+ Notes
+ -----
+ This function is *not* the inverse of :func:`to_nested_tuple`; the
+ only guarantee is that the rooted trees are isomorphic.
+
+ See also
+ --------
+ to_nested_tuple
+ from_prufer_sequence
+
+ Examples
+ --------
+ Sensible relabeling ensures that the nodes are labeled from the root
+ starting at 0::
+
+ >>> balanced = (((), ()), ((), ()))
+ >>> T = nx.from_nested_tuple(balanced, sensible_relabeling=True)
+ >>> edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]
+ >>> all((u, v) in T.edges() or (v, u) in T.edges() for (u, v) in edges)
+ True
+
+ """
+
+ def _make_tree(sequence):
+ """Recursively creates a tree from the given sequence of nested
+ tuples.
+
+ This function employs the :func:`~networkx.tree.join` function
+ to recursively join subtrees into a larger tree.
+
+ """
+ # The empty sequence represents the empty tree, which is the
+ # (unique) graph with a single node. We mark the single node
+ # with an attribute that indicates that it is the root of the
+ # graph.
+ if len(sequence) == 0:
+ return nx.empty_graph(1)
+ # For a nonempty sequence, get the subtrees for each child
+ # sequence and join all the subtrees at their roots. After
+ # joining the subtrees, the root is node 0.
+ return nx.tree.join_trees([(_make_tree(child), 0) for child in sequence])
+
+ # Make the tree and remove the `is_root` node attribute added by the
+ # helper function.
+ T = _make_tree(sequence)
+ if sensible_relabeling:
+ # Relabel the nodes according to their breadth-first search
+ # order, starting from the root node (that is, the node 0).
+ bfs_nodes = chain([0], (v for u, v in nx.bfs_edges(T, 0)))
+ labels = {v: i for i, v in enumerate(bfs_nodes)}
+ # We would like to use `copy=False`, but `relabel_nodes` doesn't
+ # allow a relabel mapping that can't be topologically sorted.
+ T = nx.relabel_nodes(T, labels)
+ return T
+
+
+@not_implemented_for("directed")
+@nx._dispatchable(graphs="T")
+def to_prufer_sequence(T):
+ r"""Returns the Prüfer sequence of the given tree.
+
+ A *Prüfer sequence* is a list of *n* - 2 numbers between 0 and
+ *n* - 1, inclusive. The tree corresponding to a given Prüfer
+ sequence can be recovered by repeatedly joining a node in the
+ sequence with a node with the smallest potential degree according to
+ the sequence.
+
+ Parameters
+ ----------
+ T : NetworkX graph
+ An undirected graph object representing a tree.
+
+ Returns
+ -------
+ list
+ The Prüfer sequence of the given tree.
+
+ Raises
+ ------
+ NetworkXPointlessConcept
+ If the number of nodes in `T` is less than two.
+
+ NotATree
+ If `T` is not a tree.
+
+ KeyError
+ If the set of nodes in `T` is not {0, …, *n* - 1}.
+
+ Notes
+ -----
+ There is a bijection from labeled trees to Prüfer sequences. This
+ function is the inverse of the :func:`from_prufer_sequence`
+ function.
+
+ Sometimes Prüfer sequences use nodes labeled from 1 to *n* instead
+ of from 0 to *n* - 1. This function requires nodes to be labeled in
+ the latter form. You can use :func:`~networkx.relabel_nodes` to
+ relabel the nodes of your tree to the appropriate format.
+
+ This implementation is from [1]_ and has a running time of
+ $O(n)$.
+
+ See also
+ --------
+ to_nested_tuple
+ from_prufer_sequence
+
+ References
+ ----------
+ .. [1] Wang, Xiaodong, Lei Wang, and Yingjie Wu.
+ "An optimal algorithm for Prufer codes."
+ *Journal of Software Engineering and Applications* 2.02 (2009): 111.
+ <https://doi.org/10.4236/jsea.2009.22016>
+
+ Examples
+ --------
+ There is a bijection between Prüfer sequences and labeled trees, so
+ this function is the inverse of the :func:`from_prufer_sequence`
+ function:
+
+ >>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]
+ >>> tree = nx.Graph(edges)
+ >>> sequence = nx.to_prufer_sequence(tree)
+ >>> sequence
+ [3, 3, 3, 4]
+ >>> tree2 = nx.from_prufer_sequence(sequence)
+ >>> list(tree2.edges()) == edges
+ True
+
+ """
+ # Perform some sanity checks on the input.
+ n = len(T)
+ if n < 2:
+ msg = "Prüfer sequence undefined for trees with fewer than two nodes"
+ raise nx.NetworkXPointlessConcept(msg)
+ if not nx.is_tree(T):
+ raise nx.NotATree("provided graph is not a tree")
+ if set(T) != set(range(n)):
+ raise KeyError("tree must have node labels {0, ..., n - 1}")
+
+ degree = dict(T.degree())
+
+ def parents(u):
+ return next(v for v in T[u] if degree[v] > 1)
+
+ index = u = next(k for k in range(n) if degree[k] == 1)
+ result = []
+ for i in range(n - 2):
+ v = parents(u)
+ result.append(v)
+ degree[v] -= 1
+ if v < index and degree[v] == 1:
+ u = v
+ else:
+ index = u = next(k for k in range(index + 1, n) if degree[k] == 1)
+ return result
+
+
+@nx._dispatchable(graphs=None, returns_graph=True)
+def from_prufer_sequence(sequence):
+ r"""Returns the tree corresponding to the given Prüfer sequence.
+
+ A *Prüfer sequence* is a list of *n* - 2 numbers between 0 and
+ *n* - 1, inclusive. The tree corresponding to a given Prüfer
+ sequence can be recovered by repeatedly joining a node in the
+ sequence with a node with the smallest potential degree according to
+ the sequence.
+
+ Parameters
+ ----------
+ sequence : list
+ A Prüfer sequence, which is a list of *n* - 2 integers between
+ zero and *n* - 1, inclusive.
+
+ Returns
+ -------
+ NetworkX graph
+ The tree corresponding to the given Prüfer sequence.
+
+ Raises
+ ------
+ NetworkXError
+ If the Prüfer sequence is not valid.
+
+ Notes
+ -----
+ There is a bijection from labeled trees to Prüfer sequences. This
+ function is the inverse of the :func:`from_prufer_sequence` function.
+
+ Sometimes Prüfer sequences use nodes labeled from 1 to *n* instead
+ of from 0 to *n* - 1. This function requires nodes to be labeled in
+ the latter form. You can use :func:`networkx.relabel_nodes` to
+ relabel the nodes of your tree to the appropriate format.
+
+ This implementation is from [1]_ and has a running time of
+ $O(n)$.
+
+ References
+ ----------
+ .. [1] Wang, Xiaodong, Lei Wang, and Yingjie Wu.
+ "An optimal algorithm for Prufer codes."
+ *Journal of Software Engineering and Applications* 2.02 (2009): 111.
+ <https://doi.org/10.4236/jsea.2009.22016>
+
+ See also
+ --------
+ from_nested_tuple
+ to_prufer_sequence
+
+ Examples
+ --------
+ There is a bijection between Prüfer sequences and labeled trees, so
+ this function is the inverse of the :func:`to_prufer_sequence`
+ function:
+
+ >>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]
+ >>> tree = nx.Graph(edges)
+ >>> sequence = nx.to_prufer_sequence(tree)
+ >>> sequence
+ [3, 3, 3, 4]
+ >>> tree2 = nx.from_prufer_sequence(sequence)
+ >>> list(tree2.edges()) == edges
+ True
+
+ """
+ n = len(sequence) + 2
+ # `degree` stores the remaining degree (plus one) for each node. The
+ # degree of a node in the decoded tree is one more than the number
+ # of times it appears in the code.
+ degree = Counter(chain(sequence, range(n)))
+ T = nx.empty_graph(n)
+ # `not_orphaned` is the set of nodes that have a parent in the
+ # tree. After the loop, there should be exactly two nodes that are
+ # not in this set.
+ not_orphaned = set()
+ index = u = next(k for k in range(n) if degree[k] == 1)
+ for v in sequence:
+ # check the validity of the prufer sequence
+ if v < 0 or v > n - 1:
+ raise nx.NetworkXError(
+ f"Invalid Prufer sequence: Values must be between 0 and {n-1}, got {v}"
+ )
+ T.add_edge(u, v)
+ not_orphaned.add(u)
+ degree[v] -= 1
+ if v < index and degree[v] == 1:
+ u = v
+ else:
+ index = u = next(k for k in range(index + 1, n) if degree[k] == 1)
+ # At this point, there must be exactly two orphaned nodes; join them.
+ orphans = set(T) - not_orphaned
+ u, v = orphans
+ T.add_edge(u, v)
+ return T
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/decomposition.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/decomposition.py
new file mode 100644
index 00000000..c8b8f247
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/decomposition.py
@@ -0,0 +1,88 @@
+r"""Function for computing a junction tree of a graph."""
+
+from itertools import combinations
+
+import networkx as nx
+from networkx.algorithms import chordal_graph_cliques, complete_to_chordal_graph, moral
+from networkx.utils import not_implemented_for
+
+__all__ = ["junction_tree"]
+
+
+@not_implemented_for("multigraph")
+@nx._dispatchable(returns_graph=True)
+def junction_tree(G):
+ r"""Returns a junction tree of a given graph.
+
+ A junction tree (or clique tree) is constructed from a (un)directed graph G.
+ The tree is constructed based on a moralized and triangulated version of G.
+ The tree's nodes consist of maximal cliques and sepsets of the revised graph.
+ The sepset of two cliques is the intersection of the nodes of these cliques,
+ e.g. the sepset of (A,B,C) and (A,C,E,F) is (A,C). These nodes are often called
+ "variables" in this literature. The tree is bipartite with each sepset
+ connected to its two cliques.
+
+ Junction Trees are not unique as the order of clique consideration determines
+ which sepsets are included.
+
+ The junction tree algorithm consists of five steps [1]_:
+
+ 1. Moralize the graph
+ 2. Triangulate the graph
+ 3. Find maximal cliques
+ 4. Build the tree from cliques, connecting cliques with shared
+ nodes, set edge-weight to number of shared variables
+ 5. Find maximum spanning tree
+
+
+ Parameters
+ ----------
+ G : networkx.Graph
+ Directed or undirected graph.
+
+ Returns
+ -------
+ junction_tree : networkx.Graph
+ The corresponding junction tree of `G`.
+
+ Raises
+ ------
+ NetworkXNotImplemented
+ Raised if `G` is an instance of `MultiGraph` or `MultiDiGraph`.
+
+ References
+ ----------
+ .. [1] Junction tree algorithm:
+ https://en.wikipedia.org/wiki/Junction_tree_algorithm
+
+ .. [2] Finn V. Jensen and Frank Jensen. 1994. Optimal
+ junction trees. In Proceedings of the Tenth international
+ conference on Uncertainty in artificial intelligence (UAI’94).
+ Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 360–366.
+ """
+
+ clique_graph = nx.Graph()
+
+ if G.is_directed():
+ G = moral.moral_graph(G)
+ chordal_graph, _ = complete_to_chordal_graph(G)
+
+ cliques = [tuple(sorted(i)) for i in chordal_graph_cliques(chordal_graph)]
+ clique_graph.add_nodes_from(cliques, type="clique")
+
+ for edge in combinations(cliques, 2):
+ set_edge_0 = set(edge[0])
+ set_edge_1 = set(edge[1])
+ if not set_edge_0.isdisjoint(set_edge_1):
+ sepset = tuple(sorted(set_edge_0.intersection(set_edge_1)))
+ clique_graph.add_edge(edge[0], edge[1], weight=len(sepset), sepset=sepset)
+
+ junction_tree = nx.maximum_spanning_tree(clique_graph)
+
+ for edge in list(junction_tree.edges(data=True)):
+ junction_tree.add_node(edge[2]["sepset"], type="sepset")
+ junction_tree.add_edge(edge[0], edge[2]["sepset"])
+ junction_tree.add_edge(edge[1], edge[2]["sepset"])
+ junction_tree.remove_edge(edge[0], edge[1])
+
+ return junction_tree
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/mst.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/mst.py
new file mode 100644
index 00000000..554613b8
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/mst.py
@@ -0,0 +1,1284 @@
+"""
+Algorithms for calculating min/max spanning trees/forests.
+
+"""
+
+from dataclasses import dataclass, field
+from enum import Enum
+from heapq import heappop, heappush
+from itertools import count
+from math import isnan
+from operator import itemgetter
+from queue import PriorityQueue
+
+import networkx as nx
+from networkx.utils import UnionFind, not_implemented_for, py_random_state
+
+__all__ = [
+ "minimum_spanning_edges",
+ "maximum_spanning_edges",
+ "minimum_spanning_tree",
+ "maximum_spanning_tree",
+ "number_of_spanning_trees",
+ "random_spanning_tree",
+ "partition_spanning_tree",
+ "EdgePartition",
+ "SpanningTreeIterator",
+]
+
+
+class EdgePartition(Enum):
+ """
+ An enum to store the state of an edge partition. The enum is written to the
+ edges of a graph before being pasted to `kruskal_mst_edges`. Options are:
+
+ - EdgePartition.OPEN
+ - EdgePartition.INCLUDED
+ - EdgePartition.EXCLUDED
+ """
+
+ OPEN = 0
+ INCLUDED = 1
+ EXCLUDED = 2
+
+
+@not_implemented_for("multigraph")
+@nx._dispatchable(edge_attrs="weight", preserve_edge_attrs="data")
+def boruvka_mst_edges(
+ G, minimum=True, weight="weight", keys=False, data=True, ignore_nan=False
+):
+ """Iterate over edges of a Borůvka's algorithm min/max spanning tree.
+
+ Parameters
+ ----------
+ G : NetworkX Graph
+ The edges of `G` must have distinct weights,
+ otherwise the edges may not form a tree.
+
+ minimum : bool (default: True)
+ Find the minimum (True) or maximum (False) spanning tree.
+
+ weight : string (default: 'weight')
+ The name of the edge attribute holding the edge weights.
+
+ keys : bool (default: True)
+ This argument is ignored since this function is not
+ implemented for multigraphs; it exists only for consistency
+ with the other minimum spanning tree functions.
+
+ data : bool (default: True)
+ Flag for whether to yield edge attribute dicts.
+ If True, yield edges `(u, v, d)`, where `d` is the attribute dict.
+ If False, yield edges `(u, v)`.
+
+ 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.
+
+ """
+ # Initialize a forest, assuming initially that it is the discrete
+ # partition of the nodes of the graph.
+ forest = UnionFind(G)
+
+ def best_edge(component):
+ """Returns the optimum (minimum or maximum) edge on the edge
+ boundary of the given set of nodes.
+
+ A return value of ``None`` indicates an empty boundary.
+
+ """
+ sign = 1 if minimum else -1
+ minwt = float("inf")
+ boundary = None
+ for e in nx.edge_boundary(G, component, data=True):
+ wt = e[-1].get(weight, 1) * sign
+ if isnan(wt):
+ if ignore_nan:
+ continue
+ msg = f"NaN found as an edge weight. Edge {e}"
+ raise ValueError(msg)
+ if wt < minwt:
+ minwt = wt
+ boundary = e
+ return boundary
+
+ # Determine the optimum edge in the edge boundary of each component
+ # in the forest.
+ best_edges = (best_edge(component) for component in forest.to_sets())
+ best_edges = [edge for edge in best_edges if edge is not None]
+ # If each entry was ``None``, that means the graph was disconnected,
+ # so we are done generating the forest.
+ while best_edges:
+ # Determine the optimum edge in the edge boundary of each
+ # component in the forest.
+ #
+ # This must be a sequence, not an iterator. In this list, the
+ # same edge may appear twice, in different orientations (but
+ # that's okay, since a union operation will be called on the
+ # endpoints the first time it is seen, but not the second time).
+ #
+ # Any ``None`` indicates that the edge boundary for that
+ # component was empty, so that part of the forest has been
+ # completed.
+ #
+ # TODO This can be parallelized, both in the outer loop over
+ # each component in the forest and in the computation of the
+ # minimum. (Same goes for the identical lines outside the loop.)
+ best_edges = (best_edge(component) for component in forest.to_sets())
+ best_edges = [edge for edge in best_edges if edge is not None]
+ # Join trees in the forest using the best edges, and yield that
+ # edge, since it is part of the spanning tree.
+ #
+ # TODO This loop can be parallelized, to an extent (the union
+ # operation must be atomic).
+ for u, v, d in best_edges:
+ if forest[u] != forest[v]:
+ if data:
+ yield u, v, d
+ else:
+ yield u, v
+ forest.union(u, v)
+
+
+@nx._dispatchable(
+ edge_attrs={"weight": None, "partition": None}, preserve_edge_attrs="data"
+)
+def kruskal_mst_edges(
+ G, minimum, weight="weight", keys=True, data=True, ignore_nan=False, partition=None
+):
+ """
+ Iterate over edge of a Kruskal's algorithm min/max spanning tree.
+
+ Parameters
+ ----------
+ G : NetworkX Graph
+ The graph holding the tree of interest.
+
+ minimum : bool (default: True)
+ Find the minimum (True) or maximum (False) spanning tree.
+
+ weight : string (default: 'weight')
+ The name of the edge attribute holding the edge weights.
+
+ keys : bool (default: True)
+ If `G` is a multigraph, `keys` controls whether edge keys ar yielded.
+ Otherwise `keys` is ignored.
+
+ data : bool (default: True)
+ Flag for whether to yield edge attribute dicts.
+ If True, yield edges `(u, v, d)`, where `d` is the attribute dict.
+ If False, yield edges `(u, v)`.
+
+ 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.
+
+ partition : string (default: None)
+ The name of the edge attribute holding the partition data, if it exists.
+ Partition data is written to the edges using the `EdgePartition` enum.
+ If a partition exists, all included edges and none of the excluded edges
+ will appear in the final tree. Open edges may or may not be used.
+
+ Yields
+ ------
+ edge tuple
+ The edges as discovered by Kruskal's method. Each edge can
+ take the following forms: `(u, v)`, `(u, v, d)` or `(u, v, k, d)`
+ depending on the `key` and `data` parameters
+ """
+ subtrees = UnionFind()
+ if G.is_multigraph():
+ edges = G.edges(keys=True, data=True)
+ else:
+ edges = G.edges(data=True)
+
+ """
+ Sort the edges of the graph with respect to the partition data.
+ Edges are returned in the following order:
+
+ * Included edges
+ * Open edges from smallest to largest weight
+ * Excluded edges
+ """
+ included_edges = []
+ open_edges = []
+ for e in edges:
+ d = e[-1]
+ wt = d.get(weight, 1)
+ if isnan(wt):
+ if ignore_nan:
+ continue
+ raise ValueError(f"NaN found as an edge weight. Edge {e}")
+
+ edge = (wt,) + e
+ if d.get(partition) == EdgePartition.INCLUDED:
+ included_edges.append(edge)
+ elif d.get(partition) == EdgePartition.EXCLUDED:
+ continue
+ else:
+ open_edges.append(edge)
+
+ if minimum:
+ sorted_open_edges = sorted(open_edges, key=itemgetter(0))
+ else:
+ sorted_open_edges = sorted(open_edges, key=itemgetter(0), reverse=True)
+
+ # Condense the lists into one
+ included_edges.extend(sorted_open_edges)
+ sorted_edges = included_edges
+ del open_edges, sorted_open_edges, included_edges
+
+ # Multigraphs need to handle edge keys in addition to edge data.
+ if G.is_multigraph():
+ for wt, u, v, k, d in sorted_edges:
+ if subtrees[u] != subtrees[v]:
+ if keys:
+ if data:
+ yield u, v, k, d
+ else:
+ yield u, v, k
+ else:
+ if data:
+ yield u, v, d
+ else:
+ yield u, v
+ subtrees.union(u, v)
+ else:
+ for wt, u, v, d in sorted_edges:
+ if subtrees[u] != subtrees[v]:
+ if data:
+ yield u, v, d
+ else:
+ yield u, v
+ subtrees.union(u, v)
+
+
+@nx._dispatchable(edge_attrs="weight", preserve_edge_attrs="data")
+def prim_mst_edges(G, minimum, weight="weight", keys=True, data=True, ignore_nan=False):
+ """Iterate over edges of Prim's algorithm min/max spanning tree.
+
+ Parameters
+ ----------
+ G : NetworkX Graph
+ The graph holding the tree of interest.
+
+ minimum : bool (default: True)
+ Find the minimum (True) or maximum (False) spanning tree.
+
+ weight : string (default: 'weight')
+ The name of the edge attribute holding the edge weights.
+
+ keys : bool (default: True)
+ If `G` is a multigraph, `keys` controls whether edge keys ar yielded.
+ Otherwise `keys` is ignored.
+
+ data : bool (default: True)
+ Flag for whether to yield edge attribute dicts.
+ If True, yield edges `(u, v, d)`, where `d` is the attribute dict.
+ If False, yield edges `(u, v)`.
+
+ 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.
+
+ """
+ is_multigraph = G.is_multigraph()
+ push = heappush
+ pop = heappop
+
+ nodes = set(G)
+ c = count()
+
+ sign = 1 if minimum else -1
+
+ while nodes:
+ u = nodes.pop()
+ frontier = []
+ visited = {u}
+ if is_multigraph:
+ for v, keydict in G.adj[u].items():
+ for k, d in keydict.items():
+ wt = d.get(weight, 1) * sign
+ if isnan(wt):
+ if ignore_nan:
+ continue
+ msg = f"NaN found as an edge weight. Edge {(u, v, k, d)}"
+ raise ValueError(msg)
+ push(frontier, (wt, next(c), u, v, k, d))
+ else:
+ for v, d in G.adj[u].items():
+ wt = d.get(weight, 1) * sign
+ if isnan(wt):
+ if ignore_nan:
+ continue
+ msg = f"NaN found as an edge weight. Edge {(u, v, d)}"
+ raise ValueError(msg)
+ push(frontier, (wt, next(c), u, v, d))
+ while nodes and frontier:
+ if is_multigraph:
+ W, _, u, v, k, d = pop(frontier)
+ else:
+ W, _, u, v, d = pop(frontier)
+ if v in visited or v not in nodes:
+ continue
+ # Multigraphs need to handle edge keys in addition to edge data.
+ if is_multigraph and keys:
+ if data:
+ yield u, v, k, d
+ else:
+ yield u, v, k
+ else:
+ if data:
+ yield u, v, d
+ else:
+ yield u, v
+ # update frontier
+ visited.add(v)
+ nodes.discard(v)
+ if is_multigraph:
+ for w, keydict in G.adj[v].items():
+ if w in visited:
+ continue
+ for k2, d2 in keydict.items():
+ new_weight = d2.get(weight, 1) * sign
+ if isnan(new_weight):
+ if ignore_nan:
+ continue
+ msg = f"NaN found as an edge weight. Edge {(v, w, k2, d2)}"
+ raise ValueError(msg)
+ push(frontier, (new_weight, next(c), v, w, k2, d2))
+ else:
+ for w, d2 in G.adj[v].items():
+ if w in visited:
+ continue
+ new_weight = d2.get(weight, 1) * sign
+ if isnan(new_weight):
+ if ignore_nan:
+ continue
+ msg = f"NaN found as an edge weight. Edge {(v, w, d2)}"
+ raise ValueError(msg)
+ push(frontier, (new_weight, next(c), v, w, d2))
+
+
+ALGORITHMS = {
+ "boruvka": boruvka_mst_edges,
+ "borůvka": boruvka_mst_edges,
+ "kruskal": kruskal_mst_edges,
+ "prim": prim_mst_edges,
+}
+
+
+@not_implemented_for("directed")
+@nx._dispatchable(edge_attrs="weight", preserve_edge_attrs="data")
+def minimum_spanning_edges(
+ G, algorithm="kruskal", weight="weight", keys=True, data=True, ignore_nan=False
+):
+ """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').
+
+ keys : bool
+ Whether to yield edge key in multigraphs in addition to the edge.
+ If `G` is not a multigraph, this is ignored.
+
+ 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 : iterator
+ 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)`
+
+ If `G` is a multigraph, `keys` indicates whether the edge key `k` will
+ be reported in the third position in the edge tuple. `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 `(u, v, d)` if `data` is True
+ or `(u, v)` if `data` is False.
+
+ Examples
+ --------
+ >>> from networkx.algorithms import tree
+
+ Find minimum spanning edges by Kruskal's algorithm
+
+ >>> G = nx.cycle_graph(4)
+ >>> G.add_edge(0, 3, weight=2)
+ >>> mst = tree.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 = nx.cycle_graph(4)
+ >>> G.add_edge(0, 3, weight=2)
+ >>> mst = tree.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/
+
+ """
+ try:
+ algo = ALGORITHMS[algorithm]
+ except KeyError as err:
+ msg = f"{algorithm} is not a valid choice for an algorithm."
+ raise ValueError(msg) from err
+
+ return algo(
+ G, minimum=True, weight=weight, keys=keys, data=data, ignore_nan=ignore_nan
+ )
+
+
+@not_implemented_for("directed")
+@nx._dispatchable(edge_attrs="weight", preserve_edge_attrs="data")
+def maximum_spanning_edges(
+ G, algorithm="kruskal", weight="weight", keys=True, data=True, ignore_nan=False
+):
+ """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').
+
+ keys : bool
+ Whether to yield edge key in multigraphs in addition to the edge.
+ If `G` is not a multigraph, this is ignored.
+
+ 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 : iterator
+ 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)`
+
+ If `G` is a multigraph, `keys` indicates whether the edge key `k` will
+ be reported in the third position in the edge tuple. `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 `(u, v, d)` if `data` is True
+ or `(u, v)` if `data` is False.
+
+ Examples
+ --------
+ >>> 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)
+ >>> 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]]
+
+ 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/
+ """
+ try:
+ algo = ALGORITHMS[algorithm]
+ except KeyError as err:
+ msg = f"{algorithm} is not a valid choice for an algorithm."
+ raise ValueError(msg) from err
+
+ return algo(
+ G, minimum=False, weight=weight, keys=keys, data=data, ignore_nan=ignore_nan
+ )
+
+
+@nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
+def minimum_spanning_tree(G, weight="weight", algorithm="kruskal", ignore_nan=False):
+ """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 : NetworkX Graph
+ A minimum spanning tree or forest.
+
+ Examples
+ --------
+ >>> G = nx.cycle_graph(4)
+ >>> G.add_edge(0, 3, weight=2)
+ >>> T = nx.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.
+
+ There may be more than one tree with the same minimum or maximum weight.
+ See :mod:`networkx.tree.recognition` for more detailed definitions.
+
+ Isolated nodes with self-loops are in the tree as edgeless isolated nodes.
+
+ """
+ edges = minimum_spanning_edges(
+ G, algorithm, weight, keys=True, data=True, ignore_nan=ignore_nan
+ )
+ T = G.__class__() # Same graph class as G
+ T.graph.update(G.graph)
+ T.add_nodes_from(G.nodes.items())
+ T.add_edges_from(edges)
+ return T
+
+
+@nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
+def partition_spanning_tree(
+ G, minimum=True, weight="weight", partition="partition", ignore_nan=False
+):
+ """
+ Find a spanning tree while respecting a partition of edges.
+
+ Edges can be flagged as either `INCLUDED` which are required to be in the
+ returned tree, `EXCLUDED`, which cannot be in the returned tree and `OPEN`.
+
+ This is used in the SpanningTreeIterator to create new partitions following
+ the algorithm of Sörensen and Janssens [1]_.
+
+ Parameters
+ ----------
+ G : undirected graph
+ An undirected graph.
+
+ minimum : bool (default: True)
+ Determines whether the returned tree is the minimum spanning tree of
+ the partition of the maximum one.
+
+ weight : str
+ Data key to use for edge weights.
+
+ partition : str
+ The key for the edge attribute containing the partition
+ data on the graph. Edges can be included, excluded or open using the
+ `EdgePartition` enum.
+
+ 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 : NetworkX Graph
+ A minimum spanning tree using all of the included edges in the graph and
+ none of the excluded edges.
+
+ References
+ ----------
+ .. [1] G.K. Janssens, K. Sörensen, An algorithm to generate all spanning
+ trees in order of increasing cost, Pesquisa Operacional, 2005-08,
+ Vol. 25 (2), p. 219-229,
+ https://www.scielo.br/j/pope/a/XHswBwRwJyrfL88dmMwYNWp/?lang=en
+ """
+ edges = kruskal_mst_edges(
+ G,
+ minimum,
+ weight,
+ keys=True,
+ data=True,
+ ignore_nan=ignore_nan,
+ partition=partition,
+ )
+ T = G.__class__() # Same graph class as G
+ T.graph.update(G.graph)
+ T.add_nodes_from(G.nodes.items())
+ T.add_edges_from(edges)
+ return T
+
+
+@nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
+def maximum_spanning_tree(G, weight="weight", algorithm="kruskal", ignore_nan=False):
+ """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 : NetworkX Graph
+ A maximum spanning tree or forest.
+
+
+ Examples
+ --------
+ >>> G = nx.cycle_graph(4)
+ >>> G.add_edge(0, 3, weight=2)
+ >>> T = nx.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 :mod:`networkx.tree.recognition` for more detailed definitions.
+
+ Isolated nodes with self-loops are in the tree as edgeless isolated nodes.
+
+ """
+ edges = maximum_spanning_edges(
+ G, algorithm, weight, keys=True, data=True, ignore_nan=ignore_nan
+ )
+ edges = list(edges)
+ T = G.__class__() # Same graph class as G
+ T.graph.update(G.graph)
+ T.add_nodes_from(G.nodes.items())
+ T.add_edges_from(edges)
+ return T
+
+
+@py_random_state(3)
+@nx._dispatchable(preserve_edge_attrs=True, returns_graph=True)
+def random_spanning_tree(G, weight=None, *, multiplicative=True, seed=None):
+ """
+ Sample a random spanning tree using the edges weights of `G`.
+
+ This function supports two different methods for determining the
+ probability of the graph. If ``multiplicative=True``, the probability
+ is based on the product of edge weights, and if ``multiplicative=False``
+ it is based on the sum of the edge weight. However, since it is
+ easier to determine the total weight of all spanning trees for the
+ multiplicative version, that is significantly faster and should be used if
+ possible. Additionally, setting `weight` to `None` will cause a spanning tree
+ to be selected with uniform probability.
+
+ The function uses algorithm A8 in [1]_ .
+
+ Parameters
+ ----------
+ G : nx.Graph
+ An undirected version of the original graph.
+
+ weight : string
+ The edge key for the edge attribute holding edge weight.
+
+ multiplicative : bool, default=True
+ If `True`, the probability of each tree is the product of its edge weight
+ over the sum of the product of all the spanning trees in the graph. If
+ `False`, the probability is the sum of its edge weight over the sum of
+ the sum of weights for all spanning trees in the graph.
+
+ seed : integer, random_state, or None (default)
+ Indicator of random number generation state.
+ See :ref:`Randomness<randomness>`.
+
+ Returns
+ -------
+ nx.Graph
+ A spanning tree using the distribution defined by the weight of the tree.
+
+ References
+ ----------
+ .. [1] V. Kulkarni, Generating random combinatorial objects, Journal of
+ Algorithms, 11 (1990), pp. 185–207
+ """
+
+ def find_node(merged_nodes, node):
+ """
+ We can think of clusters of contracted nodes as having one
+ representative in the graph. Each node which is not in merged_nodes
+ is still its own representative. Since a representative can be later
+ contracted, we need to recursively search though the dict to find
+ the final representative, but once we know it we can use path
+ compression to speed up the access of the representative for next time.
+
+ This cannot be replaced by the standard NetworkX union_find since that
+ data structure will merge nodes with less representing nodes into the
+ one with more representing nodes but this function requires we merge
+ them using the order that contract_edges contracts using.
+
+ Parameters
+ ----------
+ merged_nodes : dict
+ The dict storing the mapping from node to representative
+ node
+ The node whose representative we seek
+
+ Returns
+ -------
+ The representative of the `node`
+ """
+ if node not in merged_nodes:
+ return node
+ else:
+ rep = find_node(merged_nodes, merged_nodes[node])
+ merged_nodes[node] = rep
+ return rep
+
+ def prepare_graph():
+ """
+ For the graph `G`, remove all edges not in the set `V` and then
+ contract all edges in the set `U`.
+
+ Returns
+ -------
+ A copy of `G` which has had all edges not in `V` removed and all edges
+ in `U` contracted.
+ """
+
+ # The result is a MultiGraph version of G so that parallel edges are
+ # allowed during edge contraction
+ result = nx.MultiGraph(incoming_graph_data=G)
+
+ # Remove all edges not in V
+ edges_to_remove = set(result.edges()).difference(V)
+ result.remove_edges_from(edges_to_remove)
+
+ # Contract all edges in U
+ #
+ # Imagine that you have two edges to contract and they share an
+ # endpoint like this:
+ # [0] ----- [1] ----- [2]
+ # If we contract (0, 1) first, the contraction function will always
+ # delete the second node it is passed so the resulting graph would be
+ # [0] ----- [2]
+ # and edge (1, 2) no longer exists but (0, 2) would need to be contracted
+ # in its place now. That is why I use the below dict as a merge-find
+ # data structure with path compression to track how the nodes are merged.
+ merged_nodes = {}
+
+ for u, v in U:
+ u_rep = find_node(merged_nodes, u)
+ v_rep = find_node(merged_nodes, v)
+ # We cannot contract a node with itself
+ if u_rep == v_rep:
+ continue
+ nx.contracted_nodes(result, u_rep, v_rep, self_loops=False, copy=False)
+ merged_nodes[v_rep] = u_rep
+
+ return merged_nodes, result
+
+ def spanning_tree_total_weight(G, weight):
+ """
+ Find the sum of weights of the spanning trees of `G` using the
+ appropriate `method`.
+
+ This is easy if the chosen method is 'multiplicative', since we can
+ use Kirchhoff's Tree Matrix Theorem directly. However, with the
+ 'additive' method, this process is slightly more complex and less
+ computationally efficient as we have to find the number of spanning
+ trees which contain each possible edge in the graph.
+
+ Parameters
+ ----------
+ G : NetworkX Graph
+ The graph to find the total weight of all spanning trees on.
+
+ weight : string
+ The key for the weight edge attribute of the graph.
+
+ Returns
+ -------
+ float
+ The sum of either the multiplicative or additive weight for all
+ spanning trees in the graph.
+ """
+ if multiplicative:
+ return nx.total_spanning_tree_weight(G, weight)
+ else:
+ # There are two cases for the total spanning tree additive weight.
+ # 1. There is one edge in the graph. Then the only spanning tree is
+ # that edge itself, which will have a total weight of that edge
+ # itself.
+ if G.number_of_edges() == 1:
+ return G.edges(data=weight).__iter__().__next__()[2]
+ # 2. There are no edges or two or more edges in the graph. Then, we find the
+ # total weight of the spanning trees using the formula in the
+ # reference paper: take the weight of each edge and multiply it by
+ # the number of spanning trees which include that edge. This
+ # can be accomplished by contracting the edge and finding the
+ # multiplicative total spanning tree weight if the weight of each edge
+ # is assumed to be 1, which is conveniently built into networkx already,
+ # by calling total_spanning_tree_weight with weight=None.
+ # Note that with no edges the returned value is just zero.
+ else:
+ total = 0
+ for u, v, w in G.edges(data=weight):
+ total += w * nx.total_spanning_tree_weight(
+ nx.contracted_edge(G, edge=(u, v), self_loops=False), None
+ )
+ return total
+
+ if G.number_of_nodes() < 2:
+ # no edges in the spanning tree
+ return nx.empty_graph(G.nodes)
+
+ U = set()
+ st_cached_value = 0
+ V = set(G.edges())
+ shuffled_edges = list(G.edges())
+ seed.shuffle(shuffled_edges)
+
+ for u, v in shuffled_edges:
+ e_weight = G[u][v][weight] if weight is not None else 1
+ node_map, prepared_G = prepare_graph()
+ G_total_tree_weight = spanning_tree_total_weight(prepared_G, weight)
+ # Add the edge to U so that we can compute the total tree weight
+ # assuming we include that edge
+ # Now, if (u, v) cannot exist in G because it is fully contracted out
+ # of existence, then it by definition cannot influence G_e's Kirchhoff
+ # value. But, we also cannot pick it.
+ rep_edge = (find_node(node_map, u), find_node(node_map, v))
+ # Check to see if the 'representative edge' for the current edge is
+ # in prepared_G. If so, then we can pick it.
+ if rep_edge in prepared_G.edges:
+ prepared_G_e = nx.contracted_edge(
+ prepared_G, edge=rep_edge, self_loops=False
+ )
+ G_e_total_tree_weight = spanning_tree_total_weight(prepared_G_e, weight)
+ if multiplicative:
+ threshold = e_weight * G_e_total_tree_weight / G_total_tree_weight
+ else:
+ numerator = (
+ st_cached_value + e_weight
+ ) * nx.total_spanning_tree_weight(prepared_G_e) + G_e_total_tree_weight
+ denominator = (
+ st_cached_value * nx.total_spanning_tree_weight(prepared_G)
+ + G_total_tree_weight
+ )
+ threshold = numerator / denominator
+ else:
+ threshold = 0.0
+ z = seed.uniform(0.0, 1.0)
+ if z > threshold:
+ # Remove the edge from V since we did not pick it.
+ V.remove((u, v))
+ else:
+ # Add the edge to U since we picked it.
+ st_cached_value += e_weight
+ U.add((u, v))
+ # If we decide to keep an edge, it may complete the spanning tree.
+ if len(U) == G.number_of_nodes() - 1:
+ spanning_tree = nx.Graph()
+ spanning_tree.add_edges_from(U)
+ return spanning_tree
+ raise Exception(f"Something went wrong! Only {len(U)} edges in the spanning tree!")
+
+
+class SpanningTreeIterator:
+ """
+ Iterate over all spanning trees of a graph in either increasing or
+ decreasing cost.
+
+ Notes
+ -----
+ This iterator uses the partition scheme from [1]_ (included edges,
+ excluded edges and open edges) as well as a modified Kruskal's Algorithm
+ to generate minimum spanning trees which respect the partition of edges.
+ For spanning trees with the same weight, ties are broken arbitrarily.
+
+ References
+ ----------
+ .. [1] G.K. Janssens, K. Sörensen, An algorithm to generate all spanning
+ trees in order of increasing cost, Pesquisa Operacional, 2005-08,
+ Vol. 25 (2), p. 219-229,
+ https://www.scielo.br/j/pope/a/XHswBwRwJyrfL88dmMwYNWp/?lang=en
+ """
+
+ @dataclass(order=True)
+ class Partition:
+ """
+ This dataclass represents a partition and stores a dict with the edge
+ data and the weight of the minimum spanning tree of the partition dict.
+ """
+
+ mst_weight: float
+ partition_dict: dict = field(compare=False)
+
+ def __copy__(self):
+ return SpanningTreeIterator.Partition(
+ self.mst_weight, self.partition_dict.copy()
+ )
+
+ def __init__(self, G, weight="weight", minimum=True, ignore_nan=False):
+ """
+ Initialize the iterator
+
+ Parameters
+ ----------
+ G : nx.Graph
+ The directed graph which we need to iterate trees over
+
+ weight : String, default = "weight"
+ The edge attribute used to store the weight of the edge
+
+ minimum : bool, default = True
+ Return the trees in increasing order while true and decreasing order
+ while false.
+
+ 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.
+ """
+ self.G = G.copy()
+ self.G.__networkx_cache__ = None # Disable caching
+ self.weight = weight
+ self.minimum = minimum
+ self.ignore_nan = ignore_nan
+ # Randomly create a key for an edge attribute to hold the partition data
+ self.partition_key = (
+ "SpanningTreeIterators super secret partition attribute name"
+ )
+
+ def __iter__(self):
+ """
+ Returns
+ -------
+ SpanningTreeIterator
+ The iterator object for this graph
+ """
+ self.partition_queue = PriorityQueue()
+ self._clear_partition(self.G)
+ mst_weight = partition_spanning_tree(
+ self.G, self.minimum, self.weight, self.partition_key, self.ignore_nan
+ ).size(weight=self.weight)
+
+ self.partition_queue.put(
+ self.Partition(mst_weight if self.minimum else -mst_weight, {})
+ )
+
+ return self
+
+ def __next__(self):
+ """
+ Returns
+ -------
+ (multi)Graph
+ The spanning tree of next greatest weight, which ties broken
+ arbitrarily.
+ """
+ if self.partition_queue.empty():
+ del self.G, self.partition_queue
+ raise StopIteration
+
+ partition = self.partition_queue.get()
+ self._write_partition(partition)
+ next_tree = partition_spanning_tree(
+ self.G, self.minimum, self.weight, self.partition_key, self.ignore_nan
+ )
+ self._partition(partition, next_tree)
+
+ self._clear_partition(next_tree)
+ return next_tree
+
+ def _partition(self, partition, partition_tree):
+ """
+ Create new partitions based of the minimum spanning tree of the
+ current minimum partition.
+
+ Parameters
+ ----------
+ partition : Partition
+ The Partition instance used to generate the current minimum spanning
+ tree.
+ partition_tree : nx.Graph
+ The minimum spanning tree of the input partition.
+ """
+ # create two new partitions with the data from the input partition dict
+ p1 = self.Partition(0, partition.partition_dict.copy())
+ p2 = self.Partition(0, partition.partition_dict.copy())
+ for e in partition_tree.edges:
+ # determine if the edge was open or included
+ if e not in partition.partition_dict:
+ # This is an open edge
+ p1.partition_dict[e] = EdgePartition.EXCLUDED
+ p2.partition_dict[e] = EdgePartition.INCLUDED
+
+ self._write_partition(p1)
+ p1_mst = partition_spanning_tree(
+ self.G,
+ self.minimum,
+ self.weight,
+ self.partition_key,
+ self.ignore_nan,
+ )
+ p1_mst_weight = p1_mst.size(weight=self.weight)
+ if nx.is_connected(p1_mst):
+ p1.mst_weight = p1_mst_weight if self.minimum else -p1_mst_weight
+ self.partition_queue.put(p1.__copy__())
+ p1.partition_dict = p2.partition_dict.copy()
+
+ def _write_partition(self, partition):
+ """
+ Writes the desired partition into the graph to calculate the minimum
+ spanning tree.
+
+ Parameters
+ ----------
+ partition : Partition
+ A Partition dataclass describing a partition on the edges of the
+ graph.
+ """
+
+ partition_dict = partition.partition_dict
+ partition_key = self.partition_key
+ G = self.G
+
+ edges = (
+ G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
+ )
+ for *e, d in edges:
+ d[partition_key] = partition_dict.get(tuple(e), EdgePartition.OPEN)
+
+ def _clear_partition(self, G):
+ """
+ Removes partition data from the graph
+ """
+ partition_key = self.partition_key
+ edges = (
+ G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
+ )
+ for *e, d in edges:
+ if partition_key in d:
+ del d[partition_key]
+
+
+@nx._dispatchable(edge_attrs="weight")
+def number_of_spanning_trees(G, *, root=None, weight=None):
+ """Returns the number of spanning trees in `G`.
+
+ A spanning tree for an undirected graph is a tree that connects
+ all nodes in the graph. For a directed graph, the analog of a
+ spanning tree is called a (spanning) arborescence. The arborescence
+ includes a unique directed path from the `root` node to each other node.
+ The graph must be weakly connected, and the root must be a node
+ that includes all nodes as successors [3]_. Note that to avoid
+ discussing sink-roots and reverse-arborescences, we have reversed
+ the edge orientation from [3]_ and use the in-degree laplacian.
+
+ This function (when `weight` is `None`) returns the number of
+ spanning trees for an undirected graph and the number of
+ arborescences from a single root node for a directed graph.
+ When `weight` is the name of an edge attribute which holds the
+ weight value of each edge, the function returns the sum over
+ all trees of the multiplicative weight of each tree. That is,
+ the weight of the tree is the product of its edge weights.
+
+ Kirchoff's Tree Matrix Theorem states that any cofactor of the
+ Laplacian matrix of a graph is the number of spanning trees in the
+ graph. (Here we use cofactors for a diagonal entry so that the
+ cofactor becomes the determinant of the matrix with one row
+ and its matching column removed.) For a weighted Laplacian matrix,
+ the cofactor is the sum across all spanning trees of the
+ multiplicative weight of each tree. That is, the weight of each
+ tree is the product of its edge weights. The theorem is also
+ known as Kirchhoff's theorem [1]_ and the Matrix-Tree theorem [2]_.
+
+ For directed graphs, a similar theorem (Tutte's Theorem) holds with
+ the cofactor chosen to be the one with row and column removed that
+ correspond to the root. The cofactor is the number of arborescences
+ with the specified node as root. And the weighted version gives the
+ sum of the arborescence weights with root `root`. The arborescence
+ weight is the product of its edge weights.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+
+ root : node
+ A node in the directed graph `G` that has all nodes as descendants.
+ (This is ignored for undirected graphs.)
+
+ weight : string or None, optional (default=None)
+ The name of the edge attribute holding the edge weight.
+ If `None`, then each edge is assumed to have a weight of 1.
+
+ Returns
+ -------
+ Number
+ Undirected graphs:
+ The number of spanning trees of the graph `G`.
+ Or the sum of all spanning tree weights of the graph `G`
+ where the weight of a tree is the product of its edge weights.
+ Directed graphs:
+ The number of arborescences of `G` rooted at node `root`.
+ Or the sum of all arborescence weights of the graph `G` with
+ specified root where the weight of an arborescence is the product
+ of its edge weights.
+
+ Raises
+ ------
+ NetworkXPointlessConcept
+ If `G` does not contain any nodes.
+
+ NetworkXError
+ If the graph `G` is directed and the root node
+ is not specified or is not in G.
+
+ Examples
+ --------
+ >>> G = nx.complete_graph(5)
+ >>> round(nx.number_of_spanning_trees(G))
+ 125
+
+ >>> G = nx.Graph()
+ >>> G.add_edge(1, 2, weight=2)
+ >>> G.add_edge(1, 3, weight=1)
+ >>> G.add_edge(2, 3, weight=1)
+ >>> round(nx.number_of_spanning_trees(G, weight="weight"))
+ 5
+
+ Notes
+ -----
+ Self-loops are excluded. Multi-edges are contracted in one edge
+ equal to the sum of the weights.
+
+ References
+ ----------
+ .. [1] Wikipedia
+ "Kirchhoff's theorem."
+ https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem
+ .. [2] Kirchhoff, G. R.
+ Über die Auflösung der Gleichungen, auf welche man
+ bei der Untersuchung der linearen Vertheilung
+ Galvanischer Ströme geführt wird
+ Annalen der Physik und Chemie, vol. 72, pp. 497-508, 1847.
+ .. [3] Margoliash, J.
+ "Matrix-Tree Theorem for Directed Graphs"
+ https://www.math.uchicago.edu/~may/VIGRE/VIGRE2010/REUPapers/Margoliash.pdf
+ """
+ import numpy as np
+
+ if len(G) == 0:
+ raise nx.NetworkXPointlessConcept("Graph G must contain at least one node.")
+
+ # undirected G
+ if not nx.is_directed(G):
+ if not nx.is_connected(G):
+ return 0
+ G_laplacian = nx.laplacian_matrix(G, weight=weight).toarray()
+ return float(np.linalg.det(G_laplacian[1:, 1:]))
+
+ # directed G
+ if root is None:
+ raise nx.NetworkXError("Input `root` must be provided when G is directed")
+ if root not in G:
+ raise nx.NetworkXError("The node root is not in the graph G.")
+ if not nx.is_weakly_connected(G):
+ return 0
+
+ # Compute directed Laplacian matrix
+ nodelist = [root] + [n for n in G if n != root]
+ A = nx.adjacency_matrix(G, nodelist=nodelist, weight=weight)
+ D = np.diag(A.sum(axis=0))
+ G_laplacian = D - A
+
+ # Compute number of spanning trees
+ return float(np.linalg.det(G_laplacian[1:, 1:]))
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/operations.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/operations.py
new file mode 100644
index 00000000..6c3e8394
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/operations.py
@@ -0,0 +1,105 @@
+"""Operations on trees."""
+
+from functools import partial
+from itertools import accumulate, chain
+
+import networkx as nx
+
+__all__ = ["join_trees"]
+
+
+# Argument types don't match dispatching, but allow manual selection of backend
+@nx._dispatchable(graphs=None, returns_graph=True)
+def join_trees(rooted_trees, *, label_attribute=None, first_label=0):
+ """Returns a new rooted tree made by joining `rooted_trees`
+
+ Constructs a new tree by joining each tree in `rooted_trees`.
+ A new root node is added and connected to each of the roots
+ of the input trees. While copying the nodes from the trees,
+ relabeling to integers occurs. If the `label_attribute` is provided,
+ the old node labels will be stored in the new tree under this attribute.
+
+ Parameters
+ ----------
+ rooted_trees : list
+ A list of pairs in which each left element is a NetworkX graph
+ object representing a tree and each right element is the root
+ node of that tree. The nodes of these trees will be relabeled to
+ integers.
+
+ label_attribute : str
+ If provided, the old node labels will be stored in the new tree
+ under this node attribute. If not provided, the original labels
+ of the nodes in the input trees are not stored.
+
+ first_label : int, optional (default=0)
+ Specifies the label for the new root node. If provided, the root node of the joined tree
+ will have this label. If not provided, the root node will default to a label of 0.
+
+ Returns
+ -------
+ NetworkX graph
+ The rooted tree resulting from joining the provided `rooted_trees`. The new tree has a root node
+ labeled as specified by `first_label` (defaulting to 0 if not provided). Subtrees from the input
+ `rooted_trees` are attached to this new root node. Each non-root node, if the `label_attribute`
+ is provided, has an attribute that indicates the original label of the node in the input tree.
+
+ Notes
+ -----
+ Trees are stored in NetworkX as NetworkX Graphs. There is no specific
+ enforcement of the fact that these are trees. Testing for each tree
+ can be done using :func:`networkx.is_tree`.
+
+ Graph, edge, and node attributes are propagated from the given
+ rooted trees to the created tree. If there are any overlapping graph
+ attributes, those from later trees will overwrite those from earlier
+ trees in the tuple of positional arguments.
+
+ Examples
+ --------
+ Join two full balanced binary trees of height *h* to get a full
+ balanced binary tree of depth *h* + 1::
+
+ >>> h = 4
+ >>> left = nx.balanced_tree(2, h)
+ >>> right = nx.balanced_tree(2, h)
+ >>> joined_tree = nx.join_trees([(left, 0), (right, 0)])
+ >>> nx.is_isomorphic(joined_tree, nx.balanced_tree(2, h + 1))
+ True
+
+ """
+ if not rooted_trees:
+ return nx.empty_graph(1)
+
+ # Unzip the zipped list of (tree, root) pairs.
+ trees, roots = zip(*rooted_trees)
+
+ # The join of the trees has the same type as the type of the first tree.
+ R = type(trees[0])()
+
+ lengths = (len(tree) for tree in trees[:-1])
+ first_labels = list(accumulate(lengths, initial=first_label + 1))
+
+ new_roots = []
+ for tree, root, first_node in zip(trees, roots, first_labels):
+ new_root = first_node + list(tree.nodes()).index(root)
+ new_roots.append(new_root)
+
+ # Relabel the nodes so that their union is the integers starting at first_label.
+ relabel = partial(
+ nx.convert_node_labels_to_integers, label_attribute=label_attribute
+ )
+ new_trees = [
+ relabel(tree, first_label=first_label)
+ for tree, first_label in zip(trees, first_labels)
+ ]
+
+ # Add all sets of nodes and edges, attributes
+ for tree in new_trees:
+ R.update(tree)
+
+ # Finally, join the subtrees at the root. We know first_label is unused by the way we relabeled the subtrees.
+ R.add_node(first_label)
+ R.add_edges_from((first_label, root) for root in new_roots)
+
+ return R
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/recognition.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/recognition.py
new file mode 100644
index 00000000..a9eae987
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/recognition.py
@@ -0,0 +1,273 @@
+"""
+Recognition Tests
+=================
+
+A *forest* is an acyclic, undirected graph, and a *tree* is a connected forest.
+Depending on the subfield, there are various conventions for generalizing these
+definitions to directed graphs.
+
+In one convention, directed variants of forest and tree are defined in an
+identical manner, except that the direction of the edges is ignored. In effect,
+each directed edge is treated as a single undirected edge. Then, additional
+restrictions are imposed to define *branchings* and *arborescences*.
+
+In another convention, directed variants of forest and tree correspond to
+the previous convention's branchings and arborescences, respectively. Then two
+new terms, *polyforest* and *polytree*, are defined to correspond to the other
+convention's forest and tree.
+
+Summarizing::
+
+ +-----------------------------+
+ | Convention A | Convention B |
+ +=============================+
+ | forest | polyforest |
+ | tree | polytree |
+ | branching | forest |
+ | arborescence | tree |
+ +-----------------------------+
+
+Each convention has its reasons. The first convention emphasizes definitional
+similarity in that directed forests and trees are only concerned with
+acyclicity and do not have an in-degree constraint, just as their undirected
+counterparts do not. The second convention emphasizes functional similarity
+in the sense that the directed analog of a spanning tree is a spanning
+arborescence. That is, take any spanning tree and choose one node as the root.
+Then every edge is assigned a direction such there is a directed path from the
+root to every other node. The result is a spanning arborescence.
+
+NetworkX follows convention "A". Explicitly, these are:
+
+undirected forest
+ An undirected graph with no undirected cycles.
+
+undirected tree
+ A connected, undirected forest.
+
+directed forest
+ A directed graph with no undirected cycles. Equivalently, the underlying
+ graph structure (which ignores edge orientations) is an undirected forest.
+ In convention B, this is known as a polyforest.
+
+directed tree
+ A weakly connected, directed forest. Equivalently, the underlying graph
+ structure (which ignores edge orientations) is an undirected tree. In
+ convention B, this is known as a polytree.
+
+branching
+ A directed forest with each node having, at most, one parent. So the maximum
+ in-degree is equal to 1. In convention B, this is known as a forest.
+
+arborescence
+ A directed tree with each node having, at most, one parent. So the maximum
+ in-degree is equal to 1. In convention B, this is known as a tree.
+
+For trees and arborescences, the adjective "spanning" may be added to designate
+that the graph, when considered as a forest/branching, consists of a single
+tree/arborescence that includes all nodes in the graph. It is true, by
+definition, that every tree/arborescence is spanning with respect to the nodes
+that define the tree/arborescence and so, it might seem redundant to introduce
+the notion of "spanning". However, the nodes may represent a subset of
+nodes from a larger graph, and it is in this context that the term "spanning"
+becomes a useful notion.
+
+"""
+
+import networkx as nx
+
+__all__ = ["is_arborescence", "is_branching", "is_forest", "is_tree"]
+
+
+@nx.utils.not_implemented_for("undirected")
+@nx._dispatchable
+def is_arborescence(G):
+ """
+ Returns True if `G` is an arborescence.
+
+ An arborescence is a directed tree with maximum in-degree equal to 1.
+
+ Parameters
+ ----------
+ G : graph
+ The graph to test.
+
+ Returns
+ -------
+ b : bool
+ A boolean that is True if `G` is an arborescence.
+
+ Examples
+ --------
+ >>> G = nx.DiGraph([(0, 1), (0, 2), (2, 3), (3, 4)])
+ >>> nx.is_arborescence(G)
+ True
+ >>> G.remove_edge(0, 1)
+ >>> G.add_edge(1, 2) # maximum in-degree is 2
+ >>> nx.is_arborescence(G)
+ False
+
+ Notes
+ -----
+ In another convention, an arborescence is known as a *tree*.
+
+ See Also
+ --------
+ is_tree
+
+ """
+ return is_tree(G) and max(d for n, d in G.in_degree()) <= 1
+
+
+@nx.utils.not_implemented_for("undirected")
+@nx._dispatchable
+def is_branching(G):
+ """
+ Returns True if `G` is a branching.
+
+ A branching is a directed forest with maximum in-degree equal to 1.
+
+ Parameters
+ ----------
+ G : directed graph
+ The directed graph to test.
+
+ Returns
+ -------
+ b : bool
+ A boolean that is True if `G` is a branching.
+
+ Examples
+ --------
+ >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4)])
+ >>> nx.is_branching(G)
+ True
+ >>> G.remove_edge(2, 3)
+ >>> G.add_edge(3, 1) # maximum in-degree is 2
+ >>> nx.is_branching(G)
+ False
+
+ Notes
+ -----
+ In another convention, a branching is also known as a *forest*.
+
+ See Also
+ --------
+ is_forest
+
+ """
+ return is_forest(G) and max(d for n, d in G.in_degree()) <= 1
+
+
+@nx._dispatchable
+def is_forest(G):
+ """
+ Returns True if `G` is a forest.
+
+ A forest is a graph with no undirected cycles.
+
+ For directed graphs, `G` is a forest if the underlying graph is a forest.
+ The underlying graph is obtained by treating each directed edge as a single
+ undirected edge in a multigraph.
+
+ Parameters
+ ----------
+ G : graph
+ The graph to test.
+
+ Returns
+ -------
+ b : bool
+ A boolean that is True if `G` is a forest.
+
+ Raises
+ ------
+ NetworkXPointlessConcept
+ If `G` is empty.
+
+ Examples
+ --------
+ >>> G = nx.Graph()
+ >>> G.add_edges_from([(1, 2), (1, 3), (2, 4), (2, 5)])
+ >>> nx.is_forest(G)
+ True
+ >>> G.add_edge(4, 1)
+ >>> nx.is_forest(G)
+ False
+
+ Notes
+ -----
+ In another convention, a directed forest is known as a *polyforest* and
+ then *forest* corresponds to a *branching*.
+
+ See Also
+ --------
+ is_branching
+
+ """
+ if len(G) == 0:
+ raise nx.exception.NetworkXPointlessConcept("G has no nodes.")
+
+ if G.is_directed():
+ components = (G.subgraph(c) for c in nx.weakly_connected_components(G))
+ else:
+ components = (G.subgraph(c) for c in nx.connected_components(G))
+
+ return all(len(c) - 1 == c.number_of_edges() for c in components)
+
+
+@nx._dispatchable
+def is_tree(G):
+ """
+ Returns True if `G` is a tree.
+
+ A tree is a connected graph with no undirected cycles.
+
+ For directed graphs, `G` is a tree if the underlying graph is a tree. The
+ underlying graph is obtained by treating each directed edge as a single
+ undirected edge in a multigraph.
+
+ Parameters
+ ----------
+ G : graph
+ The graph to test.
+
+ Returns
+ -------
+ b : bool
+ A boolean that is True if `G` is a tree.
+
+ Raises
+ ------
+ NetworkXPointlessConcept
+ If `G` is empty.
+
+ Examples
+ --------
+ >>> G = nx.Graph()
+ >>> G.add_edges_from([(1, 2), (1, 3), (2, 4), (2, 5)])
+ >>> nx.is_tree(G) # n-1 edges
+ True
+ >>> G.add_edge(3, 4)
+ >>> nx.is_tree(G) # n edges
+ False
+
+ Notes
+ -----
+ In another convention, a directed tree is known as a *polytree* and then
+ *tree* corresponds to an *arborescence*.
+
+ See Also
+ --------
+ is_arborescence
+
+ """
+ if len(G) == 0:
+ raise nx.exception.NetworkXPointlessConcept("G has no nodes.")
+
+ if G.is_directed():
+ is_connected = nx.is_weakly_connected
+ else:
+ is_connected = nx.is_connected
+
+ # A connected graph with no cycles has n-1 edges.
+ return len(G) - 1 == G.number_of_edges() and is_connected(G)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/__init__.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/__init__.py
new file mode 100644
index 00000000..e69de29b
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/__init__.py
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_branchings.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_branchings.py
new file mode 100644
index 00000000..e19ddee3
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_branchings.py
@@ -0,0 +1,624 @@
+import math
+from operator import itemgetter
+
+import pytest
+
+np = pytest.importorskip("numpy")
+
+import networkx as nx
+from networkx.algorithms.tree import branchings, recognition
+
+#
+# Explicitly discussed examples from Edmonds paper.
+#
+
+# Used in Figures A-F.
+#
+# fmt: off
+G_array = np.array([
+ # 0 1 2 3 4 5 6 7 8
+ [0, 0, 12, 0, 12, 0, 0, 0, 0], # 0
+ [4, 0, 0, 0, 0, 13, 0, 0, 0], # 1
+ [0, 17, 0, 21, 0, 12, 0, 0, 0], # 2
+ [5, 0, 0, 0, 17, 0, 18, 0, 0], # 3
+ [0, 0, 0, 0, 0, 0, 0, 12, 0], # 4
+ [0, 0, 0, 0, 0, 0, 14, 0, 12], # 5
+ [0, 0, 21, 0, 0, 0, 0, 0, 15], # 6
+ [0, 0, 0, 19, 0, 0, 15, 0, 0], # 7
+ [0, 0, 0, 0, 0, 0, 0, 18, 0], # 8
+], dtype=int)
+
+# Two copies of the graph from the original paper as disconnected components
+G_big_array = np.zeros(np.array(G_array.shape) * 2, dtype=int)
+G_big_array[:G_array.shape[0], :G_array.shape[1]] = G_array
+G_big_array[G_array.shape[0]:, G_array.shape[1]:] = G_array
+
+# fmt: on
+
+
+def G1():
+ G = nx.from_numpy_array(G_array, create_using=nx.MultiDiGraph)
+ return G
+
+
+def G2():
+ # Now we shift all the weights by -10.
+ # Should not affect optimal arborescence, but does affect optimal branching.
+ Garr = G_array.copy()
+ Garr[np.nonzero(Garr)] -= 10
+ G = nx.from_numpy_array(Garr, create_using=nx.MultiDiGraph)
+ return G
+
+
+# An optimal branching for G1 that is also a spanning arborescence. So it is
+# also an optimal spanning arborescence.
+#
+optimal_arborescence_1 = [
+ (0, 2, 12),
+ (2, 1, 17),
+ (2, 3, 21),
+ (1, 5, 13),
+ (3, 4, 17),
+ (3, 6, 18),
+ (6, 8, 15),
+ (8, 7, 18),
+]
+
+# For G2, the optimal branching of G1 (with shifted weights) is no longer
+# an optimal branching, but it is still an optimal spanning arborescence
+# (just with shifted weights). An optimal branching for G2 is similar to what
+# appears in figure G (this is greedy_subopt_branching_1a below), but with the
+# edge (3, 0, 5), which is now (3, 0, -5), removed. Thus, the optimal branching
+# is not a spanning arborescence. The code finds optimal_branching_2a.
+# An alternative and equivalent branching is optimal_branching_2b. We would
+# need to modify the code to iterate through all equivalent optimal branchings.
+#
+# These are maximal branchings or arborescences.
+optimal_branching_2a = [
+ (5, 6, 4),
+ (6, 2, 11),
+ (6, 8, 5),
+ (8, 7, 8),
+ (2, 1, 7),
+ (2, 3, 11),
+ (3, 4, 7),
+]
+optimal_branching_2b = [
+ (8, 7, 8),
+ (7, 3, 9),
+ (3, 4, 7),
+ (3, 6, 8),
+ (6, 2, 11),
+ (2, 1, 7),
+ (1, 5, 3),
+]
+optimal_arborescence_2 = [
+ (0, 2, 2),
+ (2, 1, 7),
+ (2, 3, 11),
+ (1, 5, 3),
+ (3, 4, 7),
+ (3, 6, 8),
+ (6, 8, 5),
+ (8, 7, 8),
+]
+
+# Two suboptimal maximal branchings on G1 obtained from a greedy algorithm.
+# 1a matches what is shown in Figure G in Edmonds's paper.
+greedy_subopt_branching_1a = [
+ (5, 6, 14),
+ (6, 2, 21),
+ (6, 8, 15),
+ (8, 7, 18),
+ (2, 1, 17),
+ (2, 3, 21),
+ (3, 0, 5),
+ (3, 4, 17),
+]
+greedy_subopt_branching_1b = [
+ (8, 7, 18),
+ (7, 6, 15),
+ (6, 2, 21),
+ (2, 1, 17),
+ (2, 3, 21),
+ (1, 5, 13),
+ (3, 0, 5),
+ (3, 4, 17),
+]
+
+
+def build_branching(edges, double=False):
+ G = nx.DiGraph()
+ for u, v, weight in edges:
+ G.add_edge(u, v, weight=weight)
+ if double:
+ G.add_edge(u + 9, v + 9, weight=weight)
+ return G
+
+
+def sorted_edges(G, attr="weight", default=1):
+ edges = [(u, v, data.get(attr, default)) for (u, v, data) in G.edges(data=True)]
+ edges = sorted(edges, key=lambda x: (x[2], x[1], x[0]))
+ return edges
+
+
+def assert_equal_branchings(G1, G2, attr="weight", default=1):
+ edges1 = list(G1.edges(data=True))
+ edges2 = list(G2.edges(data=True))
+ assert len(edges1) == len(edges2)
+
+ # Grab the weights only.
+ e1 = sorted_edges(G1, attr, default)
+ e2 = sorted_edges(G2, attr, default)
+
+ for a, b in zip(e1, e2):
+ assert a[:2] == b[:2]
+ np.testing.assert_almost_equal(a[2], b[2])
+
+
+################
+
+
+def test_optimal_branching1():
+ G = build_branching(optimal_arborescence_1)
+ assert recognition.is_arborescence(G), True
+ assert branchings.branching_weight(G) == 131
+
+
+def test_optimal_branching2a():
+ G = build_branching(optimal_branching_2a)
+ assert recognition.is_arborescence(G), True
+ assert branchings.branching_weight(G) == 53
+
+
+def test_optimal_branching2b():
+ G = build_branching(optimal_branching_2b)
+ assert recognition.is_arborescence(G), True
+ assert branchings.branching_weight(G) == 53
+
+
+def test_optimal_arborescence2():
+ G = build_branching(optimal_arborescence_2)
+ assert recognition.is_arborescence(G), True
+ assert branchings.branching_weight(G) == 51
+
+
+def test_greedy_suboptimal_branching1a():
+ G = build_branching(greedy_subopt_branching_1a)
+ assert recognition.is_arborescence(G), True
+ assert branchings.branching_weight(G) == 128
+
+
+def test_greedy_suboptimal_branching1b():
+ G = build_branching(greedy_subopt_branching_1b)
+ assert recognition.is_arborescence(G), True
+ assert branchings.branching_weight(G) == 127
+
+
+def test_greedy_max1():
+ # Standard test.
+ #
+ G = G1()
+ B = branchings.greedy_branching(G)
+ # There are only two possible greedy branchings. The sorting is such
+ # that it should equal the second suboptimal branching: 1b.
+ B_ = build_branching(greedy_subopt_branching_1b)
+ assert_equal_branchings(B, B_)
+
+
+def test_greedy_branching_kwarg_kind():
+ G = G1()
+ with pytest.raises(nx.NetworkXException, match="Unknown value for `kind`."):
+ B = branchings.greedy_branching(G, kind="lol")
+
+
+def test_greedy_branching_for_unsortable_nodes():
+ G = nx.DiGraph()
+ G.add_weighted_edges_from([((2, 3), 5, 1), (3, "a", 1), (2, 4, 5)])
+ edges = [(u, v, data.get("weight", 1)) for (u, v, data) in G.edges(data=True)]
+ with pytest.raises(TypeError):
+ edges.sort(key=itemgetter(2, 0, 1), reverse=True)
+ B = branchings.greedy_branching(G, kind="max").edges(data=True)
+ assert list(B) == [
+ ((2, 3), 5, {"weight": 1}),
+ (3, "a", {"weight": 1}),
+ (2, 4, {"weight": 5}),
+ ]
+
+
+def test_greedy_max2():
+ # Different default weight.
+ #
+ G = G1()
+ del G[1][0][0]["weight"]
+ B = branchings.greedy_branching(G, default=6)
+ # Chosen so that edge (3,0,5) is not selected and (1,0,6) is instead.
+
+ edges = [
+ (1, 0, 6),
+ (1, 5, 13),
+ (7, 6, 15),
+ (2, 1, 17),
+ (3, 4, 17),
+ (8, 7, 18),
+ (2, 3, 21),
+ (6, 2, 21),
+ ]
+ B_ = build_branching(edges)
+ assert_equal_branchings(B, B_)
+
+
+def test_greedy_max3():
+ # All equal weights.
+ #
+ G = G1()
+ B = branchings.greedy_branching(G, attr=None)
+
+ # This is mostly arbitrary...the output was generated by running the algo.
+ edges = [
+ (2, 1, 1),
+ (3, 0, 1),
+ (3, 4, 1),
+ (5, 8, 1),
+ (6, 2, 1),
+ (7, 3, 1),
+ (7, 6, 1),
+ (8, 7, 1),
+ ]
+ B_ = build_branching(edges)
+ assert_equal_branchings(B, B_, default=1)
+
+
+def test_greedy_min():
+ G = G1()
+ B = branchings.greedy_branching(G, kind="min")
+
+ edges = [
+ (1, 0, 4),
+ (0, 2, 12),
+ (0, 4, 12),
+ (2, 5, 12),
+ (4, 7, 12),
+ (5, 8, 12),
+ (5, 6, 14),
+ (7, 3, 19),
+ ]
+ B_ = build_branching(edges)
+ assert_equal_branchings(B, B_)
+
+
+def test_edmonds1_maxbranch():
+ G = G1()
+ x = branchings.maximum_branching(G)
+ x_ = build_branching(optimal_arborescence_1)
+ assert_equal_branchings(x, x_)
+
+
+def test_edmonds1_maxarbor():
+ G = G1()
+ x = branchings.maximum_spanning_arborescence(G)
+ x_ = build_branching(optimal_arborescence_1)
+ assert_equal_branchings(x, x_)
+
+
+def test_edmonds1_minimal_branching():
+ # graph will have something like a minimum arborescence but no spanning one
+ G = nx.from_numpy_array(G_big_array, create_using=nx.DiGraph)
+ B = branchings.minimal_branching(G)
+ edges = [
+ (3, 0, 5),
+ (0, 2, 12),
+ (0, 4, 12),
+ (2, 5, 12),
+ (4, 7, 12),
+ (5, 8, 12),
+ (5, 6, 14),
+ (2, 1, 17),
+ ]
+ B_ = build_branching(edges, double=True)
+ assert_equal_branchings(B, B_)
+
+
+def test_edmonds2_maxbranch():
+ G = G2()
+ x = branchings.maximum_branching(G)
+ x_ = build_branching(optimal_branching_2a)
+ assert_equal_branchings(x, x_)
+
+
+def test_edmonds2_maxarbor():
+ G = G2()
+ x = branchings.maximum_spanning_arborescence(G)
+ x_ = build_branching(optimal_arborescence_2)
+ assert_equal_branchings(x, x_)
+
+
+def test_edmonds2_minarbor():
+ G = G1()
+ x = branchings.minimum_spanning_arborescence(G)
+ # This was obtained from algorithm. Need to verify it independently.
+ # Branch weight is: 96
+ edges = [
+ (3, 0, 5),
+ (0, 2, 12),
+ (0, 4, 12),
+ (2, 5, 12),
+ (4, 7, 12),
+ (5, 8, 12),
+ (5, 6, 14),
+ (2, 1, 17),
+ ]
+ x_ = build_branching(edges)
+ assert_equal_branchings(x, x_)
+
+
+def test_edmonds3_minbranch1():
+ G = G1()
+ x = branchings.minimum_branching(G)
+ edges = []
+ x_ = build_branching(edges)
+ assert_equal_branchings(x, x_)
+
+
+def test_edmonds3_minbranch2():
+ G = G1()
+ G.add_edge(8, 9, weight=-10)
+ x = branchings.minimum_branching(G)
+ edges = [(8, 9, -10)]
+ x_ = build_branching(edges)
+ assert_equal_branchings(x, x_)
+
+
+# Need more tests
+
+
+def test_mst():
+ # Make sure we get the same results for undirected graphs.
+ # Example from: https://en.wikipedia.org/wiki/Kruskal's_algorithm
+ G = nx.Graph()
+ edgelist = [
+ (0, 3, [("weight", 5)]),
+ (0, 1, [("weight", 7)]),
+ (1, 3, [("weight", 9)]),
+ (1, 2, [("weight", 8)]),
+ (1, 4, [("weight", 7)]),
+ (3, 4, [("weight", 15)]),
+ (3, 5, [("weight", 6)]),
+ (2, 4, [("weight", 5)]),
+ (4, 5, [("weight", 8)]),
+ (4, 6, [("weight", 9)]),
+ (5, 6, [("weight", 11)]),
+ ]
+ G.add_edges_from(edgelist)
+ G = G.to_directed()
+ x = branchings.minimum_spanning_arborescence(G)
+
+ edges = [
+ ({0, 1}, 7),
+ ({0, 3}, 5),
+ ({3, 5}, 6),
+ ({1, 4}, 7),
+ ({4, 2}, 5),
+ ({4, 6}, 9),
+ ]
+
+ assert x.number_of_edges() == len(edges)
+ for u, v, d in x.edges(data=True):
+ assert ({u, v}, d["weight"]) in edges
+
+
+def test_mixed_nodetypes():
+ # Smoke test to make sure no TypeError is raised for mixed node types.
+ G = nx.Graph()
+ edgelist = [(0, 3, [("weight", 5)]), (0, "1", [("weight", 5)])]
+ G.add_edges_from(edgelist)
+ G = G.to_directed()
+ x = branchings.minimum_spanning_arborescence(G)
+
+
+def test_edmonds1_minbranch():
+ # Using -G_array and min should give the same as optimal_arborescence_1,
+ # but with all edges negative.
+ edges = [(u, v, -w) for (u, v, w) in optimal_arborescence_1]
+
+ G = nx.from_numpy_array(-G_array, create_using=nx.DiGraph)
+
+ # Quickly make sure max branching is empty.
+ x = branchings.maximum_branching(G)
+ x_ = build_branching([])
+ assert_equal_branchings(x, x_)
+
+ # Now test the min branching.
+ x = branchings.minimum_branching(G)
+ x_ = build_branching(edges)
+ assert_equal_branchings(x, x_)
+
+
+def test_edge_attribute_preservation_normal_graph():
+ # Test that edge attributes are preserved when finding an optimum graph
+ # using the Edmonds class for normal graphs.
+ G = nx.Graph()
+
+ edgelist = [
+ (0, 1, [("weight", 5), ("otherattr", 1), ("otherattr2", 3)]),
+ (0, 2, [("weight", 5), ("otherattr", 2), ("otherattr2", 2)]),
+ (1, 2, [("weight", 6), ("otherattr", 3), ("otherattr2", 1)]),
+ ]
+ G.add_edges_from(edgelist)
+
+ B = branchings.maximum_branching(G, preserve_attrs=True)
+
+ assert B[0][1]["otherattr"] == 1
+ assert B[0][1]["otherattr2"] == 3
+
+
+def test_edge_attribute_preservation_multigraph():
+ # Test that edge attributes are preserved when finding an optimum graph
+ # using the Edmonds class for multigraphs.
+ G = nx.MultiGraph()
+
+ edgelist = [
+ (0, 1, [("weight", 5), ("otherattr", 1), ("otherattr2", 3)]),
+ (0, 2, [("weight", 5), ("otherattr", 2), ("otherattr2", 2)]),
+ (1, 2, [("weight", 6), ("otherattr", 3), ("otherattr2", 1)]),
+ ]
+ G.add_edges_from(edgelist * 2) # Make sure we have duplicate edge paths
+
+ B = branchings.maximum_branching(G, preserve_attrs=True)
+
+ assert B[0][1][0]["otherattr"] == 1
+ assert B[0][1][0]["otherattr2"] == 3
+
+
+def test_edge_attribute_discard():
+ # Test that edge attributes are discarded if we do not specify to keep them
+ G = nx.Graph()
+
+ edgelist = [
+ (0, 1, [("weight", 5), ("otherattr", 1), ("otherattr2", 3)]),
+ (0, 2, [("weight", 5), ("otherattr", 2), ("otherattr2", 2)]),
+ (1, 2, [("weight", 6), ("otherattr", 3), ("otherattr2", 1)]),
+ ]
+ G.add_edges_from(edgelist)
+
+ B = branchings.maximum_branching(G, preserve_attrs=False)
+
+ edge_dict = B[0][1]
+ with pytest.raises(KeyError):
+ _ = edge_dict["otherattr"]
+
+
+def test_partition_spanning_arborescence():
+ """
+ Test that we can generate minimum spanning arborescences which respect the
+ given partition.
+ """
+ G = nx.from_numpy_array(G_array, create_using=nx.DiGraph)
+ G[3][0]["partition"] = nx.EdgePartition.EXCLUDED
+ G[2][3]["partition"] = nx.EdgePartition.INCLUDED
+ G[7][3]["partition"] = nx.EdgePartition.EXCLUDED
+ G[0][2]["partition"] = nx.EdgePartition.EXCLUDED
+ G[6][2]["partition"] = nx.EdgePartition.INCLUDED
+
+ actual_edges = [
+ (0, 4, 12),
+ (1, 0, 4),
+ (1, 5, 13),
+ (2, 3, 21),
+ (4, 7, 12),
+ (5, 6, 14),
+ (5, 8, 12),
+ (6, 2, 21),
+ ]
+
+ B = branchings.minimum_spanning_arborescence(G, partition="partition")
+ assert_equal_branchings(build_branching(actual_edges), B)
+
+
+def test_arborescence_iterator_min():
+ """
+ Tests the arborescence iterator.
+
+ A brute force method found 680 arborescences in this graph.
+ This test will not verify all of them individually, but will check two
+ things
+
+ * The iterator returns 680 arborescences
+ * The weight of the arborescences is non-strictly increasing
+
+ for more information please visit
+ https://mjschwenne.github.io/2021/06/10/implementing-the-iterators.html
+ """
+ G = nx.from_numpy_array(G_array, create_using=nx.DiGraph)
+
+ arborescence_count = 0
+ arborescence_weight = -math.inf
+ for B in branchings.ArborescenceIterator(G):
+ arborescence_count += 1
+ new_arborescence_weight = B.size(weight="weight")
+ assert new_arborescence_weight >= arborescence_weight
+ arborescence_weight = new_arborescence_weight
+
+ assert arborescence_count == 680
+
+
+def test_arborescence_iterator_max():
+ """
+ Tests the arborescence iterator.
+
+ A brute force method found 680 arborescences in this graph.
+ This test will not verify all of them individually, but will check two
+ things
+
+ * The iterator returns 680 arborescences
+ * The weight of the arborescences is non-strictly decreasing
+
+ for more information please visit
+ https://mjschwenne.github.io/2021/06/10/implementing-the-iterators.html
+ """
+ G = nx.from_numpy_array(G_array, create_using=nx.DiGraph)
+
+ arborescence_count = 0
+ arborescence_weight = math.inf
+ for B in branchings.ArborescenceIterator(G, minimum=False):
+ arborescence_count += 1
+ new_arborescence_weight = B.size(weight="weight")
+ assert new_arborescence_weight <= arborescence_weight
+ arborescence_weight = new_arborescence_weight
+
+ assert arborescence_count == 680
+
+
+def test_arborescence_iterator_initial_partition():
+ """
+ Tests the arborescence iterator with three included edges and three excluded
+ in the initial partition.
+
+ A brute force method similar to the one used in the above tests found that
+ there are 16 arborescences which contain the included edges and not the
+ excluded edges.
+ """
+ G = nx.from_numpy_array(G_array, create_using=nx.DiGraph)
+ included_edges = [(1, 0), (5, 6), (8, 7)]
+ excluded_edges = [(0, 2), (3, 6), (1, 5)]
+
+ arborescence_count = 0
+ arborescence_weight = -math.inf
+ for B in branchings.ArborescenceIterator(
+ G, init_partition=(included_edges, excluded_edges)
+ ):
+ arborescence_count += 1
+ new_arborescence_weight = B.size(weight="weight")
+ assert new_arborescence_weight >= arborescence_weight
+ arborescence_weight = new_arborescence_weight
+ for e in included_edges:
+ assert e in B.edges
+ for e in excluded_edges:
+ assert e not in B.edges
+ assert arborescence_count == 16
+
+
+def test_branchings_with_default_weights():
+ """
+ Tests that various branching algorithms work on graphs without weights.
+ For more information, see issue #7279.
+ """
+ graph = nx.erdos_renyi_graph(10, p=0.2, directed=True, seed=123)
+
+ assert all(
+ "weight" not in d for (u, v, d) in graph.edges(data=True)
+ ), "test is for graphs without a weight attribute"
+
+ # Calling these functions will modify graph inplace to add weights
+ # copy the graph to avoid this.
+ nx.minimum_spanning_arborescence(graph.copy())
+ nx.maximum_spanning_arborescence(graph.copy())
+ nx.minimum_branching(graph.copy())
+ nx.maximum_branching(graph.copy())
+ nx.algorithms.tree.minimal_branching(graph.copy())
+ nx.algorithms.tree.branching_weight(graph.copy())
+ nx.algorithms.tree.greedy_branching(graph.copy())
+
+ assert all(
+ "weight" not in d for (u, v, d) in graph.edges(data=True)
+ ), "The above calls should not modify the initial graph in-place"
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_coding.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_coding.py
new file mode 100644
index 00000000..26bd4083
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_coding.py
@@ -0,0 +1,114 @@
+"""Unit tests for the :mod:`~networkx.algorithms.tree.coding` module."""
+
+from itertools import product
+
+import pytest
+
+import networkx as nx
+from networkx.utils import edges_equal, nodes_equal
+
+
+class TestPruferSequence:
+ """Unit tests for the Prüfer sequence encoding and decoding
+ functions.
+
+ """
+
+ def test_nontree(self):
+ with pytest.raises(nx.NotATree):
+ G = nx.cycle_graph(3)
+ nx.to_prufer_sequence(G)
+
+ def test_null_graph(self):
+ with pytest.raises(nx.NetworkXPointlessConcept):
+ nx.to_prufer_sequence(nx.null_graph())
+
+ def test_trivial_graph(self):
+ with pytest.raises(nx.NetworkXPointlessConcept):
+ nx.to_prufer_sequence(nx.trivial_graph())
+
+ def test_bad_integer_labels(self):
+ with pytest.raises(KeyError):
+ T = nx.Graph(nx.utils.pairwise("abc"))
+ nx.to_prufer_sequence(T)
+
+ def test_encoding(self):
+ """Tests for encoding a tree as a Prüfer sequence using the
+ iterative strategy.
+
+ """
+ # Example from Wikipedia.
+ tree = nx.Graph([(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)])
+ sequence = nx.to_prufer_sequence(tree)
+ assert sequence == [3, 3, 3, 4]
+
+ def test_decoding(self):
+ """Tests for decoding a tree from a Prüfer sequence."""
+ # Example from Wikipedia.
+ sequence = [3, 3, 3, 4]
+ tree = nx.from_prufer_sequence(sequence)
+ assert nodes_equal(list(tree), list(range(6)))
+ edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]
+ assert edges_equal(list(tree.edges()), edges)
+
+ def test_decoding2(self):
+ # Example from "An Optimal Algorithm for Prufer Codes".
+ sequence = [2, 4, 0, 1, 3, 3]
+ tree = nx.from_prufer_sequence(sequence)
+ assert nodes_equal(list(tree), list(range(8)))
+ edges = [(0, 1), (0, 4), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)]
+ assert edges_equal(list(tree.edges()), edges)
+
+ def test_inverse(self):
+ """Tests that the encoding and decoding functions are inverses."""
+ for T in nx.nonisomorphic_trees(4):
+ T2 = nx.from_prufer_sequence(nx.to_prufer_sequence(T))
+ assert nodes_equal(list(T), list(T2))
+ assert edges_equal(list(T.edges()), list(T2.edges()))
+
+ for seq in product(range(4), repeat=2):
+ seq2 = nx.to_prufer_sequence(nx.from_prufer_sequence(seq))
+ assert list(seq) == seq2
+
+
+class TestNestedTuple:
+ """Unit tests for the nested tuple encoding and decoding functions."""
+
+ def test_nontree(self):
+ with pytest.raises(nx.NotATree):
+ G = nx.cycle_graph(3)
+ nx.to_nested_tuple(G, 0)
+
+ def test_unknown_root(self):
+ with pytest.raises(nx.NodeNotFound):
+ G = nx.path_graph(2)
+ nx.to_nested_tuple(G, "bogus")
+
+ def test_encoding(self):
+ T = nx.full_rary_tree(2, 2**3 - 1)
+ expected = (((), ()), ((), ()))
+ actual = nx.to_nested_tuple(T, 0)
+ assert nodes_equal(expected, actual)
+
+ def test_canonical_form(self):
+ T = nx.Graph()
+ T.add_edges_from([(0, 1), (0, 2), (0, 3)])
+ T.add_edges_from([(1, 4), (1, 5)])
+ T.add_edges_from([(3, 6), (3, 7)])
+ root = 0
+ actual = nx.to_nested_tuple(T, root, canonical_form=True)
+ expected = ((), ((), ()), ((), ()))
+ assert actual == expected
+
+ def test_decoding(self):
+ balanced = (((), ()), ((), ()))
+ expected = nx.full_rary_tree(2, 2**3 - 1)
+ actual = nx.from_nested_tuple(balanced)
+ assert nx.is_isomorphic(expected, actual)
+
+ def test_sensible_relabeling(self):
+ balanced = (((), ()), ((), ()))
+ T = nx.from_nested_tuple(balanced, sensible_relabeling=True)
+ edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]
+ assert nodes_equal(list(T), list(range(2**3 - 1)))
+ assert edges_equal(list(T.edges()), edges)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_decomposition.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_decomposition.py
new file mode 100644
index 00000000..8c376053
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_decomposition.py
@@ -0,0 +1,79 @@
+import networkx as nx
+from networkx.algorithms.tree.decomposition import junction_tree
+
+
+def test_junction_tree_directed_confounders():
+ B = nx.DiGraph()
+ B.add_edges_from([("A", "C"), ("B", "C"), ("C", "D"), ("C", "E")])
+
+ G = junction_tree(B)
+ J = nx.Graph()
+ J.add_edges_from(
+ [
+ (("C", "E"), ("C",)),
+ (("C",), ("A", "B", "C")),
+ (("A", "B", "C"), ("C",)),
+ (("C",), ("C", "D")),
+ ]
+ )
+
+ assert nx.is_isomorphic(G, J)
+
+
+def test_junction_tree_directed_unconnected_nodes():
+ B = nx.DiGraph()
+ B.add_nodes_from([("A", "B", "C", "D")])
+ G = junction_tree(B)
+
+ J = nx.Graph()
+ J.add_nodes_from([("A", "B", "C", "D")])
+
+ assert nx.is_isomorphic(G, J)
+
+
+def test_junction_tree_directed_cascade():
+ B = nx.DiGraph()
+ B.add_edges_from([("A", "B"), ("B", "C"), ("C", "D")])
+ G = junction_tree(B)
+
+ J = nx.Graph()
+ J.add_edges_from(
+ [
+ (("A", "B"), ("B",)),
+ (("B",), ("B", "C")),
+ (("B", "C"), ("C",)),
+ (("C",), ("C", "D")),
+ ]
+ )
+ assert nx.is_isomorphic(G, J)
+
+
+def test_junction_tree_directed_unconnected_edges():
+ B = nx.DiGraph()
+ B.add_edges_from([("A", "B"), ("C", "D"), ("E", "F")])
+ G = junction_tree(B)
+
+ J = nx.Graph()
+ J.add_nodes_from([("A", "B"), ("C", "D"), ("E", "F")])
+
+ assert nx.is_isomorphic(G, J)
+
+
+def test_junction_tree_undirected():
+ B = nx.Graph()
+ B.add_edges_from([("A", "C"), ("A", "D"), ("B", "C"), ("C", "E")])
+ G = junction_tree(B)
+
+ J = nx.Graph()
+ J.add_edges_from(
+ [
+ (("A", "D"), ("A",)),
+ (("A",), ("A", "C")),
+ (("A", "C"), ("C",)),
+ (("C",), ("B", "C")),
+ (("B", "C"), ("C",)),
+ (("C",), ("C", "E")),
+ ]
+ )
+
+ assert nx.is_isomorphic(G, J)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_mst.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_mst.py
new file mode 100644
index 00000000..f8945a71
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_mst.py
@@ -0,0 +1,918 @@
+"""Unit tests for the :mod:`networkx.algorithms.tree.mst` module."""
+
+import pytest
+
+import networkx as nx
+from networkx.utils import edges_equal, nodes_equal
+
+
+def test_unknown_algorithm():
+ with pytest.raises(ValueError):
+ nx.minimum_spanning_tree(nx.Graph(), algorithm="random")
+ with pytest.raises(
+ ValueError, match="random is not a valid choice for an algorithm."
+ ):
+ nx.maximum_spanning_edges(nx.Graph(), algorithm="random")
+
+
+class MinimumSpanningTreeTestBase:
+ """Base class for test classes for minimum spanning tree algorithms.
+ This class contains some common tests that will be inherited by
+ subclasses. Each subclass must have a class attribute
+ :data:`algorithm` that is a string representing the algorithm to
+ run, as described under the ``algorithm`` keyword argument for the
+ :func:`networkx.minimum_spanning_edges` function. Subclasses can
+ then implement any algorithm-specific tests.
+ """
+
+ def setup_method(self, method):
+ """Creates an example graph and stores the expected minimum and
+ maximum spanning tree edges.
+ """
+ # This stores the class attribute `algorithm` in an instance attribute.
+ self.algo = self.algorithm
+ # This example graph comes from Wikipedia:
+ # https://en.wikipedia.org/wiki/Kruskal's_algorithm
+ edges = [
+ (0, 1, 7),
+ (0, 3, 5),
+ (1, 2, 8),
+ (1, 3, 9),
+ (1, 4, 7),
+ (2, 4, 5),
+ (3, 4, 15),
+ (3, 5, 6),
+ (4, 5, 8),
+ (4, 6, 9),
+ (5, 6, 11),
+ ]
+ self.G = nx.Graph()
+ self.G.add_weighted_edges_from(edges)
+ self.minimum_spanning_edgelist = [
+ (0, 1, {"weight": 7}),
+ (0, 3, {"weight": 5}),
+ (1, 4, {"weight": 7}),
+ (2, 4, {"weight": 5}),
+ (3, 5, {"weight": 6}),
+ (4, 6, {"weight": 9}),
+ ]
+ self.maximum_spanning_edgelist = [
+ (0, 1, {"weight": 7}),
+ (1, 2, {"weight": 8}),
+ (1, 3, {"weight": 9}),
+ (3, 4, {"weight": 15}),
+ (4, 6, {"weight": 9}),
+ (5, 6, {"weight": 11}),
+ ]
+
+ def test_minimum_edges(self):
+ edges = nx.minimum_spanning_edges(self.G, algorithm=self.algo)
+ # Edges from the spanning edges functions don't come in sorted
+ # orientation, so we need to sort each edge individually.
+ actual = sorted((min(u, v), max(u, v), d) for u, v, d in edges)
+ assert edges_equal(actual, self.minimum_spanning_edgelist)
+
+ def test_maximum_edges(self):
+ edges = nx.maximum_spanning_edges(self.G, algorithm=self.algo)
+ # Edges from the spanning edges functions don't come in sorted
+ # orientation, so we need to sort each edge individually.
+ actual = sorted((min(u, v), max(u, v), d) for u, v, d in edges)
+ assert edges_equal(actual, self.maximum_spanning_edgelist)
+
+ def test_without_data(self):
+ edges = nx.minimum_spanning_edges(self.G, algorithm=self.algo, data=False)
+ # Edges from the spanning edges functions don't come in sorted
+ # orientation, so we need to sort each edge individually.
+ actual = sorted((min(u, v), max(u, v)) for u, v in edges)
+ expected = [(u, v) for u, v, d in self.minimum_spanning_edgelist]
+ assert edges_equal(actual, expected)
+
+ def test_nan_weights(self):
+ # Edge weights NaN never appear in the spanning tree. see #2164
+ G = self.G
+ G.add_edge(0, 12, weight=float("nan"))
+ edges = nx.minimum_spanning_edges(
+ G, algorithm=self.algo, data=False, ignore_nan=True
+ )
+ actual = sorted((min(u, v), max(u, v)) for u, v in edges)
+ expected = [(u, v) for u, v, d in self.minimum_spanning_edgelist]
+ assert edges_equal(actual, expected)
+ # Now test for raising exception
+ edges = nx.minimum_spanning_edges(
+ G, algorithm=self.algo, data=False, ignore_nan=False
+ )
+ with pytest.raises(ValueError):
+ list(edges)
+ # test default for ignore_nan as False
+ edges = nx.minimum_spanning_edges(G, algorithm=self.algo, data=False)
+ with pytest.raises(ValueError):
+ list(edges)
+
+ def test_nan_weights_MultiGraph(self):
+ G = nx.MultiGraph()
+ G.add_edge(0, 12, weight=float("nan"))
+ edges = nx.minimum_spanning_edges(
+ G, algorithm="prim", data=False, ignore_nan=False
+ )
+ with pytest.raises(ValueError):
+ list(edges)
+ # test default for ignore_nan as False
+ edges = nx.minimum_spanning_edges(G, algorithm="prim", data=False)
+ with pytest.raises(ValueError):
+ list(edges)
+
+ def test_nan_weights_order(self):
+ # now try again with a nan edge at the beginning of G.nodes
+ edges = [
+ (0, 1, 7),
+ (0, 3, 5),
+ (1, 2, 8),
+ (1, 3, 9),
+ (1, 4, 7),
+ (2, 4, 5),
+ (3, 4, 15),
+ (3, 5, 6),
+ (4, 5, 8),
+ (4, 6, 9),
+ (5, 6, 11),
+ ]
+ G = nx.Graph()
+ G.add_weighted_edges_from([(u + 1, v + 1, wt) for u, v, wt in edges])
+ G.add_edge(0, 7, weight=float("nan"))
+ edges = nx.minimum_spanning_edges(
+ G, algorithm=self.algo, data=False, ignore_nan=True
+ )
+ actual = sorted((min(u, v), max(u, v)) for u, v in edges)
+ shift = [(u + 1, v + 1) for u, v, d in self.minimum_spanning_edgelist]
+ assert edges_equal(actual, shift)
+
+ def test_isolated_node(self):
+ # now try again with an isolated node
+ edges = [
+ (0, 1, 7),
+ (0, 3, 5),
+ (1, 2, 8),
+ (1, 3, 9),
+ (1, 4, 7),
+ (2, 4, 5),
+ (3, 4, 15),
+ (3, 5, 6),
+ (4, 5, 8),
+ (4, 6, 9),
+ (5, 6, 11),
+ ]
+ G = nx.Graph()
+ G.add_weighted_edges_from([(u + 1, v + 1, wt) for u, v, wt in edges])
+ G.add_node(0)
+ edges = nx.minimum_spanning_edges(
+ G, algorithm=self.algo, data=False, ignore_nan=True
+ )
+ actual = sorted((min(u, v), max(u, v)) for u, v in edges)
+ shift = [(u + 1, v + 1) for u, v, d in self.minimum_spanning_edgelist]
+ assert edges_equal(actual, shift)
+
+ def test_minimum_tree(self):
+ T = nx.minimum_spanning_tree(self.G, algorithm=self.algo)
+ actual = sorted(T.edges(data=True))
+ assert edges_equal(actual, self.minimum_spanning_edgelist)
+
+ def test_maximum_tree(self):
+ T = nx.maximum_spanning_tree(self.G, algorithm=self.algo)
+ actual = sorted(T.edges(data=True))
+ assert edges_equal(actual, self.maximum_spanning_edgelist)
+
+ def test_disconnected(self):
+ G = nx.Graph([(0, 1, {"weight": 1}), (2, 3, {"weight": 2})])
+ T = nx.minimum_spanning_tree(G, algorithm=self.algo)
+ assert nodes_equal(list(T), list(range(4)))
+ assert edges_equal(list(T.edges()), [(0, 1), (2, 3)])
+
+ def test_empty_graph(self):
+ G = nx.empty_graph(3)
+ T = nx.minimum_spanning_tree(G, algorithm=self.algo)
+ assert nodes_equal(sorted(T), list(range(3)))
+ assert T.number_of_edges() == 0
+
+ def test_attributes(self):
+ G = nx.Graph()
+ G.add_edge(1, 2, weight=1, color="red", distance=7)
+ G.add_edge(2, 3, weight=1, color="green", distance=2)
+ G.add_edge(1, 3, weight=10, color="blue", distance=1)
+ G.graph["foo"] = "bar"
+ T = nx.minimum_spanning_tree(G, algorithm=self.algo)
+ assert T.graph == G.graph
+ assert nodes_equal(T, G)
+ for u, v in T.edges():
+ assert T.adj[u][v] == G.adj[u][v]
+
+ def test_weight_attribute(self):
+ G = nx.Graph()
+ G.add_edge(0, 1, weight=1, distance=7)
+ G.add_edge(0, 2, weight=30, distance=1)
+ G.add_edge(1, 2, weight=1, distance=1)
+ G.add_node(3)
+ T = nx.minimum_spanning_tree(G, algorithm=self.algo, weight="distance")
+ assert nodes_equal(sorted(T), list(range(4)))
+ assert edges_equal(sorted(T.edges()), [(0, 2), (1, 2)])
+ T = nx.maximum_spanning_tree(G, algorithm=self.algo, weight="distance")
+ assert nodes_equal(sorted(T), list(range(4)))
+ assert edges_equal(sorted(T.edges()), [(0, 1), (0, 2)])
+
+
+class TestBoruvka(MinimumSpanningTreeTestBase):
+ """Unit tests for computing a minimum (or maximum) spanning tree
+ using Borůvka's algorithm.
+ """
+
+ algorithm = "boruvka"
+
+ def test_unicode_name(self):
+ """Tests that using a Unicode string can correctly indicate
+ Borůvka's algorithm.
+ """
+ edges = nx.minimum_spanning_edges(self.G, algorithm="borůvka")
+ # Edges from the spanning edges functions don't come in sorted
+ # orientation, so we need to sort each edge individually.
+ actual = sorted((min(u, v), max(u, v), d) for u, v, d in edges)
+ assert edges_equal(actual, self.minimum_spanning_edgelist)
+
+
+class MultigraphMSTTestBase(MinimumSpanningTreeTestBase):
+ # Abstract class
+
+ def test_multigraph_keys_min(self):
+ """Tests that the minimum spanning edges of a multigraph
+ preserves edge keys.
+ """
+ G = nx.MultiGraph()
+ G.add_edge(0, 1, key="a", weight=2)
+ G.add_edge(0, 1, key="b", weight=1)
+ min_edges = nx.minimum_spanning_edges
+ mst_edges = min_edges(G, algorithm=self.algo, data=False)
+ assert edges_equal([(0, 1, "b")], list(mst_edges))
+
+ def test_multigraph_keys_max(self):
+ """Tests that the maximum spanning edges of a multigraph
+ preserves edge keys.
+ """
+ G = nx.MultiGraph()
+ G.add_edge(0, 1, key="a", weight=2)
+ G.add_edge(0, 1, key="b", weight=1)
+ max_edges = nx.maximum_spanning_edges
+ mst_edges = max_edges(G, algorithm=self.algo, data=False)
+ assert edges_equal([(0, 1, "a")], list(mst_edges))
+
+
+class TestKruskal(MultigraphMSTTestBase):
+ """Unit tests for computing a minimum (or maximum) spanning tree
+ using Kruskal's algorithm.
+ """
+
+ algorithm = "kruskal"
+
+ def test_key_data_bool(self):
+ """Tests that the keys and data values are included in
+ MST edges based on whether keys and data parameters are
+ true or false"""
+ G = nx.MultiGraph()
+ G.add_edge(1, 2, key=1, weight=2)
+ G.add_edge(1, 2, key=2, weight=3)
+ G.add_edge(3, 2, key=1, weight=2)
+ G.add_edge(3, 1, key=1, weight=4)
+
+ # keys are included and data is not included
+ mst_edges = nx.minimum_spanning_edges(
+ G, algorithm=self.algo, keys=True, data=False
+ )
+ assert edges_equal([(1, 2, 1), (2, 3, 1)], list(mst_edges))
+
+ # keys are not included and data is included
+ mst_edges = nx.minimum_spanning_edges(
+ G, algorithm=self.algo, keys=False, data=True
+ )
+ assert edges_equal(
+ [(1, 2, {"weight": 2}), (2, 3, {"weight": 2})], list(mst_edges)
+ )
+
+ # both keys and data are not included
+ mst_edges = nx.minimum_spanning_edges(
+ G, algorithm=self.algo, keys=False, data=False
+ )
+ assert edges_equal([(1, 2), (2, 3)], list(mst_edges))
+
+ # both keys and data are included
+ mst_edges = nx.minimum_spanning_edges(
+ G, algorithm=self.algo, keys=True, data=True
+ )
+ assert edges_equal(
+ [(1, 2, 1, {"weight": 2}), (2, 3, 1, {"weight": 2})], list(mst_edges)
+ )
+
+
+class TestPrim(MultigraphMSTTestBase):
+ """Unit tests for computing a minimum (or maximum) spanning tree
+ using Prim's algorithm.
+ """
+
+ algorithm = "prim"
+
+ def test_prim_mst_edges_simple_graph(self):
+ H = nx.Graph()
+ H.add_edge(1, 2, key=2, weight=3)
+ H.add_edge(3, 2, key=1, weight=2)
+ H.add_edge(3, 1, key=1, weight=4)
+
+ mst_edges = nx.minimum_spanning_edges(H, algorithm=self.algo, ignore_nan=True)
+ assert edges_equal(
+ [(1, 2, {"key": 2, "weight": 3}), (2, 3, {"key": 1, "weight": 2})],
+ list(mst_edges),
+ )
+
+ def test_ignore_nan(self):
+ """Tests that the edges with NaN weights are ignored or
+ raise an Error based on ignore_nan is true or false"""
+ H = nx.MultiGraph()
+ H.add_edge(1, 2, key=1, weight=float("nan"))
+ H.add_edge(1, 2, key=2, weight=3)
+ H.add_edge(3, 2, key=1, weight=2)
+ H.add_edge(3, 1, key=1, weight=4)
+
+ # NaN weight edges are ignored when ignore_nan=True
+ mst_edges = nx.minimum_spanning_edges(H, algorithm=self.algo, ignore_nan=True)
+ assert edges_equal(
+ [(1, 2, 2, {"weight": 3}), (2, 3, 1, {"weight": 2})], list(mst_edges)
+ )
+
+ # NaN weight edges raise Error when ignore_nan=False
+ with pytest.raises(ValueError):
+ list(nx.minimum_spanning_edges(H, algorithm=self.algo, ignore_nan=False))
+
+ def test_multigraph_keys_tree(self):
+ G = nx.MultiGraph()
+ G.add_edge(0, 1, key="a", weight=2)
+ G.add_edge(0, 1, key="b", weight=1)
+ T = nx.minimum_spanning_tree(G, algorithm=self.algo)
+ assert edges_equal([(0, 1, 1)], list(T.edges(data="weight")))
+
+ def test_multigraph_keys_tree_max(self):
+ G = nx.MultiGraph()
+ G.add_edge(0, 1, key="a", weight=2)
+ G.add_edge(0, 1, key="b", weight=1)
+ T = nx.maximum_spanning_tree(G, algorithm=self.algo)
+ assert edges_equal([(0, 1, 2)], list(T.edges(data="weight")))
+
+
+class TestSpanningTreeIterator:
+ """
+ Tests the spanning tree iterator on the example graph in the 2005 Sörensen
+ and Janssens paper An Algorithm to Generate all Spanning Trees of a Graph in
+ Order of Increasing Cost
+ """
+
+ def setup_method(self):
+ # Original Graph
+ edges = [(0, 1, 5), (1, 2, 4), (1, 4, 6), (2, 3, 5), (2, 4, 7), (3, 4, 3)]
+ self.G = nx.Graph()
+ self.G.add_weighted_edges_from(edges)
+ # List of lists of spanning trees in increasing order
+ self.spanning_trees = [
+ # 1, MST, cost = 17
+ [
+ (0, 1, {"weight": 5}),
+ (1, 2, {"weight": 4}),
+ (2, 3, {"weight": 5}),
+ (3, 4, {"weight": 3}),
+ ],
+ # 2, cost = 18
+ [
+ (0, 1, {"weight": 5}),
+ (1, 2, {"weight": 4}),
+ (1, 4, {"weight": 6}),
+ (3, 4, {"weight": 3}),
+ ],
+ # 3, cost = 19
+ [
+ (0, 1, {"weight": 5}),
+ (1, 4, {"weight": 6}),
+ (2, 3, {"weight": 5}),
+ (3, 4, {"weight": 3}),
+ ],
+ # 4, cost = 19
+ [
+ (0, 1, {"weight": 5}),
+ (1, 2, {"weight": 4}),
+ (2, 4, {"weight": 7}),
+ (3, 4, {"weight": 3}),
+ ],
+ # 5, cost = 20
+ [
+ (0, 1, {"weight": 5}),
+ (1, 2, {"weight": 4}),
+ (1, 4, {"weight": 6}),
+ (2, 3, {"weight": 5}),
+ ],
+ # 6, cost = 21
+ [
+ (0, 1, {"weight": 5}),
+ (1, 4, {"weight": 6}),
+ (2, 4, {"weight": 7}),
+ (3, 4, {"weight": 3}),
+ ],
+ # 7, cost = 21
+ [
+ (0, 1, {"weight": 5}),
+ (1, 2, {"weight": 4}),
+ (2, 3, {"weight": 5}),
+ (2, 4, {"weight": 7}),
+ ],
+ # 8, cost = 23
+ [
+ (0, 1, {"weight": 5}),
+ (1, 4, {"weight": 6}),
+ (2, 3, {"weight": 5}),
+ (2, 4, {"weight": 7}),
+ ],
+ ]
+
+ def test_minimum_spanning_tree_iterator(self):
+ """
+ Tests that the spanning trees are correctly returned in increasing order
+ """
+ tree_index = 0
+ for tree in nx.SpanningTreeIterator(self.G):
+ actual = sorted(tree.edges(data=True))
+ assert edges_equal(actual, self.spanning_trees[tree_index])
+ tree_index += 1
+
+ def test_maximum_spanning_tree_iterator(self):
+ """
+ Tests that the spanning trees are correctly returned in decreasing order
+ """
+ tree_index = 7
+ for tree in nx.SpanningTreeIterator(self.G, minimum=False):
+ actual = sorted(tree.edges(data=True))
+ assert edges_equal(actual, self.spanning_trees[tree_index])
+ tree_index -= 1
+
+
+class TestSpanningTreeMultiGraphIterator:
+ """
+ Uses the same graph as the above class but with an added edge of twice the weight.
+ """
+
+ def setup_method(self):
+ # New graph
+ edges = [
+ (0, 1, 5),
+ (0, 1, 10),
+ (1, 2, 4),
+ (1, 2, 8),
+ (1, 4, 6),
+ (1, 4, 12),
+ (2, 3, 5),
+ (2, 3, 10),
+ (2, 4, 7),
+ (2, 4, 14),
+ (3, 4, 3),
+ (3, 4, 6),
+ ]
+ self.G = nx.MultiGraph()
+ self.G.add_weighted_edges_from(edges)
+
+ # There are 128 trees. I'd rather not list all 128 here, and computing them
+ # on such a small graph actually doesn't take that long.
+ from itertools import combinations
+
+ self.spanning_trees = []
+ for e in combinations(self.G.edges, 4):
+ tree = self.G.edge_subgraph(e)
+ if nx.is_tree(tree):
+ self.spanning_trees.append(sorted(tree.edges(keys=True, data=True)))
+
+ def test_minimum_spanning_tree_iterator_multigraph(self):
+ """
+ Tests that the spanning trees are correctly returned in increasing order
+ """
+ tree_index = 0
+ last_weight = 0
+ for tree in nx.SpanningTreeIterator(self.G):
+ actual = sorted(tree.edges(keys=True, data=True))
+ weight = sum([e[3]["weight"] for e in actual])
+ assert actual in self.spanning_trees
+ assert weight >= last_weight
+ tree_index += 1
+
+ def test_maximum_spanning_tree_iterator_multigraph(self):
+ """
+ Tests that the spanning trees are correctly returned in decreasing order
+ """
+ tree_index = 127
+ # Maximum weight tree is 46
+ last_weight = 50
+ for tree in nx.SpanningTreeIterator(self.G, minimum=False):
+ actual = sorted(tree.edges(keys=True, data=True))
+ weight = sum([e[3]["weight"] for e in actual])
+ assert actual in self.spanning_trees
+ assert weight <= last_weight
+ tree_index -= 1
+
+
+def test_random_spanning_tree_multiplicative_small():
+ """
+ Using a fixed seed, sample one tree for repeatability.
+ """
+ from math import exp
+
+ pytest.importorskip("scipy")
+
+ gamma = {
+ (0, 1): -0.6383,
+ (0, 2): -0.6827,
+ (0, 5): 0,
+ (1, 2): -1.0781,
+ (1, 4): 0,
+ (2, 3): 0,
+ (5, 3): -0.2820,
+ (5, 4): -0.3327,
+ (4, 3): -0.9927,
+ }
+
+ # The undirected support of gamma
+ G = nx.Graph()
+ for u, v in gamma:
+ G.add_edge(u, v, lambda_key=exp(gamma[(u, v)]))
+
+ solution_edges = [(2, 3), (3, 4), (0, 5), (5, 4), (4, 1)]
+ solution = nx.Graph()
+ solution.add_edges_from(solution_edges)
+
+ sampled_tree = nx.random_spanning_tree(G, "lambda_key", seed=42)
+
+ assert nx.utils.edges_equal(solution.edges, sampled_tree.edges)
+
+
+@pytest.mark.slow
+def test_random_spanning_tree_multiplicative_large():
+ """
+ Sample many trees from the distribution created in the last test
+ """
+ from math import exp
+ from random import Random
+
+ pytest.importorskip("numpy")
+ stats = pytest.importorskip("scipy.stats")
+
+ gamma = {
+ (0, 1): -0.6383,
+ (0, 2): -0.6827,
+ (0, 5): 0,
+ (1, 2): -1.0781,
+ (1, 4): 0,
+ (2, 3): 0,
+ (5, 3): -0.2820,
+ (5, 4): -0.3327,
+ (4, 3): -0.9927,
+ }
+
+ # The undirected support of gamma
+ G = nx.Graph()
+ for u, v in gamma:
+ G.add_edge(u, v, lambda_key=exp(gamma[(u, v)]))
+
+ # Find the multiplicative weight for each tree.
+ total_weight = 0
+ tree_expected = {}
+ for t in nx.SpanningTreeIterator(G):
+ # Find the multiplicative weight of the spanning tree
+ weight = 1
+ for u, v, d in t.edges(data="lambda_key"):
+ weight *= d
+ tree_expected[t] = weight
+ total_weight += weight
+
+ # Assert that every tree has an entry in the expected distribution
+ assert len(tree_expected) == 75
+
+ # Set the sample size and then calculate the expected number of times we
+ # expect to see each tree. This test uses a near minimum sample size where
+ # the most unlikely tree has an expected frequency of 5.15.
+ # (Minimum required is 5)
+ #
+ # Here we also initialize the tree_actual dict so that we know the keys
+ # match between the two. We will later take advantage of the fact that since
+ # python 3.7 dict order is guaranteed so the expected and actual data will
+ # have the same order.
+ sample_size = 1200
+ tree_actual = {}
+ for t in tree_expected:
+ tree_expected[t] = (tree_expected[t] / total_weight) * sample_size
+ tree_actual[t] = 0
+
+ # Sample the spanning trees
+ #
+ # Assert that they are actually trees and record which of the 75 trees we
+ # have sampled.
+ #
+ # For repeatability, we want to take advantage of the decorators in NetworkX
+ # to randomly sample the same sample each time. However, if we pass in a
+ # constant seed to sample_spanning_tree we will get the same tree each time.
+ # Instead, we can create our own random number generator with a fixed seed
+ # and pass those into sample_spanning_tree.
+ rng = Random(37)
+ for _ in range(sample_size):
+ sampled_tree = nx.random_spanning_tree(G, "lambda_key", seed=rng)
+ assert nx.is_tree(sampled_tree)
+
+ for t in tree_expected:
+ if nx.utils.edges_equal(t.edges, sampled_tree.edges):
+ tree_actual[t] += 1
+ break
+
+ # Conduct a Chi squared test to see if the actual distribution matches the
+ # expected one at an alpha = 0.05 significance level.
+ #
+ # H_0: The distribution of trees in tree_actual matches the normalized product
+ # of the edge weights in the tree.
+ #
+ # H_a: The distribution of trees in tree_actual follows some other
+ # distribution of spanning trees.
+ _, p = stats.chisquare(list(tree_actual.values()), list(tree_expected.values()))
+
+ # Assert that p is greater than the significance level so that we do not
+ # reject the null hypothesis
+ assert not p < 0.05
+
+
+def test_random_spanning_tree_additive_small():
+ """
+ Sample a single spanning tree from the additive method.
+ """
+ pytest.importorskip("scipy")
+
+ edges = {
+ (0, 1): 1,
+ (0, 2): 1,
+ (0, 5): 3,
+ (1, 2): 2,
+ (1, 4): 3,
+ (2, 3): 3,
+ (5, 3): 4,
+ (5, 4): 5,
+ (4, 3): 4,
+ }
+
+ # Build the graph
+ G = nx.Graph()
+ for u, v in edges:
+ G.add_edge(u, v, weight=edges[(u, v)])
+
+ solution_edges = [(0, 2), (1, 2), (2, 3), (3, 4), (3, 5)]
+ solution = nx.Graph()
+ solution.add_edges_from(solution_edges)
+
+ sampled_tree = nx.random_spanning_tree(
+ G, weight="weight", multiplicative=False, seed=37
+ )
+
+ assert nx.utils.edges_equal(solution.edges, sampled_tree.edges)
+
+
+@pytest.mark.slow
+def test_random_spanning_tree_additive_large():
+ """
+ Sample many spanning trees from the additive method.
+ """
+ from random import Random
+
+ pytest.importorskip("numpy")
+ stats = pytest.importorskip("scipy.stats")
+
+ edges = {
+ (0, 1): 1,
+ (0, 2): 1,
+ (0, 5): 3,
+ (1, 2): 2,
+ (1, 4): 3,
+ (2, 3): 3,
+ (5, 3): 4,
+ (5, 4): 5,
+ (4, 3): 4,
+ }
+
+ # Build the graph
+ G = nx.Graph()
+ for u, v in edges:
+ G.add_edge(u, v, weight=edges[(u, v)])
+
+ # Find the additive weight for each tree.
+ total_weight = 0
+ tree_expected = {}
+ for t in nx.SpanningTreeIterator(G):
+ # Find the multiplicative weight of the spanning tree
+ weight = 0
+ for u, v, d in t.edges(data="weight"):
+ weight += d
+ tree_expected[t] = weight
+ total_weight += weight
+
+ # Assert that every tree has an entry in the expected distribution
+ assert len(tree_expected) == 75
+
+ # Set the sample size and then calculate the expected number of times we
+ # expect to see each tree. This test uses a near minimum sample size where
+ # the most unlikely tree has an expected frequency of 5.07.
+ # (Minimum required is 5)
+ #
+ # Here we also initialize the tree_actual dict so that we know the keys
+ # match between the two. We will later take advantage of the fact that since
+ # python 3.7 dict order is guaranteed so the expected and actual data will
+ # have the same order.
+ sample_size = 500
+ tree_actual = {}
+ for t in tree_expected:
+ tree_expected[t] = (tree_expected[t] / total_weight) * sample_size
+ tree_actual[t] = 0
+
+ # Sample the spanning trees
+ #
+ # Assert that they are actually trees and record which of the 75 trees we
+ # have sampled.
+ #
+ # For repeatability, we want to take advantage of the decorators in NetworkX
+ # to randomly sample the same sample each time. However, if we pass in a
+ # constant seed to sample_spanning_tree we will get the same tree each time.
+ # Instead, we can create our own random number generator with a fixed seed
+ # and pass those into sample_spanning_tree.
+ rng = Random(37)
+ for _ in range(sample_size):
+ sampled_tree = nx.random_spanning_tree(
+ G, "weight", multiplicative=False, seed=rng
+ )
+ assert nx.is_tree(sampled_tree)
+
+ for t in tree_expected:
+ if nx.utils.edges_equal(t.edges, sampled_tree.edges):
+ tree_actual[t] += 1
+ break
+
+ # Conduct a Chi squared test to see if the actual distribution matches the
+ # expected one at an alpha = 0.05 significance level.
+ #
+ # H_0: The distribution of trees in tree_actual matches the normalized product
+ # of the edge weights in the tree.
+ #
+ # H_a: The distribution of trees in tree_actual follows some other
+ # distribution of spanning trees.
+ _, p = stats.chisquare(list(tree_actual.values()), list(tree_expected.values()))
+
+ # Assert that p is greater than the significance level so that we do not
+ # reject the null hypothesis
+ assert not p < 0.05
+
+
+def test_random_spanning_tree_empty_graph():
+ G = nx.Graph()
+ rst = nx.tree.random_spanning_tree(G)
+ assert len(rst.nodes) == 0
+ assert len(rst.edges) == 0
+
+
+def test_random_spanning_tree_single_node_graph():
+ G = nx.Graph()
+ G.add_node(0)
+ rst = nx.tree.random_spanning_tree(G)
+ assert len(rst.nodes) == 1
+ assert len(rst.edges) == 0
+
+
+def test_random_spanning_tree_single_node_loop():
+ G = nx.Graph()
+ G.add_node(0)
+ G.add_edge(0, 0)
+ rst = nx.tree.random_spanning_tree(G)
+ assert len(rst.nodes) == 1
+ assert len(rst.edges) == 0
+
+
+class TestNumberSpanningTrees:
+ @classmethod
+ def setup_class(cls):
+ global np
+ np = pytest.importorskip("numpy")
+ sp = pytest.importorskip("scipy")
+
+ def test_nst_disconnected(self):
+ G = nx.empty_graph(2)
+ assert np.isclose(nx.number_of_spanning_trees(G), 0)
+
+ def test_nst_no_nodes(self):
+ G = nx.Graph()
+ with pytest.raises(nx.NetworkXPointlessConcept):
+ nx.number_of_spanning_trees(G)
+
+ def test_nst_weight(self):
+ G = nx.Graph()
+ G.add_edge(1, 2, weight=1)
+ G.add_edge(1, 3, weight=1)
+ G.add_edge(2, 3, weight=2)
+ # weights are ignored
+ assert np.isclose(nx.number_of_spanning_trees(G), 3)
+ # including weight
+ assert np.isclose(nx.number_of_spanning_trees(G, weight="weight"), 5)
+
+ def test_nst_negative_weight(self):
+ G = nx.Graph()
+ G.add_edge(1, 2, weight=1)
+ G.add_edge(1, 3, weight=-1)
+ G.add_edge(2, 3, weight=-2)
+ # weights are ignored
+ assert np.isclose(nx.number_of_spanning_trees(G), 3)
+ # including weight
+ assert np.isclose(nx.number_of_spanning_trees(G, weight="weight"), -1)
+
+ def test_nst_selfloop(self):
+ # self-loops are ignored
+ G = nx.complete_graph(3)
+ G.add_edge(1, 1)
+ assert np.isclose(nx.number_of_spanning_trees(G), 3)
+
+ def test_nst_multigraph(self):
+ G = nx.MultiGraph()
+ G.add_edge(1, 2)
+ G.add_edge(1, 2)
+ G.add_edge(1, 3)
+ G.add_edge(2, 3)
+ assert np.isclose(nx.number_of_spanning_trees(G), 5)
+
+ def test_nst_complete_graph(self):
+ # this is known as Cayley's formula
+ N = 5
+ G = nx.complete_graph(N)
+ assert np.isclose(nx.number_of_spanning_trees(G), N ** (N - 2))
+
+ def test_nst_path_graph(self):
+ G = nx.path_graph(5)
+ assert np.isclose(nx.number_of_spanning_trees(G), 1)
+
+ def test_nst_cycle_graph(self):
+ G = nx.cycle_graph(5)
+ assert np.isclose(nx.number_of_spanning_trees(G), 5)
+
+ def test_nst_directed_noroot(self):
+ G = nx.empty_graph(3, create_using=nx.MultiDiGraph)
+ with pytest.raises(nx.NetworkXError):
+ nx.number_of_spanning_trees(G)
+
+ def test_nst_directed_root_not_exist(self):
+ G = nx.empty_graph(3, create_using=nx.MultiDiGraph)
+ with pytest.raises(nx.NetworkXError):
+ nx.number_of_spanning_trees(G, root=42)
+
+ def test_nst_directed_not_weak_connected(self):
+ G = nx.DiGraph()
+ G.add_edge(1, 2)
+ G.add_edge(3, 4)
+ assert np.isclose(nx.number_of_spanning_trees(G, root=1), 0)
+
+ def test_nst_directed_cycle_graph(self):
+ G = nx.DiGraph()
+ G = nx.cycle_graph(7, G)
+ assert np.isclose(nx.number_of_spanning_trees(G, root=0), 1)
+
+ def test_nst_directed_complete_graph(self):
+ G = nx.DiGraph()
+ G = nx.complete_graph(7, G)
+ assert np.isclose(nx.number_of_spanning_trees(G, root=0), 7**5)
+
+ def test_nst_directed_multi(self):
+ G = nx.MultiDiGraph()
+ G = nx.cycle_graph(3, G)
+ G.add_edge(1, 2)
+ assert np.isclose(nx.number_of_spanning_trees(G, root=0), 2)
+
+ def test_nst_directed_selfloop(self):
+ G = nx.MultiDiGraph()
+ G = nx.cycle_graph(3, G)
+ G.add_edge(1, 1)
+ assert np.isclose(nx.number_of_spanning_trees(G, root=0), 1)
+
+ def test_nst_directed_weak_connected(self):
+ G = nx.MultiDiGraph()
+ G = nx.cycle_graph(3, G)
+ G.remove_edge(1, 2)
+ assert np.isclose(nx.number_of_spanning_trees(G, root=0), 0)
+
+ def test_nst_directed_weighted(self):
+ # from root=1:
+ # arborescence 1: 1->2, 1->3, weight=2*1
+ # arborescence 2: 1->2, 2->3, weight=2*3
+ G = nx.DiGraph()
+ G.add_edge(1, 2, weight=2)
+ G.add_edge(1, 3, weight=1)
+ G.add_edge(2, 3, weight=3)
+ Nst = nx.number_of_spanning_trees(G, root=1, weight="weight")
+ assert np.isclose(Nst, 8)
+ Nst = nx.number_of_spanning_trees(G, root=2, weight="weight")
+ assert np.isclose(Nst, 0)
+ Nst = nx.number_of_spanning_trees(G, root=3, weight="weight")
+ assert np.isclose(Nst, 0)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_operations.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_operations.py
new file mode 100644
index 00000000..284d94e2
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_operations.py
@@ -0,0 +1,53 @@
+from itertools import chain
+
+import networkx as nx
+from networkx.utils import edges_equal, nodes_equal
+
+
+def _check_custom_label_attribute(input_trees, res_tree, label_attribute):
+ res_attr_dict = nx.get_node_attributes(res_tree, label_attribute)
+ res_attr_set = set(res_attr_dict.values())
+ input_label = (tree for tree, root in input_trees)
+ input_label_set = set(chain.from_iterable(input_label))
+ return res_attr_set == input_label_set
+
+
+def test_empty_sequence():
+ """Joining the empty sequence results in the tree with one node."""
+ T = nx.join_trees([])
+ assert len(T) == 1
+ assert T.number_of_edges() == 0
+
+
+def test_single():
+ """Joining just one tree yields a tree with one more node."""
+ T = nx.empty_graph(1)
+ trees = [(T, 0)]
+ actual_with_label = nx.join_trees(trees, label_attribute="custom_label")
+ expected = nx.path_graph(2)
+ assert nodes_equal(list(expected), list(actual_with_label))
+ assert edges_equal(list(expected.edges()), list(actual_with_label.edges()))
+
+
+def test_basic():
+ """Joining multiple subtrees at a root node."""
+ trees = [(nx.full_rary_tree(2, 2**2 - 1), 0) for i in range(2)]
+ expected = nx.full_rary_tree(2, 2**3 - 1)
+ actual = nx.join_trees(trees, label_attribute="old_labels")
+ assert nx.is_isomorphic(actual, expected)
+ assert _check_custom_label_attribute(trees, actual, "old_labels")
+
+ actual_without_label = nx.join_trees(trees)
+ assert nx.is_isomorphic(actual_without_label, expected)
+ # check that no labels were stored
+ assert all(not data for _, data in actual_without_label.nodes(data=True))
+
+
+def test_first_label():
+ """Test the functionality of the first_label argument."""
+ T1 = nx.path_graph(3)
+ T2 = nx.path_graph(2)
+ actual = nx.join_trees([(T1, 0), (T2, 0)], first_label=10)
+ expected_nodes = set(range(10, 16))
+ assert set(actual.nodes()) == expected_nodes
+ assert set(actual.neighbors(10)) == {11, 14}
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_recognition.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_recognition.py
new file mode 100644
index 00000000..105f5a89
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tree/tests/test_recognition.py
@@ -0,0 +1,174 @@
+import pytest
+
+import networkx as nx
+
+
+class TestTreeRecognition:
+ graph = nx.Graph
+ multigraph = nx.MultiGraph
+
+ @classmethod
+ def setup_class(cls):
+ cls.T1 = cls.graph()
+
+ cls.T2 = cls.graph()
+ cls.T2.add_node(1)
+
+ cls.T3 = cls.graph()
+ cls.T3.add_nodes_from(range(5))
+ edges = [(i, i + 1) for i in range(4)]
+ cls.T3.add_edges_from(edges)
+
+ cls.T5 = cls.multigraph()
+ cls.T5.add_nodes_from(range(5))
+ edges = [(i, i + 1) for i in range(4)]
+ cls.T5.add_edges_from(edges)
+
+ cls.T6 = cls.graph()
+ cls.T6.add_nodes_from([6, 7])
+ cls.T6.add_edge(6, 7)
+
+ cls.F1 = nx.compose(cls.T6, cls.T3)
+
+ cls.N4 = cls.graph()
+ cls.N4.add_node(1)
+ cls.N4.add_edge(1, 1)
+
+ cls.N5 = cls.graph()
+ cls.N5.add_nodes_from(range(5))
+
+ cls.N6 = cls.graph()
+ cls.N6.add_nodes_from(range(3))
+ cls.N6.add_edges_from([(0, 1), (1, 2), (2, 0)])
+
+ cls.NF1 = nx.compose(cls.T6, cls.N6)
+
+ def test_null_tree(self):
+ with pytest.raises(nx.NetworkXPointlessConcept):
+ nx.is_tree(self.graph())
+
+ def test_null_tree2(self):
+ with pytest.raises(nx.NetworkXPointlessConcept):
+ nx.is_tree(self.multigraph())
+
+ def test_null_forest(self):
+ with pytest.raises(nx.NetworkXPointlessConcept):
+ nx.is_forest(self.graph())
+
+ def test_null_forest2(self):
+ with pytest.raises(nx.NetworkXPointlessConcept):
+ nx.is_forest(self.multigraph())
+
+ def test_is_tree(self):
+ assert nx.is_tree(self.T2)
+ assert nx.is_tree(self.T3)
+ assert nx.is_tree(self.T5)
+
+ def test_is_not_tree(self):
+ assert not nx.is_tree(self.N4)
+ assert not nx.is_tree(self.N5)
+ assert not nx.is_tree(self.N6)
+
+ def test_is_forest(self):
+ assert nx.is_forest(self.T2)
+ assert nx.is_forest(self.T3)
+ assert nx.is_forest(self.T5)
+ assert nx.is_forest(self.F1)
+ assert nx.is_forest(self.N5)
+
+ def test_is_not_forest(self):
+ assert not nx.is_forest(self.N4)
+ assert not nx.is_forest(self.N6)
+ assert not nx.is_forest(self.NF1)
+
+
+class TestDirectedTreeRecognition(TestTreeRecognition):
+ graph = nx.DiGraph
+ multigraph = nx.MultiDiGraph
+
+
+def test_disconnected_graph():
+ # https://github.com/networkx/networkx/issues/1144
+ G = nx.Graph()
+ G.add_edges_from([(0, 1), (1, 2), (2, 0), (3, 4)])
+ assert not nx.is_tree(G)
+
+ G = nx.DiGraph()
+ G.add_edges_from([(0, 1), (1, 2), (2, 0), (3, 4)])
+ assert not nx.is_tree(G)
+
+
+def test_dag_nontree():
+ G = nx.DiGraph()
+ G.add_edges_from([(0, 1), (0, 2), (1, 2)])
+ assert not nx.is_tree(G)
+ assert nx.is_directed_acyclic_graph(G)
+
+
+def test_multicycle():
+ G = nx.MultiDiGraph()
+ G.add_edges_from([(0, 1), (0, 1)])
+ assert not nx.is_tree(G)
+ assert nx.is_directed_acyclic_graph(G)
+
+
+def test_emptybranch():
+ G = nx.DiGraph()
+ G.add_nodes_from(range(10))
+ assert nx.is_branching(G)
+ assert not nx.is_arborescence(G)
+
+
+def test_is_branching_empty_graph_raises():
+ G = nx.DiGraph()
+ with pytest.raises(nx.NetworkXPointlessConcept, match="G has no nodes."):
+ nx.is_branching(G)
+
+
+def test_path():
+ G = nx.DiGraph()
+ nx.add_path(G, range(5))
+ assert nx.is_branching(G)
+ assert nx.is_arborescence(G)
+
+
+def test_notbranching1():
+ # Acyclic violation.
+ G = nx.MultiDiGraph()
+ G.add_nodes_from(range(10))
+ G.add_edges_from([(0, 1), (1, 0)])
+ assert not nx.is_branching(G)
+ assert not nx.is_arborescence(G)
+
+
+def test_notbranching2():
+ # In-degree violation.
+ G = nx.MultiDiGraph()
+ G.add_nodes_from(range(10))
+ G.add_edges_from([(0, 1), (0, 2), (3, 2)])
+ assert not nx.is_branching(G)
+ assert not nx.is_arborescence(G)
+
+
+def test_notarborescence1():
+ # Not an arborescence due to not spanning.
+ G = nx.MultiDiGraph()
+ G.add_nodes_from(range(10))
+ G.add_edges_from([(0, 1), (0, 2), (1, 3), (5, 6)])
+ assert nx.is_branching(G)
+ assert not nx.is_arborescence(G)
+
+
+def test_notarborescence2():
+ # Not an arborescence due to in-degree violation.
+ G = nx.MultiDiGraph()
+ nx.add_path(G, range(5))
+ G.add_edge(6, 4)
+ assert not nx.is_branching(G)
+ assert not nx.is_arborescence(G)
+
+
+def test_is_arborescense_empty_graph_raises():
+ G = nx.DiGraph()
+ with pytest.raises(nx.NetworkXPointlessConcept, match="G has no nodes."):
+ nx.is_arborescence(G)