Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/hugo/full_graph.h
changeset 784 a48964a87141
parent 774 4297098d9677
child 798 6d1abeb62dd3
equal deleted inserted replaced
6:515cedae628b 7:f6650130b800 
     6 ///\ingroup graphs
 
     6 ///\ingroup graphs
 
     7 ///\file
 
     7 ///\file
 
     8 ///\brief FullGraph and SymFullGraph classes.
 
     8 ///\brief FullGraph and SymFullGraph classes.
 
     9 
     9 
    10 #include <vector>
 
    10 #include <vector>
 
    11 #include <limits.h>
 
    11 #include <climits>
 
    12 
    12 
    13 #include <hugo/invalid.h>
 
    13 #include <hugo/invalid.h>
 
       
    14 
       
    15 #include <hugo/map_registry.h>
 
       
    16 #include <hugo/array_map_factory.h>
 
    14 
    17 
    15 namespace hugo {
 
    18 namespace hugo {
 
    16 
    19 
    17 /// \addtogroup graphs
 
    20 /// \addtogroup graphs
 
    18 /// @{
 
    21 /// @{
 
    31   ///\author Alpar Juttner
 
    34   ///\author Alpar Juttner
 
    32   class FullGraph {
 
    35   class FullGraph {
 
    33     int NodeNum;
 
    36     int NodeNum;
 
    34     int EdgeNum;
 
    37     int EdgeNum;
 
    35   public:
 
    38   public:
 
    36     template <typename T> class EdgeMap;
 
    39 
    37     template <typename T> class NodeMap;
 
    40     typedef FullGraph Graph;
 
    38 
    41 
    39     class Node;
 
    42     class Node;
 
    40     class Edge;
 
    43     class Edge;
 
       
    44 
    41     class NodeIt;
 
    45     class NodeIt;
 
    42     class EdgeIt;
 
    46     class EdgeIt;
 
    43     class OutEdgeIt;
 
    47     class OutEdgeIt;
 
    44     class InEdgeIt;
 
    48     class InEdgeIt;
 
    45     
    49     
    46     template <typename T> class NodeMap;
 
    50     CREATE_MAP_REGISTRIES;
 
    47     template <typename T> class EdgeMap;
 
    51     CREATE_MAPS(ArrayMapFactory);
 
    48     
    52     
    49   public:
 
    53   public:
 
    50 
    54 
    51     ///Creates a full graph with \c n nodes.
 
    55     ///Creates a full graph with \c n nodes.
 
    52     FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
 
    56     FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
 
    83     /// It finds the first edge from \c u to \c v. Otherwise it looks for
 
    87     /// It finds the first edge from \c u to \c v. Otherwise it looks for
 
    84     /// the next edge from \c u to \c v after \c prev.
 
    88     /// the next edge from \c u to \c v after \c prev.
 
    85     /// \return The found edge or INVALID if there is no such an edge.
 
    89     /// \return The found edge or INVALID if there is no such an edge.
 
    86     Edge findEdge(Node u,Node v, Edge prev = INVALID) 
    90     Edge findEdge(Node u,Node v, Edge prev = INVALID) 
    87     {
 
    91     {
 
    88       return prev.n==-1?Edge(*this,u.n,v.n):INVALID;
 
    92       return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
 
    89     }
 
    93     }
 
    90     
    94     
    91       
    95       
    92     class Node {
 
    96     class Node {
 
    93       friend class FullGraph;
 
    97       friend class FullGraph;
 
   185       InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
 
   189       InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
 
   186       InEdgeIt& operator++()
 
   190       InEdgeIt& operator++()
 
   187       { if(!((++n)%G->NodeNum)) n=-1; return *this; }
 
   191       { if(!((++n)%G->NodeNum)) n=-1; return *this; }
 
   188     };
 
   192     };
 
   189 
   193 
   190     template <typename T> class NodeMap
 
       
   191     {
 
       
   192       std::vector<T> container;
 
       
   193 
       
   194     public:
 
       
   195       typedef T ValueType;
 
       
   196       typedef Node KeyType;
 
       
   197 
       
   198       NodeMap(const FullGraph &_G) : container(_G.NodeNum) { }
 
       
   199       NodeMap(const FullGraph &_G,const T &t) : container(_G.NodeNum,t) { }
 
       
   200       NodeMap(const NodeMap<T> &m) : container(m.container) { }
 
       
   201 
       
   202       template<typename TT> friend class NodeMap;
 
       
   203       ///\todo It can copy between different types.
 
       
   204       template<typename TT> NodeMap(const NodeMap<TT> &m)
 
       
   205 	: container(m.container.size())
 
       
   206       {
 
       
   207 	typename std::vector<TT>::const_iterator i;
 
       
   208 	for(typename std::vector<TT>::const_iterator i=m.container.begin();
 
       
   209 	    i!=m.container.end();
 
       
   210 	    i++)
 
       
   211 	  container.push_back(*i);
 
       
   212       }
 
       
   213       void set(Node n, T a) { container[n.n]=a; }
 
       
   214       //'T& operator[](Node n)' would be wrong here
 
       
   215       typename std::vector<T>::reference
 
       
   216       operator[](Node n) { return container[n.n]; }
 
       
   217       //'const T& operator[](Node n)' would be wrong here
 
       
   218       typename std::vector<T>::const_reference 
       
   219       operator[](Node n) const { return container[n.n]; }
 
       
   220 
       
   221       ///\warning There is no safety check at all!
 
       
   222       ///Using operator = between maps attached to different graph may
 
       
   223       ///cause serious problem.
 
       
   224       ///\todo Is this really so?
 
       
   225       ///\todo It can copy between different types.
 
       
   226       const NodeMap<T>& operator=(const NodeMap<T> &m)
 
       
   227       {
 
       
   228 	container = m.container;
 
       
   229 	return *this;
 
       
   230       }
 
       
   231       template<typename TT>
 
       
   232       const NodeMap<T>& operator=(const NodeMap<TT> &m)
 
       
   233       {
 
       
   234 	std::copy(m.container.begin(), m.container.end(), container.begin());
 
       
   235 	return *this;
 
       
   236       }
 
       
   237       
       
   238       void update() {}    //Useless for Dynamic Maps
 
       
   239       void update(T a) {}  //Useless for Dynamic Maps
 
       
   240     };
 
       
   241     
       
   242     template <typename T> class EdgeMap
 
       
   243     {
 
       
   244       std::vector<T> container;
 
       
   245 
       
   246     public:
 
       
   247       typedef T ValueType;
 
       
   248       typedef Edge KeyType;
 
       
   249 
       
   250       EdgeMap(const FullGraph &_G) : container(_G.EdgeNum) { }
 
       
   251       EdgeMap(const FullGraph &_G,const T &t) : container(_G.EdgeNum,t) { } 
       
   252       EdgeMap(const EdgeMap<T> &m) : container(m.container) { }
 
       
   253 
       
   254       template<typename TT> friend class EdgeMap;
 
       
   255       ///\todo It can copy between different types. 
       
   256       ///\todo We could use 'copy'
 
       
   257       template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
 
       
   258 	container(m.container.size())
 
       
   259       {
 
       
   260 	typename std::vector<TT>::const_iterator i;
 
       
   261 	for(typename std::vector<TT>::const_iterator i=m.container.begin();
 
       
   262 	    i!=m.container.end();
 
       
   263 	    i++)
 
       
   264 	  container.push_back(*i);
 
       
   265       }
 
       
   266       void set(Edge n, T a) { container[n.n]=a; }
 
       
   267       //T get(Edge n) const { return container[n.n]; }
 
       
   268       typename std::vector<T>::reference
 
       
   269       operator[](Edge n) { return container[n.n]; }
 
       
   270       typename std::vector<T>::const_reference
 
       
   271       operator[](Edge n) const { return container[n.n]; }
 
       
   272 
       
   273       ///\warning There is no safety check at all!
 
       
   274       ///Using operator = between maps attached to different graph may
 
       
   275       ///cause serious problem.
 
       
   276       ///\todo Is this really so?
 
       
   277       ///\todo It can copy between different types.
 
       
   278       const EdgeMap<T>& operator=(const EdgeMap<T> &m)
 
       
   279       {
 
       
   280 	container = m.container;
 
       
   281 	return *this;
 
       
   282       }
 
       
   283       template<typename TT>
 
       
   284       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
 
       
   285       {
 
       
   286 	std::copy(m.container.begin(), m.container.end(), container.begin());
 
       
   287 	return *this;
 
       
   288       }
 
       
   289 
       
   290       void update() {}
 
       
   291       void update(T a) {}
 
       
   292     };
 
       
   293 
       
   294   };
 
   194   };
 
   295 
   195 
   296   /// @}  
   196   /// @}  
   297 
   197 
   298 } //namespace hugo
 
   198 } //namespace hugo
lemon-0.x