source: lemon-0.x/src/include/graph.h @ 95:3322fbf254d2

// -*-mode: c++; -*-
#ifndef __GRAPH_H_
#define __GRAPH_H_

//inline void *operator new(size_t s, void *p) { return p; }
#include <new>
#include <vector>

namespace NEGRO 
{
  using namespace std;
  
#include "oldgraph.h"
  
  template <class N, class E> class Graph : protected OldGraph<N,E>
  {
  public:
    typedef E EdgeType;
    typedef N NodeType;
    
    class EdgeIt
    {
    public:
      NEGRO::EdgePoint e;
      bool valid() { return e; }
    };
    
    class InEdgeIt : public EdgeIt {};
    class OutEdgeIt : public EdgeIt {};
    class BiEdgeIt : public EdgeIt {};
    class SymEdgeIt : public EdgeIt {};
    
    typedef int NodeIt;
    
    typedef NodeIt EachNodeIt;
    
    class NodeIterator;
    
    class EdgeIterator;
    class InEdgeIterator;
    class OutEdgeIterator;
    class BiEdgeIterator;
    class SymEdgeIterator;
    class AllEdgeIterator;
    
    class FirstAnythingTypeNode; //Required by the unified First() function.

    friend class NodeIterator;
    friend class EdgeIterator;
    friend class InEdgeIterator;
    friend class OutEdgeIterator;
    friend class BiEdgeIterator;
    friend class SymEdgeIterator;
    friend class EachEdgeIterator;
    
    class NodeIterator
    {
      Graph<N,E> *G;  //operator*() miatt kell!!!
      int n;     //nem kellene, ha itt mutato lenne!!
    public:    
      
      NodeIterator() {;} 
      NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
      {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();} 
      NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
      
      NodeIterator &goNext() { n=G->NextNode(n); return *this;}
      NodeIterator next() const { return NodeIterator(*this).goNext();}
      NodeIterator &operator++() { return goNext();} 
      NodeIterator operator++(int)
      {NodeIterator tmp(*this); goNext(); return tmp;}
      bool valid() { return n!=INVALID; }
      
      N &operator*() const { return G->Data(n); }
      N *operator->() const { return &G->Data(n); }
      
      bool operator==(const NodeIterator &i) const {return n==i.n;}
      bool operator!=(const NodeIterator &i) const {return n!=i.n;}
      
      int index() const { return n; } //If the nodes are indexable 
      friend class Graph;
      friend class EdgeIterator;
      friend class InEdgeIterator;
      friend class OutEdgeIterator;
      friend class BiEdgeIterator;
      friend class SymEdgeIterator;
      friend class EachEdgeIterator;
      friend class FirstAnythingTypeNode;

      //Nem kellene egy:
      //      static NodeIterator &GetInvalid();  ?
    };
    
    class EdgeIterator
    {
      
      Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
      //Ez csak kicsit baj, de:
      // Meg a From() es To() miatt!!!!!!!!!!
      
      NEGRO::EdgeIt e;
      
    public:
      EdgeIterator() {;} //Kell inicializalni? (Nem)
      EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
      
      // Lehet, hogy ez a ketto nem kell!!!
      
      NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
      NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
      NodeIterator opposite(const NodeIterator &n) const
      {return n==tail()?head():tail();}
      
      bool valid() {return e;}
      E &operator*() const { return G->Data(e); }
      E *operator->() const { return &G->Data(e); }
      
      //operator const OutEdgeIterator ();
      //operator const InEdgeIterator ();
      //operator const BiEdgeIterator ();
      //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
      
      bool operator==(const EdgeIterator &i) const {return e==i.e;}
      bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
       
      int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}
      //If the edges are indexable 

      friend class Graph;
      friend class InEdgeIterator;
      friend class OutEdgeIterator;
      friend class BiEdgeIterator;
      friend class SymEdgeIterator;
      friend class EachEdgeIterator;
    };
    
    class BiEdgeIterator : public EdgeIterator
    {
    public:
      BiEdgeIterator &goNextIn()  { e=e->NextIn(); return *this;}
      BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;}
      BiEdgeIterator nextIn() const  {return BiEdgeIterator(*this).goNextIn();}
      BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();}
      
      operator InEdgeIterator ()
      {InEdgeIterator i; i.G=G;i.e=e;return i;}
      operator OutEdgeIterator ()
      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
      //operator const SymEdgeIterator ()
      
      friend class Graph;
    };
    
    class InEdgeIterator : public EdgeIterator
    //Ne a BiEdgeIterator-bol szarmazzon?
    {
    public:
      InEdgeIterator() {}
      InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
      { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}

      InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
      InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
      InEdgeIterator &operator++() { return GoNext();}
      InEdgeIterator operator++(int)
      {InEdgeIterator tmp(*this); GoNext(); return tmp;}
      
      operator const OutEdgeIterator ()
      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const BiEdgeIterator ()
      {EdgeIterator i; i.G=G;i.e=e;return i;}
      //      operator const SymEdgeIterator ();
      
      NodeIterator Anode() const {return To();}
      NodeIterator Bnode() const {return From();}
      
      friend class Graph;
    };
    
    class OutEdgeIterator : public EdgeIterator
    {
    public:
      OutEdgeIterator() {}
      OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
      { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}

      OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}
      OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}
      OutEdgeIterator &operator++() { return goNext();}
      OutEdgeIterator operator++(int)
      {OutEdgeIterator tmp(*this); goNext(); return tmp;}
      
      NodeIterator aNode() const {return tail();}
      NodeIterator bNode() const {return head();}
      
      operator const InEdgeIterator ()
      {InEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const BiEdgeIterator ()
      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
      //operator const SymEdgeIterator(); 
      
      friend class Graph;
    };
    
    class SymEdgeIterator : public EdgeIterator
    {
      NodeIterator n;  // Itt ketszer van a G
      
    public:
      SymEdgeIterator() {}
      SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)
      { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }

      SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}
      SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}
      SymEdgeIterator &operator++() { return goNext();}
      SymEdgeIterator operator++(int)
      {SymEdgeIterator tmp(*this); goNext(); return tmp;}
      
      NodeIterator aNode() const {return n;}
      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
      
      operator const InEdgeIterator ()
      {InEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const OutEdgeIterator ()
      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const BiEdgeIterator ()
      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
      
      friend class Graph;
    };
    
    class EachEdgeIterator : public EdgeIterator
    {
      NodeIterator n;  // Itt ketszer van a G
      
    public:
      EachEdgeIterator() {}
      EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)
      {
        e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
      }  

      EachEdgeIterator &goNext()
      {
        e=e->NextOut();
        if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);
        return *this;
      }
      EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}
      EachEdgeIterator &operator++() { return goNext();}
      EachEdgeIterator operator++(int)
        {EachEdgeIterator tmp(*this); goNext(); return tmp;}
      
      
      NodeIterator aNode() const {return n;}
      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
      
      operator const EdgeIterator ()
      {EdgeIterator i; i.G=G;i.e=e;return i;}
      operator const InEdgeIterator ()
      {InEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const OutEdgeIterator ()
      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const BiEdgeIterator ()
      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
      
      friend class Graph;
    };
    
    typedef NodeIterator DeletingNodeIterator;
    typedef EdgeIterator DeletingEdgeIterator;
    typedef BiEdgeIterator DeletingBiEdgeIterator;
    typedef OutEdgeIterator DeletingOutEdgeIterator;
    typedef InEdgeIterator DeletingInEdgeIterator;
    typedef SymEdgeIterator DeletingSymEdgeIterator;
    
    const NodeIterator firstNode()
    {
      NodeIterator i;
      i.G=this;i.n=OldGraph<N,E>::FirstNode();
      return i;
    }
    
    void getFirst(NodeIt &p)   { p=OldGraph<N,E>::FirstNode(); }
    
    void getFirst(InEdgeIt &p,const NodeIt &n)
    { p=OldGraph<N,E>::FirstIn(n); }
    void getFirst(OutEdgeIt &p,const NodeIt &n)
    { p=OldGraph<N,E>::FirstOut(n); }
    void getFirst(SymEdgeIt &p,const NodeIt &n)
    { p=OldGraph<N,E>::FirstEdge(n); }
    void getFirst(EdgeIt &p) //Vegigmegy mindenen
    { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}

    void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
    
    void getFirst(InEdgeIterator &i,const NodeIterator &n)
    { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
    void getFirst(OutEdgeIterator &i,const NodeIterator &n)
    { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
    void getFirst(SymEdgeIterator &i,const NodeIterator &n)
    { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); }
    void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen
    {
      i.G=this;
      getFirst(i.n);
      i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
    }  
    
    
    
    //Vagy beginnode()?
    const DeletingEdgeIterator firstOut(const NodeIterator &n)
    {
      EdgeIterator i;
      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
      return i;
    }
    const DeletingEdgeIterator firstIn(const NodeIterator &n)
    {
      EdgeIterator i;
      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
      return i;
    }
    const DeletingSymEdgeIterator firstSym(const NodeIterator &n)
    {
      EdgeIterator i;
      i.G=n.G;i.n=n.n;
      i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
      return i;
    }
    
    //    class FirstAnythingType;
    //    friend class FirstAnythingType;

    class FirstAnythingTypeNode
    {
      NodeIterator n;
    public:
      FirstAnythingTypeNode(NodeIterator i) : n(i) {}

      operator const InEdgeIterator () const
      {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
      operator const OutEdgeIterator () const
      {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
      operator const SymEdgeIterator () const
      {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
  
      operator const InEdgeIt () const
      {InEdgeIt i; n.G->GetFirst(i,n);return i;}
      operator const OutEdgeIt () const
      {OutEdgeIt i; n.G->GetFirst(i,n);return i;}
      operator const SymEdgeIt () const
      {SymEdgeIt i; n.G->GetFirst(i,n);return i;}
    };
    
    class FirstAnythingType
    {
      Graph<N,E> *G;
    public:
      FirstAnythingType(Graph<N,E> *gg) : G(gg) {}

      operator const EachEdgeIterator () const
      {EachEdgeIterator i; G->GetFirst(i);return i;}  
      operator const EdgeIt () const
      {EdgeIt i; G->GetFirst(i);return i;}
      operator const NodeIterator () const
      {NodeIterator i; G->GetFirst(i);return i;}  
      operator const NodeIt () const
      {NodeIt i; G->GetFirst(i);return i;}
    } _FST;
    
    //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
    FirstAnythingTypeNode first(NodeIterator &i)
    {FirstAnythingTypeNode t(i); return t;}
    const FirstAnythingType &first() {return _FST;}
    
    // LastNode() vagy endnode() stb. Nem kell?
    
    DeletingNodeIterator addNode()
    {
      DeletingNodeIterator i;
      i.G=this; i.n=OldGraph<N,E>::AddNode();
      return i;
    }
    DeletingEdgeIterator
    addEdge(const NodeIterator from,const NodeIterator to)
    {
      DeletingEdgeIterator i;
      i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
    }
    
    void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
    void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
    
    int nodeNum() { OldGraph<N,E>::NodeNum(); }
    void clean() { OldGraph<N,E>::Clean(); }

    Graph() : _FST(this) {}

    // MAPS:
    template<class T> class NodeMap
    {
      Graph<N,E> *G;
      vector<T> map;

    public:
      typedef T value_type;
      void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
      T get(const NodeIterator i) const {return map[i.Index()];}
      T operator[](NodeIterator i) {return map[i.Index()];}

      void update() { map.resize(G->MaxNode());}

      NodeMap() {}
      void setG(Graph<N,E> &Gr) { G=&Gr; update();}      
    };

    template<class T> class EdgeMap
    {
      Graph<N,E> *G;
      vector<T> map;

    public:
      typedef T value_type;
      void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;}
      T get(const EdgeIterator i) const {return map[i.Index()];}
      T &operator[](EdgeIterator i) {return map[i.Index()];}
      
      void update()
        { map.resize(G->MaxEdge());}
      
      EdgeMap() {}
      void setG(Graph<N,E> &Gr) 
      { G=&Gr ;update();}
      
    };
    

    int maxNode() { return OldGraph<N,E>::MaxNode();}
    int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
    
  };
  
  template <class G> //G is a graph-type
  class Path
  {
  public:
    typedef G Graph;
    typedef typename G::NodeIterator NodeIterator;
    typedef typename G::EdgeIterator EdgeIterator;
    typedef typename G::SymEdgeIterator SymEdgeIterator;
    
  private:
    std::vector<EdgeIterator> path;
    std::vector<bool> reversed;

  public:
    void setLength(int n) { path.resize(n);reversed.resize(n);}
    int getLength() { return path.size(); }
    EdgeIterator &operator[](int n) {return path[n];}
    NodeIterator GetNode(int n) // What about path of length 1?
    {
      return n?
        reversed[n-1]?path[n-1].tail():path[n-1].head():
        reversed[0]?path[0].head():path[0].tail();
    }
    void setRevert(int n,bool r=true) {reversed[n]=r;}
    void setEdge(int n,SymEdgeIterator i)
    {
      path[n]=i;
      reversed[n] = i.head()==i.aNode();
    }
    void setEdge(int n,EdgeIterator i,bool r)
    {
      path[n]=i;
      reversed[n] = r;
    }

    NodeIterator tail() { return getNode(0); }
    NodeIterator head() { return getNode(getLength()); }
  };
  
  /*   Ez itt a fiam kommentje:
       <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
       vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
       <<  < < <  < <  <   .cx..x.c.cc.c          
       mcmn   
  */
};

#endif