COIN-OR::LEMON - Graph Library

Changeset 909:6a22e0dfd453 in lemon-0.x for src


Ignore:
Timestamp:
09/26/04 23:43:38 (16 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1220
Message:

New symmetric Graph concept.
New symmetric list and smart graph.
Symmetric Graph tests based on the Graph Tests.

Location:
src
Files:
3 added
1 deleted
10 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/Makefile.am

    r899 r909  
    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                                                       \
    2726        time_measure.h                                                  \
    2827        unionfind.h                                                     \
     
    3231noinst_HEADERS =                                                        \
    3332        skeletons/graph.h                                               \
     33        skeletons/sym_graph.h                                           \
    3434        skeletons/maps.h                                                \
    3535        skeletons/path.h
  • src/hugo/default_map.h

    r906 r909  
    6060template <typename TT> \
    6161DefaultMap(const DefaultMap<MapRegistry, TT>& copy) \
    62   : { \
    63   Parent::MapBase::operator= \
    64     (static_cast<const typename Parent::MapBase&>(copy)); \
     62  : Parent(*copy.getGraph()) { \
    6563  if (Parent::getGraph()) { \
    6664    for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\
    67       Parent::add(it); \
    6865      Parent::operator[](it) = copy[it]; \
    6966    } \
  • src/hugo/list_graph.h

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

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

    r906 r909  
    115115 */
    116116#define CREATE_SYM_EDGE_MAP_REGISTRY \
    117 typedef SymEdgeIt<Graph, Edge, EdgeIt> SymEdgeIt; \
    118 typedef MapRegistry<Graph, Edge, SymEdgeIt> SymEdgeMapRegistry; \
     117typedef MapRegistry<Graph, SymEdge, SymEdgeIt> SymEdgeMapRegistry; \
    119118mutable SymEdgeMapRegistry sym_edge_maps;
    120119
     
    128127#define CREATE_SYM_EDGE_MAP(DynMap) \
    129128template <typename Value> \
    130 class SymEdgeMap : public SymMap<DynMap, SymEdgeMapRegistry, Value> { \
    131 public: \
    132 typedef SymMap<DynMap, SymEdgeMapRegistry, Value> Parent; \
     129class SymEdgeMap : public DynMap<SymEdgeMapRegistry, Value> { \
     130public: \
     131typedef DynMap<SymEdgeMapRegistry, Value> Parent; \
    133132\
    134133SymEdgeMap(const typename Parent::Graph& g) \
  • src/hugo/map_registry.h

    r906 r909  
    253253     * Notify all the registered maps about a Key added.
    254254     */
    255     void add(KeyType& key) {
     255    void add(const 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(KeyType& key) {
     265    void erase(const KeyType& key) {
    266266      typename Container::iterator it;
    267267      for (it = container.begin(); it != container.end(); ++it) {
  • src/hugo/smart_graph.h

    r906 r909  
    2828
    2929#include <hugo/array_map.h>
    30 #include <hugo/sym_map.h>
    31 
    3230#include <hugo/map_registry.h>
    3331
     
    299297  };
    300298
     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  };
    301674  ///Graph for bidirectional edges.
    302675
     
    319692  //\sa SmartGraph.
    320693
    321   class SymSmartGraph : public SmartGraph
     694  /*  class SymSmartGraph : public SmartGraph
    322695  {
    323696  public:
     
    354727   
    355728
    356   };
     729    };*/
    357730 
    358731  /// @} 
  • src/test/Makefile.am

    r899 r909  
    1010        dijkstra_test \
    1111        graph_test \
     12        sym_graph_test \
    1213        graph_wrapper_test \
    1314        kruskal_test \
     
    2930dijkstra_test_SOURCES = dijkstra_test.cc
    3031graph_test_SOURCES = graph_test.cc
     32sym_graph_test_SOURCES = sym_graph_test.cc
    3133graph_wrapper_test_SOURCES = graph_wrapper_test.cc
    3234kruskal_test_SOURCES = kruskal_test.cc
  • src/test/graph_test.cc

    r906 r909  
    6464    checkGraphInEdgeList(G,n,3);
    6565    checkGraphOutEdgeList(G,n,3);
    66     ++n;
    6766  } 
    6867}
     
    8382
    8483//Compile SymSmartGraph
    85 template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
    86 template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
     84//template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
     85//template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
    8786
    8887//Compile ListGraph
     
    9392
    9493//Compile SymListGraph
    95 template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
    96 template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
    97 template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
     94//template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
     95//template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
     96//template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
    9897
    9998//Compile FullGraph
     
    132131  }
    133132  {
    134     SymSmartGraph G;
    135     addPetersen(G);
    136     checkPetersen(G);
     133    //    SymSmartGraph G;
     134    //    addPetersen(G);
     135    //    checkPetersen(G);
    137136  }
    138137  {
    139     SymListGraph G;
    140     addPetersen(G);
    141     checkPetersen(G);
     138    //    SymListGraph G;
     139    //    addPetersen(G);
     140    //    checkPetersen(G);
    142141  }
    143142
  • src/test/test_tools.h

    r906 r909  
    6868
    6969///Adds a Petersen graph to \c G.
    70 ///\return The nodes end edges og the generated graph.
     70///\return The nodes and edges of the generated graph.
    7171
    7272template<typename Graph>
     
    8888}
    8989
     90///Structure returned by \ref addSymPetersen().
    9091
     92///Structure returned by \ref addSymPetersen().
     93///
     94template<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
     113template<typename Graph>
     114SymPetStruct<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}
    91130
    92131#endif
Note: See TracChangeset for help on using the changeset viewer.