   C++ Graph Implementation
  I am interested in creating a C++ graph class.  My previous idea was to create the entire thing out of nodes, with each node pointing to multiple other nodes.  I wasnt able to get very far before I ran into problems.  I see that everybody else is creating either a matrix or a hash table for the implementation.  Is there any reason why my idea would not work?   
  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.