a h@sdZddlZddlmZmZddlmZddlmZddl m Z ddl Z ddl mZdd lmZmZgd Zd d hZd dddZedZedd?ddZddZddZe jddidd@ddZede jddiddAdd ZGd!d"d"e jZd#d$ZGd%d&d&Z e jddd'd(d)dBd+d,Z!e jddd'd(d)dCd-d.Z"e jddd'd(d)ddd*dd/d0d1Z#e jddd'd(d)dDd2d3Z$e jddd'd(d)dEd4d5Z%d6Z&e&d7Z'e&j(d8d d9e!_e&j(d:d d9d;e"_e'j(d8dd>Z)dS)Fu 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 N) dataclassfield)Enum) itemgetter) PriorityQueue)py_random_state)is_arborescence is_branching) branching_weightgreedy_branchingmaximum_branchingminimum_branchingminimal_branchingmaximum_spanning_arborescenceminimum_spanning_arborescenceArborescenceIteratorEdmondsmaxmin branching arborescence)rrspanning arborescenceinfcsdfddt|DS)Ncsg|]}tjqS)choicestring ascii_letters).0nseedrQ/var/www/auris/lib/python3.9/site-packages/networkx/algorithms/tree/branchings.py Az!random_string..)joinrange)Lr#rr"r$ random_string?sr*cCs| SNrweightrrr$ _min_weightDsr.cCs|Sr+rr,rrr$ _max_weightHsr/attrdefault) edge_attrsr-cs tfdd|jddDS)a 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 c3s|]}|dVqdS)Nget)r edger0r1rr$ kr&z#branching_weight..Tdata)sumedges)Gr0r1rr7r$r Lsr cs$|tvrtd|dkr d}nd}dur6t|dfdd|jdd D}z|jtd d d |d Wn$ty|jtd |d Yn0t}| |tj }t |D]h\} \} } } || || krqq| | d krqqi} dur| | <|j| | fi| || | q|S)a7 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`. Returns ------- B : directed graph The greedily obtained branching. Unknown value for `kind`.rFTNr"cs$g|]\}}}|||fqSrr4)r uvr:r7rr$r%r&z$greedy_branching..r9r3rr)keyreverse)KINDSnxNetworkXExceptionr*r<sortr TypeErrorZDiGraphadd_nodes_fromutils UnionFind enumerate in_degreeadd_edgeunion)r=r0r1kindr#rCr<Bufir@rAwr:rr7r$r ns4#     r csReZdZdZdfdd ZddZddZd d Zd d Zd dZ ddZ Z S)MultiDiGraph_EdgeKeya MultiDiGraph which assigns unique keys to every edge. Adds a dictionary edge_index which maps edge keys to (u, v, data) tuples. This is not a complete implementation. For Edmonds algorithm, we only use add_node and add_edge, so that is all that is implemented here. During additions, any specified keys are ignored---this means that you also cannot update edge attributes through add_node and add_edge. Why do we need this? Edmonds algorithm requires that we track edges, even as we change the head and tail of an edge, and even changing the weight of edges. We must reliably track edges across graph mutations. Nc sBt}|jfd|i|||_i|_ddl}d}||tdS)Nincoming_graph_datarzMMultiDiGraph_EdgeKey has been deprecated and will be removed in NetworkX 3.4.)super__init___cls edge_indexwarningswarnDeprecationWarning)selfrVr0clsr[msg __class__rr$rXszMultiDiGraph_EdgeKey.__init__cCsdt}|j|D]}||q|j|D]}||q2|D] }|j|=qF|j|dSr+)setpredvaluesupdatesuccrZrY remove_node)r^r!keyskeydictrBrrr$rhs   z MultiDiGraph_EdgeKey.remove_nodecCs|D]}||qdSr+)rh)r^nbunchr!rrr$remove_nodes_fromsz&MultiDiGraph_EdgeKey.remove_nodes_fromc Ks|||}}}||jvrJ|j|\}} } ||ks:|| krJtd|d|jj|||fi||||j|||f|j|<dS)z' Key is now required. Key  is already in use.N)rZ ExceptionrYrNrg) r^Z u_for_edgeZ v_for_edgeZ key_for_edger0r@rArBuuvv_rrr$rNs zMultiDiGraph_EdgeKey.add_edgecKs,|D]"\}}}}|j|||fi|qdSr+)rN)r^Z ebunch_to_addr0r@rAkdrrr$add_edges_fromsz#MultiDiGraph_EdgeKey.add_edges_fromc Csfz|j|\}}}Wn4tyH}ztd||WYd}~n"d}~00|j|=|j|||dS)NzInvalid edge key )rZKeyErrorrYZ remove_edge)r^rBr@rArrerrrrr$remove_edge_with_keys &z)MultiDiGraph_EdgeKey.remove_edge_with_keycCstdSr+)NotImplementedError)r^Zebunchrrr$remove_edges_fromsz&MultiDiGraph_EdgeKey.remove_edges_from)N) __name__ __module__ __qualname____doc__rXrhrlrNrurxrz __classcell__rrrar$rUs   rUcsBt||fddfddtddD}|fS)z Returns the edge keys of the unique path between u and v. This is not a generic function. G must be a branching and an instance of MultiDiGraph_EdgeKey. cs$||}t|}|dS)Nr)rilist)rSrqri)r=nodesrr$ first_keyszget_path..first_keycsg|]\}}||qSrrr rSrq)rrr$r%r&zget_path..rN)rE shortest_pathrL)r=r@rAr<r)r=rrr$get_path src@s,eZdZdZdddZddZdd d ZdS)ra Edmonds algorithm [1]_ for finding optimal branchings and spanning arborescences. This algorithm can find both minimum and maximum spanning arborescences and branchings. Notes ----- While this algorithm can find a minimum branching, since it isn't required to be spanning, the minimum branching is always from the set of negative weight edges which is most likely the empty set for most graphs. References ---------- .. [1] J. Edmonds, Optimum Branchings, Journal of Research of the National Bureau of Standards, 1967, Vol. 71B, p.233-240, https://archive.org/details/jresv71Bn4p233 NcCs>||_d|_g|_t|dd|_ddl}d}||tdS)NTr"z_{0}rzEdmonds has been deprecated and will be removed in NetworkX 3.4. Please use the appropriate minimum or maximum branching or arborescence function directly.) G_originalstorer<r*templater[r\r])r^r=r#r[r`rrr$rX8szEdmonds.__init__cCsH|tvrtd||_||_||_||_|dkr>t|_}n t |_}|durZt |d}||_ dt |d|_ t |_} t|jjddD]z\} \} } } ||| ||i}| |dur| |||<|r| D]\}}||kr|||<q| j| | | fi|qd|_t |_i|j_g|_g|_tj|_g|_g|_dS) a So we need the code in _init and find_optimum to successfully run edmonds algorithm. Responsibilities of the _init function: - Check that the kind argument is in {min, max} or raise a NetworkXException. - Transform the graph if we need a minimum arborescence/branching. - The current method is to map weight -> -weight. This is NOT a good approach since the algorithm can and does choose to ignore negative weights when creating a branching since that is always optimal when maximzing the weights. I think we should set the edge weights to be (max_weight + 1) - edge_weight. - Transform the graph into a MultiDiGraph, adding the partition information and potoentially other edge attributes if we set preserve_attrs = True. - Setup the buckets and union find data structures required for the algorithm. r?rNr"Z candidate_Tr9r)rDrErFr0r1rPstyler.transr/r*_attrcandidate_attrrUr=rLrr<r5itemsrNlevelrQrZgraphs branchingsrJrKrRcircuitsminedge_circuit)r^r0r1rPrpreserve_attrsr# partitionrr=rBr@rAr:rtd_kd_vrrr$_initJs>         z Edmonds._initr-rrrFc) s|||||||j}|j|j} t} tt} |jj } fdd} z t | }Wn~t yt t | ksJt | rt | sJ|jr|j|j| |jg|jdYqYn 0|| vrq\| || || |\}}|dur q\q\|d}||||krZt| ||\}}||dnd\}}|jdkr~|dkr~d}nd }|r\|i}|d dur|d |<| j|||dfi|d |||d|j<||||dur\t}d}i}|D]P}| j|\}}}|}|||<|tj j!krHq ||kr |}|}q |j||j||jr|j|j| |j"#|j$}|g}j%d d d D]\}}}}||vr ||vrqn|}|||||fnJ||vr|}||||7}|}||<|||||fnqȐqȈ&|| &|| 't||D]Z\}}}}j|||fi||j|vr~||j=| j|||fi||||q~tt} |j$d 7_$q\|j()}d d} t|j|j$j}!|j$dkr|j$d 8_$|j"#|j$}"|j|j$}#| |j|j$d |"|!\}$}%|!*|#|$r|j|j$}|durt+|!,|nX|j|j$j|%d }&|#D]&}%j|%\}}}||&krqqt+d|!,|%q|!|_%|-|j(|!D]z}%|jdj|%\}}}'|j.|/|'|j.i}|rz|'0D]$\}}(||j.|jfvrT|(||<qT|j||fi|q|S)a9 Returns a branching from G. Parameters ---------- 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`. kind : {'min', 'max'} The type of optimum to search for, either 'min' or 'max'. style : {'branching', 'arborescence'} If 'branching', then an optimal branching is found. If `style` is 'arborescence', then a branching is found, such that if the branching is also an arborescence, then the branching is an optimal spanning arborescences. A given graph G need not have an optimal spanning arborescence. preserve_attrs : bool If True, preserve the other edge attributes of the original graph (that are not the one passed to `attr`) partition : str The edge attribute holding edge partition data. Used in the spanning arborescence iterator. seed : integer, random_state, or None (default) Indicator of random number generation state. See :ref:`Randomness`. Returns ------- H : (multi)digraph The branching. csd}t }j|dddD]r\}}}}|tjjkr:q|}|tjjkrr|}|||||f}||fS||kr|}|||||f}q||fS)aQ Find the edge directed toward v with maximal weight. If an edge partition exists in this graph, return the included edge if it exists and no not return any excluded edges. There can only be one included edge for each vertex otherwise the edge partition is empty. NTr:riINFin_edgesr5rE EdgePartitionEXCLUDEDINCLUDED)rAr6r-r@rrrBr: new_weightr=r0rrr$ desired_edges  z*Edmonds.find_optimum..desired_edgeNrr3)NNrFTr>rrcSsV||vrt|d|j|D]0}|j||D]}||vr2d|fSq2q dS)z Returns True if `u` is a root node in G. Node `u` will be a root node if its in-degree, restricted to the specified edges, is equal to 0. not in GFTNNrordr=r@ZedgekeysrAedgekeyrrr$is_rootsz%Edmonds.find_optimum..is_root+Couldn't find edge incoming to merged node.)1rrRr=rQrciterrrrrdnext StopIterationlenr rrappendcopyrrraddadd_noderrr5rNrrOrrZrErrrformatrr<rldifference_updaterrbrfroremoverIr0rr))r^r0r1rPrrrr#rRrQDrZG_predrrAr6r-r@Q_nodesQ_edgesZ acceptabledd minweightminedgeQ_incoming_weightedge_keyr:rTnew_node new_edgesrBHrr< merged_nodecircuitisrootrtargetrtvaluerrr$ find_optimums,                                 zEdmonds.find_optimum)N)r-rrrFNN)r{r|r}r~rXrrrrrr$r"s \r)r0rr)r2Zpreserve_edge_attrsFcs"dddd dd }tit|jddD]x\}\}}} | |i} |  durr|  | <|r| D]\} } | kr~| | | <q~|||fi| q8d } tig gttjgg  fd d } fd d }dd}t t j }z t |}Wnt yttksdJtr|ts|J ffg dYqYn0|vr֐q2||||\}}|dur2|d kr2|d }||k}|i}|d durP|d | <|||dfi|d|||d<|||r2|||| t t  }| d7} q2|}t| d}| d kr| d8} t| }| }| | dd ||\}}|||rJ | }|dur>t||nT | \|d}|D]$}|\}}} ||krfqqftd||q|||D]l} d d|\}}} | i}|r| D] \}}|fvr|||<q|j||fi|q|S)Nc [sl||vr6||\}}}||ks&||kr6td|d|j|||fi||||j|||f||<dS)aS 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. rmrnN)rorNrg) r=rZr@rArBrtrprqrrrrr$edmonds_add_edges z+maximum_branching..edmonds_add_edgecSs`t}|j|D]}||q|j|D]}||q2|D] }||=qF||dS)aR 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`. N)rcrdrerfrgrh)r=rZr!rirjrBrrr$edmonds_remove_nodes   z.maximum_branching..edmonds_remove_nodez#edmonds' secret candidate attributezedmonds new node base name Tr9rcsd}t }j|dddD]j\}}}}|tjjkr:q|}|tjjkrj|}|||||f}q||kr|}|||||f}q||fS)a 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. NTrr)rAr6 max_weightr@rrrBr:rrrr$edmonds_find_desired_edge~sz4maximum_branching..edmonds_find_desired_edgecs*|d}t||fddtddD}||dt}d}i}|D]F}|\}}} | } | ||<| tjjkrqT| |krT| }|}qT| | ff t |}  | g} j dddD]\}}} } ||vrF||vr*qn| }| | || |fnJ||vr| } | |||7} | }| |<| || | |fnqqD]} | |q t | D]Z\}}} } ||| fi| | vr| = ||| fi| ||qdS) a 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. rcs,g|]$\}}t||dqS)r)rrir)rQrrr$r%sz>maximum_branching..edmonds_step_I2..rNr3Tr)rErrLrrr5rrrstrrr<rrcrO)rArrr@rrrrrr:rTrrrBrnoderQZ B_edge_indexr=Z G_edge_indexr0rrrrrrrZnew_node_base_namerZselected_nodesrR)rr$edmonds_step_I2s`          z*maximum_branching..edmonds_step_I2cSsV||vrt|d|j|D]0}|j||D]}||vr2d|fSq2q dS)a 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. rFrNrrrrr$rsz"maximum_branching..is_rootr>r3rr)rE MultiDiGraphrLr<r5rrcrJrKrrrrrrr rrrrrOrbrrfrorrIrN)r=r0r1rrrrBr@rAr:rtrrrrrrrrZdesired_edge_weightrrrr<rrrrrrrrr$r s!   %*W                       r cCs|jddD]\}}}|| ||<q t|||||}|jddD]\}}}|| ||<qB|jddD]\}}}|| ||<qh|S)NTr9)r<r )r=r0r1rrrrrtrQrrr$rsrr0r1rrc Cst }t}|j|dD]"\}}}||kr,|}||kr|}q|jddD]&\}}} |d||| || |<qFt|||||} |jddD]&\}}} |d||| || |<q| jddD]&\}}} |d||| || |<q| S)a 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. r9Tr)rr<r ) r=r0r1rrr min_weightrrrTrtrQrrr$rs%rc Cst}t }|j|dD]"\}}}||kr,|}||kr|}q|jddD]&\}}} | ||d||| |<qFt|||||} |jddD]&\}}} | ||d||| |<q| jddD]&\}}} | ||d||| |<qt| stjd| S)Nr9Trz&No maximum spanning arborescence in G.)rr<r r rE exceptionrF) r=r0r1rrrrrrrTrtrQrrr$rs" rcCs*t|||||d}t|s&tjd|S)Nrz&No minimum spanning arborescence in G.)rr rErrF)r=r0r1rrrQrrr$rs ra 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}. zV Raises ------ NetworkXException If the graph does not contain a {kind} {style}. maximum)rPrminimumz+ See Also -------- minimal_branching rc@sZeZdZdZeddGdddZddd Zd d Zd d ZddZ ddZ ddZ dS)ru 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 T)orderc@s4eZdZUdZeed<eddZeed<ddZ dS) zArborescenceIterator.Partitionz 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_weightF)comparepartition_dictcCst|j|jSr+)r Partitionrrr)r^rrr$__copy__s z'ArborescenceIterator.Partition.__copy__N) r{r|r}r~float__annotations__rrdictrrrrr$r|s rr-NcCs||_||_||_|rtnt|_d|_|durzi}|dD]}tj j ||<q>|dD]}tj j ||<qXt d||_nd|_dS)a 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. z;ArborescenceIterators super secret partition attribute nameNrr)rr=r-rrrmethod partition_keyrErrrrrinit_partition)r^r=r-rrrerrr$rXs    zArborescenceIterator.__init__cCst|_||j|jdur*||j|j|j|j|jddj |jd}|j | |j r`|n| |jdurrin|jj |S)zu Returns ------- ArborescenceIterator The iterator object for this graph NTrrr,)rpartition_queue_clear_partitionr=r_write_partitionrr-rsizeputrrr)r^rrrr$__iter__s*    zArborescenceIterator.__iter__cCs\|jr|`|`t|j}|||j|j|j|jdd}| ||| ||S)z Returns ------- (multi)Graph The spanning tree of next greatest weight, which ties broken arbitrarily. Tr) remptyr=rr5rrr-r _partitionr)r^rZnext_arborescencerrr$__next__s     zArborescenceIterator.__next__c Cs|d|j}|d|j}|jD]}||jvr*tjj|j|<tjj|j|<||zL|j |j |j |j dd}|j |j d}|jr|n| |_|j|WntjyYn0|j|_q*dS)a 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. rTrr,N)rrrr<rErrrrrr=r-rrrrrrrrF)r^rZpartition_arborescencep1p2rZp1_mstZ p1_mst_weightrrr$rs(   zArborescenceIterator._partitioncCs|jjddD]<\}}}||f|jvr<|j||f||j<qtjj||j<q|jD]}d}d}|jj|ddD]D\}}}||jtjj kr|d7}qn||jtjj krn|d7}qn|dkrR||j |dkrR|jj|ddD],\}}}||jtjj krtjj ||j<qqRdS)a 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. Tr9r)rkr:rN) r=r<rrrErZOPENrr5rrrM)r^rr@rArtr!Zincluded_countZexcluded_countrrr$rs    z%ArborescenceIterator._write_partitioncCs.|jddD]\}}}|j|vr ||j=q dS)z7 Removes partition data from the graph Tr9N)r<r)r^r=r@rArtrrr$r:s z%ArborescenceIterator._clear_partition)r-TN) r{r|r}r~rrrXrrrrrrrrr$rgs + ("r)rN)r-r)r-rrN)r-rFN)r-rFN)r-rFN)r-rFN)*r~rZ dataclassesrrenumroperatorrqueuerZnetworkxrEZnetworkx.utilsrZ recognitionr r __all__rDZSTYLESrrr*r.r/ _dispatchr r rrUrrr rrrrZdocstring_branchingZdocstring_arborescencerrrrrr$s       !OKM + < &