Analysis Software
Documentation for sPHENIX simulation software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
dfs Class Reference

Depth-First-Search (DFS) algorithm. More...

#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/dfs.h>

+ Inheritance diagram for dfs:
+ Collaboration diagram for dfs:

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< edgetree
 
list< nodedfs_order
 
node_map< int > dfs_number
 
int reached_nodes
 
edge_map< int > * used
 
list< dfs_iteratorroots
 
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 &)
 

Detailed Description

Depth-First-Search (DFS) algorithm.

Date:
2003/03/24 15:58:54
Revision:
1.25

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:

  • dfs::start_node (default: an arbitrary node will be chosen)
  • dfs::scan_whole_graph states whether BFS will be continued in the unused part of the graph, if not all nodes were touched at the end of DFS started at the start-node. (default: disabled)
  • dfs::calc_comp_num toggle storing of completion-numbers for each node, i.e. a numbering which reflects the order in which nodes were finished. (default: disabled)
  • dfs::store_preds toggle storing the predecessor of each node, i.e. the father in DFS-tree. (default: disabled)
  • dfs::store_non_tree_edges toggle storing of all non-tree-edges (tree-edges are always stored) in a list and thus enable or disable iteration through all non-tree-edges. (default: disabled)

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

Member Typedef Documentation

typedef list<node>::const_iterator dfs::dfs_iterator

Iterator for the (reached) nodes in DFS-order.

Definition at line 314 of file dfs.h.

View newest version in sPHENIX GitHub at line 314 of file dfs.h

typedef list<edge>::const_iterator dfs::non_tree_edges_iterator

Iterator for the non-tree-edges.

Definition at line 336 of file dfs.h.

View newest version in sPHENIX GitHub at line 336 of file dfs.h

typedef list<dfs_iterator>::const_iterator dfs::roots_iterator

Iterator for the roots of the DFS-forest.

Definition at line 360 of file dfs.h.

View newest version in sPHENIX GitHub at line 360 of file dfs.h

typedef list<edge>::const_iterator dfs::tree_edges_iterator

Iterator for the tree edges of the DFS-tree.

Definition at line 289 of file dfs.h.

View newest version in sPHENIX GitHub at line 289 of file dfs.h

Constructor & Destructor Documentation

__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.

dfs::~dfs ( )
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.

Member Function Documentation

virtual void dfs::after_recursive_call_handler ( graph G,
edge e,
node n 
)
inlinevirtual

Handler called after the algorithm returns from the subtree starting at n connected to the actual node by e.

Parameters
Ggraph for which DFS was invoked.
eedge connecting the actual node to the unused one.
nunused 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().

+ Here is the caller graph for this function:

virtual void dfs::before_recursive_call_handler ( graph G,
edge e,
node n 
)
inlinevirtual

Handler called when a unused node n connected to the actual node by e is found.

Parameters
Ggraph for which DFS was invoked.
eedge connecting the actual node to the unused one.
nunused 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().

+ Here is the caller graph for this function:

dfs_iterator dfs::begin ( void  ) const
inline

Iterate through all (reached) nodes in DFS-order.

Returns
start for iteration through all 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().

+ Here is the caller graph for this function:

void dfs::calc_comp_num ( bool  set)

Enables or Disables the calculation of the completion number.

Parameters
setif true completion-numbers will be calculated.
See Also
dfs::comp_num

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().

+ Here is the caller graph for this function:

bool dfs::calc_comp_num ( ) const
inline

Returns true iff completion-numbers will be calculated.

Return values
trueiff completion-numbers will be calculated.
See Also
dfs::comp_num

Definition at line 182 of file dfs.h.

View newest version in sPHENIX GitHub at line 182 of file dfs.h

int dfs::check ( graph G)
virtual

Checks whether the preconditions for DFS are satisfied.

Currently there aren't any restricitions for the DFS algorithm.

Parameters
Ggraph.
Return values
algorithm::GTL_OKif algorithm can be applied
algorithm::GTL_ERRORotherwise.

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().

+ Here is the caller graph for this function:

int dfs::comp_num ( const node n) const
inline

Completion-number of node n, if enabled in last run.

Parameters
nnode.
Returns
Completion-number of n.
See Also
dfs::calc_comp_num

Definition at line 270 of file dfs.h.

View newest version in sPHENIX GitHub at line 270 of file dfs.h

References assert, and n.

int dfs::dfs_num ( const node n) const
inline

DFS-Number of n.

Please note that DFS-Number 0 means that this node wasn't reached.

Parameters
nnode.
Returns
DFS-Number of n.

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().

+ Here is the caller graph for this function:

void dfs::dfs_sub ( graph G,
node curr,
node father 
)
private

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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

dfs_iterator dfs::end ( void  ) const
inline

End-Iterator for iteration through all (reached) nodes in DFS-order.

Returns
end for iteration through all (reached) nodes

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().

+ Here is the caller graph for this function:

virtual void dfs::end_handler ( graph G)
inlinevirtual

Handler called at the end of DFS.

Parameters
Ggraph for which DFS was invoked.

Reimplemented in biconnectivity.

Definition at line 427 of file dfs.h.

View newest version in sPHENIX GitHub at line 427 of file dfs.h

Referenced by run().

+ Here is the caller graph for this function:

virtual void dfs::entry_handler ( graph G,
node n,
node f 
)
inlinevirtual

Handler called when touching node n.

Parameters
Ggraph for which DFS was invoked.
nactual node.
fpredecessor.

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().

+ Here is the caller graph for this function:

node dfs::father ( const node n) const
inline

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().

Parameters
nnode.
Returns
Father of n.
See Also
dfs::store_preds

Definition at line 283 of file dfs.h.

View newest version in sPHENIX GitHub at line 283 of file dfs.h

References assert, and n.

Referenced by biconnectivity::after_recursive_call_handler(), dfs_sub(), and biconnectivity::entry_handler().

+ Here is the caller graph for this function:

virtual void dfs::init_handler ( graph G)
inlinevirtual

Handler called before the start of DFS.

Parameters
Ggraph for which DFS was invoked.

Reimplemented in biconnectivity, and topsort.

Definition at line 420 of file dfs.h.

View newest version in sPHENIX GitHub at line 420 of file dfs.h

Referenced by run().

+ Here is the caller graph for this function:

virtual void dfs::leave_handler ( graph G,
node n,
node f 
)
inlinevirtual

Handler called after all the adjacent edges of n have been examined.

Parameters
Ggraph for which DFS was invoked.
nactual node.
fpredecessor.

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().

+ Here is the caller graph for this function:

virtual void dfs::new_start_handler ( graph G,
node n 
)
inlinevirtual

Called when DFS is started with start-node n.

This is particularly useful when DFS was invoked with the scan_whole_graph option.

Parameters
Ggraph for which DFS was invoked.
nstart-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().

+ Here is the caller graph for this function:

non_tree_edges_iterator dfs::non_tree_edges_begin ( ) const
inline

Iterate through all non-tree-edges (if enabled).

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

Definition at line 344 of file dfs.h.

View newest version in sPHENIX GitHub at line 344 of file dfs.h

References assert.

non_tree_edges_iterator dfs::non_tree_edges_end ( ) const
inline

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

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

Definition at line 354 of file dfs.h.

View newest version in sPHENIX GitHub at line 354 of file dfs.h

References assert.

int dfs::number_of_reached_nodes ( ) const
inline

Number of nodes reached in last DFS.

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

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().

+ Here is the caller graph for this function:

virtual void dfs::old_adj_node_handler ( graph G,
edge e,
node n 
)
inlinevirtual

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.

Parameters
Ggraph for which DFS was invoked.
eedge connecting the actual node to the old one.
nused 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().

+ Here is the caller graph for this function:

int dfs::operator[] ( const node n) const
inline

DFS-Number of n.

Please note that DFS-Number 0 means that this node wasn't reached.

Parameters
nnode.
Returns
DFS-Number of n.

Definition at line 259 of file dfs.h.

View newest version in sPHENIX GitHub at line 259 of file dfs.h

References n.

bool dfs::reached ( const node n) const
inline

Checks whether node n was reached in last DFS.

Parameters
nnode to be checked.
Returns
true iff n was reached.

Definition at line 235 of file dfs.h.

View newest version in sPHENIX GitHub at line 235 of file dfs.h

References n.

void dfs::reset ( )
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().

+ Here is the caller graph for this function:

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

Returns
start for iteration through all roots in DFS-forest.
See Also
dfs::scan_whole_graph

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().

+ Here is the caller graph for this function:

roots_iterator dfs::roots_end ( ) const
inline

Iterator pointing to the end of all roots.

Returns
end for iteration through all roots in DFS-forest.
See Also
dfs::scan_whole_graph

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().

+ Here is the caller graph for this function:

int dfs::run ( graph g)
virtual

Applies algorithm to graph g.

Parameters
ggraph
Return values
algorithm::GTL_OKon success
algorithm::GTL_ERRORotherwise

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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

Parameters
setif true enable scanning the whole graph.
See Also
dfs::roots_begin
dfs::roots_end

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().

+ Here is the caller graph for this function:

bool dfs::scan_whole_graph ( ) const
inline

Returns true iff the whole graph will be scanned.

Return values
trueiff the whole graph will be scanned.
See Also
dfs::roots_begin
dfs::roots_end

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().

+ Here is the caller graph for this function:

void dfs::start_node ( const node n)
inline

Sets start-node for DFS.

Parameters
nstart-node.

Definition at line 129 of file dfs.h.

View newest version in sPHENIX GitHub at line 129 of file dfs.h

References n, and start.

Referenced by AnalyzeGraph(), main(), Jetscape::JetScapeWriterHepMC::Write(), and Jetscape::JetScapeWriterRootHepMC::Write().

+ Here is the caller graph for this function:

node dfs::start_node ( ) const
inline

Returns start-node for DFS.

Returns
start-node.

Definition at line 137 of file dfs.h.

View newest version in sPHENIX GitHub at line 137 of file dfs.h

References start.

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.

Parameters
setif true non_tree_edges will be stored.
See Also
dfs::non_tree_edges_begin
dfs::non_tree_edges_end

Definition at line 231 of file dfs.cpp.

View newest version in sPHENIX GitHub at line 231 of file dfs.cpp

References back_edges.

bool dfs::store_non_tree_edges ( ) const
inline

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

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

Definition at line 223 of file dfs.h.

View newest version in sPHENIX GitHub at line 223 of file dfs.h

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.

Parameters
setif true predecessors will be stored.
See Also
dfs::father

Definition at line 221 of file dfs.cpp.

View newest version in sPHENIX GitHub at line 221 of file dfs.cpp

References preds.

bool dfs::store_preds ( ) const
inline

Returns true iff the storing of predecessors is enabled.

Return values
trueiff the storing of predecessors is enabled.
See Also
dfs::father

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().

+ Here is the caller graph for this function:

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

Returns
start for iteration through all edges followed in DFS.

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().

+ Here is the caller graph for this function:

tree_edges_iterator dfs::tree_edges_end ( ) const
inline

End-iterator for iteration through all edges picked in last DFS.

Returns
end for iteration through all edges followed in 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().

+ Here is the caller graph for this function:

Member Data Documentation

int dfs::act_comp_num
protected

Definition at line 512 of file dfs.h.

View newest version in sPHENIX GitHub at line 512 of file dfs.h

Referenced by dfs(), dfs_sub(), and reset().

int dfs::act_dfs_num
protected

Definition at line 508 of file dfs.h.

View newest version in sPHENIX GitHub at line 508 of file dfs.h

Referenced by dfs(), dfs_sub(), and reset().

list<edge>* dfs::back_edges
protected

Definition at line 554 of file dfs.h.

View newest version in sPHENIX GitHub at line 554 of file dfs.h

Referenced by dfs(), dfs_sub(), reset(), run(), store_non_tree_edges(), and ~dfs().

node_map<int>* dfs::comp_number
protected

Definition at line 546 of file dfs.h.

View newest version in sPHENIX GitHub at line 546 of file dfs.h

Referenced by calc_comp_num(), dfs(), dfs_sub(), run(), and ~dfs().

node_map<int> dfs::dfs_number
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().

list<node> dfs::dfs_order
protected

Definition at line 520 of file dfs.h.

View newest version in sPHENIX GitHub at line 520 of file dfs.h

Referenced by dfs_sub(), and reset().

node_map<node>* dfs::preds
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().

int dfs::reached_nodes
protected

Definition at line 528 of file dfs.h.

View newest version in sPHENIX GitHub at line 528 of file dfs.h

Referenced by dfs(), dfs_sub(), reset(), and run().

list<dfs_iterator> dfs::roots
protected

Definition at line 536 of file dfs.h.

View newest version in sPHENIX GitHub at line 536 of file dfs.h

Referenced by dfs_sub(), and reset().

node dfs::start
protected

Definition at line 558 of file dfs.h.

View newest version in sPHENIX GitHub at line 558 of file dfs.h

Referenced by biconnectivity::init_handler(), reset(), and run().

list<edge> dfs::tree
protected

Definition at line 516 of file dfs.h.

View newest version in sPHENIX GitHub at line 516 of file dfs.h

Referenced by dfs_sub(), and reset().

edge_map<int>* dfs::used
protected

Definition at line 532 of file dfs.h.

View newest version in sPHENIX GitHub at line 532 of file dfs.h

Referenced by dfs(), dfs_sub(), run(), and ~dfs().

bool dfs::whole_graph
protected

Definition at line 562 of file dfs.h.

View newest version in sPHENIX GitHub at line 562 of file dfs.h

Referenced by components::check(), dfs(), and run().


The documentation for this class was generated from the following files: