File Visit.h

↰ Parent directory (ADS/graph)

The visits of a GRAPH of section 9.5 and their applications, each in Theta( n + m ) time on lists or vectors of adjacency:

Definition (ADS/graph/Visit.h)

Detailed Description

  • genericVisit(), the general scheme of which the others are cases: the reached nodes R and the open ones Q start as { r }, the tree B as empty; while Q is not empty a node j is chosen from Q, and if some k adjacent to j is not in R then k joins R and Q and ( j , k ) joins B, otherwise j leaves Q. Choosing the newest node of Q gives the visit in depth, the oldest the visit in breadth; B is a tree spanning the nodes reachable from r. A cursor in the adjacency of each node makes each edge examined once;

  • bfs(), the visit in breadth with a QUEUE, which examines the nodes by increasing distance from the root r; distance() computes the distance (the minimum number of edges, the Erdos number of the example) and the tree of the shortest paths as a vector of parents, and path() reads a path from it, as printPath() does; distance() runs on an ArrayQueue or on any queue given, with enqueue() and dequeue() [see VisitCounts];

  • dfs(), the visit in depth, recursive, with a previsit and a postvisit;

  • cc(), the connected components of an unoriented graph, starting the visits from the nodes in the order in which they leave a STACK;

  • DfsSchema, the dfs-schema() of the book, which numbers the discovery time dt[ u ] and the finish time ft[ u ] of each node and says of each edge ( u , v ) whether it is in the tree T (dt[ v ] = 0), back (dt[ u ] > dt[ v ] and ft[ v ] = 0), forward (dt[ u ] < dt[ v ] and ft[ v ] != 0) or cross (the others);

  • hasCycle(), true if and only if a visit finds a back edge;

  • topsort(), the nodes by decreasing finish time, a topological order of an acyclic graph: if ( u , v ) is an edge then ft[ v ] < ft[ u ]; topsortKahn() builds one by removing the nodes with no entering edge, and isTopologicalOrder() checks one;

  • unilaterallyConnected(), true if for every two nodes u and v there is a path from u to v or one from v to u: so it is exactly when the graph of the strongly connected components, which is acyclic, has a path through all of them, i.e., when its topological order is unique, which the algorithm of Kahn finds out by never having two sources at once;

  • transpose() and scc(), the strongly connected components of an oriented graph by the algorithm of Kosaraju: a visit gives the nodes by decreasing finish time, and cc() on the transposed graph starts its visits in that order. By the Teorema 9.1, if there is an edge from the component C to C’ then ft( C ) > ft( C’ ), so the second visit meets C first and, the edge being reversed, cannot reach C’ from it.

Nil is -1 and the infinite distance is INF. The visits in depth and path() keep their recursion on an explicit stack, in the order of the recursive ones, so that a path of 10^5 nodes does not overflow the stack of the calls.

The contracts [see File Contract.h]: a visit starts from a node of the graph (and dfs() from one not visited yet, with a vector of a place per name); distance() ensures, at the level of the audits, that its distances are those of a breadth first tree, topsort() and topsortKahn() that their order is topological when the graph is acyclic, transpose() that it reverses each edge. The functions are defined in Visit.tpp.

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

    1. Moore, The shortest path through a maze, Proceedings of the International Symposium on the Theory of Switching, 285-292, 1959

    1. Tarjan, Depth-first search and linear graph algorithms, SIAM Journal on Computing 1(2), 146-160, 1972, doi:10.1137/0201010

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

  1. Sharir, A strong-connectivity algorithm and its applications in data flow analysis, Computers & Mathematics with Applications 7(1), 67-72, 1981, doi:10.1016/0898-1221(81)90008-0

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Enums

Functions

Variables