SCC.cpp File Reference

Tarjan's algorithm to determine strongly connected components of a directed graph. This was the first algorithm that solved the problem in linear time. More...

#include <cassert>
#include <map>
#include <set>
#include <stack>
#include <OpenAnalysis/Utils/SCC.hpp>
#include <OpenAnalysis/Utils/Util.hpp>

Include dependency graph for SCC.cpp:

Go to the source code of this file.

Classes
class	OA::LowLinkState
class	OA::LowLinkState::SCCNodeStatus
Namespaces
namespace	OA
	Namespace for the whole OpenAnalysis Toolkit.
Functions
static void	CreateHelper (OA::SCCSet *sccSet, OA::OA_ptr< OA::RIFG > rifg, OA::OA_ptr< OA::DGraph::Interface::Node > v, OA::RIFG::NodeId vid, OA::LowLinkState *state)

---

Detailed Description

Tarjan's algorithm to determine strongly connected components of a directed graph. This was the first algorithm that solved the problem in linear time.

Authors:

Original DSystem code by John Mellor-Crummey, Lei Zhou; Ported to OpenAnalysis by Nathan Tallent

Version:

Id

SCC.cpp,v 1.9 2005/06/08 20:31:50 eraxxon Exp

Copyright (c) 2002-2005, Rice University
Copyright (c) 2004-2005, University of Chicago
Copyright (c) 2006, Contributors
All rights reserved.
See ../../../Copyright.txt for details.

The algorithm uses a push-down STACK. With every node in the graph, three variables are associated: visited, dfn, link. Furthermore, the algorithm uses counters df-count and r.

Definition in file SCC.cpp.

---

Function Documentation

static void CreateHelper	(	OA::SCCSet *	sccSet,
		OA::OA_ptr< OA::RIFG >	rifg,
		OA::OA_ptr< OA::DGraph::Interface::Node >	v,
		OA::RIFG::NodeId	vid,
		OA::LowLinkState *	state
	)			[static]

Definition at line 239 of file SCC.cpp.

References OA::LowLinkState::Count(), OA::LowLinkState::DFNUMBER(), OA::LowLinkState::IsMarked(), OA::LowLinkState::IsOnStack(), OA::LowLinkState::LOWLINK(), OA::LowLinkState::Mark(), OA_MIN, OA::LowLinkState::Pop(), and OA::LowLinkState::Push().

Referenced by OA::SCCSet::Create().

Here is the call graph for this function: