COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 919:6153d9cf78c6 in lemon-0.x for src/hugo/list_graph.h


Ignore:
Timestamp:
09/29/04 16:02:14 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1230
Message:
  • Backport -r1227 and -r1220
  • Temporarily remove (move to attic) tight_edge_filter.h
File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/hugo/list_graph.h

    r916 r919  
    3030#include <hugo/array_map.h>
    3131
     32#include <hugo/sym_map.h>
     33
    3234#include <hugo/map_defines.h>
    3335
    … …  
    103105        first_free_edge(_g.first_free_edge) {}
    104106   
    105     /// \bug In the vector can be hole if a node is erased from the graph.
    106107    ///Number of nodes.
    107108    int nodeNum() const { return nodes.size(); }
    … …  
    438439  ///\todo this date structure need some reconsiderations. Maybe it
    439440  ///should be implemented independently from ListGraph.
    440   /* 
     441 
    441442  class SymListGraph : public ListGraph
    442443  {
    … …  
    483484      ListGraph::erase(e);
    484485    }   
    485     };*/
    486 
    487   class SymListGraph : public ListGraph {
    488     typedef ListGraph Parent;
    489   public:
    490 
    491     typedef SymListGraph Graph;
    492 
    493     typedef ListGraph::Node Node;
    494     typedef ListGraph::NodeIt NodeIt;
    495 
    496     class SymEdge;
    497     class SymEdgeIt;
    498 
    499     class Edge;
    500     class EdgeIt;
    501     class OutEdgeIt;
    502     class InEdgeIt;
    503 
    504     template <typename Value>
    505     class NodeMap : public Parent::NodeMap<Value> {     
    506     public:
    507       NodeMap(const SymListGraph& g)
    508         : SymListGraph::Parent::NodeMap<Value>(g) {}
    509       NodeMap(const SymListGraph& g, Value v)
    510         : SymListGraph::Parent::NodeMap<Value>(g, v) {}
    511       template<typename TT>
    512       NodeMap(const NodeMap<TT>& copy)
    513         : SymListGraph::Parent::NodeMap<Value>(copy) { }           
    514     };
    515 
    516     template <typename Value>
    517     class SymEdgeMap : public Parent::EdgeMap<Value> {
    518     public:
    519       typedef SymEdge KeyType;
    520 
    521       SymEdgeMap(const SymListGraph& g)
    522         : SymListGraph::Parent::EdgeMap<Value>(g) {}
    523       SymEdgeMap(const SymListGraph& g, Value v)
    524         : SymListGraph::Parent::EdgeMap<Value>(g, v) {}
    525       template<typename TT>
    526       SymEdgeMap(const SymEdgeMap<TT>& copy)
    527         : SymListGraph::Parent::EdgeMap<Value>(copy) { }
    528      
    529     };
    530 
    531     // Create edge map registry.
    532     CREATE_EDGE_MAP_REGISTRY;
    533     // Create edge maps.
    534     CREATE_EDGE_MAP(ArrayMap);
    535 
    536     class Edge {
    537       friend class SymListGraph;
    538       friend class SymListGraph::EdgeIt;
    539       friend class SymListGraph::OutEdgeIt;
    540       friend class SymListGraph::InEdgeIt;
    541      
    542     protected:
    543       int id;
    544 
    545       Edge(int pid) { id = pid; }
    546 
    547     public:
    548       /// An Edge with id \c n.
    549 
    550       Edge() { }
    551       Edge (Invalid) { id = -1; }
    552 
    553       operator SymEdge(){ return SymEdge(id >> 1);}
    554      
    555       bool operator==(const Edge i) const {return id == i.id;}
    556       bool operator!=(const Edge i) const {return id != i.id;}
    557       bool operator<(const Edge i) const {return id < i.id;}
    558       //      ///Validity check
    559       //      operator bool() { return n!=-1; }
    560     };
    561 
    562     class SymEdge : public ListGraph::Edge {
    563       friend class SymListGraph;
    564       friend class SymListGraph::Edge;
    565       typedef ListGraph::Edge Parent;
    566 
    567     protected:     
    568       SymEdge(int pid) : Parent(pid) {}
    569     public:
    570 
    571       SymEdge() { }
    572       SymEdge(const ListGraph::Edge& i) : Parent(i) {}
    573       SymEdge (Invalid) : Parent(INVALID) {}
    574 
    575     };
    576 
    577     class OutEdgeIt {
    578       Parent::OutEdgeIt out;
    579       Parent::InEdgeIt in;     
    580     public:
    581       OutEdgeIt() {}
    582       OutEdgeIt(const SymListGraph& g, Edge e) {
    583         if ((e.id & 1) == 0) { 
    584           out = Parent::OutEdgeIt(g, SymEdge(e));
    585           in = Parent::InEdgeIt(g, g.tail(e));
    586         } else {
    587           out = Parent::OutEdgeIt(INVALID);
    588           in = Parent::InEdgeIt(g, SymEdge(e));
    589         }
    590       }
    591       OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    592 
    593       OutEdgeIt(const SymListGraph& g, const Node v)
    594         : out(g, v), in(g, v) {}
    595       OutEdgeIt &operator++() {
    596         if (out != INVALID) {
    597           ++out;
    598         } else {
    599           ++in;
    600         }
    601         return *this;
    602       }
    603 
    604       operator Edge() const {
    605         if (out == INVALID && in == INVALID) return INVALID;
    606         return out != INVALID ? forward(out) : backward(in);
    607       }
    608 
    609       bool operator==(const Edge i) const {return Edge(*this) == i;}
    610       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    611       bool operator<(const Edge i) const {return Edge(*this) < i;}
    612     };
    613 
    614     class InEdgeIt {
    615       Parent::OutEdgeIt out;
    616       Parent::InEdgeIt in;     
    617     public:
    618       InEdgeIt() {}
    619       InEdgeIt(const SymListGraph& g, Edge e) {
    620         if ((e.id & 1) == 0) { 
    621           out = Parent::OutEdgeIt(g, SymEdge(e));
    622           in = Parent::InEdgeIt(g, g.tail(e));
    623         } else {
    624           out = Parent::OutEdgeIt(INVALID);
    625           in = Parent::InEdgeIt(g, SymEdge(e));
    626         }
    627       }
    628       InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    629 
    630       InEdgeIt(const SymListGraph& g, const Node v)
    631         : out(g, v), in(g, v) {}
    632 
    633       InEdgeIt &operator++() {
    634         if (out != INVALID) {
    635           ++out;
    636         } else {
    637           ++in;
    638         }
    639         return *this;
    640       }
    641 
    642       operator Edge() const {
    643         if (out == INVALID && in == INVALID) return INVALID;
    644         return out != INVALID ? backward(out) : forward(in);
    645       }
    646 
    647       bool operator==(const Edge i) const {return Edge(*this) == i;}
    648       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    649       bool operator<(const Edge i) const {return Edge(*this) < i;}
    650     };
    651 
    652     class SymEdgeIt : public Parent::EdgeIt {
    653 
    654     public:
    655       SymEdgeIt() {}
    656 
    657       SymEdgeIt(const SymListGraph& g)
    658         : SymListGraph::Parent::EdgeIt(g) {}
    659 
    660       SymEdgeIt(const SymListGraph& g, SymEdge e)
    661         : SymListGraph::Parent::EdgeIt(g, e) {}
    662 
    663       SymEdgeIt(Invalid i)
    664         : SymListGraph::Parent::EdgeIt(INVALID) {}
    665 
    666       SymEdgeIt& operator++() {
    667         SymListGraph::Parent::EdgeIt::operator++();
    668         return *this;
    669       }
    670 
    671       operator SymEdge() const {
    672         return SymEdge
    673           (static_cast<const SymListGraph::Parent::EdgeIt&>(*this));
    674       }
    675       bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
    676       bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
    677       bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
    678     };
    679 
    680     class EdgeIt {
    681       SymEdgeIt it;
    682       bool fw;
    683     public:
    684       EdgeIt(const SymListGraph& g) : it(g), fw(true) {}
    685       EdgeIt (Invalid i) : it(i) { }
    686       EdgeIt(const SymListGraph& g, Edge e)
    687         : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
    688       EdgeIt() { }
    689       EdgeIt& operator++() {
    690         fw = !fw;
    691         if (fw) ++it;
    692         return *this;
    693       }
    694       operator Edge() const {
    695         if (it == INVALID) return INVALID;
    696         return fw ? forward(it) : backward(it);
    697       }
    698       bool operator==(const Edge i) const {return Edge(*this) == i;}
    699       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    700       bool operator<(const Edge i) const {return Edge(*this) < i;}
    701 
    702     };
    703 
    704     ///Number of nodes.
    705     int nodeNum() const { return Parent::nodeNum(); }
    706     ///Number of edges.
    707     int edgeNum() const { return 2*Parent::edgeNum(); }
    708     ///Number of symmetric edges.
    709     int symEdgeNum() const { return Parent::edgeNum(); }
    710 
    711     ///Set the expected maximum number of edges.
    712 
    713     ///With this function, it is possible to set the expected number of edges.
    714     ///The use of this fasten the building of the graph and makes
    715     ///it possible to avoid the superfluous memory allocation.
    716     void reserveSymEdge(int n) { Parent::reserveEdge(n); };
    717    
    718     /// Maximum node ID.
    719    
    720     /// Maximum node ID.
    721     ///\sa id(Node)
    722     int maxNodeId() const { return Parent::maxNodeId(); }
    723     /// Maximum edge ID.
    724    
    725     /// Maximum edge ID.
    726     ///\sa id(Edge)
    727     int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
    728     /// Maximum symmetric edge ID.
    729    
    730     /// Maximum symmetric edge ID.
    731     ///\sa id(SymEdge)
    732     int maxSymEdgeId() const { return Parent::maxEdgeId(); }
    733 
    734 
    735     Node tail(Edge e) const {
    736       return (e.id & 1) == 0 ?
    737         Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
    738     }
    739 
    740     Node head(Edge e) const {
    741       return (e.id & 1) == 0 ?
    742         Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
    743     }
    744 
    745     Node tail(SymEdge e) const {
    746       return Parent::tail(e);
    747     }
    748 
    749     Node head(SymEdge e) const {
    750       return Parent::head(e);
    751     }
    752 
    753     NodeIt& first(NodeIt& v) const {
    754       v=NodeIt(*this); return v; }
    755     EdgeIt& first(EdgeIt& e) const {
    756       e=EdgeIt(*this); return e; }
    757     SymEdgeIt& first(SymEdgeIt& e) const {
    758       e=SymEdgeIt(*this); return e; }
    759     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    760       e=OutEdgeIt(*this,v); return e; }
    761     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    762       e=InEdgeIt(*this,v); return e; }
    763 
    764     /// Node ID.
    765    
    766     /// The ID of a valid Node is a nonnegative integer not greater than
    767     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    768     /// and the greatest node ID can be actually less then \ref maxNodeId().
    769     ///
    770     /// The ID of the \ref INVALID node is -1.
    771     ///\return The ID of the node \c v.
    772     static int id(Node v) { return Parent::id(v); }
    773     /// Edge ID.
    774    
    775     /// The ID of a valid Edge is a nonnegative integer not greater than
    776     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    777     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    778     ///
    779     /// The ID of the \ref INVALID edge is -1.
    780     ///\return The ID of the edge \c e.
    781     static int id(Edge e) { return e.id; }
    782 
    783     /// The ID of a valid SymEdge is a nonnegative integer not greater than
    784     /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
    785     /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
    786     ///
    787     /// The ID of the \ref INVALID symmetric edge is -1.
    788     ///\return The ID of the edge \c e.
    789     static int id(SymEdge e) { return Parent::id(e); }
    790 
    791     /// Adds a new node to the graph.
    792 
    793     /// \warning It adds the new node to the front of the list.
    794     /// (i.e. the lastly added node becomes the first.)
    795     Node addNode() {
    796       return Parent::addNode();
    797     }
    798    
    799     SymEdge addEdge(Node u, Node v) {
    800       SymEdge se = Parent::addEdge(u, v);
    801       edge_maps.add(forward(se));
    802       edge_maps.add(backward(se));
    803       return se;
    804     }
    805    
    806     /// Finds an edge between two nodes.
    807 
    808     /// Finds an edge from node \c u to node \c v.
    809     ///
    810     /// If \c prev is \ref INVALID (this is the default value), then
    811     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    812     /// the next edge from \c u to \c v after \c prev.
    813     /// \return The found edge or INVALID if there is no such an edge.
    814     Edge findEdge(Node u, Node v, Edge prev = INVALID)
    815     {     
    816       if (prev == INVALID || id(prev) & 1 == 0) {
    817         SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    818         if (se != INVALID) return forward(se);
    819       } else {
    820         SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    821         if (se != INVALID) return backward(se);
    822       }
    823       return INVALID;
    824     }
    825 
    826 //     /// Finds an symmetric edge between two nodes.
    827 
    828 //     /// Finds an symmetric edge from node \c u to node \c v.
    829 //     ///
    830 //     /// If \c prev is \ref INVALID (this is the default value), then
    831 //     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    832 //     /// the next edge from \c u to \c v after \c prev.
    833 //     /// \return The found edge or INVALID if there is no such an edge.
    834 
    835 //     SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
    836 //     {     
    837 //       if (prev == INVALID || id(prev) & 1 == 0) {
    838 //      SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    839 //      if (se != INVALID) return se;
    840 //       } else {
    841 //      SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    842 //      if (se != INVALID) return se;   
    843 //       }
    844 //       return INVALID;
    845 //     }
    846    
    847   public:
    848 
    849     void erase(Node n) {     
    850       for (OutEdgeIt it(*this, n); it != INVALID; ++it) {
    851         edge_maps.erase(it);
    852         edge_maps.erase(opposite(it));
    853       }
    854       Parent::erase(n);
    855     }
    856    
    857     void erase(SymEdge e) {
    858       edge_maps.erase(forward(e));
    859       edge_maps.erase(backward(e));
    860       Parent::erase(e);
    861     };
    862 
    863     void clear() {
    864       edge_maps.clear();
    865       Parent::clear();
    866     }
    867 
    868     static Edge opposite(Edge e) {
    869       return Edge(id(e) ^ 1);
    870     }
    871 
    872     static Edge forward(SymEdge e) {
    873       return Edge(id(e) << 1);
    874     }
    875 
    876     static Edge backward(SymEdge e) {
    877       return Edge((id(e) << 1) | 1);
    878     }
    879 
    880486  };
     487
    881488
    882489  ///A graph class containing only nodes.
Note: See TracChangeset for help on using the changeset viewer.