alpar@1: // -*-mode: c++; -*-
alpar@1: #ifndef __GRAPH_H_
alpar@1: #define __GRAPH_H_
alpar@1: 
alpar@1: //inline void *operator new(size_t s, void *p) { return p; }
alpar@1: #include <new>
alpar@6: #include <vector>
alpar@1: 
alpar@1: namespace NEGRO 
alpar@1: {
alpar@1:   using namespace std;
alpar@1:   
alpar@1: #include "oldgraph.h"
alpar@1:   
alpar@1:   template <class N, class E> class Graph : protected OldGraph<N,E>
alpar@1:   {
alpar@1:   public:
alpar@1:     typedef E EdgeType;
alpar@1:     typedef N NodeType;
alpar@1:     
alpar@1:     class EdgePoint
alpar@1:     {
alpar@1:     public:
alpar@1:       NEGRO::EdgePoint e;
alpar@1:       bool isValid() { return e; }
alpar@1:     };
alpar@1:     
alpar@1:     class InEdgePoint : public EdgePoint {};
alpar@1:     class OutEdgePoint : public EdgePoint {};
alpar@1:     class BiEdgePoint : public EdgePoint {};
alpar@1:     class SymEdgePoint : public EdgePoint {};
alpar@1:     
alpar@1:     typedef int NodePoint;
alpar@1:     
alpar@1:     class NodeIterator;
alpar@1:     
alpar@1:     class EdgeIterator;
alpar@1:     class InEdgeIterator;
alpar@1:     class OutEdgeIterator;
alpar@1:     class BiEdgeIterator;
alpar@1:     class SymEdgeIterator;
alpar@1:     class AllEdgeIterator;
alpar@1:     
alpar@6:     class FirstAnythingTypeNode; //Required by the unified First() function.
alpar@1: 
alpar@1:     friend class NodeIterator;
alpar@1:     friend class EdgeIterator;
alpar@1:     friend class InEdgeIterator;
alpar@1:     friend class OutEdgeIterator;
alpar@1:     friend class BiEdgeIterator;
alpar@1:     friend class SymEdgeIterator;
alpar@1:     friend class AllEdgeIterator;
alpar@1:     
alpar@1:     class NodeIterator
alpar@1:     {
alpar@1:       Graph<N,E> *G;  //operator*() miatt kell!!!
alpar@1:       int n;     //nem kellene, ha itt mutato lenne!!
alpar@1:     public:    
alpar@1:       
alpar@1:       NodeIterator() {;} 
alpar@3:       NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
alpar@3:       {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();} 
alpar@1:       NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
alpar@1:       
alpar@1:       NodeIterator &GoNext() { n=G->NextNode(n); return *this;}
alpar@1:       NodeIterator Next() const { return NodeIterator(*this).GoNext();}
alpar@1:       NodeIterator &operator++() { return GoNext();} 
alpar@1:       NodeIterator operator++(int)
alpar@1:       {NodeIterator tmp(*this); GoNext(); return tmp;}
alpar@1:       bool isValid() { return n!=INVALID; }
alpar@1:       
alpar@1:       N &operator*() const { return G->Data(n); }
alpar@1:       N *operator->() const { return &G->Data(n); }
alpar@1:       
alpar@1:       bool operator==(const NodeIterator &i) const {return n==i.n;}
alpar@1:       bool operator!=(const NodeIterator &i) const {return n!=i.n;}
alpar@1:       
alpar@8:       int Index() const { return n; } //If the nodes are indexable 
alpar@1:       friend class Graph;
alpar@1:       friend class EdgeIterator;
alpar@1:       friend class InEdgeIterator;
alpar@1:       friend class OutEdgeIterator;
alpar@1:       friend class BiEdgeIterator;
alpar@1:       friend class SymEdgeIterator;
alpar@1:       friend class AllEdgeIterator;
alpar@1:       friend class FirstAnythingTypeNode;
alpar@1: 
alpar@1:       //Nem kellene egy:
alpar@1:       //      static NodeIterator &GetInvalid();  ?
alpar@1:     };
alpar@1:     
alpar@1:     class EdgeIterator
alpar@1:     {
alpar@1:       
alpar@1:       Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
alpar@1:       //Ez csak kicsit baj, de:
alpar@1:       // Meg a From() es To() miatt!!!!!!!!!!
alpar@1:       
alpar@1:       NEGRO::EdgePoint e;
alpar@1:       
alpar@1:     public:
alpar@1:       EdgeIterator() {;} //Kell inicializalni? (Nem)
alpar@1:       EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
alpar@1:       
alpar@1:       // Lehet, hogy ez a ketto nem kell!!!
alpar@1:       
alpar@1:       NodeIterator From() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
alpar@1:       NodeIterator To() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
alpar@1:       
alpar@1:       bool isValid() {return e;}
alpar@1:       E &operator*() const { return G->Data(e); }
alpar@1:       E *operator->() const { return &G->Data(e); }
alpar@1:       
alpar@1:       //operator const OutEdgeIterator ();
alpar@1:       //operator const InEdgeIterator ();
alpar@1:       //operator const BiEdgeIterator ();
alpar@1:       //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
alpar@1:       
alpar@1:       bool operator==(const EdgeIterator &i) const {return e==i.e;}
alpar@1:       bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
alpar@2:        
alpar@8:       int Index() const { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
alpar@2:       //If the edges are indexable 
alpar@2: 
alpar@1:       friend class Graph;
alpar@1:       friend class InEdgeIterator;
alpar@1:       friend class OutEdgeIterator;
alpar@1:       friend class BiEdgeIterator;
alpar@1:       friend class SymEdgeIterator;
alpar@1:       friend class AllEdgeIterator;
alpar@1:     };
alpar@1:     
alpar@1:     class BiEdgeIterator : public EdgeIterator
alpar@1:     {
alpar@1:     public:
alpar@1:       BiEdgeIterator &GoNextIn()  { e=e->NextIn(); return *this;}
alpar@1:       BiEdgeIterator &GoNextOut() { e=e->NextOut(); return *this;}
alpar@1:       BiEdgeIterator NextIn() const  {return BiEdgeIterator(*this).GoNextIn();}
alpar@1:       BiEdgeIterator NextOut() const {return BiEdgeIterator(*this).GoNextOut();}
alpar@1:       
alpar@1:       operator InEdgeIterator ()
alpar@1:       {InEdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       operator OutEdgeIterator ()
alpar@1:       {OutEdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       //operator const SymEdgeIterator ()
alpar@1:       
alpar@1:       friend class Graph;
alpar@1:     };
alpar@1:     
alpar@1:     class InEdgeIterator : public EdgeIterator
alpar@1:     //Ne a BiEdgeIterator-bol szarmazzon?
alpar@1:     {
alpar@1:     public:
alpar@3:       InEdgeIterator() {}
alpar@3:       InEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &n)
alpar@3:       { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
alpar@3: 
alpar@1:       InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
alpar@1:       InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
alpar@1:       InEdgeIterator &operator++() { return GoNext();}
alpar@1:       InEdgeIterator operator++(int)
alpar@1:       {InEdgeIterator tmp(*this); GoNext(); return tmp;}
alpar@1:       
alpar@1:       operator const OutEdgeIterator ()
alpar@1:       {OutEdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       operator const BiEdgeIterator ()
alpar@1:       {EdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       //      operator const SymEdgeIterator ();
alpar@1:       
alpar@1:       NodeIterator Anode() const {return To();}
alpar@1:       NodeIterator Bnode() const {return From();}
alpar@1:       
alpar@1:       friend class Graph;
alpar@1:     };
alpar@1:     
alpar@1:     class OutEdgeIterator : public EdgeIterator
alpar@1:     {
alpar@1:     public:
alpar@3:       OutEdgeIterator() {}
alpar@3:       OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
alpar@3:       { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
alpar@3: 
alpar@1:       OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;}
alpar@1:       OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}
alpar@1:       OutEdgeIterator &operator++() { return GoNext();}
alpar@1:       OutEdgeIterator operator++(int)
alpar@1:       {OutEdgeIterator tmp(*this); GoNext(); return tmp;}
alpar@1:       
alpar@1:       NodeIterator Anode() const {return From();}
alpar@1:       NodeIterator Bnode() const {return To();}
alpar@1:       
alpar@1:       operator const InEdgeIterator ()
alpar@1:       {InEdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       operator const BiEdgeIterator ()
alpar@1:       {BiEdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       //operator const SymEdgeIterator(); 
alpar@1:       
alpar@1:       friend class Graph;
alpar@1:     };
alpar@1:     
alpar@1:     class SymEdgeIterator : public EdgeIterator
alpar@1:     {
alpar@1:       NodeIterator n;  // Itt ketszer van a G
alpar@1:       
alpar@1:     public:
alpar@3:       SymEdgeIterator() {}
alpar@3:       SymEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &nn)
alpar@3:       { G=&Gr; n=nn; e=Gr.FirstSym(nn.n); }
alpar@3: 
alpar@1:       SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;}
alpar@1:       SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}
alpar@1:       SymEdgeIterator &operator++() { return GoNext();}
alpar@1:       SymEdgeIterator operator++(int)
alpar@1:       {SymEdgeIterator tmp(*this); GoNext(); return tmp;}
alpar@1:       
alpar@1:       NodeIterator Anode() const {return n;}
alpar@1:       NodeIterator Bnode() const {return n.n==From().n?To():From();}
alpar@1:       
alpar@1:       operator const InEdgeIterator ()
alpar@1:       {InEdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       operator const OutEdgeIterator ()
alpar@1:       {OutEdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       operator const BiEdgeIterator ()
alpar@1:       {BiEdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       
alpar@1:       friend class Graph;
alpar@1:     };
alpar@1:     
alpar@1:     class AllEdgeIterator : public EdgeIterator
alpar@1:     {
alpar@1:       NodeIterator n;  // Itt ketszer van a G
alpar@1:       
alpar@1:     public:
alpar@3:       AllEdgeIterator() {}
alpar@3:       AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)
alpar@3:       {
alpar@3: 	e=n.isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
alpar@3:       }  
alpar@3: 
alpar@1:       AllEdgeIterator &GoNext()
alpar@1:       {
alpar@1: 	e=e->NextOut();
alpar@1: 	if(!e && (++n).isValid()) e=G->OldGraph<N,E>::FirstOut(n.n);
alpar@1: 	return *this;
alpar@1:       }
alpar@1:       AllEdgeIterator Next() const {return AllEdgeIterator(*this).GoNext();}
alpar@1:       AllEdgeIterator &operator++() { return GoNext();}
alpar@1:       AllEdgeIterator operator++(int)
alpar@1: 	{AllEdgeIterator tmp(*this); GoNext(); return tmp;}
alpar@1:       
alpar@1:       
alpar@1:       NodeIterator Anode() const {return n;}
alpar@1:       NodeIterator Bnode() const {return n.n==From().n?To():From();}
alpar@1:       
alpar@1:       operator const InEdgeIterator ()
alpar@1:       {InEdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       operator const OutEdgeIterator ()
alpar@1:       {OutEdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       operator const BiEdgeIterator ()
alpar@1:       {BiEdgeIterator i; i.G=G;i.e=e;return i;}
alpar@1:       
alpar@1:       friend class Graph;
alpar@1:     };
alpar@1:     
alpar@1:     typedef NodeIterator DeletingNodeIterator;
alpar@1:     typedef EdgeIterator DeletingEdgeIterator;
alpar@1:     typedef BiEdgeIterator DeletingBiEdgeIterator;
alpar@1:     typedef OutEdgeIterator DeletingOutEdgeIterator;
alpar@1:     typedef InEdgeIterator DeletingInEdgeIterator;
alpar@1:     typedef SymEdgeIterator DeletingSymEdgeIterator;
alpar@1:     
alpar@3:     const NodeIterator FirstNode()
alpar@1:     {
alpar@1:       NodeIterator i;
alpar@1:       i.G=this;i.n=OldGraph<N,E>::FirstNode();
alpar@1:       return i;
alpar@1:     }
alpar@1:     
alpar@1:     void GetFirst(NodePoint &p)   { p=OldGraph<N,E>::FirstNode(); }
alpar@1:     
alpar@1:     void GetFirst(InEdgePoint &p,const NodePoint &n)
alpar@1:     { p=OldGraph<N,E>::FirstIn(n); }
alpar@1:     void GetFirst(OutEdgePoint &p,const NodePoint &n)
alpar@1:     { p=OldGraph<N,E>::FirstOut(n); }
alpar@1:     void GetFirst(SymEdgePoint &p,const NodePoint &n)
alpar@1:     { p=OldGraph<N,E>::FirstEdge(n); }
alpar@1:     void GetFirst(EdgePoint &p) //Vegigmegy mindenen
alpar@1:     { p.e=NodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
alpar@1: 
alpar@1:     void GetFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
alpar@1:     
alpar@1:     void GetFirst(InEdgeIterator &i,const NodeIterator &n)
alpar@1:     { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
alpar@1:     void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
alpar@1:     { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
alpar@1:     void GetFirst(SymEdgeIterator &i,const NodeIterator &n)
alpar@1:     { i.G=this;i.e=OldGraph<N,E>::FirstSym(n.n); }
alpar@1:     void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen
alpar@1:     {
alpar@1:       i.G=this;
alpar@1:       GetFirst(i.n);
alpar@1:       i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
alpar@1:     }  
alpar@1:     
alpar@1:     
alpar@1:     
alpar@1:     //Vagy beginnode()?
alpar@3:     const DeletingEdgeIterator FirstOut(const NodeIterator &n)
alpar@1:     {
alpar@1:       EdgeIterator i;
alpar@1:       i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
alpar@1:       return i;
alpar@1:     }
alpar@3:     const DeletingEdgeIterator FirstIn(const NodeIterator &n)
alpar@1:     {
alpar@1:       EdgeIterator i;
alpar@1:       i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
alpar@1:       return i;
alpar@1:     }
alpar@3:     const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)
alpar@1:     {
alpar@1:       EdgeIterator i;
alpar@1:       i.G=n.G;i.n=n.n;
alpar@1:       i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
alpar@1:       return i;
alpar@1:     }
alpar@1:     
alpar@1:     //    class FirstAnythingType;
alpar@1:     //    friend class FirstAnythingType;
alpar@1: 
alpar@1:     class FirstAnythingTypeNode
alpar@1:     {
alpar@1:       NodeIterator n;
alpar@1:     public:
alpar@1:       FirstAnythingTypeNode(NodeIterator i) : n(i) {}
alpar@1: 
alpar@1:       operator const InEdgeIterator () const
alpar@1:       {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
alpar@1:       operator const OutEdgeIterator () const
alpar@1:       {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
alpar@1:       operator const SymEdgeIterator () const
alpar@1:       {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
alpar@1:   
alpar@1:       operator const InEdgePoint () const
alpar@1:       {InEdgePoint i; n.G->GetFirst(i,n);return i;}
alpar@1:       operator const OutEdgePoint () const
alpar@1:       {OutEdgePoint i; n.G->GetFirst(i,n);return i;}
alpar@1:       operator const SymEdgePoint () const
alpar@1:       {SymEdgePoint i; n.G->GetFirst(i,n);return i;}
alpar@1:     };
alpar@1:     
alpar@1:     class FirstAnythingType
alpar@1:     {
alpar@1:       Graph<N,E> *G;
alpar@1:     public:
alpar@1:       FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
alpar@1: 
alpar@1:       operator const AllEdgeIterator () const
alpar@1:       {AllEdgeIterator i; G->GetFirst(i);return i;}  
alpar@1:       operator const EdgePoint () const
alpar@1:       {EdgePoint i; G->GetFirst(i);return i;}
alpar@1:       operator const NodeIterator () const
alpar@1:       {NodeIterator i; G->GetFirst(i);return i;}  
alpar@1:       operator const NodePoint () const
alpar@1:       {NodePoint i; G->GetFirst(i);return i;}
alpar@1:     } _FST;
alpar@1:     
alpar@1:     //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
alpar@1:     FirstAnythingTypeNode First(NodeIterator &i)
alpar@1:     {FirstAnythingTypeNode t(i); return t;}
alpar@1:     const FirstAnythingType &First() {return _FST;}
alpar@1:     
alpar@1:     // LastNode() vagy endnode() stb. Nem kell?
alpar@1:     
alpar@1:     DeletingNodeIterator AddNode()
alpar@1:     {
alpar@1:       DeletingNodeIterator i;
alpar@1:       i.G=this; i.n=OldGraph<N,E>::AddNode();
alpar@1:       return i;
alpar@1:     }
alpar@1:     DeletingEdgeIterator
alpar@1:     AddEdge(const NodeIterator from,const NodeIterator to)
alpar@1:     {
alpar@1:       DeletingEdgeIterator i;
alpar@1:       i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
alpar@1:     }
alpar@1:     
alpar@1:     void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
alpar@1:     void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
alpar@1:     
alpar@1:     int NodeNum() { OldGraph<N,E>::NodeNum(); }
alpar@3:     void Clean() { OldGraph<N,E>::Clean(); }
alpar@1: 
alpar@1:     Graph() : _FST(this) {}
alpar@6: 
alpar@6:     // MAPS:
alpar@6:     template<class T> class NodeMap
alpar@6:     {
alpar@6:       Graph<N,E> *G;
alpar@6:       vector<T> map;
alpar@6: 
alpar@6:     public:
alpar@6:       typedef T value_type;
alpar@8:       void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
alpar@8:       T Get(const NodeIterator i) const {return map[i.Index()];}
alpar@8:       T operator[](NodeIterator i) {return map[i.Index()];}
alpar@6: 
alpar@8:       void update() { map.resize(G->MaxNode());}
alpar@6: 
alpar@8:       NodeMap() {}
alpar@8:       void SetG(Graph<N,E> &Gr) { G=&Gr; update();}      
alpar@6:     };
alpar@6: 
alpar@6:     template<class T> class EdgeMap
alpar@6:     {
alpar@6:       Graph<N,E> *G;
alpar@6:       vector<T> map;
alpar@6: 
alpar@6:     public:
alpar@6:       typedef T value_type;
alpar@8:       void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
alpar@8:       T &Get(const NodeIterator i) {return map[i.Index()];}
alpar@6:       T &operator[](NodeIterator i) {return map[i.Index()];}
alpar@6:       
alpar@6:       void update()
alpar@8: 	{ map.resize(G->MaxEdge());}
alpar@6:       
alpar@8:       EdgeMap() {}
alpar@8:       void SetG(Graph<N,E> &Gr) 
alpar@8:       { G=&Gr ;update();}
alpar@6:       
alpar@6:     };
alpar@6:     
alpar@8: 
alpar@8:     int MaxNode() { return OldGraph<N,E>::MaxNode();}
alpar@8:     int MaxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
alpar@8:     
alpar@1:   };
alpar@1:   
alpar@1:   /*   Ez itt a fiam kommentje:
alpar@1:        <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
alpar@1:        vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
alpar@1:        <<  < < <  < <  <   .cx..x.c.cc.c          
alpar@1:        mcmn   
alpar@1:   */
alpar@1:   
alpar@1: }
alpar@1: 
alpar@1: #endif