Breadth-First-Search (BFS) algorithm. More...
#include <GTL/bfs.h>
Inherits: algorithm
Encapsulates the BFS-algorithm together with all data produced by it. There are a few parameters, which on the one hand influence the behaviour of BFS (e.g. start-node) and on the other hand toggle the storing of extra information, such as the level-number of each node. In detail these are:
Please note that the algorithm always starts with the given start-node (if none was given, the first node is chosen and stored, thus after BFS the root of the tree is always accesible via bfs::start_node and continues until no more unused nodes are reachable from already used ones. Thus if the graph isn't connected not all nodes will be reached. If bfs::scan_whole_graph isn't set the BFS stops here. If it is set, the BFS will be continued with the next unused node and so on until all nodes were used.
For further customization a few virtual functions, so called handler, are called at crucial stages of the algorithm. In this basic implementation all of these handler are empty. So if one wants to add only a few lines of code (e.g. some new numbering) he is likely to take this class as base-class and override the handler where neccessary. In detail these are (please look at the source code to see where they are called):
Please note: We do not claim that the set of handler provided 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 BFS (e.g. nodes in bfs-order, list of non-tree edges). Some of it can be obtained directly by using the corresponding member-function (e.g. bfs::bfs_num , but all information that can be thought of as a list (e.g. nodes in bfs-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 BFS.
G | graph. |
algorithm::GTL_OK
on success,
algorithm::GTL_ERROR
otherwise.[public virtual]
Checks whether the preconditions for BFS are satisfied.
G | graph. |
algorithm::GTL_OK
on success,
algorithm::GTL_ERROR
otherwise.[public virtual]
Reset.
[public]
Sets start-node for BFS. The default start-node is the invalid node
node()
, in this case an arbitrary node is chosen and
stored when BFS is run.
n | start-node. |
[public]
Returns actual start-node for BFS.
[public]
Enables or disables scanning of the whole graph. If enabled and the BFS 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 bfs_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 BFS at the start-node, because for those not reached bfs-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 level-numbers for each node. If enabled each node gets a level-number meaning its distance from the start-node.
set | if true level-number will be calculated. |
[public]
Returns true iff level-numbers will be calculated.
[public]
Enables the storing of non-tree-edges. If enabled the list of
non-tree-edges can be traversed in the order they occured using
back_edges_iterator
set | if true back_edges will be stored. |
[public]
Returns true iff the storing of non-tree-edges is enabled.
[public]
Enables or disables the storing of predecessors. If enabled for every node the predecessor in BFS will be stored.
set | if true predecessors will be stored. |
[public]
Returns true iff the storing of predecessors is enabled.
[public]
Checks whether node n
was reached in BFS.
n | node to be checked. |
n
was reached.[public]
BFS-Number of n
. Please note that BFS-Number 0 means
that this node wasn't reached.
n | node. |
n
.[public]
BFS-Number of n
. Please note that BFS-Number 0 means
that this node wasn't reached.
n | node. |
n
.[public]
Returns level-number of node n
, if enabled during last
run.
n | node. |
n
.[public]
Returns father of node n
in BFS-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 BFS. Please note that this edges not always form a tree. In case the graph is not (strongly) connected and the whole graph was scanned, they form a forest.
[public]
End-Iterator for iteration through all edges picked in last BFS.
[public]
Iterate through all (reached) nodes in BFS-Order.
[public]
End-Iterator for iteration through all (reached) nodes in BFS-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 BFS-forest.
Please note that intstead of pointing directly towards the node
(i.e. *it
is of type node) the iterator points towards
a bfs-iterator, which represents the root (i.e. *it
is of type bfs_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 BFS-ordering and by definition of BFS all the descendents of
the root, i.e. the whole tree below, will come later in BFS, such that by
incrementing the bfs_iterator
, a
roots_iterator
refers to,
one can traverse the whole tree with this given root.
Of course if the root isn't the last node in the
BFS-forest all following trees will be traversed, too.
But since the first node of such
a tree, that will be discovered, 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]
Called at the start of BFS.
G | graph for which BFS was invoked. |
[public virtual]
Called right before the end of BFS.
G | graph for which BFS was invoked. |
[public virtual]
Called after a node was taken out of the queue.
G | graph for which BFS was invoked. |
n | node taken out of the queue. |
[public virtual]
Called when finished with the actual node, i.e. after looking at all its neighbours.
G | graph for which BFS was invoked. |
n | node taken out of the queue. |
[public virtual]
Called when an unused node was found.
G | graph for which BFS was invoked. |
f | actual node. |
n | unused node. |
[public virtual]
Called when an used node was found.
G | graph for which BFS was invoked. |
f | actual node. |
n | used node. |
[public virtual]
Called when BFS is started with start-node
n
. This is particularly useful when
BFS was invoked with the scan_whole_graph
option.
G | graph for which BFS was invoked. |
n | start-node. |
Kdoc |