SVF::SCCDetection< GraphType > Class Template Reference

#include <SCC.h>

Classes
class	GNodeSCCInfo

Public Types
typedef std::stack< NodeID >	GNodeStack
typedef Map< NodeID, GNodeSCCInfo >	GNODESCCInfoMap
typedef Map< NodeID, NodeID >	NodeToNodeMap

Public Member Functions
	SCCDetection (const GraphType &GT)
GNodeStack &	topoNodeStack ()
const GNODESCCInfoMap &	GNodeSCCInfo () const
NodeID	repNode (NodeID n) const
	get the rep node if not found return itself More...
bool	isInCycle (NodeID n) const
	whether the node is in a cycle More...
const NodeBS &	subNodes (NodeID n) const
	get all subnodes in one scc, if size is empty insert itself into the set More...
const NodeBS &	getRepNodes () const
	get all repNodeID More...
const GraphType &	graph ()
void	find (void)
void	find (NodeSet &candidates)

Private Types
typedef SVF::GenericGraphTraits< GraphType >	GTraits
	Define the GTraits and node iterator for printing. More...
typedef GTraits::NodeRef	GNODE
typedef GTraits::nodes_iterator	node_iterator
typedef GTraits::ChildIteratorType	child_iterator
typedef unsigned	NodeID

Private Member Functions
bool	visited (NodeID n)
bool	inSCC (NodeID n)
void	setVisited (NodeID n, bool v)
void	setInSCC (NodeID n, bool v)
void	rep (NodeID n, NodeID r)
NodeID	rep (NodeID n)
bool	isInSCC (NodeID n)
GNODE	Node (NodeID id) const
NodeID	Node_Index (GNODE node) const
void	visit (NodeID v)
void	clear ()

Private Attributes
GNODESCCInfoMap	_NodeSCCAuxInfo
const GraphType &	_graph
NodeID	_I
NodeToNodeMap	_D
GNodeStack	_SS
GNodeStack	_T
NodeBS	repNodes

Detailed Description

template<class GraphType>
class SVF::SCCDetection< GraphType >

Definition at line 54 of file SCC.h.

Member Typedef Documentation

child_iterator

template<class GraphType >

typedef GTraits::ChildIteratorType SVF::SCCDetection< GraphType >::child_iterator

private

Definition at line 62 of file SCC.h.

GNODE

template<class GraphType >

typedef GTraits::NodeRef SVF::SCCDetection< GraphType >::GNODE

private

Definition at line 60 of file SCC.h.

GNODESCCInfoMap

template<class GraphType >

typedef Map<NodeID,GNodeSCCInfo > SVF::SCCDetection< GraphType >::GNODESCCInfoMap

Definition at line 116 of file SCC.h.

GNodeStack

template<class GraphType >

typedef std::stack<NodeID> SVF::SCCDetection< GraphType >::GNodeStack

Definition at line 66 of file SCC.h.

GTraits

template<class GraphType >

typedef SVF::GenericGraphTraits<GraphType> SVF::SCCDetection< GraphType >::GTraits

private

Define the GTraits and node iterator for printing.

Definition at line 59 of file SCC.h.

node_iterator

template<class GraphType >

typedef GTraits::nodes_iterator SVF::SCCDetection< GraphType >::node_iterator

private

Definition at line 61 of file SCC.h.

NodeID

template<class GraphType >

typedef unsigned SVF::SCCDetection< GraphType >::NodeID

private

Definition at line 63 of file SCC.h.

NodeToNodeMap

template<class GraphType >

typedef Map<NodeID, NodeID> SVF::SCCDetection< GraphType >::NodeToNodeMap

Definition at line 117 of file SCC.h.

Constructor & Destructor Documentation

SCCDetection()

template<class GraphType >

SVF::SCCDetection< GraphType >::SCCDetection ( const GraphType &  GT )

inline

Definition at line 119 of file SCC.h.

        : _graph(GT),
          _I(0)
    {}

Member Function Documentation

clear()

template<class GraphType >

void SVF::SCCDetection< GraphType >::clear ( )

inlineprivate

Definition at line 295 of file SCC.h.

    {
        _NodeSCCAuxInfo.clear();
        _I = 0;
        _D.clear();
        repNodes.clear();
        while(!_SS.empty())
            _SS.pop();
        while(!_T.empty())
            _T.pop();
    }

find() [1/2]

template<class GraphType >

void SVF::SCCDetection< GraphType >::find ( NodeSet &  candidates )

inline

Definition at line 334 of file SCC.h.

    {
        // This function is reloaded to only visit candidate NODES
        clear();
        for (NodeID node : candidates)
        {
            if (!this->visited(node))
            {
                if (this->rep(node) == UINT_MAX || this->rep(node) == node)
                    visit(node);
                else
                    this->visited(node);
            }
        }
    }

find() [2/2]

template<class GraphType >

void SVF::SCCDetection< GraphType >::find ( void  )

inline

Definition at line 308 of file SCC.h.

    {
        // Visit each unvisited root node.   A root node is defined
        // to be a node that has no incoming copy/skew edges
        clear();
        node_iterator I = GTraits::nodes_begin(_graph);
        node_iterator E = GTraits::nodes_end(_graph);
        for (; I != E; ++I)
        {
            NodeID node = Node_Index(*I);
            if (!this->visited(node))
            {
                // We skip any nodes that have a representative other than
                // themselves.  Such nodes occur as a result of merging
                // nodes either through unifying an ACC or other node
                // merging optimizations.  Any such node should have no
                // outgoing edges and therefore should no longer be a member
                // of an SCC.
                if (this->rep(node) == UINT_MAX || this->rep(node) == node)
                    visit(node);
                else
                    this->visited(node);
            }
        }
    }

getRepNodes()

template<class GraphType >

const NodeBS& SVF::SCCDetection< GraphType >::getRepNodes ( ) const

inline

get all repNodeID

Definition at line 181 of file SCC.h.

    {
        return repNodes;
    }

GNodeSCCInfo()

template<class GraphType >

const GNODESCCInfoMap& SVF::SCCDetection< GraphType >::GNodeSCCInfo ( ) const

inline

Definition at line 133 of file SCC.h.

    {
        return _NodeSCCAuxInfo;
    }

graph()

template<class GraphType >

const GraphType& SVF::SCCDetection< GraphType >::graph ( )

inline

Definition at line 186 of file SCC.h.

    {
        return _graph;
    }

inSCC()

template<class GraphType >

bool SVF::SCCDetection< GraphType >::inSCC ( NodeID  n )

inlineprivate

Definition at line 205 of file SCC.h.

    {
        return _NodeSCCAuxInfo[n].inSCC();
    }

isInCycle()

template<class GraphType >

bool SVF::SCCDetection< GraphType >::isInCycle ( NodeID  n ) const

inline

whether the node is in a cycle

Definition at line 149 of file SCC.h.

    {
        NodeID rep = repNode(n);
        // multi-node cycle
        if (subNodes(rep).count() > 1)
        {
            return true;
        }
        // self-cycle
        else
        {
            child_iterator EI = GTraits::direct_child_begin(Node(rep));
            child_iterator EE = GTraits::direct_child_end(Node(rep));
            for (; EI != EE; ++EI)
            {
                NodeID w = Node_Index(*EI);
                if(w==rep)
                    return true;
            }
            return false;
        }
    }

isInSCC()

template<class GraphType >

bool SVF::SCCDetection< GraphType >::isInSCC ( NodeID  n )

inlineprivate

Definition at line 234 of file SCC.h.

    {
        return _NodeSCCAuxInfo[n].inSCC();
    }

Node()

template<class GraphType >

GNODE SVF::SCCDetection< GraphType >::Node ( NodeID  id ) const

inlineprivate

Definition at line 239 of file SCC.h.

    {
        return GTraits::getNode(_graph, id);
    }

Node_Index()

template<class GraphType >

NodeID SVF::SCCDetection< GraphType >::Node_Index ( GNODE  node ) const

inlineprivate

Definition at line 244 of file SCC.h.

    {
        return GTraits::getNodeID(node);
    }

rep() [1/2]

template<class GraphType >

NodeID SVF::SCCDetection< GraphType >::rep ( NodeID  n )

inlineprivate

Definition at line 230 of file SCC.h.

    {
        return _NodeSCCAuxInfo[n].rep();
    }

rep() [2/2]

template<class GraphType >

void SVF::SCCDetection< GraphType >::rep ( NodeID  n, NodeID  r  )

inlineprivate

Definition at line 218 of file SCC.h.

    {
        _NodeSCCAuxInfo[n].rep(r);
        _NodeSCCAuxInfo[r].addSubNodes(n);
        if (n != r)
        {
            _NodeSCCAuxInfo[n].subNodes().clear();
            repNodes.reset(n);
            repNodes.set(r);
        }
    }

repNode()

template<class GraphType >

NodeID SVF::SCCDetection< GraphType >::repNode ( NodeID  n ) const

inline

get the rep node if not found return itself

Definition at line 139 of file SCC.h.

    {
        typename GNODESCCInfoMap::const_iterator it = _NodeSCCAuxInfo.find(n);
        assert(it!=_NodeSCCAuxInfo.end() && "scc rep not found");
        NodeID rep = it->second.rep();
        return rep!= UINT_MAX ? rep : n ;
    }

setInSCC()

template<class GraphType >

void SVF::SCCDetection< GraphType >::setInSCC ( NodeID  n, bool  v  )

inlineprivate

Definition at line 214 of file SCC.h.

    {
        _NodeSCCAuxInfo[n].inSCC(v);
    }

setVisited()

template<class GraphType >

void SVF::SCCDetection< GraphType >::setVisited ( NodeID  n, bool  v  )

inlineprivate

Definition at line 210 of file SCC.h.

    {
        _NodeSCCAuxInfo[n].visited(v);
    }

subNodes()

template<class GraphType >

const NodeBS& SVF::SCCDetection< GraphType >::subNodes ( NodeID  n ) const

inline

get all subnodes in one scc, if size is empty insert itself into the set

Definition at line 173 of file SCC.h.

    {
        typename GNODESCCInfoMap::const_iterator it = _NodeSCCAuxInfo.find(n);
        assert(it!=_NodeSCCAuxInfo.end() && "scc rep not found");
        return it->second.subNodes();
    }

topoNodeStack()

template<class GraphType >

GNodeStack& SVF::SCCDetection< GraphType >::topoNodeStack ( )

inline

Definition at line 128 of file SCC.h.

    {
        return _T;
    }

visit()

template<class GraphType >

void SVF::SCCDetection< GraphType >::visit ( NodeID  v )

inlineprivate

Definition at line 249 of file SCC.h.

    {
        // SVFUtil::outs() << "visit GNODE: " << Node_Index(v)<< "\n";
        _I += 1;
        _D[v] = _I;
        this->rep(v,v);
        this->setVisited(v,true);
 
        child_iterator EI = GTraits::direct_child_begin(Node(v));
        child_iterator EE = GTraits::direct_child_end(Node(v));
 
        for (; EI != EE; ++EI)
        {
            NodeID w = Node_Index(*EI);
 
            if (!this->visited(w))
                visit(w);
            if (!this->inSCC(w))
            {
                NodeID rep;
                rep = _D[this->rep(v)] < _D[this->rep(w)] ?
                      this->rep(v) : this->rep(w);
                this->rep(v,rep);
            }
        }
        if (this->rep(v) == v)
        {
            this->setInSCC(v,true);
            while (!_SS.empty())
            {
                NodeID w = _SS.top();
                if (_D[w] <= _D[v])
                    break;
                else
                {
                    _SS.pop();
                    this->setInSCC(w,true);
                    this->rep(w,v);
                }
            }
            _T.push(v);
        }
        else
            _SS.push(v);
    }

visited()

template<class GraphType >

bool SVF::SCCDetection< GraphType >::visited ( NodeID  n )

inlineprivate

Definition at line 201 of file SCC.h.

    {
        return _NodeSCCAuxInfo[n].visited();
    }

Member Data Documentation

_D

template<class GraphType >

NodeToNodeMap SVF::SCCDetection< GraphType >::_D

private

Definition at line 196 of file SCC.h.

_graph

template<class GraphType >

const GraphType& SVF::SCCDetection< GraphType >::_graph

private

Definition at line 194 of file SCC.h.

_I

template<class GraphType >

NodeID SVF::SCCDetection< GraphType >::_I

private

Definition at line 195 of file SCC.h.

_NodeSCCAuxInfo

template<class GraphType >

GNODESCCInfoMap SVF::SCCDetection< GraphType >::_NodeSCCAuxInfo

private

Definition at line 192 of file SCC.h.

_SS

template<class GraphType >

GNodeStack SVF::SCCDetection< GraphType >::_SS

private

Definition at line 197 of file SCC.h.

_T

template<class GraphType >

GNodeStack SVF::SCCDetection< GraphType >::_T

private

Definition at line 198 of file SCC.h.

repNodes

template<class GraphType >

NodeBS SVF::SCCDetection< GraphType >::repNodes

private

Definition at line 199 of file SCC.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/Graphs/SCC.h