C++ Graph Implementation

You should probably check out boost.graph before going further unless you are trying to learn.

Clearly, you can have nodes with attachments to other nodes. You may wish to model the arcs as separate objects as well.

The reason people may use hash tables or matrices is that those representations may be more efficient for whatever use they will make of the graph. It all depends on what you want to use your graph for.

Here is a sketch for how you might go about it:

class Graph {  public:    Graph() {}    class Node {        friend class std::list< Graph::Node >;        friend class Graph;        Node( Graph & g ) : g_( g ) {}        ~Node();      public:        void destroy() { g_.nodes_.erase( *this ); }        std::set< Arc * > outgoing_;        std::set< Arc * > incoming_;        Graph & g_;        Graph::Arc * newArcTo( Node * );    };    class Arc {        friend class std::list< Graph::Arc >;        friend class Graph;        Arc( Graph & g ) : g_( g ) from_( 0 ), to_( 0 ) {}        ~Arc();      public:        void destroy() { g_.arcs_.erase( *this ); }        Graph & g_;        Graph::Node * from_;        Graph::Node * to_;    };    std::list< Node > nodes_;    std::list< Arc > arcs_;    Node * newNode();    Arc * newArc();};Graph::Node::~Node() {  while( !outgoing_.empty() ) {    delete *outgoing_.begin();  }}Graph::Arc * Graph::Node::newArcTo( Node * n ) {  Graph::Arc * a = g_.newArc();  a->to_ = n;  n->incoming_.insert( a );  a->from_ = this;  outgoing_.insert( a );}Graph::Arc::~Arc() {  if( from_ ) {    from_->outgoing_.erase( this );    to_->incoming_.erase( this );  }}Graph::Node * Graph::newNode() {  nodes_.push_back( Graph::Node( this ) );  return &nodes_.back();}Graph::Node * Graph::newArc() {  nodes_.push_back( Graph::Node( this ) );  return &nodes_.back();}

Obviously, you probably want to be able to name nodes (and arcs) and have iteration by name; you probably also want to make Node and Arc templates on whatever data you want to store in the nodes and arcs, and thus Graph itself needs to be a template of those two types.