concurrency::TarjanSCCFinder Class Reference

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

#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 (DataNode &)
virtual bool	visit (ConditionNode &)
virtual bool	visitEnter (DataNode &) const
Public Member Functions inherited from concurrency::IGraphVisitor
virtual	~IGraphVisitor ()=default

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 168 of file Validators.h.

Member Function Documentation

on_stack()

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

inlineprivate

Definition at line 198 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 182 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 189 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/4]

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() [2/4]

virtual bool concurrency::IGraphVisitor::visit ( ConditionNode & )

inlinevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 34 of file IGraphVisitor.h.

{ return true; }

visit() [3/4]

virtual bool concurrency::IGraphVisitor::visit ( DataNode & )

inlinevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 31 of file IGraphVisitor.h.

{ return true; }

visit() [4/4]

virtual bool concurrency::IGraphVisitor::visit ( DecisionNode & )

inlinevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 25 of file IGraphVisitor.h.

{ return true; }

visitEnter() [1/4]

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

inlineoverridevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 175 of file Validators.h.

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

visitEnter() [2/4]

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

inlineoverridevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 173 of file Validators.h.

{ return false; }

visitEnter() [3/4]

virtual bool concurrency::IGraphVisitor::visitEnter ( DataNode & ) const

inlinevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 30 of file IGraphVisitor.h.

{ return true; }

visitEnter() [4/4]

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

inlineoverridevirtual

Reimplemented from concurrency::IGraphVisitor.

Definition at line 174 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 204 of file Validators.h.

m_nodes_count

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

private

Definition at line 202 of file Validators.h.

{ 0 };

m_scc

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

private

Definition at line 205 of file Validators.h.

m_stack

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

private

Definition at line 206 of file Validators.h.

m_status

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

private

Definition at line 208 of file Validators.h.

{ "  No strongly connected components found in DF realm" };

---

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

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