Class BaseGraph

Class BaseGraph#

Defined in File BaseGraph.h

Nested Relationships#

Nested Types#

Inheritance Relationships#

Derived Types#

public DGraph (Class DGraph)
public Graph (Class Graph)

Class Documentation#

class BaseGraph#

BaseGraph is the abstract base class (the “interface”) for a general graph.

It defines graph properties common to directed and undirected graphs. It leaves out some loose ends in the interface:

A node has no notion of incident edges or neighboring nodes because the number of kinds of incident edges or neighboring nodes is dependent upon the graph being directed or undirected.
For the same reason, the method delete(node) cannot delete any incident edges. Therefore the directed or undirected graph must override it with a more complete version. Similarly, the method delete(edge) cannot delete the edge from the list(s) of the nodes involved.
In an analogous manner, the method add(edge) must be overridden with a more complete version that adds the edge into the records of the nodes involved, if needed.

The only restriction on nodes and edges is that they should be unique objects, meaning, an edge or a node cannot be shared between two graphs. A node or edge can also not be inserted twice. Nodes and edges are identified by their pointer values (BaseGraph::Node* and BaseGraph::Edge*).

Following exceptions are thrown by the class (all are subclasses of Exception):

BaseGraph::EmptyEdge — attempt to add, or remove, an empty edge (null pointer)
BaseGraph::DuplicateEdge — attempt to add an edge more than once
BaseGraph::NonexistentEdge — attempt to remove an edge that does not belong to the graph
BaseGraph::EdgeInUse — attempt to add an edge that is already a part of another graph
BaseGraph::EmptyNode — attempt to add, or remove, an empty node (null pointer)
BaseGraph::DuplicateNode — attempt to add a node more than once
BaseGraph::NonexistentNode — attempt to remove a node that does not belong to the graph
BaseGraph::NodeInUse — attempt to add a node that is already a part of another graph
BaseGraph::DeletingRootOfNonSingletonGraph — attempt to delete the root node when graph has more nodes & edges

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

Subclassed by DGraph, Graph

Public Functions

inline BaseGraph()#

inline BaseGraph(Node *root)#

virtual ~BaseGraph()#

inline Node *root()#

inline void set_root(Node *n)#

inline int num_nodes()#

inline int num_edges()#

inline bool isempty()#

void dump(std::ostream&)#

Protected Functions

void add(Edge *e)#

void add(Node *n)#

void remove(Edge *e)#

void remove(Node *n)#

virtual Node *create_DFS_links(Node *start_node) = 0#

virtual Node *create_BFS_links(Node *start_node) = 0#

Protected Attributes

std::set<Node*> node_set#

std::set<Edge*> edge_set#

Node *root_node#

bool DFS_needed#

bool BFS_needed#

Friends

friend class DFSIterator

friend class BFSIterator

friend class NodesIterator

friend class BiDirNodesIterator

friend class EdgesIterator

class BFSIterator : public Iterator #

The BFSiterator calls the virtual function create_BFS_links the first time it is called, or if the graph has been changed since the last call.

Subclassed by DGraph::BFSIterator, Graph::BFSIterator

Public Functions

BFSIterator(BaseGraph &g)#

inline ~BFSIterator()#

inline virtual void operator++()#

inline virtual operator bool()#

Protected Attributes

Node *p#

class BiDirNodesIterator : public Iterator #

The bi-directional node iterator iterates over all the nodes in the graph in no particular order — except that the Forward direction is guaranteed to be opposite of the Reverse direction.

Subclassed by DGraph::BiDirNodesIterator, Graph::BiDirNodesIterator

Public Types

enum dirType#

Values:

enumerator Forward#

enumerator Reverse#

Public Functions

inline BiDirNodesIterator(BaseGraph &g)#

inline BiDirNodesIterator(BaseGraph &g, dirType d)#

inline ~BiDirNodesIterator()#

inline virtual void operator++()#

inline void operator--()#

inline virtual operator bool()#

Protected Attributes

std::set<Node*>::iterator iter#

std::set<Node*>::iterator pre_begin#

BaseGraph *gr#

dirType dir#

class DeletingRootOfNonSingletonGraph : public Exception #

Public Functions

inline DeletingRootOfNonSingletonGraph(BaseGraph::Node *n)#

inline ~DeletingRootOfNonSingletonGraph()#

inline void report(std::ostream &o) const#

class DFSIterator : public Iterator #

The DFSiterator calls the virtual function create_DFS_links the first time it is called, or if the graph has been changed since the last call.

Subclassed by DGraph::DFSIterator, Graph::DFSIterator

Public Functions

DFSIterator(BaseGraph &g)#

inline ~DFSIterator()#

inline virtual void operator++()#

inline virtual operator bool()#

Protected Attributes

Node *p#

class DuplicateEdge : public Exception #

DuplicateEdge exception is thrown if an edge being added is already a part of the graph.

Public Functions

inline DuplicateEdge(BaseGraph::Edge *e)#

inline ~DuplicateEdge()#

void report(std::ostream &o) const#

class DuplicateNode : public Exception #

DuplicateNode exception is thrown if a node being added is already a part of the graph.

Public Functions

inline DuplicateNode(BaseGraph::Node *n)#

inline ~DuplicateNode()#

inline void report(std::ostream &o) const#

class Edge#

Subclassed by DGraph::Edge, Graph::Edge

Public Functions

inline Edge(Node *_n1, Node *_n2)#

inline virtual ~Edge()#

inline virtual void dump(std::ostream &os)#

Protected Attributes

bool in_use#

Node *n1#

Node *n2#

Friends

friend class BaseGraph

friend class BaseGraph::DFSIterator

friend class BaseGraph::BFSIterator

friend class BaseGraph::DuplicateEdge

class EdgeInUse : public Exception #

EdgeInUse exception is thrown if an edge being added is already a part of another graph.

Public Functions

inline EdgeInUse(BaseGraph::Edge *e)#

inline ~EdgeInUse()#

inline void report(std::ostream &o) const#

class EdgesIterator : public Iterator #

The edge iterator iterates over all the edges in the graph in no particular order.

Subclassed by DGraph::EdgesIterator, Graph::EdgesIterator

Public Functions

inline EdgesIterator(BaseGraph &g)#

inline ~EdgesIterator()#

inline virtual void operator++()#

inline virtual operator bool()#

Protected Attributes

std::set<Edge*>::iterator iter#

BaseGraph *gr#

class EmptyEdge : public Exception #

EmptyEdge exception is thrown if an edge being added is null (0)

Public Functions

inline EmptyEdge()#

inline ~EmptyEdge()#

inline void report(std::ostream &o) const#

class EmptyNode : public Exception #

EmptyNode exception is thrown if a node being added is null (0)

Public Functions

inline EmptyNode()#

inline ~EmptyNode()#

inline void report(std::ostream &o) const#

class Node#

Subclassed by DGraph::Node, Graph::Node

Public Functions

inline Node()#

inline virtual ~Node()#

inline virtual void dump(std::ostream &os)#

Protected Attributes

bool in_use#

Node *dfs_succ#

Node *bfs_succ#

Friends

friend class BaseGraph

friend class BaseGraph::DFSIterator

friend class BaseGraph::BFSIterator

class NodeInUse : public Exception #

NodeInUse exception is thrown if a node being added is already a part of another graph.

Public Functions

inline NodeInUse(BaseGraph::Node *n)#

inline ~NodeInUse()#

inline void report(std::ostream &o) const#

class NodesIterator : public Iterator #

The node iterator iterates over all the nodes in the graph in no particular order.

Subclassed by DGraph::NodesIterator, Graph::NodesIterator

Public Functions

inline NodesIterator(BaseGraph &g)#

inline ~NodesIterator()#

inline virtual void operator++()#

inline virtual operator bool()#

Protected Attributes

std::set<Node*>::iterator iter#

BaseGraph *gr#

class NonexistentEdge : public Exception #

NonexistentEdge exception is thrown if an edge being deleted is not a part of the graph.

Public Functions

inline NonexistentEdge(BaseGraph::Edge *e)#

inline ~NonexistentEdge()#

inline void report(std::ostream &o) const#

class NonexistentNode : public Exception #

NonexistentNode exception is thrown if a node being deleted is not a part of the graph.

Public Functions

inline NonexistentNode(BaseGraph::Node *n)#

inline ~NonexistentNode()#

inline void report(std::ostream &o) const#

Class BaseGraph

Contents

Class BaseGraph#

Nested Relationships#

Nested Types#

Inheritance Relationships#

Derived Types#

Class Documentation#