Analysis Software
Documentation for sPHENIX simulation software
|
Depth-First-Search (DFS) algorithm. More...
#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/dfs.h>
Public Types | |
typedef list< edge > ::const_iterator | tree_edges_iterator |
Iterator for the tree edges of the DFS-tree. | |
typedef list< node > ::const_iterator | dfs_iterator |
Iterator for the (reached) nodes in DFS-order. | |
typedef list< edge > ::const_iterator | non_tree_edges_iterator |
Iterator for the non-tree-edges. | |
typedef list< dfs_iterator > ::const_iterator | roots_iterator |
Iterator for the roots of the DFS-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 | |
dfs () | |
Constructor. | |
virtual | ~dfs () |
Destructor. | |
int | run (graph &G) |
Applies algorithm to graph g. | |
virtual int | check (graph &G) |
Checks whether the preconditions for DFS are satisfied. | |
virtual void | reset () |
Resets algorithm. | |
void | start_node (const node &n) |
Sets start-node for DFS. | |
node | start_node () const |
Returns start-node for DFS. | |
void | scan_whole_graph (bool set) |
Enables or disables scanning of the whole graph. | |
bool | scan_whole_graph () const |
Returns true iff the whole graph will be scanned. | |
void | calc_comp_num (bool set) |
Enables or Disables the calculation of the completion number. | |
bool | calc_comp_num () const |
Returns true iff completion-numbers will be calculated. | |
void | store_preds (bool set) |
Enables or disables the storing of predecessors. | |
bool | store_preds () const |
Returns true iff the storing of predecessors is enabled. | |
void | store_non_tree_edges (bool set) |
Enables the storing of back-edges. | |
bool | store_non_tree_edges () const |
Returns true iff the storing of non-tree-edges is enabled. | |
bool | reached (const node &n) const |
Checks whether node n was reached in last DFS. | |
int | dfs_num (const node &n) const |
DFS-Number of n. | |
int | operator[] (const node &n) const |
DFS-Number of n. | |
int | comp_num (const node &n) const |
Completion-number of node n, if enabled in last run. | |
node | father (const node &n) const |
Returns father of node n in DFS-forest. | |
tree_edges_iterator | tree_edges_begin () const |
Iterate through all edges picked in last DFS. | |
tree_edges_iterator | tree_edges_end () const |
End-iterator for iteration through all edges picked in last DFS. | |
dfs_iterator | begin () const |
Iterate through all (reached) nodes in DFS-order. | |
dfs_iterator | end () const |
End-Iterator for iteration through all (reached) nodes in DFS-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 DFS-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 DFS. | |
virtual void | init_handler (graph &G) |
Handler called before the start of DFS. | |
virtual void | end_handler (graph &G) |
Handler called at the end of DFS. | |
virtual void | entry_handler (graph &G, node &n, node &f) |
Handler called when touching node n. | |
virtual void | leave_handler (graph &G, node &n, node &f) |
Handler called after all the adjacent edges of n have been examined. | |
virtual void | before_recursive_call_handler (graph &G, edge &e, node &n) |
Handler called when a unused node n connected to the actual node by e is found. | |
virtual void | after_recursive_call_handler (graph &G, edge &e, node &n) |
Handler called after the algorithm returns from the subtree starting at n connected to the actual node by e. | |
virtual void | old_adj_node_handler (graph &G, edge &e, node &n) |
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. | |
virtual void | new_start_handler (graph &G, node &n) |
Called when DFS 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_dfs_num |
int | act_comp_num |
list< edge > | tree |
list< node > | dfs_order |
node_map< int > | dfs_number |
int | reached_nodes |
edge_map< int > * | used |
list< dfs_iterator > | roots |
node_map< int > * | comp_number |
node_map< node > * | preds |
list< edge > * | back_edges |
node | start |
bool | whole_graph |
Private Member Functions | |
void | dfs_sub (graph &, node &, node &) |
Depth-First-Search (DFS) 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 well-defined, 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 handlers 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!):
Definition at line 88 of file dfs.h.
View newest version in sPHENIX GitHub at line 88 of file dfs.h
typedef list<node>::const_iterator dfs::dfs_iterator |
typedef list<edge>::const_iterator dfs::non_tree_edges_iterator |
typedef list<dfs_iterator>::const_iterator dfs::roots_iterator |
typedef list<edge>::const_iterator dfs::tree_edges_iterator |
__GTL_BEGIN_NAMESPACE dfs::dfs | ( | ) |
Constructor.
Definition at line 29 of file dfs.cpp.
View newest version in sPHENIX GitHub at line 29 of file dfs.cpp
References act_comp_num, act_dfs_num, back_edges, comp_number, preds, reached_nodes, used, and whole_graph.
|
virtual |
Destructor.
Definition at line 41 of file dfs.cpp.
View newest version in sPHENIX GitHub at line 41 of file dfs.cpp
References back_edges, comp_number, preds, and used.
Handler called after the algorithm returns 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. |
Reimplemented in biconnectivity.
Definition at line 467 of file dfs.h.
View newest version in sPHENIX GitHub at line 467 of file dfs.h
Referenced by dfs_sub().
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. |
Reimplemented in biconnectivity, and components.
Definition at line 456 of file dfs.h.
View newest version in sPHENIX GitHub at line 456 of file dfs.h
Referenced by dfs_sub().
|
inline |
Iterate through all (reached) nodes in DFS-order.
Definition at line 321 of file dfs.h.
View newest version in sPHENIX GitHub at line 321 of file dfs.h
Referenced by AnalyzeGraph(), biconnectivity::components_begin(), main(), biconnectivity::reset(), and Acts::MultiEigenStepperLoop< extensionlist_t, component_reducer_t, auctioneer_t >::step().
void dfs::calc_comp_num | ( | bool | set | ) |
Enables or Disables the calculation of the completion number.
set | if true completion-numbers will be calculated. |
Definition at line 211 of file dfs.cpp.
View newest version in sPHENIX GitHub at line 211 of file dfs.cpp
References comp_number.
Referenced by AnalyzeGraph().
|
inline |
Returns true iff completion-numbers will be calculated.
true | iff completion-numbers will be calculated. |
Definition at line 182 of file dfs.h.
View newest version in sPHENIX GitHub at line 182 of file dfs.h
|
virtual |
Checks whether the preconditions for DFS are satisfied.
Currently there aren't any restricitions for the DFS algorithm.
G | graph. |
algorithm::GTL_OK | if algorithm can be applied |
algorithm::GTL_ERROR | otherwise. |
Implements algorithm.
Reimplemented in topsort, biconnectivity, and components.
Definition at line 72 of file dfs.cpp.
View newest version in sPHENIX GitHub at line 72 of file dfs.cpp
References algorithm::GTL_OK.
Referenced by components::check(), biconnectivity::check(), biconnectivity::init_handler(), and ratio_cut_partition::make_connected().
|
inline |
|
inline |
DFS-Number of n.
Please note that DFS-Number 0 means that this node wasn't reached.
n | node. |
Definition at line 247 of file dfs.h.
View newest version in sPHENIX GitHub at line 247 of file dfs.h
References n.
Referenced by biconnectivity::after_recursive_call_handler(), components::old_adj_node_handler(), and biconnectivity::old_adj_node_handler().
Definition at line 148 of file dfs.cpp.
View newest version in sPHENIX GitHub at line 148 of file dfs.cpp
References act_comp_num, act_dfs_num, node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), after_recursive_call_handler(), back_edges, before_recursive_call_handler(), comp_number, dfs_number, dfs_order, end(), entry_handler(), father(), it, leave_handler(), old_adj_node_handler(), node::opposite(), preds, reached_nodes, roots, tree, and used.
Referenced by run().
|
inline |
End-Iterator for iteration through all (reached) nodes in DFS-order.
Definition at line 330 of file dfs.h.
View newest version in sPHENIX GitHub at line 330 of file dfs.h
Referenced by biconnectivity::after_recursive_call_handler(), AnalyzeGraph(), biconnectivity::components_end(), dfs_sub(), biconnectivity::end_handler(), biconnectivity::init_handler(), main(), biconnectivity::new_start_handler(), biconnectivity::reset(), and Acts::MultiEigenStepperLoop< extensionlist_t, component_reducer_t, auctioneer_t >::step().
|
inlinevirtual |
Handler called when touching node n.
G | graph for which DFS was invoked. |
n | actual node. |
f | predecessor. |
Reimplemented in biconnectivity.
Definition at line 436 of file dfs.h.
View newest version in sPHENIX GitHub at line 436 of file dfs.h
Referenced by dfs_sub().
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. |
Definition at line 283 of file dfs.h.
View newest version in sPHENIX GitHub at line 283 of file dfs.h
Referenced by biconnectivity::after_recursive_call_handler(), dfs_sub(), and biconnectivity::entry_handler().
|
inlinevirtual |
Handler called after all the adjacent edges of n have been examined.
G | graph for which DFS was invoked. |
n | actual node. |
f | predecessor. |
Reimplemented in biconnectivity, and topsort.
Definition at line 446 of file dfs.h.
View newest version in sPHENIX GitHub at line 446 of file dfs.h
Referenced by dfs_sub().
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. |
Reimplemented in biconnectivity, and components.
Definition at line 490 of file dfs.h.
View newest version in sPHENIX GitHub at line 490 of file dfs.h
Referenced by run().
|
inline |
|
inline |
|
inline |
Number of nodes reached in last DFS.
Definition at line 407 of file dfs.h.
View newest version in sPHENIX GitHub at line 407 of file dfs.h
Referenced by AnalyzeGraph(), graph::is_connected(), and main().
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. |
Reimplemented in biconnectivity, topsort, and components.
Definition at line 478 of file dfs.h.
View newest version in sPHENIX GitHub at line 478 of file dfs.h
Referenced by dfs_sub().
|
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.
Reimplemented in topsort, biconnectivity, and components.
Definition at line 56 of file dfs.cpp.
View newest version in sPHENIX GitHub at line 56 of file dfs.cpp
References act_comp_num, act_dfs_num, back_edges, dfs_order, reached_nodes, roots, start, and tree.
Referenced by components::reset(), biconnectivity::reset(), and topsort::reset().
|
inline |
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.
Definition at line 389 of file dfs.h.
View newest version in sPHENIX GitHub at line 389 of file dfs.h
Referenced by AnalyzeGraph(), biconnectivity::init_handler(), and ratio_cut_partition::make_connected().
|
inline |
Iterator pointing to the end of all roots.
Definition at line 398 of file dfs.h.
View newest version in sPHENIX GitHub at line 398 of file dfs.h
Referenced by AnalyzeGraph(), biconnectivity::init_handler(), and ratio_cut_partition::make_connected().
|
virtual |
Applies algorithm to graph g.
g | graph |
algorithm::GTL_OK | on success |
algorithm::GTL_ERROR | otherwise |
Implements algorithm.
Definition at line 77 of file dfs.cpp.
View newest version in sPHENIX GitHub at line 77 of file dfs.cpp
References back_edges, graph::choose_node(), comp_number, dfs_number, dfs_sub(), dummy, end_handler(), forall_nodes, algorithm::GTL_OK, ne_map< Key, Value, Graph, Alloc >::init(), init_handler(), new_start_handler(), graph::number_of_nodes(), preds, reached_nodes, start, used, and whole_graph.
Referenced by AnalyzeGraph(), biconnectivity::init_handler(), graph::is_acyclic(), graph::is_connected(), main(), ratio_cut_partition::make_connected(), planarity::run(), Jetscape::JetScapeWriterHepMC::Write(), and Jetscape::JetScapeWriterRootHepMC::Write().
|
inline |
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. |
Definition at line 157 of file dfs.h.
View newest version in sPHENIX GitHub at line 157 of file dfs.h
Referenced by AnalyzeGraph(), biconnectivity::init_handler(), ratio_cut_partition::make_connected(), Jetscape::JetScapeWriterHepMC::Write(), and Jetscape::JetScapeWriterRootHepMC::Write().
|
inline |
Returns true iff the whole graph will be scanned.
true | iff the whole graph will be scanned. |
Definition at line 166 of file dfs.h.
View newest version in sPHENIX GitHub at line 166 of file dfs.h
Referenced by biconnectivity::biconnectivity(), components::components(), biconnectivity::make_biconnected(), and biconnectivity::store_components().
|
inline |
Sets start-node for DFS.
n | start-node. |
Definition at line 129 of file dfs.h.
View newest version in sPHENIX GitHub at line 129 of file dfs.h
Referenced by AnalyzeGraph(), main(), Jetscape::JetScapeWriterHepMC::Write(), and Jetscape::JetScapeWriterRootHepMC::Write().
|
inline |
void dfs::store_non_tree_edges | ( | bool | set | ) |
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. |
Definition at line 231 of file dfs.cpp.
View newest version in sPHENIX GitHub at line 231 of file dfs.cpp
References back_edges.
|
inline |
void dfs::store_preds | ( | bool | set | ) |
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. |
Definition at line 221 of file dfs.cpp.
View newest version in sPHENIX GitHub at line 221 of file dfs.cpp
References preds.
|
inline |
Returns true iff the storing of predecessors is enabled.
true | iff the storing of predecessors is enabled. |
Definition at line 202 of file dfs.h.
View newest version in sPHENIX GitHub at line 202 of file dfs.h
Referenced by biconnectivity::biconnectivity().
|
inline |
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.
Definition at line 300 of file dfs.h.
View newest version in sPHENIX GitHub at line 300 of file dfs.h
References tree.
Referenced by AnalyzeGraph(), and main().
|
inline |
End-iterator for iteration through all edges picked in last DFS.
Definition at line 308 of file dfs.h.
View newest version in sPHENIX GitHub at line 308 of file dfs.h
References tree.
Referenced by AnalyzeGraph(), and main().
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
Definition at line 524 of file dfs.h.
View newest version in sPHENIX GitHub at line 524 of file dfs.h
Referenced by dfs_sub(), biconnectivity::entry_handler(), biconnectivity::old_adj_node_handler(), and run().
|
protected |
Definition at line 550 of file dfs.h.
View newest version in sPHENIX GitHub at line 550 of file dfs.h
Referenced by biconnectivity::check(), dfs(), dfs_sub(), run(), store_preds(), and ~dfs().
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |