COIN-OR::LEMON - Graph Library

Changeset 59:41c7f9c09a12 in lemon-0.x for src/work/list_graph.hh


Ignore:
Timestamp:
02/04/04 13:46:33 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@74
Message:

.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/list_graph.hh

    r46 r59  
    1 #ifndef MARCI_LIST_GRAPH_HH
    2 #define MARCI_LIST_GRAPH_HH
     1#ifndef LIST_GRAPH_HH
     2#define LIST_GRAPH_HH
    33
    44#include <iostream>
    55
    66namespace marci {
    7 
    8   template <typename It>
    9   int number_of(It _it) {
    10     int i=0;
    11     for( ; _it.valid(); ++_it) { ++i; }
    12     return i;
    13   }
    147
    158  template <typename It>
     
    2114
    2215  class ListGraph {
     16
    2317    class node_item;
    2418    class edge_item;
     19
    2520  public:
     21
    2622    class NodeIt;
    2723    class EachNodeIt;
     
    3127    class InEdgeIt;
    3228    class SymEdgeIt;
    33 
    34     template <typename T>
     29    template <typename ValueType> class NodeMap;
     30    template <typename ValueType> class EdgeMap;
     31   
     32  private:
     33   
     34    template <typename ValueType> friend class NodeMap;
     35    template <typename ValueType> friend class EdgeMap;
     36
     37    template <typename ValueType>
    3538    class NodeMap {
    36       //typedef typename Graph::NodeIt NodeIt;
    37       //typedef typename Graph::EachNodeIt EachNodeIt;
    3839      const ListGraph& G;
    39       std::vector<T> container;
    40     public:
    41       NodeMap(const ListGraph& _G) : G(_G) {
    42         int i=0;
    43         for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) ++i;
    44         container.resize(i);
    45       }
    46       NodeMap(const ListGraph& _G, const T a) : G(_G) {
    47         for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) {
    48           container.push_back(a);
    49         }
    50       }
    51       void set(const NodeIt nit, const T a) { container[G.id(nit)]=a; }
    52       T get(const NodeIt nit) const { return container[G.id(nit)]; }
    53     };
    54 
    55     template <typename T>
     40      std::vector<ValueType> container;
     41    public:
     42      NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { }
     43      NodeMap(const ListGraph& _G, const ValueType a) :
     44        G(_G), container(_G.node_id, a) { }
     45      void set(const NodeIt nit, const ValueType a) { container[G.id(nit)]=a; }
     46      ValueType get(const NodeIt nit) const { return container[G.id(nit)]; }
     47    };
     48
     49    template <typename ValueType>
    5650    class EdgeMap {
    57       //typedef typename Graph::EdgeIt EdgeIt;
    58       //typedef typename Graph::EachEdgeIt EachEdgeIt;
    5951      const ListGraph& G;
    60       std::vector<T> container;
    61     public:
    62       EdgeMap(const ListGraph& _G) : G(_G) {
    63         int i=0;
    64         for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) ++i;
    65         container.resize(i);
    66       }
    67       EdgeMap(const ListGraph& _G, const T a) : G(_G) {
    68         for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) {
    69           container.push_back(a);
    70         }
    71       }
    72       void set(const EdgeIt eit, const T a) { container[G.id(eit)]=a; }
    73       T get(const EdgeIt eit) const { return container[G.id(eit)]; }
    74     };
    75 
    76     //typedef template<typename T> NodePropertyVector<ListGraph, T> NodeMap;
    77     //template <typename T>
    78     //typedef NodePropertyVector<ListGraph, T> NodeMap;
    79     //template <typename T>
    80     //typedef typename NodePropertyVector<ListGraph, T> NodeMap;
    81     //template <typename T>
    82     //typedef NodePropertyVector<typename ListGraph, T> NodeMap;
    83     //template <typename T>
    84     //typedef typename NodePropertyVector<typename ListGraph, T> NodeMap;
    85     //template <typename T>
    86     //typedef template NodePropertyVector<ListGraph, T> NodeMap;
    87     //template <typename T>
    88     //typedef template typename NodePropertyVector<ListGraph, T> NodeMap;
    89     //template <typename T>
    90     //typedef template NodePropertyVector<typename ListGraph, T> NodeMap;
    91     //template <typename T>
    92     //typedef template typename NodePropertyVector<typename ListGraph, T> NodeMap;
    93     //template <typename T>
    94     //typedef EdgePropertyVector<ListGraph, T> EdgeMap;
    95 
    96   private:
     52      std::vector<ValueType> container;
     53    public:
     54      EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { }
     55      EdgeMap(const ListGraph& _G, const ValueType a) :
     56        G(_G), container(_G.edge_id, a) { }
     57      void set(const EdgeIt eit, const ValueType a) { container[G.id(eit)]=a; }
     58      ValueType get(const EdgeIt eit) const { return container[G.id(eit)]; }
     59    };
     60
    9761    int node_id;
    9862    int edge_id;
     
    11478      friend std::ostream& operator<<(std::ostream& os, const NodeIt& i);
    11579      friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
    116       ListGraph* G;
     80      //ListGraph* G;
    11781      int id;
    11882      edge_item* _first_out_edge;
     
    136100      friend class SymEdgeIt;
    137101      friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
    138       ListGraph* G;
     102      //ListGraph* G;
    139103      int id;
    140104      node_item* _tail;
     
    257221    /* functions to construct iterators from the graph, or from each other */
    258222
    259     EachNodeIt firstNode() const { return EachNodeIt(_first_node); }
    260     EachEdgeIt firstEdge() const {
    261       node_item* v=_first_node;
    262       edge_item* edge=v->_first_out_edge;
    263       while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
    264       return EachEdgeIt(v, edge);
    265     }
     223    //EachNodeIt firstNode() const { return EachNodeIt(*this); }
     224    //EachEdgeIt firstEdge() const { return EachEdgeIt(*this); }
    266225   
    267226    //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); }
    268     InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
    269     SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
     227    //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
     228    //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
    270229    NodeIt tail(const EdgeIt e) const { return e.tailNode(); }
    271230    NodeIt head(const EdgeIt e) const { return e.headNode(); }
     
    288247    /* for experimental purpose */
    289248
    290     void getFirst(EachNodeIt& v) const { v=EachNodeIt(_first_node); }
    291     void getFirst(EachEdgeIt& e) const { e=firstEdge(); }
     249    void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); }
     250    void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); }
    292251    void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); }
    293252    void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); }
     
    387346    class EachNodeIt : public NodeIt {
    388347      friend class ListGraph;
     348    protected:
     349      EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }
    389350    public:
    390351      EachNodeIt() : NodeIt() { }
    391352      EachNodeIt(node_item* v) : NodeIt(v) { }
    392       EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }
    393353      EachNodeIt& operator++() { node=node->_next_node; return *this; }
    394354    };
     
    423383    class EachEdgeIt : public EdgeIt {
    424384      friend class ListGraph;
    425       node_item* v;
    426     public:
    427       EachEdgeIt() : EdgeIt(), v(0) { }
    428       EachEdgeIt(node_item* _v, edge_item* _e) : EdgeIt(_e), v(_v) { }
     385    protected:
    429386      EachEdgeIt(const ListGraph& G) {
    430         v=G._first_node;
    431         edge=v->_first_out_edge;
     387        node_item* v=G._first_node;
     388        if (v) edge=v->_first_out_edge; else edge=0;
    432389        while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
    433390      }
     391    public:
     392      EachEdgeIt() : EdgeIt() { }
     393      EachEdgeIt(edge_item* _e) : EdgeIt(_e) { }
    434394      EachEdgeIt& operator++() {
     395        node_item* v=edge->_tail;
    435396        edge=edge->_next_out;
    436397        while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
     
    442403      friend class ListGraph;
    443404      node_item* v;
     405    protected:
     406      OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
    444407    public:
    445408      OutEdgeIt() : EdgeIt(), v(0) { }
    446     protected:
    447       OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
    448     public:
    449409      OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
    450410      OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
     
    458418      friend class ListGraph;
    459419      node_item* v;
     420    protected:
     421      InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; }
    460422    public:
    461423      InEdgeIt() : EdgeIt(), v(0) { }
    462     protected:
    463       InEdgeIt(const NodeIt& _v) : v(_v.node) {
    464         edge=v->_first_in_edge;
    465       }
    466     public:
    467424      InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
    468425      InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
     
    477434      bool out_or_in; //1 iff out, 0 iff in
    478435      node_item* v;
    479     public:
    480       SymEdgeIt() : EdgeIt(), v(0) { }
    481436    protected:
    482437      SymEdgeIt(const NodeIt& _v) : v(_v.node) {
     
    486441      }
    487442    public:
     443      SymEdgeIt() : EdgeIt(), v(0) { }
    488444      SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) {
    489445        out_or_in=1;
     
    550506} //namespace marci
    551507
    552 #endif //MARCI_LIST_GRAPH_HH
     508#endif //LIST_GRAPH_HH
Note: See TracChangeset for help on using the changeset viewer.