File Paths.h

↰ Parent directory (ADS/graph)

Problems on the paths of a GRAPH solved by the visits of section 9.5 and by the topological order, each in O( n + m ) time on lists or vectors of adjacency unless said otherwise:

Definition (ADS/graph/Paths.h)

Detailed Description

  • countShortestPaths(), the number of distinct shortest paths, in edges, from s to each node: a visit in breadth in which a node discovered from u inherits the count of u and adds that of every other u’ with an edge ( u’ , v ) and d[ u’ ] + 1 = d[ v ], right since all the nodes at distance d - 1 leave the queue before those at distance d. The counts grow as :math:` 2^{n/3} ` on a chain of diamonds, and are given modulo :math:` 2^{64} `. They are the first pass of the algorithm of Brandes for the betweenness centrality, which adds a second pass in the reverse order of the visit;

  • multiSourceDistance(), the distance from the nearest of a set S of sources, all of them at distance 0 in the queue, and the tree of the shortest paths as a forest rooted at the sources; it is the visit from a new node joined to the sources, without the node. setDistance() is the distance between two sets of nodes, the visit from the first one stopping at the first node of the second, 0 if they meet;

  • longestPathLayering(), for each node of an acyclic graph the edges of a longest path ending at it, by the algorithm of Kahn: a node gets its layer when its last entering edge is removed, one more than the largest layer of its predecessors. The layers are antichains, and by the theorem of Mirsky (the dual of that of Dilworth) their number, one more than the longest path, is the least number of antichains that cover the nodes, e.g., the fewest rounds for jobs with precedences, or the levels of the drawing of Sugiyama, Tagawa and Toda. A cycle leaves some node with an entering edge forever, and breaks the precondition;

  • dagLongestPaths(), for each node the largest total length of a path leaving it, along the edges kept by a predicate (all of them by default), with the weights of the graph as lengths (1 each if it has none): L[ u ] is the largest of 0 and of w( u , v ) + L[ v ] over the kept edges ( u , v ), by a memoized visit in depth, iterative, of the graph of the kept edges, which must be acyclic. With the predicate an unoriented graph gives an acyclic one, e.g., keeping the edges that go downhill on a map of altitudes. It is the critical path method of Kelley and Walker; dagShortestPaths() of File ShortestPaths.h with the lengths negated gives the same lengths from one source, while the longest path of a graph with cycles is NP-hard (section 18.4);

  • simpleCycles(), the simple oriented cycles through s, by the algorithm of Johnson: a visit in depth that blocks the nodes on its stack and keeps them blocked, with the lists B of the nodes waiting on them, while no path from them to s avoids the stack, so that no branch is explored without a cycle at its end. It takes O( ( n + m ) ( c + 1 ) ) time for c cycles, against the backtracking of section 16, which tries every simple path from s and may take exponential time between two cycles; the bound of Tarjan’s algorithm of 1973 is O( n m ( c + 1 ) ). The complete digraph of n nodes has :math:` lfloor e ( n - 1 )! rfloor - 1 ` cycles through a node;

  • refuelingStops(), the fewest stops of a trip from 0 to L along a line with stations at D, where a full tank lasts R: the greedy of chapter 14 that, when the next station is out of reach, stops at the last one in reach. It is a shortest path in the graph whose edges join the points at distance at most R, which the greedy finds in O( n ) by the exchange argument: a trip with fewer stops would get past the farthest point of the greedy at some stop, and so would the greedy.

Nil is NIL and the infinite distance INF [see File Visit.h].

The contracts [see File Contract.h]: the sources and the starts are nodes, the sets are characteristic vectors with a place per name, the graph of longestPathLayering() and the edges kept by dagLongestPaths() make no cycle (checked as they go), simpleCycles() needs an oriented graph, and refuelingStops() a sorted D in [ 0 , L ] with L , R >= 0. At the level of the audits countShortestPaths() ensures that its counts satisfy their recurrence on the levels of distance(), multiSourceDistance() that its distances are those of a breadth first forest, longestPathLayering() and dagLongestPaths() that each edge respects their lengths and that each length is reached by an edge, and refuelingStops() that its stops make the trip. The functions are defined in Paths.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 9.5 and 14, https://algoritmicamente.it/materiali/libro/capitoli/cap09.pdf

    1. Kahn, Topological sorting of large networks, Communications of the ACM 5(11), 558-562, 1962, doi:10.1145/368996.369025

  1. Brandes, A faster algorithm for betweenness centrality, Journal of Mathematical Sociology 25(2), 163-177, 2001, doi:10.1080/0022250X.2001.9990249

  1. Mirsky, A dual of Dilworth’s decomposition theorem, The American Mathematical Monthly 78(8), 876-877, 1971, doi:10.2307/2316481

  1. Sugiyama, S. Tagawa, M. Toda, Methods for visual understanding of hierarchical system structures, IEEE Transactions on Systems, Man, and Cybernetics 11(2), 109-125, 1981, doi:10.1109/TSMC.1981.4308636

    1. Kelley, M. R. Walker, Critical-path planning and scheduling, Proceedings of the Eastern Joint Computer Conference, 160-173, 1959, doi:10.1145/1460299.1460318

    1. Johnson, Finding all the elementary circuits of a directed graph, SIAM Journal on Computing 4(1), 77-84, 1975, doi:10.1137/0204007

    1. Tarjan, Enumeration of the elementary circuits of a directed graph, SIAM Journal on Computing 2(3), 211-216, 1973, doi:10.1137/0202017

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions

Typedefs