concurrency::TarjanSCCFinder Class Reference

#include </builds/gaudi/Gaudi/GaudiHive/src/PRGraph/Visitors/Validators.h>

Inheritance diagram for concurrency::TarjanSCCFinder:

Collaboration diagram for concurrency::TarjanSCCFinder:

Public Member Functions
bool	visitEnter (ConditionNode &) const override
bool	visitEnter (DecisionNode &) const override
bool	visitEnter (AlgorithmNode &node) const override
bool	visit (AlgorithmNode &nodeAt) override
bool	passed () const
std::string	reply ()
void	reset () override
virtual bool	visit (DecisionNode &)
virtual bool	visit (AlgorithmNode &)
virtual bool	visit (DataNode &)
virtual bool	visit (ConditionNode &)
virtual bool	visitEnter (DecisionNode &) const
virtual bool	visitEnter (AlgorithmNode &) const
virtual bool	visitEnter (DataNode &) const
virtual bool	visitEnter (ConditionNode &) const
Public Member Functions inherited from concurrency::IGraphVisitor
virtual	~IGraphVisitor ()=default
virtual bool	visit (DecisionNode &)
virtual bool	visitEnter (DataNode &) const
virtual bool	visit (DataNode &)
virtual bool	visit (ConditionNode &)

Private Member Functions
bool	on_stack (const AlgorithmNode &node) const

Private Attributes
unsigned int	m_nodes_count { 0 }
std::unordered_map< AlgorithmNode *, std::pair< unsigned int, unsigned int > >	m_lowlinks
std::map< unsigned int, std::vector< AlgorithmNode * > >	m_scc
std::vector< AlgorithmNode * >	m_stack
std::ostringstream	m_status { " No strongly connected components found in DF realm" }

Detailed Description

The visitor implements the Tarjan algorithm for searching strongly connected components in the data flow realm of precedence rules graph.

Definition at line 169 of file Validators.h.

Member Function Documentation

on_stack()

bool concurrency::TarjanSCCFinder::on_stack ( const AlgorithmNode &  node ) const

inlineprivate

Definition at line 199 of file Validators.h.

                                                     {
      return std::find( m_stack.begin(), m_stack.end(), &node ) != m_stack.end() ? true : false;
    }

passed()

bool concurrency::TarjanSCCFinder::passed ( ) const

inline

Definition at line 183 of file Validators.h.

                        {
      return m_scc.empty() ||
             !std::any_of( m_scc.begin(), m_scc.end(), []( const auto& pr ) { return pr.second.size() > 1; } );
    }

reply()

std::string concurrency::TarjanSCCFinder::reply

(

)

Definition at line 281 of file Validators.cpp.

                                   {
 
    if ( !passed() ) {
 
      m_status << "  Strongly connected components found in DF realm:";
 
      for ( auto& pr : m_scc ) {
        if ( pr.second.size() > 1 ) {
          m_status << "\n o [lowlink:" << std::to_string( pr.first ) << "] |";
 
          // rotate SCCs to get reproducible order
          std::vector sortedSCC( pr.second.begin(), pr.second.end() );
          std::sort( sortedSCC.begin(), sortedSCC.end(), CompareNodes<AlgorithmNode*>() );
          std::rotate( pr.second.begin(), std::find( pr.second.begin(), pr.second.end(), sortedSCC.front() ),
                       pr.second.end() );
 
          for ( const auto& algoPtr : pr.second ) m_status << " " << algoPtr->name() << " |";
        }
      }
    }
 
    return m_status.str();
  }

reset()

void concurrency::TarjanSCCFinder::reset ( )

inlineoverridevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 190 of file Validators.h.

                          {
      m_nodes_count = 0;
      m_stack.clear();
      m_lowlinks.clear();
      m_scc.clear();
      m_status = std::ostringstream{ "  No strongly connected components found in DF realm" };
    }

visit() [1/5]

virtual bool concurrency::IGraphVisitor::visit

inline

Definition at line 29 of file IGraphVisitor.h.

{ return true; }

visit() [2/5]

bool concurrency::TarjanSCCFinder::visit ( AlgorithmNode &  nodeAt )

overridevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 235 of file Validators.cpp.

                                                     {
 
    // DFS ******************************************************
 
    // put the node on stack
    m_stack.push_back( &nodeAt );
 
    // initialize and cache the low-link value of this node
    m_nodes_count += 1;
    unsigned int lowlink_init{ m_nodes_count };
    // record initial low-link value of this node
    m_lowlinks.insert( { &nodeAt, { lowlink_init, lowlink_init } } );
    auto& lowlink = m_lowlinks[&nodeAt].second;
 
    for ( const auto& output : nodeAt.getOutputDataNodes() ) {
      for ( const auto& consumer : output->getConsumers() ) {
        consumer->accept( *this );
        // DFS callback ******************************************
        // propagate the low-link value back
        if ( on_stack( *consumer ) ) {
          if ( lowlink > m_lowlinks[consumer].second ) lowlink = m_lowlinks[consumer].second;
          // this allows to detect loops (i.e., a cycle consisting of a single algorithm node: A->d->A),
          // but there is a protection against this case at Algorithm::initialize()
          if ( consumer == &nodeAt ) m_scc.insert( { lowlink, { &nodeAt } } );
        }
      }
    }
 
    // If an SCC is found, book-keep it and take it off the stack
    if ( lowlink_init == lowlink ) {
      if ( m_scc.find( lowlink ) == m_scc.end() ) m_scc.insert( { lowlink, {} } );
 
      for ( auto stackNodeRIter = m_stack.rbegin(); stackNodeRIter != m_stack.rend(); ++stackNodeRIter ) {
 
        bool lastSCCNodeOnStack{ *stackNodeRIter == &nodeAt };
        if ( lowlink == m_lowlinks[*stackNodeRIter].second ) m_scc[lowlink].push_back( *stackNodeRIter );
 
        m_stack.pop_back();
        if ( lastSCCNodeOnStack ) break;
      }
    }
 
    return true;
  }

visit() [3/5]

virtual bool concurrency::IGraphVisitor::visit

inline

Definition at line 35 of file IGraphVisitor.h.

{ return true; }

visit() [4/5]

virtual bool concurrency::IGraphVisitor::visit

inline

Definition at line 32 of file IGraphVisitor.h.

{ return true; }

visit() [5/5]

virtual bool concurrency::IGraphVisitor::visit

inline

Definition at line 26 of file IGraphVisitor.h.

{ return true; }

visitEnter() [1/7]

virtual bool concurrency::IGraphVisitor::visitEnter

inline

Definition at line 28 of file IGraphVisitor.h.

{ return true; }

visitEnter() [2/7]

bool concurrency::TarjanSCCFinder::visitEnter ( AlgorithmNode &  node ) const

inlineoverridevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 176 of file Validators.h.

                                                          {
      // check if the node was already visited
      return m_lowlinks.find( &node ) != m_lowlinks.end() ? false : true;
    }

visitEnter() [3/7]

virtual bool concurrency::IGraphVisitor::visitEnter

inline

Definition at line 34 of file IGraphVisitor.h.

{ return true; }

visitEnter() [4/7]

bool concurrency::TarjanSCCFinder::visitEnter ( ConditionNode &  ) const

inlineoverridevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 174 of file Validators.h.

{ return false; }

visitEnter() [5/7]

virtual bool concurrency::IGraphVisitor::visitEnter

inline

Definition at line 31 of file IGraphVisitor.h.

{ return true; }

visitEnter() [6/7]

virtual bool concurrency::IGraphVisitor::visitEnter

inline

Definition at line 25 of file IGraphVisitor.h.

{ return true; }

visitEnter() [7/7]

bool concurrency::TarjanSCCFinder::visitEnter ( DecisionNode &  ) const

inlineoverridevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 175 of file Validators.h.

{ return false; }

Member Data Documentation

m_lowlinks

std::unordered_map<AlgorithmNode*, std::pair<unsigned int, unsigned int> > concurrency::TarjanSCCFinder::m_lowlinks

private

Definition at line 205 of file Validators.h.

m_nodes_count

unsigned int concurrency::TarjanSCCFinder::m_nodes_count { 0 }

private

Definition at line 203 of file Validators.h.

m_scc

std::map<unsigned int, std::vector<AlgorithmNode*> > concurrency::TarjanSCCFinder::m_scc

private

Definition at line 206 of file Validators.h.

m_stack

std::vector<AlgorithmNode*> concurrency::TarjanSCCFinder::m_stack

private

Definition at line 207 of file Validators.h.

m_status

std::ostringstream concurrency::TarjanSCCFinder::m_status { " No strongly connected components found in DF realm" }

private

Definition at line 209 of file Validators.h.

---

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

• GaudiHive/src/PRGraph/Visitors/Validators.h
• GaudiHive/src/PRGraph/Visitors/Validators.cpp