lemon-0.x: src/work/jacint/j_graph.h@fc549fac0dd0

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

     3 #ifndef J_GRAPH_H

     4 #define J_GRAPH_H

     6 #include <iostream>

     7 #include <vector>

     9 namespace hugo {

    11   class JGraph {

    13     struct NodeT

    14     {

    15       int in, out;

    16       NodeT() : in(), out() {}

    17     };

    19     struct EdgeT

    20     {

    21       int head, tail, in, out;

    22     };

    25     std::vector<NodeT> nodes;

    26     std::vector<EdgeT> edges;

    29     /*    template <typename Key> class DynMapBase

    30     {

    31     protected:

    32       SmartGraph* G;

    33     public:

    34       virtual void add(const Key k) = NULL;

    35       virtual void erase(const Key k) = NULL;

    36       DynMapBase(SmartGraph &_G) : G(&_G) {}

    37       virtual ~DynMapBase() {}

    38       friend class SmartGraph;

    39       };

    41     template <typename T> class DynEdgeMap;

    42     template <typename T> class DynEdgeMap;

    43     */

    45   public:

    47     class TrivNodeIt;

    48     class TrivEdgeIt;

    49     class NodeIt;

    50     class EdgeIt;

    51     class OutEdgeIt;

    52     class InEdgeIt;

    54     /*  protected:

    55     std::vector<DynMapBase<NodeIt> * > dyn_node_maps;

    56     std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;

    57     */

    59     template <typename T> class NodeMap;

    60     template <typename T> class EdgeMap;

    62   public:

    64     JGraph() : nodes(1), edges(1) {

    65       edges[0].head=0;

    66       edges[0].tail=0;

    67       edges[0].in=0; //numEdges (numNodes is maintained in nodes[0].in)

    68       edges[0].out=0;

    69     }

    72     /*    ~SmartGraph()

    73     {

    74       for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();

    75 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;

    76       for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();

    77 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;

    78 	  }*/

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

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

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

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

    86     /*    EachNodeIt& getFirst(EachNodeIt& v) const {

    87       v=EachNodeIt(*this); return v; }

    88     EachEdgeIt& getFirst(EachEdgeIt& e) const {

    89       e=EachEdgeIt(*this); return e; }

    90     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const {

    91       e=OutEdgeIt(*this,v); return e; }

    92     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const {

    93       e=InEdgeIt(*this,v); return e; }

    94     */

    96     NodeIt firstNode() const {

    97       return NodeIt( numNodes() );

    98     }

    99     EdgeIt firstEdge() const {

   100       return EdgeIt( numEdges() );

   101     }

   102     InEdgeIt firstIn(TrivNodeIt v) const {

   103       return InEdgeIt(nodes[v.n].in);

   104     }

   105     OutEdgeIt firstOut(TrivNodeIt v) const {

   106       return OutEdgeIt(nodes[v.n].out);

   107     }

   111     void next(NodeIt& it) const {--it.n;}

   112     void next(OutEdgeIt& it) const { it.n=edges[it.n].out; }

   113     void next(InEdgeIt& it) const { it.n=edges[it.n].in; }

   114     void next(EdgeIt& it) const {--it.n;}

   116     int id(TrivNodeIt v) const { return v.n; }

   117     int id(TrivEdgeIt e) const { return e.n; }

   119     TrivNodeIt addNode() {

   120       TrivNodeIt n;

   121       n.n=++nodes[0].in;

   122       nodes.push_back(NodeT()); //FIXME

   124       /*      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();

   125 	      i!=dyn_node_maps.end(); ++i) (**i).add(n.n);*/

   127       return n;

   128     }

   131     TrivEdgeIt addEdge(TrivNodeIt u, TrivNodeIt v) {

   132       if ( u && v ) {

   133       TrivEdgeIt e;

   134       e.n=++edges[0].in;

   135       edges.push_back(EdgeT()); //FIXME: Hmmm...

   136       edges[e.n].tail=u.n;   edges[e.n].head=v.n;

   137       edges[e.n].out=nodes[u.n].out;

   138       edges[e.n].in=nodes[v.n].in;

   139       nodes[u.n].out=nodes[v.n].in=e.n;

   140       return e;

   141       }

   142       else return TrivEdgeIt();

   144 	       /*      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();

   145 		       i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);*/

   148     }

   151     void clear() {

   152       nodes.resize(1);

   153       edges.resize(1); edges[0].in=0;

   154     }

   157     class TrivNodeIt {

   158       friend class JGraph;

   159       template <typename T> friend class NodeMap;

   161       friend class TrivEdgeIt;

   162       friend class OutEdgeIt;

   163       friend class InEdgeIt;

   165     protected:

   166       int n;

   167     public:

   168       TrivNodeIt() : n() {}

   169       TrivNodeIt(int number) {n=number;}

   170       bool operator==(const TrivNodeIt i) const {return n==i.n;}

   171       bool operator!=(const TrivNodeIt i) const {return n!=i.n;}

   173       operator bool() const  { return n!=0; }

   175  };

   178     class NodeIt : public TrivNodeIt {

   179       friend class JGraph;

   180     public:

   181       NodeIt() : TrivNodeIt() { }

   182       NodeIt(int i) : TrivNodeIt(i) { }

   183       operator bool() const  { return n!=0; }

   184     };

   187     class TrivEdgeIt {

   188       friend class JGraph;

   189       template <typename T> friend class EdgeMap;

   191       friend class TrivNodeIt;

   192       friend class NodeIt;

   193     protected:

   194       int n;

   195     public:

   196       TrivEdgeIt() : n() { }

   197       TrivEdgeIt(int number) {n=number;}

   198       bool operator==(const TrivEdgeIt i) const {return n==i.n;}

   199       bool operator!=(const TrivEdgeIt i) const {return n!=i.n;}

   200       operator bool() const { return n!=0; }

   202  };

   205     class EdgeIt : public TrivEdgeIt {

   206       friend class JGraph;

   207     public:

   208       EdgeIt() : TrivEdgeIt() { }

   209       EdgeIt(int i) : TrivEdgeIt(i) { }

   210       operator bool() const { return n!=0; }

   211  };

   214     class OutEdgeIt : public TrivEdgeIt {

   215       friend class JGraph;

   216     public:

   217       OutEdgeIt() : TrivEdgeIt() { }

   218       OutEdgeIt(int i) : TrivEdgeIt(i) { }

   219     };

   222     class InEdgeIt : public TrivEdgeIt {

   223       friend class JGraph;

   224     public:

   225       InEdgeIt() : TrivEdgeIt() { }

   226       InEdgeIt(int i) : TrivEdgeIt(i) { }

   227     };

   230     // Map types

   232     template <typename T>

   233     class NodeMap {

   234       const JGraph& G;

   235       std::vector<T> container;

   236     public:

   237       NodeMap(const JGraph& _G) : G(_G), container( G.numNodes()+1  ) { }

   238       NodeMap(const JGraph& _G, T a) :

   239 	G(_G), container(G.numNodes()+1, a) { }

   240       void set(TrivNodeIt n, T a) { container[n.n]=a; }

   241       T get(TrivNodeIt n) const { return container[n.n]; }

   242       /*T& operator[](NodeIt n) { return container[n.n]; }

   243 	const T& operator[](NodeIt n) const { return container[n.n]; }*/

   244       void update() { container.resize(G.numNodes()+1); }

   245       void update(T a) { container.resize(G.numNodes()+1, a); }

   246     };

   248     template <typename T>

   249     class EdgeMap {

   250       const JGraph& G;

   251       std::vector<T> container;

   252     public:

   253       EdgeMap(const JGraph& _G) : G(_G), container(G.numEdges()+1) { }

   254       EdgeMap(const JGraph& _G, T a) :

   255 	G(_G), container(G.numEdges()+1, a) { }

   256       void set(TrivEdgeIt e, T a) { container[e.n]=a; }

   257       T get(TrivEdgeIt e) const { return container[e.n]; }

   258       /*T& operator[](EdgeIt e) { return container[e.n]; }

   259 	const T& operator[](EdgeIt e) const { return container[e.n]; } */

   260       void update() { container.resize(G.numEdges()+1); }

   261       void update(T a) { container.resize(G.numEdges()+1, a); }

   262     };

   264     /*template <typename T> class DynNodeMap : public DynMapBase<NodeIt>

   265     {

   266       std::vector<T> container;

   268     public:

   269       typedef T ValueType;

   270       typedef NodeIt KeyType;

   272       DynNodeMap(JGraph &_G) :

   273 	DynMapBase<NodeIt>(_G), container(_G.maxNodeId())

   274       {

   275 	//FIXME: What if there are empty Id's?

   276 	//FIXME: Can I use 'this' in a constructor?

   277 	G->dyn_node_maps.push_back(this);

   278       }

   279       ~DynNodeMap()

   280       {

   281 	if(G) {

   282 	  std::vector<DynMapBase<NodeIt>* >::iterator i;

   283 	  for(i=G->dyn_node_maps.begin();

   284 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;

   285 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...

   286 	  //A better way to do that: (Is this really important?)

   287 	  if(*i==this) {

   288 	    *i=G->dyn_node_maps.back();

   289 	    G->dyn_node_maps.pop_back();

   290 	  }

   291 	}

   292       }

   294       void add(const NodeIt k)

   295       {

   296 	if(k.n>=container.size()) container.resize(k.n+1);

   297       }

   298       void erase(const NodeIt k)

   299       {

   300 	//FIXME: Please implement me.

   301       }

   303       void set(NodeIt n, T a) { container[n.n]=a; }

   304       T get(NodeIt n) const { return container[n.n]; }

   305       T& operator[](NodeIt n) { return container[n.n]; }

   306       const T& operator[](NodeIt n) const { return container[n.n]; }

   308       void update() {}    //Useless for DynMaps

   309       void update(T a) {}  //Useless for DynMaps

   310     };

   312     template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>

   313     {

   314       std::vector<T> container;

   316     public:

   317       typedef T ValueType;

   318       typedef EdgeIt KeyType;

   320       DynEdgeMap(JGraph &_G) :

   321 	DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())

   322       {

   323 	//FIXME: What if there are empty Id's?

   324 	//FIXME: Can I use 'this' in a constructor?

   325 	G->dyn_edge_maps.push_back(this);

   326       }

   327       ~DynEdgeMap()

   328       {

   329 	if(G) {

   330 	  std::vector<DynMapBase<EdgeIt>* >::iterator i;

   331 	  for(i=G->dyn_edge_maps.begin();

   332 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;

   333 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...

   334 	  //A better way to do that: (Is this really important?)

   335 	  if(*i==this) {

   336 	    *i=G->dyn_edge_maps.back();

   337 	    G->dyn_edge_maps.pop_back();

   338 	  }

   339 	}

   340       }

   342       void add(const EdgeIt k)

   343       {

   344 	if(k.n>=int(container.size())) container.resize(k.n+1);

   345       }

   346       void erase(const EdgeIt k)

   347       {

   348 	//FIXME: Please implement me.

   349       }

   351       void set(EdgeIt n, T a) { container[n.n]=a; }

   352       T get(EdgeIt n) const { return container[n.n]; }

   353       T& operator[](EdgeIt n) { return container[n.n]; }

   354       const T& operator[](EdgeIt n) const { return container[n.n]; }

   356       void update() {}    //Useless for DynMaps

   357       void update(T a) {}  //Useless for DynMaps

   358       };*/

   360   };

   361 } //namespace hugo

   363 #endif //J_GRAPH_H

author	alpar
	Sat, 20 Mar 2004 16:13:19 +0000
changeset 217	fc549fac0dd0
permissions	-rw-r--r--