Review request: unw_graph class (unweighted graph)

Question

Here is my new stl-like implementation of an unweighted graph. Could you please tell me what member functions should I include to my library? Thanks in advance.

file: unweighted_graph.hpp

#include <algorithm>
#include <stdexcept>
#include <vector>
#include <map>
#include <set>

using namespace std;

#ifndef __UNWEIGHTED_GRAPH_HPP
#define __UNWEIGHTED_GRAPH_HPP

namespace lemon {
  template< class T, bool dir >
  class unw_graph {
  private:
    map< T, set< T > > adj;
    int vcnt;
    int ecnt;
  public:
    typedef typename map< T, set< T > >::iterator vertex_iterator;
    typedef typename map< T, set< T > >::const_iterator vertex_const_iterator;
    typedef typename set< T >::iterator link_iterator;
    typedef typename set< T >::const_iterator link_const_iterator;
    typedef pair< T, T > link_type;
    typedef size_t size_type;

    vertex_iterator begin() { return adj.begin(); }
    vertex_const_iterator begin() const { return adj.begin(); }

    vertex_iterator end() { return adj.end(); }
    vertex_const_iterator end() const { return adj.end(); }

    unw_graph( ) : adj( map< T, set< T > >() ), vcnt( 0 ), ecnt( 0 ) {}

    void insert_vertex( const T& init ) {
      if( adj.find( init )!=adj.end() ) return;
      else {
        adj.insert( make_pair( init, set< T >() ) );
        vcnt++;
      }
    }

    void insert_link( const pair< T, T > &e ) {
      insert_vertex( e.first );
      insert_vertex( e.second );
      if( adj[ e.first ].find( e.second ) == adj[ e.first ].end() ) {
        adj[ e.first ].insert( e.second );
        ecnt++;
      }
      if( !dir ) {
        if( adj[ e.second ].find( e.first ) == adj[ e.second ].end() ) {
          adj[ e.second ].insert( e.first );
        }
      }
    }

    unw_graph( const vector< pair< T, T > > &edge_list ) : adj( map< T, set< T > >() ), vcnt( 0 ), ecnt( 0 ) {
      typename vector< pair< T, T > >::iterator it;
      for( it=edge_list.begin(); it!=edge_list.end(); ++it ) {
        insert_link( *it );
      }
    }

    void erase_link( const pair< T, T > &e ) {
      if( adj.find( e.first ) == adj.end() || adj.find( e.second ) == adj.end() ) return;
      typename set< T >::iterator it=adj[ e.first ].find( e.second );
      if( it!=adj[ e.first ].end() ) {
        adj[ e.first ].erase( it );
        ecnt--;
      }
      if( !dir ) {
        it=adj[ e.second ].find( e.first );
        if( it!=adj[ e.second ].end() ) {
          adj[ e.second ].erase( it );
        }
      }
    }

    typename map< T, set< T > >::iterator find_vertex( const T& vr ) {
      return adj.find( vr );
    }
    typename map< T, set< T > >::const_iterator find_vertex( const T& vr ) const {
      return adj.find( vr );
    }

    bool connection( const pair< T, T > &e ) {
      if( adj.find( e.first ) == adj.end() || adj.find( e.second ) == adj.end() ) return false;
      else return adj[ e.first ].find( e.second ) != adj[ e.first ].end();
    }

    set< T >& operator[] ( T idx ) {
      return adj[ idx ];
    }
    const set< T >& operator[] ( T idx ) const {
      return adj[ idx ];
    }

    size_t vertices() const { return vcnt; }
    size_t links() const { return ecnt; }
    bool directed() const { return dir; }
  };
}

#endif

file: test1.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include "unweighted_graph.hpp"

using namespace std;

int main() {
  freopen( "file.in", "r", stdin );

  lemon::unw_graph< string, false > g;
  int Ec;
  cin >> Ec;

  while( Ec-- ) {
    string a,b;
    cin >> a >> b;
    g.insert_link( make_pair( a, b ) );
  }

  cout << g.vertices() << " " << g.links() << endl;
  lemon::unw_graph< string, false >::vertex_iterator i;
  for( i=g.begin(); i!=g.end(); ++i ) {
    cout << i->first << ": ";
    lemon::unw_graph< string, false >::link_iterator j;
    for( j=i->second.begin(); j!=i->second.end(); ++j ) {
      cout << *j << " ";
    }
    cout << endl;
  }

  g.erase_link( make_pair( "athens", "lamia" ) );

  cout << g.vertices() << " " << g.links() << endl;
  for( i=g.begin(); i!=g.end(); ++i ) {
    cout << i->first << ": ";
    lemon::unw_graph< string, false >::link_iterator j;
    for( j=i->second.begin(); j!=i->second.end(); ++j ) {
      cout << *j << " ";
    }
    cout << endl;
  }

  return 0;
} 

file: test2.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include "unweighted_graph.hpp"

using namespace std;

int main() {
  freopen( "file2.in", "r", stdin );

  lemon::unw_graph< int, true > g;
  int N,M;
  cin >> N >> M;

  for( int i=0; i<N; ++i ) {
    g.insert_vertex( i+1 );
  }

  while( M-- ) {
    int from,to;
    cin >> from >> to;
    g.insert_link( make_pair( from, to ) );
  }

  for( int i=1; i<=N; ++i ) {
    cout << i << ": ";
    lemon::unw_graph< int, false >::link_iterator j;
    for( j=g[ i ].begin(); j!=g[ i ].end(); ++j ) {
      cout << *j << " ";
    }
    cout << endl;
  }

  return 0;
}

Answer 1

The big pain points:

1. Put the include guards first.
   No point in re-including header files if you don't need to
2. Never use using namespace std; in a header file.
   Anybody that includes your code now has all the standard stuff pushed into global namespace where it can cause huge problems in other peoples code.
   I would even say never use this in your normal source files (but others think that is a bit far (I don't)). If you must import stuff keep it as confined as possable and only import what you need using std::cout; etc.. (still don't do that in global scope in a header file).
3. Double underscore in an identifier is reserved.
   DON'T DO IT WILL BREAK SOMETHING WHEN YOU LEAST EXPECT.

Interface design

Your graph looks like it wants to be treated as a container. Thus it is probably a good idea to make its types look like a standard container. So make the types of the iterators conform. begin() and end() shoud return iterator or const_iterator

typedef typename map< T, set< T > >::iterator vertex_iterator;
typedef typename map< T, set< T > >::const_iterator vertex_const_iterator;

Change too:

typedef typename std::map<T, std::set<T> >   Store;
typedef typename Store::iterator             iterator;
typedef typename Store::const_iterator       const_iterator;

// Now if the type changes you only need to change it in one place.

Misunderstanding of basic std::map/std::set

void insert_vertex( const T& init ) {
  if( adj.find( init )!=adj.end() ) return;
  else {
    adj.insert( make_pair( init, set< T >() ) );
    vcnt++;
  }
}

This is all wasted code. If the map does not contain an element then then operator[] will auto insert a default node using the default constructor for the value type (which in this case is the empty set).

void insert_vertex( const T& init )
{
    adj[init];
    vcnt = adj.size();  // which brings us to the question of why vcnt
                        // is a separate member. When it is just the size of adj?
}

I would say the same here for the set.

  if( adj[ e.first ].find( e.second ) == adj[ e.first ].end() ) {
    adj[ e.first ].insert( e.second );
    ecnt++;
  }

The only reason here you actually need the test is because you need to decide weather to increment ecnt. I would just always insert (sets don't have multiple values the same so an insert of a value that already exists does nothing).

  if (adj[e.first].insert(e.second).second)
  {   ++ecnt;
  }
  // The result of an insert is a std::pair<iterator,bool>
  // Where the iterator points at the value inserted
  // And the bool indicates weather the insert worked (if there already exists
  // a value then it will fail).

Answer 2

Loki Astari's review is good, but I wanted to add a point or two to some future things you might want to address. std::map (and std::set) take a few extra parameters in their template arguments:

template <typename Key, typename Value, typename Compare = std::less<Key>, typename Allocator>
class map
{ 
   //...
};

Allocators are a bit tricky, so we'll ignore that for now. However, you should definitely look at including a Compare parameter for your graph. This will allow users to utilize their own classes for your template parameter T. For example:

struct some_class
{
    int i;
}

struct sc_compare
{
    bool operator()(const some_class& s1, const some_class& s2) 
    { 
        return s1.i < s2.i; 
    }
};

Then users can utilize some_class as verticies: lemon::unw_graph<some_class, false, sc_compare>.