equal
deleted
inserted
replaced
71 |
71 |
72 /// \brief Function to count the nodes in the graph. |
72 /// \brief Function to count the nodes in the graph. |
73 /// |
73 /// |
74 /// This function counts the nodes in the graph. |
74 /// This function counts the nodes in the graph. |
75 /// The complexity of the function is O(n) but for some |
75 /// The complexity of the function is O(n) but for some |
76 /// graph structure it is specialized to run in O(1). |
76 /// graph structures it is specialized to run in O(1). |
77 /// |
77 /// |
78 /// \todo refer how to specialize it |
78 /// \todo refer how to specialize it |
79 |
79 |
80 template <typename Graph> |
80 template <typename Graph> |
81 inline int countNodes(const Graph& g) { |
81 inline int countNodes(const Graph& g) { |
98 |
98 |
99 /// \brief Function to count the edges in the graph. |
99 /// \brief Function to count the edges in the graph. |
100 /// |
100 /// |
101 /// This function counts the edges in the graph. |
101 /// This function counts the edges in the graph. |
102 /// The complexity of the function is O(e) but for some |
102 /// The complexity of the function is O(e) but for some |
103 /// graph structure it is specialized to run in O(1). |
103 /// graph structures it is specialized to run in O(1). |
104 |
104 |
105 template <typename Graph> |
105 template <typename Graph> |
106 inline int countEdges(const Graph& g) { |
106 inline int countEdges(const Graph& g) { |
107 return _countEdges<Graph>(g); |
107 return _countEdges<Graph>(g); |
108 } |
108 } |
119 template <typename Graph> |
119 template <typename Graph> |
120 inline int _countUndirEdges(Wrap<Graph> w) { |
120 inline int _countUndirEdges(Wrap<Graph> w) { |
121 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value); |
121 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value); |
122 } |
122 } |
123 |
123 |
124 /// \brief Function to count the edges in the graph. |
124 /// \brief Function to count the undirected edges in the graph. |
125 /// |
125 /// |
126 /// This function counts the edges in the graph. |
126 /// This function counts the undirected edges in the graph. |
127 /// The complexity of the function is O(e) but for some |
127 /// The complexity of the function is O(e) but for some |
128 /// graph structure it is specialized to run in O(1). |
128 /// graph structure it is specialized to run in O(1). |
129 |
129 |
130 template <typename Graph> |
130 template <typename Graph> |
131 inline int countUndirEdges(const Graph& g) { |
131 inline int countUndirEdges(const Graph& g) { |
172 else ++e; |
172 else ++e; |
173 while(e!=INVALID && g.target(e)!=v) ++e; |
173 while(e!=INVALID && g.target(e)!=v) ++e; |
174 return e; |
174 return e; |
175 } |
175 } |
176 |
176 |
177 ///\e |
177 /// \brief Function to count the number of the out-edges from node \c n. |
178 |
178 /// |
179 ///\todo Please document. |
179 /// This function counts the number of the out-edges from node \c n |
180 /// |
180 /// in the graph. |
181 template <typename Graph> |
181 template <typename Graph> |
182 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) { |
182 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) { |
183 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n); |
183 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n); |
184 } |
184 } |
185 |
185 |
186 ///\e |
186 /// \brief Function to count the number of the in-edges to node \c n. |
187 |
187 /// |
188 ///\todo Please document. |
188 /// This function counts the number of the in-edges to node \c n |
189 /// |
189 /// in the graph. |
190 template <typename Graph> |
190 template <typename Graph> |
191 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { |
191 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { |
192 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n); |
192 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n); |
193 } |
193 } |
194 |
194 |
362 typedef typename Map::ConstPointer ConstPointer; |
362 typedef typename Map::ConstPointer ConstPointer; |
363 }; |
363 }; |
364 |
364 |
365 /// Provides an immutable and unique id for each item in the graph. |
365 /// Provides an immutable and unique id for each item in the graph. |
366 |
366 |
367 /// The IdMap class provides an unique and immutable mapping for each item |
367 /// The IdMap class provides a unique and immutable mapping for each item |
368 /// in the graph. |
368 /// in the graph. |
369 /// |
369 /// |
370 template <typename _Graph, typename _Item> |
370 template <typename _Graph, typename _Item> |
371 class IdMap { |
371 class IdMap { |
372 public: |
372 public: |
427 InverseMap inverse() const { return InverseMap(*graph);} |
427 InverseMap inverse() const { return InverseMap(*graph);} |
428 |
428 |
429 }; |
429 }; |
430 |
430 |
431 |
431 |
432 /// \brief General inversable graph-map type. |
432 /// \brief General invertable graph-map type. |
433 |
433 |
434 /// This type provides simple inversable map functions. |
434 /// This type provides simple invertable map functions. |
435 /// The InversableMap wraps an arbitrary ReadWriteMap |
435 /// The InvertableMap wraps an arbitrary ReadWriteMap |
436 /// and if a key is setted to a new value then store it |
436 /// and if a key is set to a new value then store it |
437 /// in the inverse map. |
437 /// in the inverse map. |
438 /// \param _Graph The graph type. |
438 /// \param _Graph The graph type. |
439 /// \param _Map The map to extend with inversable functionality. |
439 /// \param _Map The map to extend with invertable functionality. |
440 template < |
440 template < |
441 typename _Graph, |
441 typename _Graph, |
442 typename _Item, |
442 typename _Item, |
443 typename _Value, |
443 typename _Value, |
444 typename _Map |
444 typename _Map |