bfs Class Reference

[Index] [Hierarchy] [Headers]


Breadth-First-Search (BFS) algorithm. More...

#include <GTL/bfs.h>

Inherits: algorithm

Public Members


Detailed Description

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!):


bfs() [public]

Default constructor. Options default like described above.

See Also:
algorithm::algorithm

~bfs() [public virtual]

Destructor.

See Also:
algorithm::~algorithm

int run(graph& G) [public]

Performs BFS.

Parameters:
G graph.
Returns:
algorithm::GTL_OK on success, algorithm::GTL_ERROR otherwise.
See Also:
algorithm::run

int check(graph& G) [public virtual]

Checks whether the preconditions for BFS are satisfied.

Parameters:
G graph.
Returns:
algorithm::GTL_OK on success, algorithm::GTL_ERROR otherwise.
See Also:
algorithm::check

void reset() [public virtual]

Reset.

See Also:
algorithm::reset

void start_node(const node& n) [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.

Parameters:
n start-node.

node start_node() const [public]

Returns actual start-node for BFS.

Returns:
start-node.

void scan_whole_graph(bool set) [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.

Parameters:
set if true enable scanning the whole graph.
See Also:
bfs::roots_begin, bfs::roots_end

bool scan_whole_graph() const [public]

Returns true iff the whole graph will be scanned.

Returns:
true iff the whole graph will be scanned.
See Also:
bfs::roots_begin, bfs::roots_end

void calc_level(bool set) [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.

Parameters:
set if true level-number will be calculated.
See Also:
bfs::level

bool calc_level() const [public]

Returns true iff level-numbers will be calculated.

Returns:
true iff level-numbers will be calculated.
See Also:
bfs::level

void store_non_tree_edges(bool set) [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

Parameters:
set if true back_edges will be stored.
See Also:
bfs::non_tree_edges_begin, bfs::non_tree_edges_end

bool store_non_tree_edges() const [public]

Returns true iff the storing of non-tree-edges is enabled.

Returns:
true iff the storing of non-tree-edges is enabled.
See Also:
bfs::non_tree_edges_begin, bfs::non_tree_edges_end

void store_preds(bool set) [public]

Enables or disables the storing of predecessors. If enabled for every node the predecessor in BFS will be stored.

Parameters:
set if true predecessors will be stored.
See Also:
bfs::father

bool store_preds() const [public]

Returns true iff the storing of predecessors is enabled.

Returns:
true iff the storing of predecessors is enabled.
See Also:
bfs::father

bool reached(const node& n) const [public]

Checks whether node n was reached in BFS.

Parameters:
n node to be checked.
Returns:
true iff n was reached.

int bfs_num(const node& n) const [public]

BFS-Number of n. Please note that BFS-Number 0 means that this node wasn't reached.

Parameters:
n node.
Returns:
BFS-Number of n.

int operator[](const node& n) const [public]

BFS-Number of n. Please note that BFS-Number 0 means that this node wasn't reached.

Parameters:
n node.
Returns:
BFS-Number of n.

int level(const node& n) const [public]

Returns level-number of node n, if enabled during last run.

Parameters:
n node.
Returns:
level-number of n.
See Also:
bfs::calc_level

node father(const node& n) const [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().

Parameters:
n node.
Returns:
Father of n.
See Also:
bfs::store_preds

tree_edges_iterator tree_edges_begin() const [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.

Returns:
start for iteration through all edges followed in BFS.

tree_edges_iterator tree_edges_end() const [public]

End-Iterator for iteration through all edges picked in last BFS.

Returns:
end for iteration through all edges followed in BFS.

bfs_iterator begin() const [public]

Iterate through all (reached) nodes in BFS-Order.

Returns:
start for iteration through all nodes in BFS-order.

bfs_iterator end() const [public]

End-Iterator for iteration through all (reached) nodes in BFS-Order.

Returns:
end for iteration through all (reached) nodes

non_tree_edges_iterator non_tree_edges_begin() const [public]

Iterate through all non_tree_edges (if enabled).

Returns:
start for iteration through all non-tree-edges.
See Also:
bfs::store_non_tree_edges

non_tree_edges_iterator non_tree_edges_end() const [public]

End-iterator for iteration through all non-tree-edges (if enabled).

Returns:
end for iteration through all non-tree-edges.
See Also:
bfs::store_non_tree_edges

roots_iterator roots_begin() const [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.

Returns:
start for iteration through all roots in BFS-forest.
See Also:
bfs::scan_whole_graph

roots_iterator roots_end() const [public]

Iterator pointing to the end of all roots.

Returns:
end for iteration through all roots in BFS-forest.
See Also:
bfs::scan_whole_graph

int number_of_reached_nodes() const [public]

Number of nodes reached in last DFS.

Returns:
number of reached nodes.
See Also:
bfs::scan_whole_graph

void init_handler(graph& G) [public virtual]

Called at the start of BFS.

Parameters:
G graph for which BFS was invoked.

void end_handler(graph& G) [public virtual]

Called right before the end of BFS.

Parameters:
G graph for which BFS was invoked.

void popped_node_handler(graph& G, node& n) [public virtual]

Called after a node was taken out of the queue.

Parameters:
G graph for which BFS was invoked.
n node taken out of the queue.

void finished_node_handler(graph& G, node& n) [public virtual]

Called when finished with the actual node, i.e. after looking at all its neighbours.

Parameters:
G graph for which BFS was invoked.
n node taken out of the queue.

void unused_node_handler(graph& G, node& n, node& f) [public virtual]

Called when an unused node was found.

Parameters:
G graph for which BFS was invoked.
f actual node.
n unused node.

void used_node_handler(graph& G, node& n, node& f) [public virtual]

Called when an used node was found.

Parameters:
G graph for which BFS was invoked.
f actual node.
n used node.

void new_start_handler(graph& G, node& n) [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.

Parameters:
G graph for which BFS was invoked.
n start-node.

Kdoc