Graph Traversals

Graph Traversals

One of the most basic graph operations is to traverse a graph, finding the nodes accessible by following edges from some starting node. You have already seen this operation in CS2110.

We mark the vertices as visited when we have visited them to keep track of the parts of the graph that we have already explored. We start with a single vertex and mark it as visited. We then consider each outgoing edge. If an edge connects to an unvisited node, we put that node in a set of nodes to explore. Then we repeatedly remove a node from the set, mark it as visited, and repeat the process with that node. If we ever take a node out of the set and it is already marked as visited, then we ignore it. The order in which we explore the vertices depends on how we maintain the set of vertices to explore. If we use a queue, so the unvisited vertices are explored in a first-infirst- out (FIFO) fashion, then the above traversal process it is known as breadth-first search (BFS). If we use a stack, so the unvisited vertices are explored in a last-in-first-out (LIFO) fashion, this is known asdepth-first search (DFS). Of course, such a traversal will only visit nodes reachable from the start node by a directed path. Here is an implementation of traversal in a directed graph using the above abstraction. This implementation makes use of a set of vertices of type VSet to keep track of the visited vertices. It performs a BFS or DFS depending on whether the Queue or Stack package is opened. It also can traverse either the edges of the graph or of the ''reverse'' graph (in which all the edges have been reversed), based on the parameter

dir.moduleVSet = Set.Make (structtype t = Graph.vertex let compare = Graph.compareend)

open Queue (* use Queue for BFS, Stack for DFS *) let traverse v0 dir =

let disc = create()

and visited = ref VSet.emptyin

(* Expand the visited set to contain everything v goes to, * and add newly seen vertices to the stack/queue. *)

let expand(v) = lethandle_edge(e) =

let (v, v', _) = Graph.edge_info(e) in if not (VSet.mem v' !visited)

then (visited := (VSet.add v' !visited); push v' disc)

else () in

List.maphandle_edge (ifdir<0 then (Graph.incoming_rev v) else (Graph.outgoing v))

in

(visited := VSet.add v0 !visited; push v0 disc;

while (not (is_empty disc))

do ignore(expand(pop disc)) done; !visited)

Connected Components

In an undirected graph, a connected component is the set of nodes that are reachable by traversal from some node. The connected components of an undirected graph have the property that all nodes in the component are reachable from all other nodes in the component. In a directed graph, however, reachable usually means by a path in which all edges go in the positive direction, i.e. from source to destination. In directed graphs, a vertex v may be reachable from u but not vice-versa. For instance, for the graph above, the set of nodes reachable from any of the nodes 1, 2, or 3 is the set {1, 2, 3, 4}, whereas the set of nodes reachable from node 4 is just the singleton {4}. The strongly connected components in a directed graph are defined in terms of the set of nodes that are mutually accessible from one another. In other words, the strongly connected component of a node u is the set of all nodes v such that v is reachable from u by a directed path and u is reachable from v by a directed path. Equivalently, u and v lie on a directed cycle. One can show that this is an equivalence relation on nodes, and the strongly connected components are the equivalence classes. For instance, the graph above has two strongly connected components, namely {1, 2, 3} and {4}. It is possible to show that the strongly connected component from a node vi can be found by searching for nodes that are accessible from vi both in G and in Grev, where Grev has the same set of vertices as G, and has the reverse of each edge in G. Thus the following simple algorithm finds the strongly connected components.

letstrong_component v0 =

VSet.inter (traverse v0 1) (traverse v0 (-1)) letstrong_components g =

letvs = ref VSet.empty andcs = ref [] in

(List.iter (function (v) ->vs :=VSet.add v !vs) (Graph.vertices g); while (not (VSet.is_empty !vs)) do

let c = strong_component (VSet.choose !vs) in (vs := VSet.diff !vs c;

cs := c::!cs) done;

!cs)

Topological Ordering

In a directed acyclic graph (DAG), the nodes can be ordered such that each node in the ordering comes before all the other nodes to which it has outbound edges. This is called a

topological sort of the graph. In general, there is not a unique topological order for a given DAG. If there are cycles in the graph, there is no topological ordering. Topological orderings have many uses for problems ranging from job scheduling to determining the order in which to compute quantities that depend on one another (e.g., spreadsheets, order of compilation of modules in OCaml). The following figure shows a DAG and a topological ordering for the graph.

Here is a simple recursive function for computing a topological ordering, which operates by choosing a vertex with no incoming edges as the first node in the ordering, and then appending that to the result of recursively computing the ordering of the graph with that node removed. If in this process there ever is a graph where all the nodes have incoming edges, then the graph is cyclic and an error is raised. The running time of this method is O(n2), whereas the asymptotically fastest methods are O(n + m).

lettopological_rec g = letrectopological_destr gr = letvl = Graph.vertices gr in ifvl = [] then []

else

letsl = List.filter (function v ->Graph.in_degree v = 0) vlin ifsl = [] (* No vertices without incoming edges *) thenfailwith "Graph is cyclic"

else

let v = List.hdslin (Graph.remove_vertex gr v; v :: topological_destr gr) in

topological_destr (Graph.copy g)

Here is an iterative version of topological sort which has O(n + m) running time. Note that while remove_vertex is O(m) time for a single vertex, it is also O(m) time when all n vertices of the graph are removed, because each edge is considered a constant number of times overall in the process of removing all the vertices.

lettopological_iter g = let gr = Graph.copy g in letsl = ref (List.filter

(function v ->Graph.in_degree v = 0) (Graph.vertices gr))

andrevorder = ref [] in

while !sl<> [] do let v = List.hd !slin (sl := List.tl !sl; List.iter

(function e ->

matchGraph.edge_info e with (_, dst, _) -> ifGraph.in_degreedst = 1

thensl := dst :: !slelse ()) (Graph.outgoing v); Graph.remove_vertex gr v; revorder := v :: !revorder) done; ifGraph.num_vertices gr = 0 thenList.rev !revorder

(* Remaining vertices all with incoming edges *) elsefailwith "Graph is cyclic"