Class DGraph

Contents

Class DGraph#

Nested Relationships#

Nested Types#

Inheritance Relationships#

Base Type#

Derived Types#

Class Documentation#

class DGraph : public BaseGraph#

DGraph is the base class for a general directed graph (DGraph) that is in turn derived from BaseGraph.

Algorithms that operate upon abstract directed graphs should, normally, use only this base DGraph class for maximum portability.

No extra restrictions are placed on nodes and edges in addition to those imposed by BaseGraph. This means that self-edges, and multiple edges between two nodes, are allowed.

A directed graph, DGraph, extends BaseGraph by adding DFS and BFS iterators, as well as iterators to enumerate source nodes, sink nodes, incoming edges, and outgoing edges for a node.

NOTE ON friend CLASSES: Many classes (especially DGraph, DGraph::Node, and DGraph::Edge) have many friend classes. This is not a kludge. It is simulating “package” visiblity in Java. We want a limited public interface to Node and Edge and yet give more permissions to methods within the Graph class.

Subclassed by CFG, CallGraph

Public Functions

inline DGraph()#
inline DGraph(Node *root)#
inline virtual ~DGraph()#
virtual void add(DGraph::Edge *e)#
virtual void add(DGraph::Node *n)#
virtual void remove(DGraph::Edge *e)#
virtual void remove(DGraph::Node *n)#

Friends

friend class DFSIterator
friend class BFSIterator
class BFSIterator : public BaseGraph::BFSIterator#

The BFSIterator here is just an extension of BaseGraph::DFSIterator to allow proper casting.

Public Functions

inline BFSIterator(DGraph &g)#
inline virtual ~BFSIterator()#
inline operator Node*()#
inline Node *operator->()#
class BiDirNodesIterator : public BaseGraph::BiDirNodesIterator#

The BiDirNodesIterator is just an extension of BaseGraph::BiDirNodesIterator to provide access to DGraph nodes.

Public Functions

inline BiDirNodesIterator(DGraph &g)#
inline BiDirNodesIterator(DGraph &g, dirType d)#
inline virtual ~BiDirNodesIterator()#
inline operator Node*()#
inline Node *operator->()#
class DFSIterator : public BaseGraph::DFSIterator#

The DFSIterator here is just an extension of BaseGraph::DFSIterator to allow proper casting.

Subclassed by CFG::DFSIterator

Public Functions

inline DFSIterator(DGraph &g)#
inline virtual ~DFSIterator()#
inline operator Node*()#
inline Node *operator->()#
class Edge : public BaseGraph::Edge#

Subclassed by CFG::Edge, CallGraph::Edge

Public Functions

inline Edge(Node *_source, Node *_sink)#
inline virtual ~Edge()#
inline Node *source()#
inline Node *sink()#
inline Node *head()#
inline Node *tail()#

Friends

friend class DGraph
class EdgesIterator : public BaseGraph::EdgesIterator#

The EdgesIterator is just and extension of BaseGraph::EdgesIterator to provide access to DGraph edges.

Public Functions

inline EdgesIterator(DGraph &g)#
inline virtual ~EdgesIterator()#
inline operator Edge*()#
inline Edge *operator->()#
class IncomingEdgesIterator : public Iterator#

Iterator to enumerate all the incoming edges into a node.

Public Functions

inline IncomingEdgesIterator(Node *n)#
inline ~IncomingEdgesIterator()#
inline virtual void operator++()#
inline virtual operator bool()#
inline Edge *operator->()#
inline operator Edge*()#
class Node : public BaseGraph::Node#

An node in an undirected graph has a list of neighboring nodes and a list of incident edges.

Subclassed by CFG::Node, CallGraph::Node

Public Functions

inline Node()#
inline virtual ~Node()#
inline int num_incoming()#
inline int num_outgoing()#

Friends

friend class DGraph::DFSIterator
friend class DGraph::BFSIterator
friend class DGraph::IncomingEdgesIterator
friend class DGraph::OutgoingEdgesIterator
friend class DGraph::SourceNodesIterator
friend class DGraph::SinkNodesIterator
class NodesIterator : public BaseGraph::NodesIterator#

The NodesIterator is just and extension of BaseGraph::NodesIterator to provide access to DGraph nodes.

Public Functions

inline NodesIterator(DGraph &g)#
inline virtual ~NodesIterator()#
inline operator Node*()#
inline Node *operator->()#
class OutgoingEdgesIterator : public Iterator#

Iterator to enumerate all the outgoing edges from a node.

Public Functions

inline OutgoingEdgesIterator(Node *n)#
inline ~OutgoingEdgesIterator()#
inline virtual void operator++()#
inline virtual operator bool()#
inline Edge *operator->()#
inline operator Edge*()#
class SinkNodesIterator : public Iterator#

Iterator to enumerate all the sink nodes.

Public Functions

inline SinkNodesIterator(Node *n)#
inline ~SinkNodesIterator()#
inline virtual void operator++()#
inline virtual operator bool()#
inline Node *operator->()#
inline operator Node*()#
class SourceNodesIterator : public Iterator#

Iterator to enumerate all the source nodes.

Public Functions

inline SourceNodesIterator(Node *n)#
inline ~SourceNodesIterator()#
inline virtual void operator++()#
inline virtual operator bool()#
inline Node *operator->()#
inline operator Node*()#
Contents