Depth-First-Search (DFS) algorithm More...
#include <GTL/dfs.h>
Inherits: algorithm
Encapsulates the DFS-algoritm together with all the data produced by a run of DFS.
Since there exits so much different things which one might want to calculate during a DFS this class provides basically two different customization features. First it is possible to take influence on the behaviour of this algortihm by changing some of the following options:
But the trouble with most DFS-algorithm is that one always wants to add a little bit of code somewhere in the algorithm. And then there are only two ways to get this done. The more efficient one (in terms of runtime) is to implement the DFS anew and add the new code where necessary. The other way (which is more efficient in terms of code-writing) is to take the algorithm as provided and run through the list of nodes it returns (resulting in an extra factor of 2)
Our DFS-algoritm class provides a new method to add small pieces of code to the algorithm: Handler. These are virtual functions called at certain important states of the algorithm (e.g. before a new recursive call). So the only thing to do is to derive your extended DFS from this class and to override the handlers where needed. In detail there are the following handler supported (have a look at the source code for details):
Please note: We do not claim that this set of handler is sufficient in any way. So if you believe that some new handler is needed urgently please let us know.
There is a lot of information stored during DFS (e.g. nodes in dfs-order, list of non-tree edges). Some of it can be obtained directly by using the corresponding member-function (e.g. dfs::dfs_num , but all information that can be thought of as a list (e.g. nodes in dfs-order) can be accessed through iterators. In detail these are (of course depending on what options are chosen!):
[public]
Default constructor. Options default like described above.
[public virtual]
Destructor.
[public]
Performs DFS.
G | graph. |
algorithm::GTL_OK
on success,
algorithm::GTL_ERROR
otherwise.[public virtual]
Checks whether the preconditions for DFS are satisfied.
G | graph. |
algorithm::GTL_OK
on success,
algorithm::GTL_ERROR
otherwise.[public virtual]
Reset. Please note that options like scanning of whole graph are not reset, but the chosen start node will be set back. So if applying this algorithm more than once with the same start node, it has to be set explicitly before every run.
[public]
Sets start-node for DFS. The default start-node is the invalid node
node()
, in this case an arbitrary node is chosen and
stored, when DFS is run.
n | start-node. |
[public]
Returns start-node for DFS.
[public]
Enables or disables scanning of the whole graph. If enabled and the DFS started at the given start-node stops without having touched all nodes, it will be continued with the next unused node, and so on until all nodes were used. This makes sure that for every node dfs_number is defined.
On the other hand, if this feature is disabled, one will be able to check what nodes can be reached, when starting a DFS at the start-node, because for those not reached dfs-number will be 0.
set | if true enable scanning the whole graph. |
[public]
Returns true iff the whole graph will be scanned.
[public]
Enables or Disables the calculation of the completion number.
set | if true completion-numbers will be calculated. |
[public]
Returns true iff completion-numbers will be calculated.
[public]
Enables or disables the storing of predecessors. If enabled for every node the predecessor in DFS will be stored.
set | if true predecessors will be stored. |
[public]
Returns true iff the storing of predecessors is enabled.
[public]
Enables the storing of back-edges. If enabled the list of
non-tree-edges can
be traversed in the order they occured using
non_tree_edges_iterator
set | if true non_tree_edges will be stored. |
[public]
Returns true iff the storing of non-tree-edges is enabled.
[public]
Checks whether node n
was reached in last DFS.
n | node to be checked. |
n
was reached.[public]
DFS-Number of n
. Please note that DFS-Number 0 means
that this node wasn't reached.
n | node. |
n
.[public]
DFS-Number of n
. Please note that DFS-Number 0 means
that this node wasn't reached.
n | node. |
n
.[public]
Returns completion-number of node n
, if enabled in last
run.
n | node. |
n
.[public]
Returns father of node n
in DFS-forest. If
n
is a root
in the forest or wasn't reached the return
value is node()
.
n | node. |
n
.[public]
Iterate through all edges picked in last DFS. Please note that this edges not always form a tree. In case the graph is not (strongly) connected they form a forest.
[public]
End-Iterator for iteration through all edges picked in last DFS.
[public]
Iterate through all (reached) nodes in DFS-order.
[public]
End-Iterator for iteration through all (reached) nodes in DFS-order.
[public]
Iterate through all non_tree_edges (if enabled).
[public]
End-iterator for iteration through all non-tree-edges (if enabled).
[public]
Iterator pointing towards the first root in the DFS-forest.
Please note that intstead of pointing directly towards the node
(i.e. *it
is of type node) the iterator points towards
a dfs-iterator, which represents the root (i.e. *it
is of type dfs_iterator
).
Using this technique
makes it possible not only to obtain all the roots in the forest,
but also the whole trees associated with each one. This can be achieved
because a root_iterator
specifies the exact position of
the root in the DFS-ordering and by definition of DFS all the descendents of
the root, i.e. the whole tree, will come later in DFS, such that by
incrementing the dfs_iterator
, a
roots_iterator
points at, one can traverse the whole tree with this given root.
Of course if the root isn't the last node in the DFS-forest on will
also traverse all following trees, but since the first node of such
a tree one will discover is its root, the successor of the
roots_iterator
can be used as end-iterator.
[public]
Iterator pointing to the end of all roots.
[public]
Number of nodes reached in last DFS.
[public virtual]
Handler called before the start of DFS.
G | graph for which DFS was invoked. |
[public virtual]
Handler called at the end of DFS.
G | graph for which DFS was invoked. |
[public virtual]
Handler called when touching node n
.
G | graph for which DFS was invoked. |
f | predecessor. |
n | actual node. |
[public virtual]
Handler called after all the adjacent edges of n
have been
examined.
G | graph for which DFS was invoked. |
f | predecessor. |
n | actual node. |
[public virtual]
Handler called when a unused node n
connected to the
actual node by e
is found.
G | graph for which DFS was invoked. |
e | edge connecting the actual node to the unused one. |
n | unused node. |
[public virtual]
Handler called after the algorithm return from the subtree starting
at n
connected to the actual node by e
.
G | graph for which DFS was invoked. |
e | edge connecting the actual node to the unused one. |
n | unused node. |
[public virtual]
Handler called when a already marked node n
connected
to the actual node by e
is found during the search of all
adjacent edges of the actual node
G | graph for which DFS was invoked. |
e | edge connecting the actual node to the old one. |
n | used node. |
[public virtual]
Called when DFS is started with start-node
n
. This is particularly useful when
DFS was invoked with the scan_whole_graph
option.
G | graph for which DFS was invoked. |
n | start-node. |
Kdoc |