Next: Shortest Path Algorithms ( Up: Graph Algorithms Previous: Graph Algorithms   Contents   Index

# Basic Graph Algorithms ( basic_graph_alg )

 bool TOPSORT(const graph& G, node_array< int> & ord) TOPSORT takes as argument a directed graph G(V, E) . It sorts G topologically (if G is acyclic) by computing for every node v V an integer ord[v] such that 1 < = ord[v] < = | V| and ord[v] < ord[w] for all edges (v, w) E . TOPSORT returns true if G is acyclic and false otherwise. The algorithm ([50]) has running time O(| V| + | E|) . bool TOPSORT(const graph& G, list< node> & L) a variant of TOPSORT that computes a list L of nodes in topological order (if G is acyclic). It returns true if G is acyclic and false otherwise. bool TOPSORT1(graph& G) a variant of TOPSORT that rearranges nodes and edges of G in topological order (edges are sorted by the topological number of their target nodes). list< node> DFS(const graph& G, node s, node_array< bool> & reached) DFS takes as argument a directed graph G(V, E) , a node s of G and a node_array reached of boolean values. It performs a depth first search starting at s visiting all reachable nodes v with reached[v] = false. For every visited node v reached[v] is changed to true. DFS returns the list of all reached nodes. The algorithm ([85]) has running time O(| V| + | E|) . list< edge> DFS_NUM(const graph& G, node_array< int> & dfsnum, node_array< int> & compnum) DFS_NUM takes as argument a directed graph G(V, E) . It performs a depth first search of G numbering the nodes of G in two different ways. dfsnum is a numbering with respect to the calling time and compnum a numbering with respect to the completion time of the recursive calls. DFS_NUM returns a depth first search forest of G (list of tree edges). The algorithm ([85]) has running time O(| V| + | E|) . list< node> BFS(const graph& G, node s, node_array< int> & dist) BFS takes as argument a directed graph G(V, E) ,a node s of G and a node array dist of integers. It performs a breadth first search starting at s visiting all nodes v with dist[v] = - 1 reachable from s . The dist value of every visited node is replaced by its distance to s . BFS returns the list of all visited nodes. The algorithm ([58]) has running time O(| V| + | E|) . list< node> BFS(const graph& G, node s, node_array< int> & dist, node_array< edge> & pred) performs a bread first search as described above and computes for every node v the predecessor edge pred[v] in the bfs shortest path tree. (You can use the function COMPUTE_SHORTEST_PATH to extract paths from the tree (cf. Section shortest_path).) int COMPONENTS(const graph& G, node_array< int> & compnum) COMPONENTS takes a graph G(V, E) as argument and computes the connected components of the underlying undirected graph, i.e., for every node v V an integer compnum[v] from [0...c - 1] where c is the number of connected components of G and v belongs to the i -th connected component iff compnum[v] = i . COMPONENTS returns c . The algorithm ([58]) has running time O(| V| + | E|) . int STRONG_COMPONENTS(const graph& G, node_array< int> & compnum) STRONG_COMPONENTS takes a directed graph G(V, E) as argument and computes for every node v V an integer compnum[v] from [0...c - 1] where c is the number of strongly connected components of G and v belongs to the i -th strongly connected component iff compnum[v] = i . STRONG_COMPONENTS returns c . The algorithm ([58]) has running time O(| V| + | E|) . int BICONNECTED_COMPONENTS(const graph& G, edge_array< int> & compnum) BICONNECTED_COMPONENTS computes the biconnected components of the undirected version of G . A biconnected component of an undirected graph is a maximal biconnected subgraph and a biconnected graph is a graph which cannot be disconnected by removing one of its nodes. A graph having only one node is biconnected. Let c be the number of biconnected component and let c' be the number of biconnected components containing at least one edge, c - c' is the number of isolated nodes in G , where a node v is isolated if is not connected to a node different from v (it may be incident to self-loops). The function returns c and labels each edge of G (which is not a self-loop) by an integer in [0...c' - 1] . Two edges receive the same label iff they belong to the same biconnected component. The edge labels are returned in compnum. Be aware that self-loops receive no label since self-loops are ignored when interpreting a graph as an undirected graph. The algorithm ([21]) has running time O(| V| + | E|) . GRAPH< node,edge> TRANSITIVE_CLOSURE(const graph& G) TRANSITIVE_CLOSURE takes a directed graph G = (V, E) as argument and computes the transitive closure of G . It returns a directed graph G' = (V', E') such that G'.inf(.) is a bijective mapping from V' to V and (v, w) E' there is a path from G'.inf(v') to G'.inf(w') in G . (The edge information of G' is undefined.) The algorithm ([40]) has running time O(| V|*| E|) . GRAPH< node,edge> TRANSITIVE_REDUCTION(const graph& G) TRANSITIVE_REDUCTION takes a directed graph G = (V, E) as argument and computes the transitive reduction of G . It returns a directed graph G' = (V', E') . The function G'.inf(.) is a bijective mapping from V' to V . The graph G and G' have the same reachability relation, i.e. there is a path from v' to w' in G' there is a path from G'.inf(v') to G'.inf(w') in G . And there is no graph with the previous property and less edges than G' . (The edge information of G' is undefined.) The algorithm ([40]) has running time O(| V|*| E|) . void MAKE_TRANSITIVELY_CLOSED(graph& G) MAKE_TRANSITIVELY_CLOSED transforms G into its transitive closure by adding edges. void MAKE_TRANSITIVELY_REDUCED(graph& G) MAKE_TRANSITIVELY_REDUCED transforms G into its transitive reduction by removing edges.

Next: Shortest Path Algorithms ( Up: Graph Algorithms Previous: Graph Algorithms   Contents   Index
Christian Uhrig 2017-04-07