jacint@131: // -*- mode:C++ -*-
jacint@131: 
jacint@131: #ifndef J_GRAPH_H
jacint@131: #define J_GRAPH_H
jacint@131: 
jacint@131: #include <iostream>
jacint@131: #include <vector>
jacint@131: 
jacint@131: namespace hugo {
jacint@131: 
jacint@131:   class JGraph {
jacint@131: 
jacint@131:     struct NodeT 
jacint@131:     {
jacint@131:       int in, out;      
jacint@131:       NodeT() : in(), out() {}
jacint@131:     };
jacint@131:    
jacint@131:     struct EdgeT 
jacint@131:     {
jacint@131:       int head, tail, in, out;      
jacint@131:     };
jacint@131: 
jacint@131: 
jacint@131:     std::vector<NodeT> nodes;
jacint@131:     std::vector<EdgeT> edges;
jacint@131:     
jacint@131: 
jacint@131:     /*    template <typename Key> class DynMapBase
jacint@131:     {
jacint@131:     protected:
jacint@131:       SmartGraph* G; 
jacint@131:     public:
jacint@131:       virtual void add(const Key k) = NULL;
jacint@131:       virtual void erase(const Key k) = NULL;
jacint@131:       DynMapBase(SmartGraph &_G) : G(&_G) {}
jacint@131:       virtual ~DynMapBase() {}
jacint@131:       friend class SmartGraph;
jacint@131:       };
jacint@131: 
jacint@131:     template <typename T> class DynEdgeMap;
jacint@131:     template <typename T> class DynEdgeMap;
jacint@131:     */
jacint@131: 
jacint@131:   public:
jacint@131:   
jacint@131:     class TrivNodeIt;
jacint@131:     class TrivEdgeIt;
jacint@131:     class NodeIt;
jacint@131:     class EdgeIt;
jacint@131:     class OutEdgeIt;
jacint@131:     class InEdgeIt;
jacint@131:     
jacint@131:     /*  protected:
jacint@131:     std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
jacint@131:     std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
jacint@131:     */
jacint@131: 
jacint@131:     template <typename T> class NodeMap;
jacint@131:     template <typename T> class EdgeMap;
jacint@131:     
jacint@131:   public:
jacint@131: 
jacint@131:     JGraph() : nodes(1), edges(1) {
jacint@131:       edges[0].head=0; 
jacint@131:       edges[0].tail=0; 
jacint@131:       edges[0].in=0; //numEdges (numNodes is maintained in nodes[0].in)
jacint@131:       edges[0].out=0; 
jacint@131:     }    
jacint@131: 
jacint@131: 
jacint@131:     /*    ~SmartGraph()
jacint@131:     {
jacint@131:       for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
jacint@131: 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
jacint@131:       for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
jacint@131: 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
jacint@131: 	  }*/
jacint@131: 
jacint@131:     int numNodes() const { return nodes[0].in; }
jacint@131:     int numEdges() const { return edges[0].in; } 
jacint@131: 
jacint@131:     TrivNodeIt tail(TrivEdgeIt e) const { return edges[e.n].tail; }
jacint@131:     TrivNodeIt head(TrivEdgeIt e) const { return edges[e.n].head; }
jacint@131: 
jacint@131:     /*    EachNodeIt& getFirst(EachNodeIt& v) const { 
jacint@131:       v=EachNodeIt(*this); return v; }
jacint@131:     EachEdgeIt& getFirst(EachEdgeIt& e) const { 
jacint@131:       e=EachEdgeIt(*this); return e; }
jacint@131:     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const { 
jacint@131:       e=OutEdgeIt(*this,v); return e; }
jacint@131:     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const { 
jacint@131:       e=InEdgeIt(*this,v); return e; }
jacint@131:     */
jacint@131: 
jacint@131:     NodeIt firstNode() const { 
jacint@131:       return NodeIt( numNodes() );
jacint@131:     }
jacint@131:     EdgeIt firstEdge() const { 
jacint@131:       return EdgeIt( numEdges() );
jacint@131:     }
jacint@131:     InEdgeIt firstIn(TrivNodeIt v) const { 
jacint@131:       return InEdgeIt(nodes[v.n].in);
jacint@131:     }
jacint@131:     OutEdgeIt firstOut(TrivNodeIt v) const { 
jacint@131:       return OutEdgeIt(nodes[v.n].out);
jacint@131:     }
jacint@131: 
jacint@131: 
jacint@131:    
jacint@131:     void next(NodeIt& it) const {--it.n;}
jacint@131:     void next(OutEdgeIt& it) const { it.n=edges[it.n].out; }
jacint@131:     void next(InEdgeIt& it) const { it.n=edges[it.n].in; }
jacint@131:     void next(EdgeIt& it) const {--it.n;}
jacint@131:     
jacint@131:     int id(TrivNodeIt v) const { return v.n; }
jacint@131:     int id(TrivEdgeIt e) const { return e.n; }
jacint@131: 
jacint@131:     TrivNodeIt addNode() {
jacint@131:       TrivNodeIt n; 
jacint@131:       n.n=++nodes[0].in;
jacint@131:       nodes.push_back(NodeT()); //FIXME
jacint@131: 
jacint@131:       /*      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
jacint@131: 	      i!=dyn_node_maps.end(); ++i) (**i).add(n.n);*/
jacint@131: 
jacint@131:       return n;
jacint@131:     }
jacint@131:     
jacint@131: 
jacint@131:     TrivEdgeIt addEdge(TrivNodeIt u, TrivNodeIt v) {
jacint@131:       if ( u && v ) {
jacint@131:       TrivEdgeIt e; 
jacint@131:       e.n=++edges[0].in;
jacint@131:       edges.push_back(EdgeT()); //FIXME: Hmmm...
jacint@131:       edges[e.n].tail=u.n;   edges[e.n].head=v.n;
jacint@131:       edges[e.n].out=nodes[u.n].out;
jacint@131:       edges[e.n].in=nodes[v.n].in;
jacint@131:       nodes[u.n].out=nodes[v.n].in=e.n;
jacint@131:       return e;
jacint@131:       } 
jacint@131:       else return TrivEdgeIt();
jacint@131: 
jacint@131: 	       /*      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
jacint@131: 		       i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);*/
jacint@131: 
jacint@131:       
jacint@131:     }
jacint@131: 
jacint@131: 
jacint@131:     void clear() {
jacint@131:       nodes.resize(1);
jacint@131:       edges.resize(1); edges[0].in=0;
jacint@131:     }
jacint@131: 
jacint@131: 
jacint@131:     class TrivNodeIt {
jacint@131:       friend class JGraph;
jacint@131:       template <typename T> friend class NodeMap;
jacint@131:       
jacint@131:       friend class TrivEdgeIt;
jacint@131:       friend class OutEdgeIt;
jacint@131:       friend class InEdgeIt;
jacint@131: 
jacint@131:     protected:
jacint@131:       int n;
jacint@131:     public:
jacint@131:       TrivNodeIt() : n() {}
jacint@131:       TrivNodeIt(int number) {n=number;}
jacint@131:       bool operator==(const TrivNodeIt i) const {return n==i.n;}
jacint@131:       bool operator!=(const TrivNodeIt i) const {return n!=i.n;}
jacint@131:    
jacint@131:       operator bool() const  { return n!=0; }
jacint@131:    
jacint@131:  };
jacint@131:     
jacint@131: 
jacint@131:     class NodeIt : public TrivNodeIt {
jacint@131:       friend class JGraph;
jacint@131:     public:
jacint@131:       NodeIt() : TrivNodeIt() { }
jacint@131:       NodeIt(int i) : TrivNodeIt(i) { }
jacint@131:       operator bool() const  { return n!=0; }
jacint@131:     };
jacint@131: 
jacint@131: 
jacint@131:     class TrivEdgeIt {
jacint@131:       friend class JGraph;
jacint@131:       template <typename T> friend class EdgeMap;
jacint@131:       
jacint@131:       friend class TrivNodeIt;
jacint@131:       friend class NodeIt;
jacint@131:     protected:
jacint@131:       int n;
jacint@131:     public:
jacint@131:       TrivEdgeIt() : n() { }
jacint@131:       TrivEdgeIt(int number) {n=number;}
jacint@131:       bool operator==(const TrivEdgeIt i) const {return n==i.n;}
jacint@131:       bool operator!=(const TrivEdgeIt i) const {return n!=i.n;}
jacint@131:       operator bool() const { return n!=0; }
jacint@131:     
jacint@131:  };
jacint@131:     
jacint@131: 
jacint@131:     class EdgeIt : public TrivEdgeIt {
jacint@131:       friend class JGraph;
jacint@131:     public:
jacint@131:       EdgeIt() : TrivEdgeIt() { }
jacint@131:       EdgeIt(int i) : TrivEdgeIt(i) { }
jacint@131:       operator bool() const { return n!=0; } 
jacint@131:  };
jacint@131:     
jacint@131: 
jacint@131:     class OutEdgeIt : public TrivEdgeIt {
jacint@131:       friend class JGraph;
jacint@131:     public: 
jacint@131:       OutEdgeIt() : TrivEdgeIt() { }
jacint@131:       OutEdgeIt(int i) : TrivEdgeIt(i) { }
jacint@131:     };
jacint@131:     
jacint@131: 
jacint@131:     class InEdgeIt : public TrivEdgeIt {
jacint@131:       friend class JGraph;
jacint@131:     public: 
jacint@131:       InEdgeIt() : TrivEdgeIt() { }
jacint@131:       InEdgeIt(int i) : TrivEdgeIt(i) { }
jacint@131:     };
jacint@131: 
jacint@131: 
jacint@131:     // Map types
jacint@131:     
jacint@131:     template <typename T>
jacint@131:     class NodeMap {
jacint@131:       const JGraph& G; 
jacint@131:       std::vector<T> container;
jacint@131:     public:
jacint@131:       NodeMap(const JGraph& _G) : G(_G), container( G.numNodes()+1  ) { }
jacint@131:       NodeMap(const JGraph& _G, T a) : 
jacint@131: 	G(_G), container(G.numNodes()+1, a) { }
jacint@131:       void set(TrivNodeIt n, T a) { container[n.n]=a; }
jacint@131:       T get(TrivNodeIt n) const { return container[n.n]; }
jacint@131:       /*T& operator[](NodeIt n) { return container[n.n]; }
jacint@131: 	const T& operator[](NodeIt n) const { return container[n.n]; }*/
jacint@131:       void update() { container.resize(G.numNodes()+1); }
jacint@131:       void update(T a) { container.resize(G.numNodes()+1, a); }
jacint@131:     };
jacint@131: 
jacint@131:     template <typename T>
jacint@131:     class EdgeMap {
jacint@131:       const JGraph& G; 
jacint@131:       std::vector<T> container;
jacint@131:     public:
jacint@131:       EdgeMap(const JGraph& _G) : G(_G), container(G.numEdges()+1) { }
jacint@131:       EdgeMap(const JGraph& _G, T a) : 
jacint@131: 	G(_G), container(G.numEdges()+1, a) { }
jacint@131:       void set(TrivEdgeIt e, T a) { container[e.n]=a; }
jacint@131:       T get(TrivEdgeIt e) const { return container[e.n]; }
jacint@131:       /*T& operator[](EdgeIt e) { return container[e.n]; } 
jacint@131: 	const T& operator[](EdgeIt e) const { return container[e.n]; } */
jacint@131:       void update() { container.resize(G.numEdges()+1); }
jacint@131:       void update(T a) { container.resize(G.numEdges()+1, a); }
jacint@131:     };
jacint@131: 
jacint@131:     /*template <typename T> class DynNodeMap : public DynMapBase<NodeIt>
jacint@131:     {
jacint@131:       std::vector<T> container;
jacint@131: 
jacint@131:     public:
jacint@131:       typedef T ValueType;
jacint@131:       typedef NodeIt KeyType;
jacint@131: 
jacint@131:       DynNodeMap(JGraph &_G) :
jacint@131: 	DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
jacint@131:       {
jacint@131: 	//FIXME: What if there are empty Id's?
jacint@131: 	//FIXME: Can I use 'this' in a constructor?
jacint@131: 	G->dyn_node_maps.push_back(this);
jacint@131:       }
jacint@131:       ~DynNodeMap()
jacint@131:       {
jacint@131: 	if(G) {
jacint@131: 	  std::vector<DynMapBase<NodeIt>* >::iterator i;
jacint@131: 	  for(i=G->dyn_node_maps.begin();
jacint@131: 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
jacint@131: 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
jacint@131: 	  //A better way to do that: (Is this really important?)
jacint@131: 	  if(*i==this) {
jacint@131: 	    *i=G->dyn_node_maps.back();
jacint@131: 	    G->dyn_node_maps.pop_back();
jacint@131: 	  }
jacint@131: 	}
jacint@131:       }
jacint@131: 
jacint@131:       void add(const NodeIt k) 
jacint@131:       {
jacint@131: 	if(k.n>=container.size()) container.resize(k.n+1);
jacint@131:       }
jacint@131:       void erase(const NodeIt k)
jacint@131:       {
jacint@131: 	//FIXME: Please implement me.
jacint@131:       }
jacint@131:       
jacint@131:       void set(NodeIt n, T a) { container[n.n]=a; }
jacint@131:       T get(NodeIt n) const { return container[n.n]; }
jacint@131:       T& operator[](NodeIt n) { return container[n.n]; }
jacint@131:       const T& operator[](NodeIt n) const { return container[n.n]; }
jacint@131: 
jacint@131:       void update() {}    //Useless for DynMaps
jacint@131:       void update(T a) {}  //Useless for DynMaps
jacint@131:     };
jacint@131:     
jacint@131:     template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>
jacint@131:     {
jacint@131:       std::vector<T> container;
jacint@131: 
jacint@131:     public:
jacint@131:       typedef T ValueType;
jacint@131:       typedef EdgeIt KeyType;
jacint@131: 
jacint@131:       DynEdgeMap(JGraph &_G) :
jacint@131: 	DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
jacint@131:       {
jacint@131: 	//FIXME: What if there are empty Id's?
jacint@131: 	//FIXME: Can I use 'this' in a constructor?
jacint@131: 	G->dyn_edge_maps.push_back(this);
jacint@131:       }
jacint@131:       ~DynEdgeMap()
jacint@131:       {
jacint@131: 	if(G) {
jacint@131: 	  std::vector<DynMapBase<EdgeIt>* >::iterator i;
jacint@131: 	  for(i=G->dyn_edge_maps.begin();
jacint@131: 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
jacint@131: 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
jacint@131: 	  //A better way to do that: (Is this really important?)
jacint@131: 	  if(*i==this) {
jacint@131: 	    *i=G->dyn_edge_maps.back();
jacint@131: 	    G->dyn_edge_maps.pop_back();
jacint@131: 	  }
jacint@131: 	}
jacint@131:       }
jacint@131:       
jacint@131:       void add(const EdgeIt k) 
jacint@131:       {
jacint@131: 	if(k.n>=int(container.size())) container.resize(k.n+1);
jacint@131:       }
jacint@131:       void erase(const EdgeIt k)
jacint@131:       {
jacint@131: 	//FIXME: Please implement me.
jacint@131:       }
jacint@131:       
jacint@131:       void set(EdgeIt n, T a) { container[n.n]=a; }
jacint@131:       T get(EdgeIt n) const { return container[n.n]; }
jacint@131:       T& operator[](EdgeIt n) { return container[n.n]; }
jacint@131:       const T& operator[](EdgeIt n) const { return container[n.n]; }
jacint@131: 
jacint@131:       void update() {}    //Useless for DynMaps
jacint@131:       void update(T a) {}  //Useless for DynMaps
jacint@131:       };*/
jacint@131:         
jacint@131:   };
jacint@131: } //namespace hugo
jacint@131: 
jacint@131: #endif //J_GRAPH_H