COIN-OR::LEMON - Graph Library

Changeset 937:d4e911acef3d in lemon-0.x


Ignore:
Timestamp:
10/04/04 19:13:21 (19 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1264
Message:

Revert backport changes -r1230.

Location:
src
Files:
3 added
1 deleted
12 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/Makefile.am

    r921 r937  
    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/lemon/default_map.h

    r921 r937  
    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/lemon/list_graph.h

    r921 r937  
    3030#include <lemon/array_map.h>
    3131
    32 #include <lemon/sym_map.h>
    33 
    3432#include <lemon/map_defines.h>
    3533
     
    105103        first_free_edge(_g.first_free_edge) {}
    106104   
     105    /// \bug In the vector can be hole if a node is erased from the graph.
    107106    ///Number of nodes.
    108107    int nodeNum() const { return nodes.size(); }
     
    439438  ///\todo this date structure need some reconsiderations. Maybe it
    440439  ///should be implemented independently from ListGraph.
    441  
     440  /* 
    442441  class SymListGraph : public ListGraph
    443442  {
     
    484483      ListGraph::erase(e);
    485484    }   
     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
    486880  };
    487 
    488881
    489882  ///A graph class containing only nodes.
  • src/lemon/map_bits.h

    r921 r937  
    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/lemon/map_defines.h

    r921 r937  
    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/lemon/map_registry.h

    r921 r937  
    2828namespace lemon {
    2929
    30 /// \addtogroup graphmapfactory
    31 /// @{
    32 
    33 /**
    34  * Registry class to register edge or node maps into the graph. The
    35  * registry helps you to implement an observer pattern. If you add
    36  * or erase an edge or node you must notify all the maps about the
    37  * event.
    38 */
     30  /// \addtogroup graphmapfactory
     31  /// @{
     32
     33  /// Map registry for graph maps.
     34
     35  /**
     36   * Registry class to register edge or node maps into the graph. The
     37   * registry helps you to implement an observer pattern. If you add
     38   * or erase an edge or node you must notify all the maps about the
     39   * event.
     40   *
     41   * \param G The graph type to register maps.
     42   * \param K The key type of the maps registered into the registry.
     43   * \param KIt The key iterator type iterates on the keys.
     44   *
     45   * \author Balazs Dezso
     46   */
     47
    3948  template <typename G, typename K, typename KIt>
    4049  class MapRegistry {
     
    4352    typedef K KeyType;
    4453    typedef KIt KeyIt;
    45        
    46     /**
    47      * MapBase is the base class of the registered maps.
     54
     55    /// MapBase is the base class of the dynamic maps.
     56       
     57    /**
     58     * MapBase is the base class of the dynamic maps.
    4859     * It defines the core modification operations on the maps and
    4960     * implements some helper functions.
     
    5970      friend class MapRegistry<G, K, KIt>;
    6071
     72      /// Default constructor.
     73
    6174      /**
    6275       * Default constructor for MapBase.
     
    6477
    6578      MapBase() : graph(0), registry(0) {}
    66                
    67       /**
    68        * Simple constructor to register into a graph registry.
     79
     80      /// Constructor to register map into a graph registry.
     81               
     82      /**
     83       * Simple constructor to register dynamic map into a graph registry.
    6984      */
    7085       
     
    7388      }
    7489
     90      /// Copy constructor.
     91
    7592      /**
    7693       * Copy constructor to register into the registry.
     94       * If the copiable map is registered into a registry
     95       * the construated map will be registered to the same registry.
    7796      */       
    7897       
     
    82101        }
    83102      }
    84        
    85       /**
    86        * Assign operator.
     103
     104      /// Assign operator.
     105       
     106      /**
     107       * Assign operator. This member detach first the map
     108       * from the current registry and then it attach to the
     109       * copiable map's registry if it exists.
    87110      */       
    88111      const MapBase& operator=(const MapBase& copy) {
     
    97120      }
    98121       
    99 
    100       /**
    101        * Destructor.
     122      /// Destructor
     123
     124      /**
     125       * This member detach the map from the its registry if the
     126       * registry exists.
    102127      */               
    103128
     
    108133      }
    109134
     135      /// The graph of the map.
     136
    110137      /*
    111138       * Returns the graph that the map belongs to.
     
    122149
    123150    protected:
    124        
    125       /**
    126          Helper function to implement constructors in the subclasses.
     151
     152      /// Helper function to implement constructors in the subclasses.
     153       
     154      /**
     155       * Helper function to implement constructors in the subclasses.
     156       * It adds all of the nodes or edges to the map via the
     157       * \ref MapRegistry::MapBase::add add
     158       * member function.
    127159      */
    128160       
     
    133165      }
    134166       
    135       /**
    136          Helper function to implement the destructor in the subclasses.
     167
     168      /// Helper function to implement destructors in the subclasses.
     169       
     170      /**
     171       * Helper function to implement destructors in the subclasses.
     172       * It erases all of the nodes or edges of the map via the
     173       * \ref MapRegistry::MapBase::erase erase
     174       * member function. It can be used by the clear function also.
    137175      */
    138176       
     
    142180        }
    143181      }
     182
     183      /// The member function to add new node or edge to the map.
    144184       
    145185      /**
    146186          The add member function should be overloaded in the subclasses.
    147           \e Add extends the map with the new node.
     187          \e Add extends the map with the new node or edge.
    148188      */
    149189       
    150190      virtual void add(const KeyType&) = 0;     
     191
     192
     193      /// The member function to erase a node or edge from the map.
     194
    151195      /**
    152196          The erase member function should be overloaded in the subclasses.
    153           \e Erase removes the node from the map.
     197          \e Erase removes the node or edge from the map.
    154198      */
    155199       
     
    162206
    163207      virtual void clear() = 0;
    164        
    165       /**
    166          Exception class to throw at unsupported operation.
     208
     209      /// Exception class to throw at unsupported operation.
     210       
     211      /**
     212       * Exception class to throw at unsupported operation.
     213       * If the map does not support erasing or adding new
     214       * node or key it must be throwed.
    167215      */
    168216       
     
    173221  protected:
    174222       
    175     /**
    176      * The container type of the maps.
    177      */
     223
    178224    typedef std::vector<MapBase*> Container;
    179225
    180     /**
    181      * The container of the registered maps.
    182      */
    183226    Container container;
    184227
    185228               
    186229  public:
    187        
    188     /**
    189      * Default Constructor of the MapRegistry. It creates an empty registry.
     230
     231    /// Default constructor.
     232       
     233    /**
     234     * Default constructor of the \e MapRegistry.
     235     * It creates an empty registry.
    190236     */
    191237    MapRegistry() {}
    192        
    193     /**
    194      * Copy Constructor of the MapRegistry. The new registry does not steal
    195      * the maps from the right value. The new registry will be an empty.
     238
     239    /// Copy Constructor of the MapRegistry.
     240       
     241    /**
     242     * Copy constructor of the \e MapRegistry.
     243     * The new registry does not steal
     244     * the maps from the copiable registry.
     245     * The new registry will be empty.
    196246     */
    197247    MapRegistry(const MapRegistry&) {}
    198                
    199     /**
    200      * Assign operator. The left value does not steal the maps
    201      * from the right value. The left value will be an empty registry.
     248
     249    /// Assign operator.
     250               
     251    /**
     252     * Assign operator. This registry does not steal the maps
     253     * from the copiable registry. This registry will be an empty registry.
     254     * This operator will be called when a graph is assigned.
    202255     */
    203256    MapRegistry& operator=(const MapRegistry&) {
    204257      typename Container::iterator it;
    205258      for (it = container.begin(); it != container.end(); ++it) {
    206         (*it)->destroy();
     259        (*it)->clear();
    207260        (*it)->graph = 0;
    208261        (*it)->registry = 0;
    209262      }
    210263    }
     264
     265    /// Destructor.
    211266                               
    212267    /**
    213      * Destructor of the MapRegistry.
     268     * Destructor of the MapRegistry. It makes empty the attached map
     269     * first then detachs them.
    214270     */
    215271    ~MapRegistry() {
    216272      typename Container::iterator it;
    217273      for (it = container.begin(); it != container.end(); ++it) {
    218         (*it)->destroy();
     274        (*it)->clear();
    219275        (*it)->registry = 0;
    220276        (*it)->graph = 0;
     
    224280       
    225281    public:
    226        
    227     /**
    228      * Attach a map into thr registry. If the map has been attached
     282
     283    /// Attachs a map to the \e MapRegistry.
     284       
     285    /**
     286     * Attachs a map into thr registry. If the map has been attached
    229287     * into an other registry it is detached from that automaticly.
    230288     */
     
    237295      map.registry_index = container.size()-1;
    238296    }
    239        
    240     /**
    241      * Detach the map from the registry.
     297
     298    /// Detachs a map from the \e MapRegistry.
     299       
     300    /**
     301     * Detachs a map from the \e MapRegistry.
    242302     */
    243303    void detach(MapBase& map) {
     
    249309    }
    250310       
     311    /// Notify all the registered maps about a Key added.
    251312               
    252313    /**
    253314     * Notify all the registered maps about a Key added.
    254      */
    255     void add(KeyType& key) {
     315     * This member should be called whenever a node or edge
     316     * is added to the graph.
     317     */
     318    void add(const KeyType& key) {
    256319      typename Container::iterator it;
    257320      for (it = container.begin(); it != container.end(); ++it) {
     
    259322      }
    260323    }   
     324
     325    /// Notify all the registered maps about a Key erased.
    261326               
    262327    /**
    263328     * Notify all the registered maps about a Key erased.
     329     * This member should be called whenever a node or edge
     330     * is erased from the graph.
    264331     */
    265     void erase(KeyType& key) {
     332    void erase(const KeyType& key) {
    266333      typename Container::iterator it;
    267334      for (it = container.begin(); it != container.end(); ++it) {
     
    270337    }
    271338
     339
     340    /// Notify all the registered maps about all the Keys are erased.
     341
    272342    /**
    273343     * Notify all the registered maps about the map should be cleared.
     344     * This member should be called whenever all of the nodes or edges
     345     * are erased from the graph.
    274346     */
    275347    void clear() {
  • src/lemon/smart_graph.h

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

    r921 r937  
    3232  /// @{
    3333 
    34   /** The ArrayMap template class is graph map structure what
     34  /** The VectorMap template class is graph map structure what
    3535   *  automatically updates the map when a key is added to or erased from
    3636   *  the map. This map factory uses the allocators to implement
     
    3838   *  uses the std::vector to implement the container function.
    3939   *
    40    *  The template parameter is the MapRegistry that the maps
    41    *  will belong to and the ValueType.
     40   *  \param MapRegistry The MapRegistry that the maps will belong to.
     41   *  \param Value The value type of the map.
    4242   *
    43    * \todo It should use a faster initialization using the maxNodeId() or
    44    * maxEdgeId() function of the graph instead of iterating through each
    45    * edge/node.
     43   *  \author Balazs Dezso
    4644   */
    4745       
     
    8583    typedef typename Container::const_pointer ConstPointerType;
    8684
    87     /** Graph and Registry initialized map constructor.
     85    /// Constructor to attach the new map into a registry.
     86
     87    /** Constructor to attach the new map into a registry.
     88     *  It adds all the nodes or edges of the graph to the map.
    8889     */
    8990    VectorMap(const Graph& g, MapRegistry& r)
    9091      : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
    9192
    92     /** Constructor to use default value to initialize the map.
     93    /// Constructor uses given value to initialize the map.
     94
     95    /** Constructor uses given value to initialize the map.
     96     *  It adds all the nodes or edges of the graph to the map.
    9397     */
    9498    VectorMap(const Graph& g, MapRegistry& r, const Value& v)
    9599      : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {}
    96100
     101    /// Assign operator to copy a map of an other map type.
     102
    97103    /** Assign operator to copy a map of an other map type.
     104     *  This map's value type must be assignable by the other
     105     *  map type's value type.
    98106     */
    99107    template <typename TT>
     
    106114    }
    107115
     116    /// Assign operator to copy a map of an other map type.
     117
    108118    /** Assign operator to copy a map of an other map type.
     119     *  This map's value type must be assignable by the other
     120     *  map type's value type.
    109121     */
    110122    template <typename TT>
     
    120132      return *this;
    121133    }
     134
     135    /// The subcript operator.
     136
    122137    /**
    123138     * The subscript operator. The map can be subscripted by the
     
    129144    }
    130145               
     146    /// The const subcript operator.
     147
    131148    /**
    132149     * The const subscript operator. The map can be subscripted by the
     
    138155    }
    139156
     157    ///Setter function of the map.
     158
    140159    /** Setter function of the map. Equivalent with map[key] = val.
    141160     *  This is a compatibility feature with the not dereferable maps.
     
    145164      container[id] = val;
    146165    }
    147                
    148     /** Add a new key to the map. It called by the map registry.
     166    /// Adds a new key to the map.
     167               
     168    /** Adds a new key to the map. It called by the map registry
     169     *  and it overrides the \ref MapRegistry::MapBase MapBase's
     170     *  add() member function.
    149171     */
    150172    void add(const KeyType& key) {
     
    154176      }
    155177    }
    156                
    157     /** Erase a key from the map. It called by the map registry.
     178
     179    /// Erases a key from the map.
     180               
     181    /** Erase a key from the map. It called by the map registry
     182     *  and it overrides the \ref MapRegistry::MapBase MapBase's
     183     *  erase() member function.
    158184     */
    159185    void erase(const KeyType& key) {}
    160186
    161     /** Clear the data structure.
    162      */
     187    /// Makes empty the map.
     188
     189    /** Makes empty the map. It called by the map registry
     190     *  and it overrides the \ref MapRegistry::MapBase MapBase's
     191     *  clear() member function.
     192     */
     193
    163194    void clear() {
    164195      container.clear();
  • src/test/Makefile.am

    r919 r937  
    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

    r921 r937  
    6464    checkGraphInEdgeList(G,n,3);
    6565    checkGraphOutEdgeList(G,n,3);
    66     ++n;
    6766  } 
    6867}
     
    8382
    8483//Compile SymSmartGraph
    85 template void lemon::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
    86 template void lemon::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 lemon::checkCompileGraph<SymListGraph>(SymListGraph &);
    96 template void lemon::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
    97 template void lemon::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/graph_test.h

    r921 r937  
    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.");
    301302        ++e;
    302303      }
     
    311312      for(int i=0;i<nn;i++) {
    312313        check(e!=INVALID,"Wrong InEdge list linking.");
     314        check(n==G.head(e), "Wrong InEdge list linking.");
    313315        ++e;
    314316      }
  • src/test/test_tools.h

    r921 r937  
    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.