diff -r 35c2543f45fb -r f45703336699 src/include/graph.h
--- a/src/include/graph.h	Fri Mar 26 23:34:45 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,493 +0,0 @@
-// -*-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