OA::Graph Class Reference

#include <Graph.hpp>

List of all members.

Classes
class	Edge
class	EdgesIterator
class	Node
class	NodesIterator
Public Member Functions
	Graph ()
	Graph (OA_ptr< Node > root)
virtual	~Graph ()
virtual void	addEdge (OA_ptr< Graph::Edge > e)
virtual void	addNode (OA_ptr< Graph::Node > n)
virtual void	removeEdge (OA_ptr< Graph::Edge > e)
virtual void	removeNode (OA_ptr< Graph::Node > n)
Private Member Functions
OA_ptr< BaseGraph::Node >	create_DFS_links (OA_ptr< BaseGraph::Node > start_node)
OA_ptr< BaseGraph::Node >	create_BFS_links (OA_ptr< BaseGraph::Node > start_node)

---

Detailed Description

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.

Definition at line 45 of file Graph.hpp.

---

Constructor & Destructor Documentation

OA::Graph::Graph

(

)

[inline]

Definition at line 104 of file Graph.hpp.

OA::Graph::Graph

(

OA_ptr< Node >

root

)

[inline]

Definition at line 105 of file Graph.hpp.

virtual OA::Graph::~Graph

(

)

[inline, virtual]

Definition at line 106 of file Graph.hpp.

---

Member Function Documentation

void OA::Graph::addEdge

(

OA_ptr< Graph::Edge >

e

)

[virtual]

Add the edge to the set of edges, as well as to the list of incident edges in both the nodes involved. Further, add the two nodes to each other's neighbor lists.

Definition at line 78 of file Graph.cpp.

void OA::Graph::addNode

(

OA_ptr< Graph::Node >

n

)

[virtual]

Add the given node to the set of nodes.

Definition at line 66 of file Graph.cpp.

OA_ptr< BaseGraph::Node > OA::Graph::create_BFS_links

(

OA_ptr< BaseGraph::Node >

n

)

[private]

This routine must be called before a BFS iterator can be used. It traverses the graph in BFS order and adds, in each node, a pointer to the next node in BFS ordering.

Definition at line 56 of file Graph.cpp.

OA_ptr< BaseGraph::Node > OA::Graph::create_DFS_links

(

OA_ptr< BaseGraph::Node >

n

)

[private]

This routine must be called before a DFS iterator can be used. It traverses the graph in DFS order and adds, in each node, a pointer to the next node in DFS ordering.

Definition at line 30 of file Graph.cpp.

void OA::Graph::removeEdge

(

OA_ptr< Graph::Edge >

e

)

[virtual]

Remove this edge from the BaseGraph as well as from the list of incident edges of the two nodes that form this edge.

Definition at line 92 of file Graph.cpp.

void OA::Graph::removeNode

(

OA_ptr< Graph::Node >

n

)

[virtual]

Remove the given node and all the edges incident on it.

Definition at line 106 of file Graph.cpp.

---

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

• Graph.hpp
• Graph.cpp