COIN-OR::LEMON - Graph Library

Changeset 919:6153d9cf78c6 in lemon-0.x


Ignore:
Timestamp:
09/29/04 16:02:14 (19 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
Location:
src
Files:
1 added
3 deleted
11 edited
1 moved

Legend:

Unmodified
Added
Removed
  • src/hugo/Makefile.am

    r909 r919  
    1919        map_bits.h                                                      \
    2020        maps.h                                                          \
    21         min_cost_flow.h                                                 \
     21        min_cost_flow.h                                                \
    2222        suurballe.h                                                     \
    2323        preflow.h                                                       \
    2424        path.h                                                          \
    2525        smart_graph.h                                                   \
     26        sym_map.h                                                       \
    2627        time_measure.h                                                  \
    2728        unionfind.h                                                     \
     
    3132noinst_HEADERS =                                                        \
    3233        skeletons/graph.h                                               \
    33         skeletons/sym_graph.h                                           \
    3434        skeletons/maps.h                                                \
    3535        skeletons/path.h
  • src/hugo/default_map.h

    r909 r919  
    6060template <typename TT> \
    6161DefaultMap(const DefaultMap<MapRegistry, TT>& copy) \
    62   : Parent(*copy.getGraph()) { \
     62  : { \
     63  Parent::MapBase::operator= \
     64    (static_cast<const typename Parent::MapBase&>(copy)); \
    6365  if (Parent::getGraph()) { \
    6466    for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\
     67      Parent::add(it); \
    6568      Parent::operator[](it) = copy[it]; \
    6669    } \
  • 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.
  • src/hugo/map_bits.h

    r909 r919  
    5555  struct KeyInfo<Graph, typename Graph::SymEdgeIt> {
    5656    static int maxId(const Graph& graph) {
    57       return graph.maxSymEdgeId();
     57      return graph.maxEdgeId() >> 1;
    5858    }
    59     static int id(const Graph& graph, const typename Graph::SymEdge& edge) {
    60       return graph.id(edge);
     59    static int id(const Graph& graph, const typename Graph::Edge& edge) {
     60      return graph.id(edge) >> 1;
    6161    }
    6262  };
  • src/hugo/map_defines.h

    r909 r919  
    115115 */
    116116#define CREATE_SYM_EDGE_MAP_REGISTRY \
    117 typedef MapRegistry<Graph, SymEdge, SymEdgeIt> SymEdgeMapRegistry; \
     117typedef SymEdgeIt<Graph, Edge, EdgeIt> SymEdgeIt; \
     118typedef MapRegistry<Graph, Edge, SymEdgeIt> SymEdgeMapRegistry; \
    118119mutable SymEdgeMapRegistry sym_edge_maps;
    119120
     
    127128#define CREATE_SYM_EDGE_MAP(DynMap) \
    128129template <typename Value> \
    129 class SymEdgeMap : public DynMap<SymEdgeMapRegistry, Value> { \
    130 public: \
    131 typedef DynMap<SymEdgeMapRegistry, Value> Parent; \
     130class SymEdgeMap : public SymMap<DynMap, SymEdgeMapRegistry, Value> { \
     131public: \
     132typedef SymMap<DynMap, SymEdgeMapRegistry, Value> Parent; \
    132133\
    133134SymEdgeMap(const typename Parent::Graph& g) \
  • src/hugo/map_registry.h

    r909 r919  
    253253     * Notify all the registered maps about a Key added.
    254254     */
    255     void add(const KeyType& key) {
     255    void add(KeyType& key) {
    256256      typename Container::iterator it;
    257257      for (it = container.begin(); it != container.end(); ++it) {
     
    263263     * Notify all the registered maps about a Key erased.
    264264     */
    265     void erase(const KeyType& key) {
     265    void erase(KeyType& key) {
    266266      typename Container::iterator it;
    267267      for (it = container.begin(); it != container.end(); ++it) {
  • src/hugo/smart_graph.h

    r916 r919  
    2828
    2929#include <hugo/array_map.h>
     30#include <hugo/sym_map.h>
     31
    3032#include <hugo/map_registry.h>
    3133
     
    297299  };
    298300
    299 
    300 
    301   class SymSmartGraph : public SmartGraph {
    302     typedef SmartGraph Parent;
    303   public:
    304 
    305     typedef SymSmartGraph Graph;
    306 
    307     typedef SmartGraph::Node Node;
    308     typedef SmartGraph::NodeIt NodeIt;
    309 
    310     class SymEdge;
    311     class SymEdgeIt;
    312 
    313     class Edge;
    314     class EdgeIt;
    315     class OutEdgeIt;
    316     class InEdgeIt;
    317 
    318     template <typename Value>
    319     class NodeMap : public Parent::NodeMap<Value> {     
    320     public:
    321       NodeMap(const SymSmartGraph& g)
    322         : SymSmartGraph::Parent::NodeMap<Value>(g) {}
    323       NodeMap(const SymSmartGraph& g, Value v)
    324         : SymSmartGraph::Parent::NodeMap<Value>(g, v) {}
    325       template<typename TT>
    326       NodeMap(const NodeMap<TT>& copy)
    327         : SymSmartGraph::Parent::NodeMap<Value>(copy) { }           
    328     };
    329 
    330     template <typename Value>
    331     class SymEdgeMap : public Parent::EdgeMap<Value> {
    332     public:
    333       typedef SymEdge KeyType;
    334 
    335       SymEdgeMap(const SymSmartGraph& g)
    336         : SymSmartGraph::Parent::EdgeMap<Value>(g) {}
    337       SymEdgeMap(const SymSmartGraph& g, Value v)
    338         : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {}
    339       template<typename TT>
    340       SymEdgeMap(const SymEdgeMap<TT>& copy)
    341         : SymSmartGraph::Parent::EdgeMap<Value>(copy) { }
    342      
    343     };
    344 
    345     // Create edge map registry.
    346     CREATE_EDGE_MAP_REGISTRY;
    347     // Create edge maps.
    348     CREATE_EDGE_MAP(ArrayMap);
    349 
    350     class Edge {
    351       friend class SymSmartGraph;
    352       friend class SymSmartGraph::EdgeIt;
    353       friend class SymSmartGraph::OutEdgeIt;
    354       friend class SymSmartGraph::InEdgeIt;
    355      
    356     protected:
    357       int id;
    358 
    359       Edge(int pid) { id = pid; }
    360 
    361     public:
    362       /// An Edge with id \c n.
    363 
    364       Edge() { }
    365       Edge (Invalid) { id = -1; }
    366 
    367       operator SymEdge(){ return SymEdge(id >> 1);}
    368      
    369       bool operator==(const Edge i) const {return id == i.id;}
    370       bool operator!=(const Edge i) const {return id != i.id;}
    371       bool operator<(const Edge i) const {return id < i.id;}
    372       //      ///Validity check
    373       //      operator bool() { return n!=-1; }
    374     };
    375 
    376     class SymEdge : public SmartGraph::Edge {
    377       friend class SymSmartGraph;
    378       friend class SymSmartGraph::Edge;
    379       typedef SmartGraph::Edge Parent;
    380 
    381     protected:     
    382       SymEdge(int pid) : Parent(pid) {}
    383     public:
    384 
    385       SymEdge() { }
    386       SymEdge(const SmartGraph::Edge& i) : Parent(i) {}
    387       SymEdge (Invalid) : Parent(INVALID) {}
    388 
    389     };
    390 
    391     class OutEdgeIt {
    392       Parent::OutEdgeIt out;
    393       Parent::InEdgeIt in;     
    394     public:
    395       OutEdgeIt() {}
    396       OutEdgeIt(const SymSmartGraph& g, Edge e) {
    397         if ((e.id & 1) == 0) { 
    398           out = Parent::OutEdgeIt(g, SymEdge(e));
    399           in = Parent::InEdgeIt(g, g.tail(e));
    400         } else {
    401           out = Parent::OutEdgeIt(INVALID);
    402           in = Parent::InEdgeIt(g, SymEdge(e));
    403         }
    404       }
    405       OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    406 
    407       OutEdgeIt(const SymSmartGraph& g, const Node v)
    408         : out(g, v), in(g, v) {}
    409       OutEdgeIt &operator++() {
    410         if (out != INVALID) {
    411           ++out;
    412         } else {
    413           ++in;
    414         }
    415         return *this;
    416       }
    417 
    418       operator Edge() const {
    419         if (out == INVALID && in == INVALID) return INVALID;
    420         return out != INVALID ? forward(out) : backward(in);
    421       }
    422 
    423       bool operator==(const Edge i) const {return Edge(*this) == i;}
    424       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    425       bool operator<(const Edge i) const {return Edge(*this) < i;}
    426     };
    427 
    428     class InEdgeIt {
    429       Parent::OutEdgeIt out;
    430       Parent::InEdgeIt in;     
    431     public:
    432       InEdgeIt() {}
    433       InEdgeIt(const SymSmartGraph& g, Edge e) {
    434         if ((e.id & 1) == 0) { 
    435           out = Parent::OutEdgeIt(g, SymEdge(e));
    436           in = Parent::InEdgeIt(g, g.tail(e));
    437         } else {
    438           out = Parent::OutEdgeIt(INVALID);
    439           in = Parent::InEdgeIt(g, SymEdge(e));
    440         }
    441       }
    442       InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    443 
    444       InEdgeIt(const SymSmartGraph& g, const Node v)
    445         : out(g, v), in(g, v) {}
    446 
    447       InEdgeIt &operator++() {
    448         if (out != INVALID) {
    449           ++out;
    450         } else {
    451           ++in;
    452         }
    453         return *this;
    454       }
    455 
    456       operator Edge() const {
    457         if (out == INVALID && in == INVALID) return INVALID;
    458         return out != INVALID ? backward(out) : forward(in);
    459       }
    460 
    461       bool operator==(const Edge i) const {return Edge(*this) == i;}
    462       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    463       bool operator<(const Edge i) const {return Edge(*this) < i;}
    464     };
    465 
    466     class SymEdgeIt : public Parent::EdgeIt {
    467 
    468     public:
    469       SymEdgeIt() {}
    470 
    471       SymEdgeIt(const SymSmartGraph& g)
    472         : SymSmartGraph::Parent::EdgeIt(g) {}
    473 
    474       SymEdgeIt(const SymSmartGraph& g, SymEdge e)
    475         : SymSmartGraph::Parent::EdgeIt(g, e) {}
    476 
    477       SymEdgeIt(Invalid i)
    478         : SymSmartGraph::Parent::EdgeIt(INVALID) {}
    479 
    480       SymEdgeIt& operator++() {
    481         SymSmartGraph::Parent::EdgeIt::operator++();
    482         return *this;
    483       }
    484 
    485       operator SymEdge() const {
    486         return SymEdge
    487           (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this));
    488       }
    489       bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
    490       bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
    491       bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
    492     };
    493 
    494     class EdgeIt {
    495       SymEdgeIt it;
    496       bool fw;
    497     public:
    498       EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {}
    499       EdgeIt (Invalid i) : it(i) { }
    500       EdgeIt(const SymSmartGraph& g, Edge e)
    501         : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
    502       EdgeIt() { }
    503       EdgeIt& operator++() {
    504         fw = !fw;
    505         if (fw) ++it;
    506         return *this;
    507       }
    508       operator Edge() const {
    509         if (it == INVALID) return INVALID;
    510         return fw ? forward(it) : backward(it);
    511       }
    512       bool operator==(const Edge i) const {return Edge(*this) == i;}
    513       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    514       bool operator<(const Edge i) const {return Edge(*this) < i;}
    515 
    516     };
    517 
    518     ///Number of nodes.
    519     int nodeNum() const { return Parent::nodeNum(); }
    520     ///Number of edges.
    521     int edgeNum() const { return 2*Parent::edgeNum(); }
    522     ///Number of symmetric edges.
    523     int symEdgeNum() const { return Parent::edgeNum(); }
    524 
    525     /// Maximum node ID.
    526    
    527     /// Maximum node ID.
    528     ///\sa id(Node)
    529     int maxNodeId() const { return Parent::maxNodeId(); }
    530     /// Maximum edge ID.
    531    
    532     /// Maximum edge ID.
    533     ///\sa id(Edge)
    534     int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
    535     /// Maximum symmetric edge ID.
    536    
    537     /// Maximum symmetric edge ID.
    538     ///\sa id(SymEdge)
    539     int maxSymEdgeId() const { return Parent::maxEdgeId(); }
    540 
    541 
    542     Node tail(Edge e) const {
    543       return (e.id & 1) == 0 ?
    544         Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
    545     }
    546 
    547     Node head(Edge e) const {
    548       return (e.id & 1) == 0 ?
    549         Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
    550     }
    551 
    552     Node tail(SymEdge e) const {
    553       return Parent::tail(e);
    554     }
    555 
    556     Node head(SymEdge e) const {
    557       return Parent::head(e);
    558     }
    559 
    560     NodeIt& first(NodeIt& v) const {
    561       v=NodeIt(*this); return v; }
    562     EdgeIt& first(EdgeIt& e) const {
    563       e=EdgeIt(*this); return e; }
    564     SymEdgeIt& first(SymEdgeIt& e) const {
    565       e=SymEdgeIt(*this); return e; }
    566     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    567       e=OutEdgeIt(*this,v); return e; }
    568     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    569       e=InEdgeIt(*this,v); return e; }
    570 
    571     /// Node ID.
    572    
    573     /// The ID of a valid Node is a nonnegative integer not greater than
    574     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    575     /// and the greatest node ID can be actually less then \ref maxNodeId().
    576     ///
    577     /// The ID of the \ref INVALID node is -1.
    578     ///\return The ID of the node \c v.
    579     static int id(Node v) { return Parent::id(v); }
    580     /// Edge ID.
    581    
    582     /// The ID of a valid Edge is a nonnegative integer not greater than
    583     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    584     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    585     ///
    586     /// The ID of the \ref INVALID edge is -1.
    587     ///\return The ID of the edge \c e.
    588     static int id(Edge e) { return e.id; }
    589 
    590     /// The ID of a valid SymEdge is a nonnegative integer not greater than
    591     /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
    592     /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
    593     ///
    594     /// The ID of the \ref INVALID symmetric edge is -1.
    595     ///\return The ID of the edge \c e.
    596     static int id(SymEdge e) { return Parent::id(e); }
    597 
    598     /// Adds a new node to the graph.
    599 
    600     /// \warning It adds the new node to the front of the list.
    601     /// (i.e. the lastly added node becomes the first.)
    602     Node addNode() {
    603       return Parent::addNode();
    604     }
    605    
    606     SymEdge addEdge(Node u, Node v) {
    607       SymEdge se = Parent::addEdge(u, v);
    608       edge_maps.add(forward(se));
    609       edge_maps.add(backward(se));
    610       return se;
    611     }
    612    
    613     /// Finds an edge between two nodes.
    614 
    615     /// Finds an edge from node \c u to node \c v.
    616     ///
    617     /// If \c prev is \ref INVALID (this is the default value), then
    618     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    619     /// the next edge from \c u to \c v after \c prev.
    620     /// \return The found edge or INVALID if there is no such an edge.
    621     Edge findEdge(Node u, Node v, Edge prev = INVALID)
    622     {     
    623       if (prev == INVALID || id(prev) & 1 == 0) {
    624         SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    625         if (se != INVALID) return forward(se);
    626       } else {
    627         SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    628         if (se != INVALID) return backward(se);
    629       }
    630       return INVALID;
    631     }
    632 
    633 //     /// Finds an symmetric edge between two nodes.
    634 
    635 //     /// Finds an symmetric edge from node \c u to node \c v.
    636 //     ///
    637 //     /// If \c prev is \ref INVALID (this is the default value), then
    638 //     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    639 //     /// the next edge from \c u to \c v after \c prev.
    640 //     /// \return The found edge or INVALID if there is no such an edge.
    641 
    642 //     SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
    643 //     {     
    644 //       if (prev == INVALID || id(prev) & 1 == 0) {
    645 //      SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    646 //      if (se != INVALID) return se;
    647 //       } else {
    648 //      SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    649 //      if (se != INVALID) return se;   
    650 //       }
    651 //       return INVALID;
    652 //     }
    653    
    654   public:
    655 
    656     void clear() {
    657       edge_maps.clear();
    658       Parent::clear();
    659     }
    660 
    661     static Edge opposite(Edge e) {
    662       return Edge(id(e) ^ 1);
    663     }
    664 
    665     static Edge forward(SymEdge e) {
    666       return Edge(id(e) << 1);
    667     }
    668 
    669     static Edge backward(SymEdge e) {
    670       return Edge((id(e) << 1) | 1);
    671     }
    672 
    673   };
    674301  ///Graph for bidirectional edges.
    675302
     
    692319  //\sa SmartGraph.
    693320
    694   /*  class SymSmartGraph : public SmartGraph
     321  class SymSmartGraph : public SmartGraph
    695322  {
    696323  public:
     
    727354   
    728355
    729     };*/
     356  };
    730357 
    731358  /// @} 
  • src/test/Makefile.am

    r909 r919  
    1010        dijkstra_test \
    1111        graph_test \
    12         sym_graph_test \
    1312        graph_wrapper_test \
    1413        kruskal_test \
     
    3029dijkstra_test_SOURCES = dijkstra_test.cc
    3130graph_test_SOURCES = graph_test.cc
    32 sym_graph_test_SOURCES = sym_graph_test.cc
    3331graph_wrapper_test_SOURCES = graph_wrapper_test.cc
    3432kruskal_test_SOURCES = kruskal_test.cc
  • src/test/graph_test.cc

    r909 r919  
    6464    checkGraphInEdgeList(G,n,3);
    6565    checkGraphOutEdgeList(G,n,3);
     66    ++n;
    6667  } 
    6768}
     
    8283
    8384//Compile SymSmartGraph
    84 //template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
    85 //template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
     85template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
     86template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
    8687
    8788//Compile ListGraph
     
    9293
    9394//Compile SymListGraph
    94 //template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
    95 //template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
    96 //template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
     95template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
     96template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
     97template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
    9798
    9899//Compile FullGraph
     
    131132  }
    132133  {
    133     //    SymSmartGraph G;
    134     //    addPetersen(G);
    135     //    checkPetersen(G);
     134    SymSmartGraph G;
     135    addPetersen(G);
     136    checkPetersen(G);
    136137  }
    137138  {
    138     //    SymListGraph G;
    139     //    addPetersen(G);
    140     //    checkPetersen(G);
     139    SymListGraph G;
     140    addPetersen(G);
     141    checkPetersen(G);
    141142  }
    142143
  • src/test/graph_test.h

    r916 r919  
    299299      for(int i=0;i<nn;i++) {
    300300        check(e!=INVALID,"Wrong OutEdge list linking.");
    301         check(n==G.tail(e), "Wrong OutEdge list linking.");
    302301        ++e;
    303302      }
     
    312311      for(int i=0;i<nn;i++) {
    313312        check(e!=INVALID,"Wrong InEdge list linking.");
    314         check(n==G.head(e), "Wrong InEdge list linking.");
    315313        ++e;
    316314      }
  • src/test/test_tools.h

    r909 r919  
    6868
    6969///Adds a Petersen graph to \c G.
    70 ///\return The nodes and edges of the generated graph.
     70///\return The nodes end edges og the generated graph.
    7171
    7272template<typename Graph>
     
    8888}
    8989
    90 ///Structure returned by \ref addSymPetersen().
    9190
    92 ///Structure returned by \ref addSymPetersen().
    93 ///
    94 template<class Graph> struct SymPetStruct
    95 {
    96   ///Vector containing the outer nodes.
    97   std::vector<typename Graph::Node> outer;
    98   ///Vector containing the inner nodes.
    99   std::vector<typename Graph::Node> inner;
    100   ///Vector containing the edges of the inner circle.
    101   std::vector<typename Graph::SymEdge> incir;
    102   ///Vector containing the edges of the outer circle.
    103   std::vector<typename Graph::SymEdge> outcir;
    104   ///Vector containing the chord edges.
    105   std::vector<typename Graph::SymEdge> chords;
    106 };
    107 
    108 ///Adds a Petersen graph to the symmetric \c G.
    109 
    110 ///Adds a Petersen graph to the symmetric \c G.
    111 ///\return The nodes and edges of the generated graph.
    112 
    113 template<typename Graph>
    114 SymPetStruct<Graph> addSymPetersen(Graph &G,int num=5)
    115 {
    116   SymPetStruct<Graph> n;
    117 
    118   for(int i=0;i<num;i++) {
    119     n.outer.push_back(G.addNode());
    120     n.inner.push_back(G.addNode());
    121   }
    122 
    123  for(int i=0;i<num;i++) {
    124    n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
    125    n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));
    126    n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));
    127   }
    128  return n;
    129 }
    13091
    13192#endif
Note: See TracChangeset for help on using the changeset viewer.