 |
Analysis Software
Documentation for sPHENIX simulation software
|
|
Analysis Software
Documentation for sPHENIX simulation software
|
Breadth-First-Search (BFS) algorithm. More...
#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/bfs.h>
Inheritance diagram for bfs: Collaboration diagram for bfs:Public Types | |
| typedef list< edge > ::const_iterator | tree_edges_iterator |
| Iterator for tree-edges. | |
| typedef list< node > ::const_iterator | bfs_iterator |
| Iterator for nodes in BFS-order. | |
| typedef list< edge > ::const_iterator | non_tree_edges_iterator |
| Iterator for non-tree-edges. | |
| typedef list< bfs_iterator > ::const_iterator | roots_iterator |
| Iterator for roots of trees in BFS-forest. | |
| Public Types inherited from algorithm | |
| enum | { GTL_OK = 1, GTL_ERROR = 0 } |
| Return values for algorithm::check and algorithm::run. More... | |
Public Member Functions | |
| bfs () | |
| Constructor. | |
| virtual | ~bfs () |
| Destructor. | |
| int | run (graph &G) |
| Applies algorithm to graph g. | |
| virtual int | check (graph &G) |
| Checks whether the preconditions for BFS are satisfied. | |
| virtual void | reset () |
| Resets algorithm. | |
| void | start_node (const node &n) |
| Sets start-node for BFS. | |
| node | start_node () const |
| Returns start-node for BFS. | |
| void | scan_whole_graph (bool set) |
| Enables or disables scanning of the whole graph. | |
| bool | scan_whole_graph () const |
| Returns whether the whole graph will be scanned. | |
| void | calc_level (bool set) |
| Enables or disables the calculation of level-numbers for each node. | |
| bool | calc_level () const |
| Returns whether level-numbers will be calculated. | |
| void | store_non_tree_edges (bool set) |
| Enables or disables the storing of non-tree-edges. | |
| bool | store_non_tree_edges () const |
| Returns whether the storing of non-tree-edges is enabled. | |
| void | store_preds (bool set) |
| Enables or disables the storing of predecessors. | |
| bool | store_preds () const |
| Returns whether the storing of predecessors is enabled. | |
| bool | reached (const node &n) const |
| Checks whether node n was reached in BFS. | |
| int | bfs_num (const node &n) const |
| BFS-number of n. | |
| int | operator[] (const node &n) const |
| BFS-number of n. | |
| int | level (const node &n) const |
| Level-number of node n. | |
| node | father (const node &n) const |
| Father of node n in BFS-forest. | |
| tree_edges_iterator | tree_edges_begin () const |
| Iterate through all tree-edges of last BFS. | |
| tree_edges_iterator | tree_edges_end () const |
| End-iterator for iteration through all tree-edges picked of last BFS. | |
| bfs_iterator | begin () const |
| Iterate through all (reached) nodes in BFS-Order. | |
| bfs_iterator | end () const |
| End-iterator for iteration through all (reached) nodes in BFS-Order. | |
| non_tree_edges_iterator | non_tree_edges_begin () const |
| Iterate through all non-tree-edges (if enabled). | |
| non_tree_edges_iterator | non_tree_edges_end () const |
| End-iterator for iteration through all non-tree-edges (if enabled). | |
| roots_iterator | roots_begin () const |
| Iterator pointing towards the first root in the BFS-forest. | |
| roots_iterator | roots_end () const |
| Iterator pointing to the end of all roots. | |
| int | number_of_reached_nodes () const |
| Number of nodes reached in last BFS. | |
| virtual void | init_handler (graph &G) |
| Called at the start of BFS. | |
| virtual void | end_handler (graph &G) |
| Called right before the end of BFS. | |
| virtual void | popped_node_handler (graph &G, node &n) |
| Called after the node n was taken out of the queue. | |
| virtual void | finished_node_handler (graph &G, node &n) |
| Called when finished with the node n. | |
| virtual void | unused_node_handler (graph &G, node &n, node &f) |
| Called when an unused node n was discovered. | |
| virtual void | used_node_handler (graph &G, node &n, node &f) |
| Called when an used node n was found. | |
| virtual void | new_start_handler (graph &G, node &n) |
| Called when BFS is started with start-node n. | |
| Public Member Functions inherited from algorithm | |
| algorithm () | |
| Creates an algorithm object. | |
| virtual | ~algorithm () |
| Destroys the algorithm object. | |
Protected Attributes | |
| int | act_bfs_num |
| BFS number that will be assigned next. | |
| deque< node > | qu |
| queue used in BFS. | |
| list< node > | bfs_order |
| List of nodes in BFS-order. | |
| list< edge > | tree |
| List of all edges of the BFS-tree. | |
| node_map< int > | bfs_number |
| Stores BFS-number of nodes. | |
| int | reached_nodes |
| Number of nodes reached so far. | |
| list< bfs_iterator > | roots |
| List of all roots of the BFS-tree. | |
| bool | whole_graph |
| Stores whether whole graph will be scanned. | |
| node | start |
| Stores start node. | |
| node_map< int > * | level_number |
| Stores level number of each node (if enabled) | |
| list< edge > * | non_tree |
| List of non-tree edges (if enabled) | |
| node_map< node > * | preds |
| Stores father of each node (if enabled) | |
Private Member Functions | |
| void | bfs_sub (graph &, const node &, edge_map< int > *) |
Breadth-First-Search (BFS) 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. bfs::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 handlers 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!):
Definition at line 87 of file bfs.h.
View newest version in sPHENIX GitHub at line 87 of file bfs.h
| typedef list<node>::const_iterator bfs::bfs_iterator |
| typedef list<edge>::const_iterator bfs::non_tree_edges_iterator |
| typedef list<bfs_iterator>::const_iterator bfs::roots_iterator |
| typedef list<edge>::const_iterator bfs::tree_edges_iterator |
| __GTL_BEGIN_NAMESPACE bfs::bfs | ( | ) |
Constructor.
Definition at line 29 of file bfs.cpp.
View newest version in sPHENIX GitHub at line 29 of file bfs.cpp
References act_bfs_num, level_number, non_tree, preds, reached_nodes, and whole_graph.
|
virtual |
|
inline |
|
inline |
Definition at line 159 of file bfs.cpp.
View newest version in sPHENIX GitHub at line 159 of file bfs.cpp
References act_bfs_num, node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), bfs_number, bfs_order, end(), finished_node_handler(), it, level_number, non_tree, node::opposite(), popped_node_handler(), preds, qu, reached_nodes, roots, Acts::Test::tmp(), tree, unused_node_handler(), and used_node_handler().
Referenced by run().
Here is the call graph for this function: Here is the caller graph for this function:| void bfs::calc_level | ( | bool | set | ) |
Enables or disables the calculation of level-numbers for each node.
If enabled each node gets a level-number, i.e. its distance from the start-node.
| set | if true level-number will be calculated. |
Definition at line 51 of file bfs.cpp.
View newest version in sPHENIX GitHub at line 51 of file bfs.cpp
References level_number.
Referenced by node::excentricity().
Here is the caller graph for this function:
|
inline |
Returns whether level-numbers will be calculated.
| true | iff level-numbers will be calculated. |
Definition at line 183 of file bfs.h.
View newest version in sPHENIX GitHub at line 183 of file bfs.h
|
inlinevirtual |
Checks whether the preconditions for BFS are satisfied.
Currently there aren't any restricitions for the BFS algorithm.
| G | graph. |
| algorithm::GTL_OK | if algorithm can be applied |
| algorithm::GTL_ERROR | otherwise. |
Implements algorithm.
Definition at line 112 of file bfs.h.
View newest version in sPHENIX GitHub at line 112 of file bfs.h
References algorithm::GTL_OK.
|
inline |
End-iterator for iteration through all (reached) nodes in BFS-Order.
Definition at line 332 of file bfs.h.
View newest version in sPHENIX GitHub at line 332 of file bfs.h
Referenced by bfs_sub(), node::excentricity(), and main().
Here is the caller graph for this function:
|
inlinevirtual |
Father of node n in BFS-forest.
If n is a root in the forest or wasn't reached the return value is the invalid node node::node().
Please note that this requires that this option was enabled during last run.
| n | node. |
Definition at line 284 of file bfs.h.
View newest version in sPHENIX GitHub at line 284 of file bfs.h
Called when finished with the node n.
A node is finished after all its neighbors have been visited.
| G | graph for which BFS was invoked. |
| n | finished node. |
Definition at line 449 of file bfs.h.
View newest version in sPHENIX GitHub at line 449 of file bfs.h
Referenced by bfs_sub().
Here is the caller graph for this function:
|
inlinevirtual |
|
inline |
Level-number of node n.
Please note that this requires that this option was enabled during last run.
| n | node. |
Definition at line 268 of file bfs.h.
View newest version in sPHENIX GitHub at line 268 of file bfs.h
Referenced by node::excentricity().
Here is the caller graph for this function: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. |
Definition at line 486 of file bfs.h.
View newest version in sPHENIX GitHub at line 486 of file bfs.h
Referenced by run().
Here is the caller graph for this function:
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
virtual |
Resets algorithm.
Prepares the algorithm to be applied to another graph. Please note: The options an algorithm may support do not get reset by this. It is just to reset internally used datastructures.
Implements algorithm.
Definition at line 85 of file bfs.cpp.
View newest version in sPHENIX GitHub at line 85 of file bfs.cpp
References act_bfs_num, bfs_order, non_tree, reached_nodes, roots, and tree.
|
inline |
Iterator pointing towards the first root in the BFS-forest.
Please note that instead 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 also will be traversed. 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.
Definition at line 393 of file bfs.h.
View newest version in sPHENIX GitHub at line 393 of file bfs.h
|
inline |
Iterator pointing to the end of all roots.
Definition at line 402 of file bfs.h.
View newest version in sPHENIX GitHub at line 402 of file bfs.h
|
virtual |
Applies algorithm to graph g.
| g | graph |
| algorithm::GTL_OK | on success |
| algorithm::GTL_ERROR | otherwise |
Implements algorithm.
Definition at line 98 of file bfs.cpp.
View newest version in sPHENIX GitHub at line 98 of file bfs.cpp
References bfs_number, bfs_sub(), graph::choose_node(), end_handler(), forall_nodes, ne_map< Key, Value, Graph, Alloc >::init(), init_handler(), level_number, new_start_handler(), non_tree, graph::number_of_nodes(), preds, reached_nodes, start, and whole_graph.
Referenced by node::excentricity(), and main().
Here is the call graph for this function: Here is the caller graph for this function:
|
inline |
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::bfs_num is defined.
If this feature is disabled, you are able to check what nodes can be reached, when starting a BFS at the start-node, because for those not reached bfs::bfs_num will be 0.
| set | if true enable scanning the whole graph. |
Definition at line 155 of file bfs.h.
View newest version in sPHENIX GitHub at line 155 of file bfs.h
|
inline |
Returns whether the whole graph will be scanned.
| true | iff the whole graph will be scanned. |
Definition at line 163 of file bfs.h.
View newest version in sPHENIX GitHub at line 163 of file bfs.h
|
inline |
Sets start-node for BFS.
The default start-node is the invalid node (node::node()), in this case an arbitrary node is chosen and stored when BFS is run.
| n | start-node. |
Definition at line 129 of file bfs.h.
View newest version in sPHENIX GitHub at line 129 of file bfs.h
Referenced by node::excentricity(), and main().
Here is the caller graph for this function:
|
inline |
| void bfs::store_non_tree_edges | ( | bool | set | ) |
Enables or disables the storing of non-tree-edges.
If enabled all non-tree-edges will be stored in the order they occured.
| set | if true non-tree-edges will be stored. |
Definition at line 71 of file bfs.cpp.
View newest version in sPHENIX GitHub at line 71 of file bfs.cpp
References non_tree.
|
inline |
| void bfs::store_preds | ( | bool | set | ) |
Enables or disables the storing of predecessors.
If enabled for every node the predecessor in the BFS-forest will be stored.
| set | if true predecessors will be stored. |
Definition at line 61 of file bfs.cpp.
View newest version in sPHENIX GitHub at line 61 of file bfs.cpp
References preds.
|
inline |
Returns whether the storing of predecessors is enabled.
| true | iff the storing of predecessors is enabled. |
Definition at line 223 of file bfs.h.
View newest version in sPHENIX GitHub at line 223 of file bfs.h
|
inline |
Iterate through all tree-edges of 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.
Definition at line 301 of file bfs.h.
View newest version in sPHENIX GitHub at line 301 of file bfs.h
References tree.
|
inline |
Called when an unused node n was discovered.
This means that the actual node's f neighbor n was not previously discovered.
| G | graph for which BFS was invoked. |
| n | unused node. |
| f | actual node. |
Definition at line 461 of file bfs.h.
View newest version in sPHENIX GitHub at line 461 of file bfs.h
Referenced by bfs_sub().
Here is the caller graph for this function:Called when an used node n was found.
This means that the actual node's (f) neighbor n has already been discovered.
| G | graph for which BFS was invoked. |
| n | used node. |
| f | actual node. |
Definition at line 473 of file bfs.h.
View newest version in sPHENIX GitHub at line 473 of file bfs.h
Referenced by bfs_sub().
Here is the caller graph for this function:
|
protected |
|
protected |
|
protected |
|
protected |
Stores level number of each node (if enabled)
Definition at line 562 of file bfs.h.
View newest version in sPHENIX GitHub at line 562 of file bfs.h
Referenced by bfs(), bfs_sub(), calc_level(), run(), and ~bfs().
|
protected |
Stores father of each node (if enabled)
Definition at line 576 of file bfs.h.
View newest version in sPHENIX GitHub at line 576 of file bfs.h
Referenced by bfs(), bfs_sub(), run(), store_preds(), and ~bfs().
|
protected |
|
protected |
|
protected |
List of all roots of the BFS-tree.
Definition at line 537 of file bfs.h.
View newest version in sPHENIX GitHub at line 537 of file bfs.h
|
protected |
|
protected |
List of all edges of the BFS-tree.
Definition at line 520 of file bfs.h.
View newest version in sPHENIX GitHub at line 520 of file bfs.h
|
protected |
1.8.2
with sPHENIX GitHub integration
