COIN-OR::LEMON - Graph Library

Changeset 774:4297098d9677 in lemon-0.x for src/hugo/list_graph.h


Ignore:
Timestamp:
08/30/04 14:01:47 (17 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1066
Message:

Merge back the whole branches/hugo++ to trunk.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/list_graph.h

    r722 r774  
    132132    Node head(Edge e) const { return edges[e.n].head; }
    133133
    134     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
    135     Node aNode(InEdgeIt e) const { return edges[e.n].head; }
    136 
    137     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
    138     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
    139 
    140134    NodeIt& first(NodeIt& v) const {
    141135      v=NodeIt(*this); return v; }
     
    147141      e=InEdgeIt(*this,v); return e; }
    148142
    149 //     template< typename It >
    150 //     It first() const { It e; first(e); return e; }
    151 
    152 //     template< typename It >
    153 //     It first(Node v) const { It e; first(e,v); return e; }
    154 
    155     static bool valid(Edge e) { return e.n!=-1; }
    156     static bool valid(Node n) { return n.n!=-1; }
    157    
    158     static void setInvalid(Edge &e) { e.n=-1; }
    159     static void setInvalid(Node &n) { n.n=-1; }
    160    
    161     template <typename It> static It getNext(It it)
    162     { It tmp(it); return next(tmp); }
    163 
    164     NodeIt& next(NodeIt& it) const {
    165       it.n=nodes[it.n].next;
    166       return it;
    167     }
    168     OutEdgeIt& next(OutEdgeIt& it) const
    169     { it.n=edges[it.n].next_out; return it; }
    170     InEdgeIt& next(InEdgeIt& it) const
    171     { it.n=edges[it.n].next_in; return it; }
    172     EdgeIt& next(EdgeIt& it) const {
    173       if(edges[it.n].next_in!=-1) {
    174         it.n=edges[it.n].next_in;
    175       }
    176       else {
    177         int n;
    178         for(n=nodes[edges[it.n].head].next;
    179             n!=-1 && nodes[n].first_in == -1;
    180             n = nodes[n].next) ;
    181         it.n = (n==-1)?-1:nodes[n].first_in;
    182       }
    183       return it;
    184     }
    185 
    186143    static int id(Node v) { return v.n; }
    187144    static int id(Edge e) { return e.n; }
     
    251208      return e;
    252209    }
    253 
     210   
     211    /// Finds an edge between two nodes.
     212
     213    /// Finds an edge from node \c u to node \c v.
     214    ///
     215    /// If \c prev is \ref INVALID (this is the default value), then
     216    /// It finds the first edge from \c u to \c v. Otherwise it looks for
     217    /// the next edge from \c u to \c v after \c prev.
     218    /// \return The found edge or INVALID if there is no such an edge.
     219    Edge findEdge(Node u,Node v, Edge prev = INVALID)
     220    {
     221      int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
     222      while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
     223      prev.n=e;
     224      return prev;
     225    }
     226   
    254227  private:
    255228    void eraseEdge(int n) {
     
    325298      bool operator!=(const Node i) const {return n!=i.n;}
    326299      bool operator<(const Node i) const {return n<i.n;}
     300      //      ///Validity check
     301      //      operator bool() { return n!=-1; }
    327302    };
    328303   
    329304    class NodeIt : public Node {
     305      const ListGraph *G;
    330306      friend class ListGraph;
    331307    public:
    332308      NodeIt() : Node() { }
    333309      NodeIt(Invalid i) : Node(i) { }
    334       NodeIt(const ListGraph& G) : Node(G.first_node) { }
     310      NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
    335311      ///\todo Undocumented conversion Node -\> NodeIt.
    336       NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
     312      NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
     313      NodeIt &operator++() {
     314        n=G->nodes[n].next;
     315        return *this;
     316      }
     317      //      ///Validity check
     318      //      operator bool() { return Node::operator bool(); }     
    337319    };
    338320
     
    365347      ///make class \c SymListGraph::SymEdgeMap friend of Edge
    366348      int &idref() {return n;}
    367       const int &idref() const {return n;}
    368     };
     349      const int &idref() const {return n;}
     350      //      ///Validity check
     351      //      operator bool() { return n!=-1; }
     352   };
    369353   
    370354    class EdgeIt : public Edge {
     355      const ListGraph *G;
    371356      friend class ListGraph;
    372357    public:
    373       EdgeIt(const ListGraph& G) : Edge() {
     358      EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
    374359        int m;
    375         for(m=G.first_node;
    376             m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
    377         n = (m==-1)?-1:G.nodes[m].first_in;
     360        for(m=_G.first_node;
     361            m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
     362        n = (m==-1)?-1:_G.nodes[m].first_in;
    378363      }
    379364      EdgeIt (Invalid i) : Edge(i) { }
     365      EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    380366      EdgeIt() : Edge() { }
    381367      ///\bug This is a workaround until somebody tells me how to
    382368      ///make class \c SymListGraph::SymEdgeMap friend of Edge
    383369      int &idref() {return n;}
     370      EdgeIt &operator++() {
     371        if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
     372        else {
     373          int nn;
     374          for(nn=G->nodes[G->edges[n].head].next;
     375              nn!=-1 && G->nodes[nn].first_in == -1;
     376              nn = G->nodes[nn].next) ;
     377          n = (nn==-1)?-1:G->nodes[nn].first_in;
     378        }
     379        return *this;
     380      }
     381      //      ///Validity check
     382      //      operator bool() { return Edge::operator bool(); }     
    384383    };
    385384   
    386385    class OutEdgeIt : public Edge {
     386      const ListGraph *G;
    387387      friend class ListGraph;
    388388    public:
    389389      OutEdgeIt() : Edge() { }
     390      OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    390391      OutEdgeIt (Invalid i) : Edge(i) { }
    391392
    392       OutEdgeIt(const ListGraph& G,const Node v)
    393         : Edge(G.nodes[v.n].first_out) {}
     393      OutEdgeIt(const ListGraph& _G,const Node v)
     394        : Edge(_G.nodes[v.n].first_out), G(&_G) {}
     395      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
     396      //      ///Validity check
     397      //      operator bool() { return Edge::operator bool(); }     
    394398    };
    395399   
    396400    class InEdgeIt : public Edge {
     401      const ListGraph *G;
    397402      friend class ListGraph;
    398403    public:
    399404      InEdgeIt() : Edge() { }
     405      InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    400406      InEdgeIt (Invalid i) : Edge(i) { }
    401       InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
     407      InEdgeIt(const ListGraph& _G,Node v)
     408        : Edge(_G.nodes[v.n].first_in), G(&_G) { }
     409      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
     410      //      ///Validity check
     411      //      operator bool() { return Edge::operator bool(); }     
    402412    };
    403413
     
    839849    Node head(Edge e) const { return INVALID; }
    840850
    841     Node aNode(OutEdgeIt e) const { return INVALID; }
    842     Node aNode(InEdgeIt e) const { return INVALID; }
    843 
    844     Node bNode(OutEdgeIt e) const { return INVALID; }
    845     Node bNode(InEdgeIt e) const { return INVALID; }
    846 
    847851    NodeIt& first(NodeIt& v) const {
    848852      v=NodeIt(*this); return v; }
     
    854858      e=InEdgeIt(*this,v); return e; }
    855859
    856 //     template< typename It >
    857 //     It first() const { It e; first(e); return e; }
    858 
    859 //     template< typename It >
    860 //     It first(Node v) const { It e; first(e,v); return e; }
    861 
    862     bool valid(Edge e) const { return false; }
    863     bool valid(Node n) const { return n.n!=-1; }
    864    
    865     void setInvalid(Edge &e) { }
    866     void setInvalid(Node &n) { n.n=-1; }
    867    
    868     template <typename It> It getNext(It it) const
    869     { It tmp(it); return next(tmp); }
    870 
    871     NodeIt& next(NodeIt& it) const {
    872       it.n=nodes[it.n].next;
    873       return it;
    874     }
    875     OutEdgeIt& next(OutEdgeIt& it) const { return it; }
    876     InEdgeIt& next(InEdgeIt& it) const { return it; }
    877     EdgeIt& next(EdgeIt& it) const { return it; }
    878 
    879860    int id(Node v) const { return v.n; }
    880861    int id(Edge e) const { return -1; }
     
    928909    }
    929910   
     911       
     912    Edge findEdge(Node u,Node v, Edge prev = INVALID)
     913    {
     914      return INVALID;
     915    }
     916   
    930917    ///\bug Dynamic maps must be updated!
    931918    ///
     
    956943   
    957944    class NodeIt : public Node {
     945      const NodeSet *G;
    958946      friend class NodeSet;
    959947    public:
    960948      NodeIt() : Node() { }
     949      NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
    961950      NodeIt(Invalid i) : Node(i) { }
    962       NodeIt(const NodeSet& G) : Node(G.first_node) { }
    963       ///\todo Undocumented conversion Node -\> NodeIt.
    964       NodeIt(const NodeSet& G, const Node &n) : Node(n) { }
    965 
     951      NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
     952      NodeIt &operator++() {
     953        n=G->nodes[n].next;
     954        return *this;
     955      }
    966956    };
    967957
     
    994984    public:
    995985      EdgeIt(const NodeSet& G) : Edge() { }
     986      EdgeIt(const NodeSet&, Edge) : Edge() { }
    996987      EdgeIt (Invalid i) : Edge(i) { }
    997988      EdgeIt() : Edge() { }
     
    999990      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
    1000991      //      int idref() {return -1;}
     992      EdgeIt operator++() { return INVALID; }
    1001993    };
    1002994   
     
    1005997    public:
    1006998      OutEdgeIt() : Edge() { }
     999      OutEdgeIt(const NodeSet&, Edge) : Edge() { }
    10071000      OutEdgeIt (Invalid i) : Edge(i) { }
    10081001      OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
     1002      OutEdgeIt operator++() { return INVALID; }
    10091003    };
    10101004   
     
    10131007    public:
    10141008      InEdgeIt() : Edge() { }
     1009      InEdgeIt(const NodeSet&, Edge) : Edge() { }
    10151010      InEdgeIt (Invalid i) : Edge(i) { }
    10161011      InEdgeIt(const NodeSet& G,Node v) :Edge() {}
     1012      InEdgeIt operator++() { return INVALID; }
    10171013    };
    10181014
     
    12001196    public:
    12011197      NodeIt() : NodeGraphType::NodeIt() { }
     1198      NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
    12021199      NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
    12031200      NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
    12041201      NodeIt(const typename NodeGraphType::NodeIt &n)
    12051202        : NodeGraphType::NodeIt(n) {}
    1206       ///\todo Undocumented conversion Node -\> NodeIt.
    1207       NodeIt(const EdgeSet& _G, const Node &n)
    1208         : NodeGraphType::NodeIt(_G.G,n) { }
    12091203
    12101204      operator Node() { return Node(*this);}
     1205      NodeIt &operator++()
     1206      { this->NodeGraphType::NodeIt::operator++(); return *this;}
    12111207    };
    12121208
     
    13111307    Node tail(Edge e) const { return edges[e.n].tail; }
    13121308    Node head(Edge e) const { return edges[e.n].head; }
    1313 
    1314     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
    1315     Node aNode(InEdgeIt e) const { return edges[e.n].head; }
    1316 
    1317     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
    1318     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
    13191309
    13201310    NodeIt& first(NodeIt& v) const {
     
    13271317      e=InEdgeIt(*this,v); return e; }
    13281318
    1329 //     template< typename It >
    1330 //     It first() const { It e; first(e); return e; }
    1331 
    1332 //     template< typename It >
    1333 //     It first(Node v) const { It e; first(e,v); return e; }
    1334 
    1335     bool valid(Edge e) const { return e.n!=-1; }
    1336     bool valid(Node n) const { return G.valid(n); }
    1337    
    1338     void setInvalid(Edge &e) { e.n=-1; }
    1339     void setInvalid(Node &n) { G.setInvalid(n); }
    1340    
    1341     template <typename It> It getNext(It it) const
    1342     { It tmp(it); return next(tmp); }
    1343 
    1344     NodeIt& next(NodeIt& it) const { G.next(it); return it; }
    1345     OutEdgeIt& next(OutEdgeIt& it) const
    1346     { it.n=edges[it.n].next_out; return it; }
    1347     InEdgeIt& next(InEdgeIt& it) const
    1348     { it.n=edges[it.n].next_in; return it; }
    1349     EdgeIt& next(EdgeIt& it) const {
    1350       if(edges[it.n].next_in!=-1) {
    1351         it.n=edges[it.n].next_in;
    1352       }
    1353       else {
    1354         NodeIt n(*this,edges[it.n].head);
    1355         for(n=next(n);
    1356             valid(n) && nodes[n].first_in == -1;
    1357             next(n)) ;
    1358         it.n = (valid(n))?-1:nodes[n].first_in;
    1359       }
    1360       return it;
    1361     }
    1362 
    13631319    int id(Edge e) const { return e.n; }
    13641320
     
    13991355    }
    14001356
     1357    /// Finds an edge between two nodes.
     1358
     1359    /// Finds an edge from node \c u to node \c v.
     1360    ///
     1361    /// If \c prev is \ref INVALID (this is the default value), then
     1362    /// It finds the first edge from \c u to \c v. Otherwise it looks for
     1363    /// the next edge from \c u to \c v after \c prev.
     1364    /// \return The found edge or INVALID if there is no such an edge.
     1365    Edge findEdge(Node u,Node v, Edge prev = INVALID)
     1366    {
     1367      int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
     1368      while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
     1369      prev.n=e;
     1370      return prev;
     1371    }
     1372   
    14011373  private:
    14021374    void eraseEdge(int n) {
     
    14611433      friend class NodeIt;
    14621434    public:
    1463       ///\bug It shoud be at least protected
     1435      ///\bug It should be at least protected
    14641436      ///
    14651437      int n;
     
    14841456      template <typename T> friend class EdgeMap;
    14851457   
    1486      
    1487     public:
    1488       EdgeIt(const EdgeSet& G) : Edge() {
     1458      const EdgeSet *G;
     1459    public:
     1460      EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
    14891461        //              typename NodeGraphType::Node m;
    14901462        NodeIt m;
    1491         for(G.first(m);
    1492             G.valid(m) && G.nodes[m].first_in == -1;  G.next(m));
    1493         //AJJAJ! This is a non sense!!!!!!!
    1494         this->n = G.valid(m)?-1:G.nodes[m].first_in;
    1495       }
     1463        for(G->first(m);
     1464            m!=INVALID && G->nodes[m].first_in == -1;  ++m);
     1465        ///\bug AJJAJ! This is a non sense!!!!!!!
     1466        this->n = m!=INVALID?-1:G->nodes[m].first_in;
     1467      }
     1468      EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
    14961469      EdgeIt (Invalid i) : Edge(i) { }
    14971470      EdgeIt() : Edge() { }
    1498       ///\bug This is a workaround until somebody tells me how to
     1471      ///.
     1472     
     1473      ///\bug UNIMPLEMENTED!!!!!
     1474      //
     1475      EdgeIt &operator++() {
     1476        return *this;
     1477      }
     1478       ///\bug This is a workaround until somebody tells me how to
    14991479      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
    15001480      int &idref() {return this->n;}
     
    15021482   
    15031483    class OutEdgeIt : public Edge {
     1484      const EdgeSet *G;
    15041485      friend class EdgeSet;
    15051486    public:
    15061487      OutEdgeIt() : Edge() { }
    15071488      OutEdgeIt (Invalid i) : Edge(i) { }
    1508 
    1509       OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { }
     1489      OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
     1490
     1491      OutEdgeIt(const EdgeSet& _G,const Node v) :
     1492        Edge(_G.nodes[v].first_out), G(&_G) { }
     1493      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
    15101494    };
    15111495   
    15121496    class InEdgeIt : public Edge {
     1497      const EdgeSet *G;
    15131498      friend class EdgeSet;
    15141499    public:
    15151500      InEdgeIt() : Edge() { }
    15161501      InEdgeIt (Invalid i) : Edge(i) { }
    1517       InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { }
     1502      InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
     1503      InEdgeIt(const EdgeSet& _G,Node v)
     1504        : Edge(_G.nodes[v].first_in), G(&_G) { }
     1505      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
    15181506    };
    15191507
     
    15551543        //FIXME: What if there are empty Id's?
    15561544        //FIXME: Can I use 'this' in a constructor?
    1557         G->dyn_edge_maps.push_back(this);
     1545        this->G->dyn_edge_maps.push_back(this);
    15581546      }
    15591547      EdgeMap(const EdgeSet &_G,const T &t) :
    15601548        DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
    15611549      {
    1562         G->dyn_edge_maps.push_back(this);
     1550        this->G->dyn_edge_maps.push_back(this);
    15631551      }
    15641552      EdgeMap(const EdgeMap<T> &m) :
    15651553        DynMapBase<Edge>(*m.G), container(m.container)
    15661554      {
    1567         G->dyn_edge_maps.push_back(this);
     1555        this->G->dyn_edge_maps.push_back(this);
    15681556      }
    15691557
     
    15731561        DynMapBase<Edge>(*m.G), container(m.container.size())
    15741562      {
    1575         G->dyn_edge_maps.push_back(this);
     1563        this->G->dyn_edge_maps.push_back(this);
    15761564        typename std::vector<TT>::const_iterator i;
    15771565        for(typename std::vector<TT>::const_iterator i=m.container.begin();
     
    15821570      ~EdgeMap()
    15831571      {
    1584         if(G) {
     1572        if(this->G) {
    15851573          typename std::vector<DynMapBase<Edge>* >::iterator i;
    1586           for(i=G->dyn_edge_maps.begin();
    1587               i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
     1574          for(i=this->G->dyn_edge_maps.begin();
     1575              i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ;
    15881576          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    15891577          //A better way to do that: (Is this really important?)
    15901578          if(*i==this) {
    1591             *i=G->dyn_edge_maps.back();
    1592             G->dyn_edge_maps.pop_back();
     1579            *i=this->G->dyn_edge_maps.back();
     1580            this->G->dyn_edge_maps.pop_back();
    15931581          }
    15941582        }
     
    16031591      ///\bug This doesn't work. Why?
    16041592      ///      void set(Edge n, T a) { container[n.n]=a; }
    1605       void set(Edge n, T a) { container[G->id(n)]=a; }
     1593      void set(Edge n, T a) { container[this->G->id(n)]=a; }
    16061594      //T get(Edge n) const { return container[n.n]; }
    16071595      typename std::vector<T>::reference
    16081596      ///\bug This doesn't work. Why?
    16091597      ///      operator[](Edge n) { return container[n.n]; }
    1610       operator[](Edge n) { return container[G->id(n)]; }
     1598      operator[](Edge n) { return container[this->G->id(n)]; }
    16111599      typename std::vector<T>::const_reference
    16121600      ///\bug This doesn't work. Why?
    16131601      ///      operator[](Edge n) const { return container[n.n]; }
    1614       operator[](Edge n) const { return container[G->id(n)]; }
     1602      operator[](Edge n) const { return container[this->G->id(n)]; }
    16151603
    16161604      ///\warning There is no safety check at all!
Note: See TracChangeset for help on using the changeset viewer.