wgpv<ddlmZmZddlmZddlZddlmZddl m Z m Z gdZ ejdZejddZejdd Zd Ze d ejd ddZGddZ ddZddZ ddZy))heappopheappush)countN)_weight_function)not_implemented_forpairwise)all_simple_pathsis_simple_pathshortest_simple_pathsall_simple_edge_pathsct|dk(ryt|dk(r|dvStfd|Dsytt|t|k7rytfdt|DS)a,Returns True if and only if `nodes` form a simple path in `G`. A *simple path* in a graph is a nonempty sequence of nodes in which no node appears more than once in the sequence, and each adjacent pair of nodes in the sequence is adjacent in the graph. Parameters ---------- G : graph A NetworkX graph. nodes : list A list of one or more nodes in the graph `G`. Returns ------- bool Whether the given list of nodes represents a simple path in `G`. Notes ----- An empty list of nodes is not a path but a list of one node is a path. Here's an explanation why. This function operates on *node paths*. One could also consider *edge paths*. There is a bijection between node paths and edge paths. The *length of a path* is the number of edges in the path, so a list of nodes of length *n* corresponds to a path of length *n* - 1. Thus the smallest edge path would be a list of zero edges, the empty path. This corresponds to a list of one node. To convert between a node path and an edge path, you can use code like the following:: >>> from networkx.utils import pairwise >>> nodes = [0, 1, 2, 3] >>> edges = list(pairwise(nodes)) >>> edges [(0, 1), (1, 2), (2, 3)] >>> nodes = [edges[0][0]] + [v for u, v in edges] >>> nodes [0, 1, 2, 3] Examples -------- >>> G = nx.cycle_graph(4) >>> nx.is_simple_path(G, [2, 3, 0]) True >>> nx.is_simple_path(G, [0, 2]) False rFc3&K|]}|v ywN).0nGs e/home/mcse/projects/flask/flask-venv/lib/python3.12/site-packages/networkx/algorithms/simple_paths.py z!is_simple_path..Ss%!qAv%sc32K|]\}}||vywrr)ruvrs rrz!is_simple_path..[s5TQqAaDy5s)lenallsetr)rnodess` rr r srr 5zQ 5zQQx1} %u% % 3u:#e*$ 5Xe_5 55c#nKt||||D]}|g|Dcgc]}|d c}zycc}ww)alGenerate all simple paths in the graph G from source to target. A simple path is a path with no repeated nodes. Parameters ---------- G : NetworkX graph source : node Starting node for path target : nodes Single node or iterable of nodes at which to end path cutoff : integer, optional Depth to stop the search. Only paths of length <= cutoff are returned. Returns ------- path_generator: generator A generator that produces lists of simple paths. If there are no paths between the source and target within the given cutoff the generator produces no output. If it is possible to traverse the same sequence of nodes in multiple ways, namely through parallel edges, then it will be returned multiple times (once for each viable edge combination). Examples -------- This iterator generates lists of nodes:: >>> G = nx.complete_graph(4) >>> for path in nx.all_simple_paths(G, source=0, target=3): ... print(path) ... [0, 1, 2, 3] [0, 1, 3] [0, 2, 1, 3] [0, 2, 3] [0, 3] You can generate only those paths that are shorter than a certain length by using the `cutoff` keyword argument:: >>> paths = nx.all_simple_paths(G, source=0, target=3, cutoff=2) >>> print(list(paths)) [[0, 1, 3], [0, 2, 3], [0, 3]] To get each path as the corresponding list of edges, you can use the :func:`networkx.utils.pairwise` helper function:: >>> paths = nx.all_simple_paths(G, source=0, target=3) >>> for path in map(nx.utils.pairwise, paths): ... print(list(path)) [(0, 1), (1, 2), (2, 3)] [(0, 1), (1, 3)] [(0, 2), (2, 1), (1, 3)] [(0, 2), (2, 3)] [(0, 3)] Pass an iterable of nodes as target to generate all paths ending in any of several nodes:: >>> G = nx.complete_graph(4) >>> for path in nx.all_simple_paths(G, source=0, target=[3, 2]): ... print(path) ... [0, 1, 2] [0, 1, 2, 3] [0, 1, 3] [0, 1, 3, 2] [0, 2] [0, 2, 1, 3] [0, 2, 3] [0, 3] [0, 3, 1, 2] [0, 3, 2] The singleton path from ``source`` to itself is considered a simple path and is included in the results: >>> G = nx.empty_graph(5) >>> list(nx.all_simple_paths(G, source=0, target=0)) [[0]] >>> G = nx.path_graph(3) >>> list(nx.all_simple_paths(G, source=0, target={0, 1, 2})) [[0], [0, 1], [0, 1, 2]] Iterate over each path from the root nodes to the leaf nodes in a directed acyclic graph using a functional programming approach:: >>> from itertools import chain >>> from itertools import product >>> from itertools import starmap >>> from functools import partial >>> >>> chaini = chain.from_iterable >>> >>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)]) >>> roots = (v for v, d in G.in_degree() if d == 0) >>> leaves = (v for v, d in G.out_degree() if d == 0) >>> all_paths = partial(nx.all_simple_paths, G) >>> list(chaini(starmap(all_paths, product(roots, leaves)))) [[0, 1, 2], [0, 3, 2]] The same list computed using an iterative approach:: >>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)]) >>> roots = (v for v, d in G.in_degree() if d == 0) >>> leaves = (v for v, d in G.out_degree() if d == 0) >>> all_paths = [] >>> for root in roots: ... for leaf in leaves: ... paths = nx.all_simple_paths(G, root, leaf) ... all_paths.extend(paths) >>> all_paths [[0, 1, 2], [0, 3, 2]] Iterate over each path from the root nodes to the leaf nodes in a directed acyclic graph passing all leaves together to avoid unnecessary compute:: >>> G = nx.DiGraph([(0, 1), (2, 1), (1, 3), (1, 4)]) >>> roots = (v for v, d in G.in_degree() if d == 0) >>> leaves = [v for v, d in G.out_degree() if d == 0] >>> all_paths = [] >>> for root in roots: ... paths = nx.all_simple_paths(G, root, leaves) ... all_paths.extend(paths) >>> all_paths [[0, 1, 3], [0, 1, 4], [2, 1, 3], [2, 1, 4]] If parallel edges offer multiple ways to traverse a given sequence of nodes, this sequence of nodes will be returned multiple times: >>> G = nx.MultiDiGraph([(0, 1), (0, 1), (1, 2)]) >>> list(nx.all_simple_paths(G, 0, 2)) [[0, 1, 2], [0, 1, 2]] Notes ----- This algorithm uses a modified depth-first search to generate the paths [1]_. A single path can be found in $O(V+E)$ time but the number of simple paths in a graph can be very large, e.g. $O(n!)$ in the complete graph of order $n$. This function does not check that a path exists between `source` and `target`. For large graphs, this may result in very long runtimes. Consider using `has_path` to check that a path exists between `source` and `target` before calling this function on large graphs. References ---------- .. [1] R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms", Addison Wesley Professional, 3rd ed., 2001. See Also -------- all_shortest_paths, shortest_path, has_path rN)r )rsourcetargetcutoff edge_pathedges rr r ^sBD+1fffE9 hi8d$q'88898s 5 05c#*K||vrtjd|d||vr|h}n t|}||n t |dz }|dk\r|rt ||||Ed{yyy#t$r}tjd|d|d}~wwxYw72w)a Generate lists of edges for all simple paths in G from source to target. A simple path is a path with no repeated nodes. Parameters ---------- G : NetworkX graph source : node Starting node for path target : nodes Single node or iterable of nodes at which to end path cutoff : integer, optional Depth to stop the search. Only paths of length <= cutoff are returned. Returns ------- path_generator: generator A generator that produces lists of simple paths. If there are no paths between the source and target within the given cutoff the generator produces no output. For multigraphs, the list of edges have elements of the form `(u,v,k)`. Where `k` corresponds to the edge key. Examples -------- Print the simple path edges of a Graph:: >>> g = nx.Graph([(1, 2), (2, 4), (1, 3), (3, 4)]) >>> for path in sorted(nx.all_simple_edge_paths(g, 1, 4)): ... print(path) [(1, 2), (2, 4)] [(1, 3), (3, 4)] Print the simple path edges of a MultiGraph. Returned edges come with their associated keys:: >>> mg = nx.MultiGraph() >>> mg.add_edge(1, 2, key="k0") 'k0' >>> mg.add_edge(1, 2, key="k1") 'k1' >>> mg.add_edge(2, 3, key="k0") 'k0' >>> for path in sorted(nx.all_simple_edge_paths(mg, 1, 3)): ... print(path) [(1, 2, 'k0'), (2, 3, 'k0')] [(1, 2, 'k1'), (2, 3, 'k0')] When ``source`` is one of the targets, the empty path starting and ending at ``source`` without traversing any edge is considered a valid simple edge path and is included in the results: >>> G = nx.Graph() >>> G.add_node(0) >>> paths = list(nx.all_simple_edge_paths(G, 0, 0)) >>> for path in paths: ... print(path) [] >>> len(paths) 1 Notes ----- This algorithm uses a modified depth-first search to generate the paths [1]_. A single path can be found in $O(V+E)$ time but the number of simple paths in a graph can be very large, e.g. $O(n!)$ in the complete graph of order $n$. References ---------- .. [1] R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms", Addison Wesley Professional, 3rd ed., 2001. See Also -------- all_shortest_paths, shortest_path, all_simple_paths source node not in graph target node Nrr)nx NodeNotFoundr TypeErrorr_all_simple_edge_paths)rr r!r"targetserrs rr r sjQoo VHMBCC {( Q&kG)Vs1vzF {w)!VWfEEE{  Q//L "FGS P Q Fs3&B A&*BBB& B/B  BBc# Kjrfdnfd}ddi td|fgg}|rt fd|dDd}|!|j j =|^}}} ||vr"t j |gzddt dz |kr<| jz |hz r%| |<|jt|||ryyw)Nc*j|dS)NT)keysedgesnoders rz(_all_simple_edge_paths..ssaggdg.rc&j|Srr2r4s rr6z(_all_simple_edge_paths..us1774=rc32K|]}|dvs |yw)rNr)re current_paths rrz)_all_simple_edge_paths..sK!A$l2J!Ks r) is_multigraphiternextpoppopitemlistvaluesrr1append) rr r-r" get_edgesstack next_edge previous_node next_node_r:s ` @rr,r,js ??  /($" # $E KU2YKTR   IIK  " '0$ y1   ++-.)>> G = nx.cycle_graph(7) >>> paths = list(nx.shortest_simple_paths(G, 0, 3)) >>> print(paths) [[0, 1, 2, 3], [0, 6, 5, 4, 3]] You can use this function to efficiently compute the k shortest/best paths between two nodes. >>> from itertools import islice >>> def k_shortest_paths(G, source, target, k, weight=None): ... return list( ... islice(nx.shortest_simple_paths(G, source, target, weight=weight), k) ... ) >>> for path in k_shortest_paths(G, 0, 3, 2): ... print(path) [0, 1, 2, 3] [0, 6, 5, 4, 3] Notes ----- This procedure is based on algorithm by Jin Y. Yen [1]_. Finding the first $K$ paths requires $O(KN^3)$ operations. See Also -------- all_shortest_paths shortest_path all_simple_paths References ---------- .. [1] Jin Y. Yen, "Finding the K Shortest Loopless Paths in a Network", Management Science, Vol. 17, No. 11, Theory Series (Jul., 1971), pp. 712-716. r&r'r(Nc Htfdt||ddDS)Nc 3XK|]!\}}||j||#ywr) get_edge_data)rrrrwts rrz=shortest_simple_paths..length_func..s.4:Q1aA./s'*r)sumzip)pathrrRs r length_funcz*shortest_simple_paths..length_funcs*>A$QR>Q r)rLrr;) ignore_nodes ignore_edgesrL)r)r*r_bidirectional_shortest_pathr_bidirectional_dijkstra PathBufferpushrrangeaddNetworkXNoPathr@rD)rr r!rLrVshortest_path_funclistAlistB prev_pathlengthrUrWrXiroot root_lengthspurrRs` @rr r sxQoo VHMBCC Qoo VHMBCC ~ 9 a (  5 E LEI -aOLFD JJvt $5L5L1c)n- + !})$/ !ADBQx4'$(($q1u+tAw)?@A #5R%1%1% $LFD 9t+DJJ{V3T:  b*' +* 99;DJ LL I E 0((s1CF  F ?1E20AF 2FF FF c$eZdZdZdZdZdZy)r[cNt|_g|_t|_yr)rpaths sortedpathsrcounterselfs r__init__zPathBuffer.__init__,sU w rc,t|jSr)rrlrns r__len__zPathBuffer.__len__1s4##$$rct|}||jvrHt|j|t |j |f|jj |yyr)tuplerkrrlr?rmr^)rocostrU hashable_paths rr\zPathBuffer.push4sLd  * T%%d4<<.@$'G H JJNN= ) +rct|j\}}}t|}|jj ||Sr)rrlrtrkremove)rorunumrUrvs rr@zPathBuffer.pop:s9#D$4$45sDd  -( rN)__name__ __module__ __qualname__rprrr\r@rrrr[r[+s %* rr[ct|||||}|\}}} g} | | j| || } | || d} | | jd| || } | t| | fS)aReturns the shortest path between source and target ignoring nodes and edges in the containers ignore_nodes and ignore_edges. This is a custom modification of the standard bidirectional shortest path implementation at networkx.algorithms.unweighted Parameters ---------- G : NetworkX graph source : node starting node for path target : node ending node for path ignore_nodes : container of nodes nodes to ignore, optional ignore_edges : container of edges edges to ignore, optional weight : None This function accepts a weight argument for convenience of shortest_simple_paths function. It will be ignored. Returns ------- path: list List of nodes in a path from source to target. Raises ------ NetworkXNoPath If no path exists between source and target. See Also -------- shortest_path r)_bidirectional_pred_succrDinsertr) rr r!rWrXrLresultspredsuccwrUs rrYrYAsZ'q&&, UGMD$ D - A G - T!W A - Aq G - t9d?rc4r$|vs|vrtjd|d|d||k(r |di|di|fS|jr|j}|j}n|j }|j }rfd}||}||}r@|jrfd}fd} ||}| |}nfd}||}||}|di} |di} |g} |g} | r| rt | t | kr@| }g} |D]6}||D])}|| vr| j||| |<|| vs"| | |fccS8n?| }g} |D]6}||D])}|| vr|| |<| j||| vs"| | |fccS8| r| rtjd|d|d) zBidirectional shortest path helper. Returns (pred,succ,w) where pred is a dictionary of predecessors from w to the source, and succ is a dictionary of successors from w to the target. No path between  and .Ncfd}|S)Nc3:K|D] }|vs| ywrrrrrWrs riteratez>_bidirectional_pred_succ..filter_iter..iterate'q A , rrrrWs` r filter_iterz-_bidirectional_pred_succ..filter_iter Nrcfd}|S)Nc3>K|D] }||fvs |ywrrrrrX pred_iters rrzC_bidirectional_pred_succ..filter_pred_iter..iterate+&q\$q65"#G$rrrrXs` rfilter_pred_iterz2_bidirectional_pred_succ..filter_pred_iter$ rcfd}|S)Nc3>K|D] }||fvs |ywrrrrrX succ_iters rrzC_bidirectional_pred_succ..filter_succ_iter..iteraterrrrrrXs` rfilter_succ_iterz2_bidirectional_pred_succ..filter_succ_iterrrcfd}|S)Nc3LK|D]}||fvs ||fvs|ywrrrrrXrs rrz>_bidirectional_pred_succ..filter_iter..iterate6"1X$q651a& :T"#G$ $$$rrrrXs` rrz-_bidirectional_pred_succ..filter_iterrr)r)r_ is_directed predecessors successors neighborsrrD)rr r!rWrXGpredGsuccrrrrrforward_fringereverse_fringe this_levelrrs `` rr~r~s </6\3I"26(%xq IJJ 77 }}    E"E" ==?  %U+E$U+E  &E&E D>D D>DXNXN ^ ~ #n"5 5'JN -q-A}&--a0"#QDy#T1}, - -(JN -q-A}"#Q&--a0Dy#T1}, - - ^0  .vheF81E FFrc r$|vs|vrtjd|d|d||k(r"||vrtjd|dd|gfS|jr|j}|j }n|j }|j }rfd}||}||}r@|jrfd} fd } | |}| |}nfd }||}||}t||} t} t} iig}||gi||gig}ggg}|di|dig}t}| |ddt||f| |d dt||f||g}g}d }|drX|d rRd |z }| ||\}}}|||vr(||||<||d |z vr|fS|||D]}|dk(r| |||j||}n| |||j||}|A||||z}|||vr||||ks_td |||vs ||||ks}||||<| |||t||f||||gz|||<||dvs||d vs|d||d |z}|gk(s|kDs|}|d |d d }|j|d||d d z}|dr|d rRtjd|d|d)a Dijkstra's algorithm for shortest paths using bidirectional search. This function returns the shortest path between source and target ignoring nodes and edges in the containers ignore_nodes and ignore_edges. This is a custom modification of the standard Dijkstra bidirectional shortest path implementation at networkx.algorithms.weighted Parameters ---------- G : NetworkX graph source : node Starting node. target : node Ending node. weight: string, function, optional (default='weight') Edge data key or weight function corresponding to the edge weight If this is a function, the weight of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number or None to indicate a hidden edge. ignore_nodes : container of nodes nodes to ignore, optional ignore_edges : container of edges edges to ignore, optional Returns ------- length : number Shortest path length. Returns a tuple of two dictionaries keyed by node. The first dictionary stores distance from the source. The second stores the path from the source to that node. Raises ------ NetworkXNoPath If no path exists between source and target. Notes ----- Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed. The weight function can be used to hide edges by returning None. So ``weight = lambda u, v, d: 1 if d['color']=="red" else None`` will find the shortest red path. In practice bidirectional Dijkstra is much more than twice as fast as ordinary Dijkstra. Ordinary Dijkstra expands nodes in a sphere-like manner from the source. The radius of this sphere will eventually be the length of the shortest path. Bidirectional Dijkstra will expand nodes from both the source and the target, making two spheres of half this radius. Volume of the first sphere is pi*r*r while the others are 2*pi*r/2*r/2, making up half the volume. This algorithm is not guaranteed to work if edge weights are negative or are floating point numbers (overflows and roundoff errors can cause problems). See Also -------- shortest_path shortest_path_length rrrzNode r'rcfd}|S)Nc3:K|D] }|vs| ywrrrs rrz=_bidirectional_dijkstra..filter_iter..iterateJrrrrs` rrz,_bidirectional_dijkstra..filter_iterIrrcfd}|S)Nc3>K|D] }||fvs |ywrrrs rrzB_bidirectional_dijkstra..filter_pred_iter..iterateYrrrrs` rrz1_bidirectional_dijkstra..filter_pred_iterXrrcfd}|S)Nc3>K|D] }||fvs |ywrrrs rrzB_bidirectional_dijkstra..filter_succ_iter..iteratearrrrs` rrz1_bidirectional_dijkstra..filter_succ_iter`rrcfd}|S)Nc3LK|D]}||fvs ||fvs|ywrrrs rrz=_bidirectional_dijkstra..filter_iter..iteratenrrrrs` rrz,_bidirectional_dijkstra..filter_itermrrrNz,Contradictory paths found: negative weights?)r)r_r*rrrrrrrrr?rQ ValueErrorreverse)rr r!rLrWrXrrrrrrRr\r@distsrkfringeseencneighs finalpathdirdistrJr finaldistr minweightvwLength totaldistrevpaths `` rrZrZs\</6\3I"26(%xq IJJ  ?//E&"?@ @F8} }}    E"E" ==?  %U+E$U+E  &E&E !V $B D C HEvh &6(!3 4E"XF QK&! %D AQQ()QQ()U^FI C )q #g6#;' q! c ? c 1 a#g y) )Q >Aaxq!Q__Q%:; q!Q__Q%:;  Sz!}y0HE#JeCjm+$%STT$s)#x$s)A,'>'S ! VC[8T!Wa"89 %c 1  3c 1 Q! )q T  .vheF81E FFrr)NNN)NN)rLNN)heapqrr itertoolsrnetworkxr)+networkx.algorithms.shortest_paths.weightedrnetworkx.utilsrr__all__ _dispatchabler r r r,r r[rYr~rZrrrrs#H8 J6J6Zb9b9JbFbFJ'5T\"X&R'#Rj.EI<~fGTIMMGr