// -*-mode: c++; -*-

class Graph
{
public:
  class EdgeIt {};
  
  class InEdgeIt : public EdgeIt
  class OutEdgeIt : public EdgeIt {};
  class SymEdgeIt : public EdgeIt {};
  class EachEdgeIt : public EdgeIt {};

  class NodeIt {};
    
  NodeIt &getFirst(NodeIt &) const;
  InEdgeIt &getFirst(InEdgeIt &,const NodeIt) const;
  OutEdgeIt &getFirst(OutEdgeIt &,const NodeIt) const;
  SymEdgeIt &getFirst(SymEdgeIt &,const NodeIt) const;
  EachEdgeIt &getFirst(EachEdgeIt &) const;

  NodeIt next(const NodeIt) const;
  InEdgeIt next(const InEdgeIt) const;
  OutEdgeIt next(const OutEdgeIt) const;
  SymEdgeIt next(const SymEdgeIt) const;
  EachEdgeIt next(const EachEdgeIt) const;

  NodeIt &goNext(NodeIt &) const;
  InEdgeIt &goNext(InEdgeIt &) const;
  OutEdgeIt &goNext(OutEdgeIt &) const;
  SymEdgeIt &goNext(SymEdgeIt &) const;
  EachEdgeIt &goNext(EachEdgeIt &) const;

  NodeIt head(const EdgeIt) const;
  NodeIt tail(const EdgeIt) const;
  
  NodeIt aNode(const InEdgeIt) const;
  NodeIt aNode(const OutEdgeIt) const;
  NodeIt aNode(const SymEdgeIt) const;

  NodeIt bNode(const InEdgeIt) const;
  NodeIt bNode(const OutEdgeIt) const;
  NodeIt bNode(const SymEdgeIt) const;

  bool valid(const NodeIt) const;
  bool valid(const EdgeIt) const;

  void setInvalid(NodeIt &) const;
  void setInvalid(EdgeIt &) const;
  
  NodeIt addNode();
  EdgeIt addEdge(const NodeIt from,const NodeIt to);
    
  void delete(NodeIt n);
  void delete(EdgeIt e);

  void clear();

  template<class T> class NodeMap
  {
  public:
    typedef T ValueType;
    typedef NodeIt KeyType;
    void set(const NodeIt i, const T &t);
    T get(const NodeIt i) const;
    T &operator[](const NodeIt i);
      
    NodeMap(const Graph &G);
  };

  template<class T> class EdgeMap
  {
  public:
    typedef T ValueType;
    typedef EdgeIt KeyType;
    void set(const EdgeIt i, const T &t);
    T get(const EdgeIt i) const;
    T &operator[](const EdgeIt i);
      
    EdgeMap(const Graph &G);
  };
};