source: lemon-0.x/src/work/jacint/j_graph.h @ 308:379e1d50089d

// -*- mode:C++ -*-

#ifndef J_GRAPH_H
#define J_GRAPH_H

#include <iostream>
#include <vector>

namespace hugo {

  class JGraph {

    struct NodeT 
    {
      int in, out;      
      NodeT() : in(), out() {}
    };
   
    struct EdgeT 
    {
      int head, tail, in, out;      
    };


    std::vector<NodeT> nodes;
    std::vector<EdgeT> edges;
    

    /*    template <typename Key> class DynMapBase
    {
    protected:
      SmartGraph* G; 
    public:
      virtual void add(const Key k) = NULL;
      virtual void erase(const Key k) = NULL;
      DynMapBase(SmartGraph &_G) : G(&_G) {}
      virtual ~DynMapBase() {}
      friend class SmartGraph;
      };

    template <typename T> class DynEdgeMap;
    template <typename T> class DynEdgeMap;
    */

  public:
  
    class TrivNodeIt;
    class TrivEdgeIt;
    class NodeIt;
    class EdgeIt;
    class OutEdgeIt;
    class InEdgeIt;
    
    /*  protected:
    std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
    std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
    */

    template <typename T> class NodeMap;
    template <typename T> class EdgeMap;
    
  public:

    JGraph() : nodes(1), edges(1) {
      edges[0].head=0; 
      edges[0].tail=0; 
      edges[0].in=0; //numEdges (numNodes is maintained in nodes[0].in)
      edges[0].out=0; 
    }    


    /*    ~SmartGraph()
    {
      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
          i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
          }*/

    int numNodes() const { return nodes[0].in; }
    int numEdges() const { return edges[0].in; } 

    TrivNodeIt tail(TrivEdgeIt e) const { return edges[e.n].tail; }
    TrivNodeIt head(TrivEdgeIt e) const { return edges[e.n].head; }

    /*    EachNodeIt& getFirst(EachNodeIt& v) const { 
      v=EachNodeIt(*this); return v; }
    EachEdgeIt& getFirst(EachEdgeIt& e) const { 
      e=EachEdgeIt(*this); return e; }
    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const { 
      e=OutEdgeIt(*this,v); return e; }
    InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const { 
      e=InEdgeIt(*this,v); return e; }
    */

    NodeIt firstNode() const { 
      return NodeIt( numNodes() );
    }
    EdgeIt firstEdge() const { 
      return EdgeIt( numEdges() );
    }
    InEdgeIt firstIn(TrivNodeIt v) const { 
      return InEdgeIt(nodes[v.n].in);
    }
    OutEdgeIt firstOut(TrivNodeIt v) const { 
      return OutEdgeIt(nodes[v.n].out);
    }


   
    void next(NodeIt& it) const {--it.n;}
    void next(OutEdgeIt& it) const { it.n=edges[it.n].out; }
    void next(InEdgeIt& it) const { it.n=edges[it.n].in; }
    void next(EdgeIt& it) const {--it.n;}
    
    int id(TrivNodeIt v) const { return v.n; }
    int id(TrivEdgeIt e) const { return e.n; }

    TrivNodeIt addNode() {
      TrivNodeIt n; 
      n.n=++nodes[0].in;
      nodes.push_back(NodeT()); //FIXME

      /*      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
              i!=dyn_node_maps.end(); ++i) (**i).add(n.n);*/

      return n;
    }
    

    TrivEdgeIt addEdge(TrivNodeIt u, TrivNodeIt v) {
      if ( u && v ) {
      TrivEdgeIt e; 
      e.n=++edges[0].in;
      edges.push_back(EdgeT()); //FIXME: Hmmm...
      edges[e.n].tail=u.n;   edges[e.n].head=v.n;
      edges[e.n].out=nodes[u.n].out;
      edges[e.n].in=nodes[v.n].in;
      nodes[u.n].out=nodes[v.n].in=e.n;
      return e;
      } 
      else return TrivEdgeIt();

               /*      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
                       i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);*/

      
    }


    void clear() {
      nodes.resize(1);
      edges.resize(1); edges[0].in=0;
    }


    class TrivNodeIt {
      friend class JGraph;
      template <typename T> friend class NodeMap;
      
      friend class TrivEdgeIt;
      friend class OutEdgeIt;
      friend class InEdgeIt;

    protected:
      int n;
    public:
      TrivNodeIt() : n() {}
      TrivNodeIt(int number) {n=number;}
      bool operator==(const TrivNodeIt i) const {return n==i.n;}
      bool operator!=(const TrivNodeIt i) const {return n!=i.n;}
   
      operator bool() const  { return n!=0; }
   
 };
    

    class NodeIt : public TrivNodeIt {
      friend class JGraph;
    public:
      NodeIt() : TrivNodeIt() { }
      NodeIt(int i) : TrivNodeIt(i) { }
      operator bool() const  { return n!=0; }
    };


    class TrivEdgeIt {
      friend class JGraph;
      template <typename T> friend class EdgeMap;
      
      friend class TrivNodeIt;
      friend class NodeIt;
    protected:
      int n;
    public:
      TrivEdgeIt() : n() { }
      TrivEdgeIt(int number) {n=number;}
      bool operator==(const TrivEdgeIt i) const {return n==i.n;}
      bool operator!=(const TrivEdgeIt i) const {return n!=i.n;}
      operator bool() const { return n!=0; }
    
 };
    

    class EdgeIt : public TrivEdgeIt {
      friend class JGraph;
    public:
      EdgeIt() : TrivEdgeIt() { }
      EdgeIt(int i) : TrivEdgeIt(i) { }
      operator bool() const { return n!=0; } 
 };
    

    class OutEdgeIt : public TrivEdgeIt {
      friend class JGraph;
    public: 
      OutEdgeIt() : TrivEdgeIt() { }
      OutEdgeIt(int i) : TrivEdgeIt(i) { }
    };
    

    class InEdgeIt : public TrivEdgeIt {
      friend class JGraph;
    public: 
      InEdgeIt() : TrivEdgeIt() { }
      InEdgeIt(int i) : TrivEdgeIt(i) { }
    };


    // Map types
    
    template <typename T>
    class NodeMap {
      const JGraph& G; 
      std::vector<T> container;
    public:
      NodeMap(const JGraph& _G) : G(_G), container( G.numNodes()+1  ) { }
      NodeMap(const JGraph& _G, T a) : 
        G(_G), container(G.numNodes()+1, a) { }
      void set(TrivNodeIt n, T a) { container[n.n]=a; }
      T get(TrivNodeIt n) const { return container[n.n]; }
      /*T& operator[](NodeIt n) { return container[n.n]; }
        const T& operator[](NodeIt n) const { return container[n.n]; }*/
      void update() { container.resize(G.numNodes()+1); }
      void update(T a) { container.resize(G.numNodes()+1, a); }
    };

    template <typename T>
    class EdgeMap {
      const JGraph& G; 
      std::vector<T> container;
    public:
      EdgeMap(const JGraph& _G) : G(_G), container(G.numEdges()+1) { }
      EdgeMap(const JGraph& _G, T a) : 
        G(_G), container(G.numEdges()+1, a) { }
      void set(TrivEdgeIt e, T a) { container[e.n]=a; }
      T get(TrivEdgeIt e) const { return container[e.n]; }
      /*T& operator[](EdgeIt e) { return container[e.n]; } 
        const T& operator[](EdgeIt e) const { return container[e.n]; } */
      void update() { container.resize(G.numEdges()+1); }
      void update(T a) { container.resize(G.numEdges()+1, a); }
    };

    /*template <typename T> class DynNodeMap : public DynMapBase<NodeIt>
    {
      std::vector<T> container;

    public:
      typedef T ValueType;
      typedef NodeIt KeyType;

      DynNodeMap(JGraph &_G) :
        DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
      {
        //FIXME: What if there are empty Id's?
        //FIXME: Can I use 'this' in a constructor?
        G->dyn_node_maps.push_back(this);
      }
      ~DynNodeMap()
      {
        if(G) {
          std::vector<DynMapBase<NodeIt>* >::iterator i;
          for(i=G->dyn_node_maps.begin();
              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
          //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
          //A better way to do that: (Is this really important?)
          if(*i==this) {
            *i=G->dyn_node_maps.back();
            G->dyn_node_maps.pop_back();
          }
        }
      }

      void add(const NodeIt k) 
      {
        if(k.n>=container.size()) container.resize(k.n+1);
      }
      void erase(const NodeIt k)
      {
        //FIXME: Please implement me.
      }
      
      void set(NodeIt n, T a) { container[n.n]=a; }
      T get(NodeIt n) const { return container[n.n]; }
      T& operator[](NodeIt n) { return container[n.n]; }
      const T& operator[](NodeIt n) const { return container[n.n]; }

      void update() {}    //Useless for DynMaps
      void update(T a) {}  //Useless for DynMaps
    };
    
    template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>
    {
      std::vector<T> container;

    public:
      typedef T ValueType;
      typedef EdgeIt KeyType;

      DynEdgeMap(JGraph &_G) :
        DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
      {
        //FIXME: What if there are empty Id's?
        //FIXME: Can I use 'this' in a constructor?
        G->dyn_edge_maps.push_back(this);
      }
      ~DynEdgeMap()
      {
        if(G) {
          std::vector<DynMapBase<EdgeIt>* >::iterator i;
          for(i=G->dyn_edge_maps.begin();
              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
          //A better way to do that: (Is this really important?)
          if(*i==this) {
            *i=G->dyn_edge_maps.back();
            G->dyn_edge_maps.pop_back();
          }
        }
      }
      
      void add(const EdgeIt k) 
      {
        if(k.n>=int(container.size())) container.resize(k.n+1);
      }
      void erase(const EdgeIt k)
      {
        //FIXME: Please implement me.
      }
      
      void set(EdgeIt n, T a) { container[n.n]=a; }
      T get(EdgeIt n) const { return container[n.n]; }
      T& operator[](EdgeIt n) { return container[n.n]; }
      const T& operator[](EdgeIt n) const { return container[n.n]; }

      void update() {}    //Useless for DynMaps
      void update(T a) {}  //Useless for DynMaps
      };*/
        
  };
} //namespace hugo

#endif //J_GRAPH_H