Macaulay2 » Documentation
Packages » Graphs :: depthFirstSearch
next | previous | forward | backward | up | index | toc

depthFirstSearch -- runs a depth first search on the digraph or digraph and returns the discovery time and finishing time for each vertex in the digraph

Synopsis

Description

A depth first search begins at the first vertex of a graph as a root and searches as far as possible along one branch from that root before backtracking to the next branch to the right. Discovery time denotes the order in which the vertex was searched first; finishing time denotes the time in which the vertex's descendents were all finished.

i1 : D = digraph ({{0,1},{1,3},{1,4},{4,7},{4,8},{0,2},{2,5},{2,6}},EntryMode=>"edges")

o1 = Digraph{0 => {1, 2}}
             1 => {3, 4}
             2 => {5, 6}
             3 => {}
             4 => {7, 8}
             5 => {}
             6 => {}
             7 => {}
             8 => {}

o1 : Digraph
 
i2 : dfs = depthFirstSearch D

o2 = HashTable{discoveryTime => HashTable{0 => 1 }}
                                          1 => 2
                                          2 => 12
                                          3 => 9
                                          4 => 3
                                          5 => 13
                                          6 => 15
                                          7 => 6
                                          8 => 4
               finishingTime => HashTable{0 => 18}
                                          1 => 11
                                          2 => 17
                                          3 => 10
                                          4 => 8
                                          5 => 14
                                          6 => 16
                                          7 => 7
                                          8 => 5

o2 : HashTable
 
i3 : G = cycleGraph 6

o3 = Graph{0 => {1, 5}}
           1 => {0, 2}
           2 => {1, 3}
           3 => {2, 4}
           4 => {3, 5}
           5 => {0, 4}

o3 : Graph
 
i4 : dfs = depthFirstSearch G

o4 = HashTable{discoveryTime => HashTable{0 => 1 }}
                                          1 => 10
                                          2 => 5
                                          3 => 4
                                          4 => 3
                                          5 => 2
               finishingTime => HashTable{0 => 12}
                                          1 => 11
                                          2 => 6
                                          3 => 7
                                          4 => 8
                                          5 => 9

o4 : HashTable

See also

Ways to use depthFirstSearch :

For the programmer

The object depthFirstSearch is a method function.