Class Graph

Contents

Class Graph#

Nested Relationships#

Nested Types#

Inheritance Relationships#

Base Type#

Class Documentation#

class Graph : public BaseGraph#

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

Algorithms that operate upon abstract undirected graphs should, normally, use only this base Graph 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.

An undirected graph, Graph, extends BaseGraph by adding DFS and BFS iterators, as well as iterators to enumerate neighboring nodes and incident edges for a node.

NOTE ON friend CLASSES: Many classes (especially Graph, Graph::Node, and Graph::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.

Public Functions

inline Graph()#
inline Graph(Node *root)#
inline virtual ~Graph()#
virtual void add(Graph::Edge *e)#
virtual void add(Graph::Node *n)#
virtual void remove(Graph::Edge *e)#
virtual void remove(Graph::Node *n)#
class BFSIterator : public BaseGraph::BFSIterator#

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

Public Functions

inline BFSIterator(Graph &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 Graph nodes.

Public Functions

inline BiDirNodesIterator(Graph &g)#
inline BiDirNodesIterator(Graph &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.

Public Functions

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

Public Functions

inline Edge(Node *n1, Node *n2)#
inline virtual ~Edge()#
inline Node *node1()#
inline Node *node2()#

Friends

friend class Graph
friend class Graph::NeighborNodesIterator
class EdgesIterator : public BaseGraph::EdgesIterator#

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

Public Functions

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

Incident edges iterator iterates over all the edges incident on a node.

Public Functions

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

Node iterator iterates over all the neighboring nodes.

Public Functions

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

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

Public Functions

inline Node()#
inline virtual ~Node()#

Friends

friend class Graph::Edge
friend class Graph::IncidentEdgesIterator
friend class Graph::NeighborNodesIterator
class NodesIterator : public BaseGraph::NodesIterator#

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

Public Functions

inline NodesIterator(Graph &g)#
inline virtual ~NodesIterator()#
inline operator Node*()#
inline Node *operator->()#
Contents