Changeset 977:48962802d168 in lemon-0.x
- Timestamp:
- 11/10/04 21:14:32 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1365
- Location:
- src
- Files:
-
- 1 added
- 9 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/Makefile.am
r962 r977 30 30 map_defines.h \ 31 31 map_bits.h \ 32 utility.h \ 32 33 iterable_graph_extender.h \ 33 34 idmappable_graph_extender.h \ -
src/lemon/bfs.h
r946 r977 26 26 #include <lemon/bin_heap.h> 27 27 #include <lemon/invalid.h> 28 #include <lemon/graph_utils.h> 28 29 29 30 namespace lemon { -
src/lemon/full_graph.h
r959 r977 20 20 21 21 #include <lemon/idmappable_graph_extender.h> 22 23 22 #include <lemon/iterable_graph_extender.h> 24 25 23 #include <lemon/alteration_observer_registry.h> 26 24 #include <lemon/default_map.h> 25 26 #include <lemon/invalid.h> 27 #include <lemon/utility.h> 28 27 29 28 30 ///\ingroup graphs … … 30 32 ///\brief FullGraph and SymFullGraph classes. 31 33 32 33 #include <lemon/invalid.h>34 34 35 35 namespace lemon { … … 59 59 // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } 60 60 61 typedef True NodeNumTag; 62 typedef True EdgeNumTag; 63 61 64 ///Number of nodes. 62 65 int nodeNum() const { return NodeNum; } … … 207 210 }; 208 211 209 template <>210 int countNodes<FullGraph>(const FullGraph& graph) {211 return graph.nodeNum();212 }213 214 template <>215 int countEdges<FullGraph>(const FullGraph& graph) {216 return graph.edgeNum();217 }218 219 212 /// @} 220 213 … … 222 215 223 216 224 225 226 217 #endif //LEMON_FULL_GRAPH_H -
src/lemon/graph_utils.h
r967 r977 21 21 22 22 #include <lemon/invalid.h> 23 #include <lemon/utility.h> 23 24 24 25 ///\ingroup gutils … … 36 37 /// @{ 37 38 38 // counters in the graph39 39 /// \brief Function to count the items in the graph. 40 40 /// … … 44 44 45 45 template <typename Graph, typename ItemIt> 46 inline int countItems(const Graph& _g) {46 inline int countItems(const Graph& g) { 47 47 int num = 0; 48 for (ItemIt it( _g); it != INVALID; ++it) {48 for (ItemIt it(g); it != INVALID; ++it) { 49 49 ++num; 50 50 } 51 51 return num; 52 } 53 54 // Node counting: 55 56 template <typename Graph> 57 inline 58 typename enable_if<typename Graph::NodeNumTag, int>::type 59 _countNodes(const Graph &g) { 60 return g.nodeNum(); 61 } 62 63 template <typename Graph> 64 inline int _countNodes(Wrap<Graph> w) { 65 return countItems<Graph, typename Graph::NodeIt>(w.value); 52 66 } 53 67 … … 57 71 /// The complexity of the function is O(n) but for some 58 72 /// graph structure it is specialized to run in O(1). 59 60 template <typename Graph> 61 inline int countNodes(const Graph& _g) { 62 return countItems<Graph, typename Graph::NodeIt>(_g); 73 /// 74 /// \todo refer how to specialize it 75 76 template <typename Graph> 77 inline int countNodes(const Graph& g) { 78 return _countNodes<Graph>(g); 79 } 80 81 // Edge counting: 82 83 template <typename Graph> 84 inline 85 typename enable_if<typename Graph::EdgeNumTag, int>::type 86 _countEdges(const Graph &g) { 87 return g.edgeNum(); 88 } 89 90 template <typename Graph> 91 inline int _countEdges(Wrap<Graph> w) { 92 return countItems<Graph, typename Graph::EdgeIt>(w.value); 63 93 } 64 94 … … 68 98 /// The complexity of the function is O(e) but for some 69 99 /// graph structure it is specialized to run in O(1). 70 template <typename Graph> 71 inline int countEdges(const Graph& _g) { 72 return countItems<Graph, typename Graph::EdgeIt>(_g); 100 101 template <typename Graph> 102 inline int countEdges(const Graph& g) { 103 return _countEdges<Graph>(g); 73 104 } 74 105 … … 82 113 return countItems<Graph, typename Graph::SymEdgeIt>(_g); 83 114 } 115 84 116 85 117 template <typename Graph, typename DegIt> -
src/lemon/maps.h
r959 r977 105 105 void set(const K&, const V&) { } 106 106 }; 107 //to document later108 typedef Const<bool, true> True;109 typedef Const<bool, false> False;110 107 111 108 /// \c std::map wrapper -
src/lemon/preflow.h
r946 r977 23 23 #include <lemon/invalid.h> 24 24 #include <lemon/maps.h> 25 #include <lemon/graph_utils.h> 25 26 26 27 /// \file -
src/lemon/smart_graph.h
r974 r977 28 28 #include <lemon/clearable_graph_extender.h> 29 29 #include <lemon/extendable_graph_extender.h> 30 31 30 #include <lemon/idmappable_graph_extender.h> 32 33 31 #include <lemon/iterable_graph_extender.h> 34 35 32 #include <lemon/alteration_observer_registry.h> 36 33 #include <lemon/default_map.h> 37 34 38 39 #include <lemon/graph_utils.h> 40 35 #include <lemon/utility.h> 41 36 42 37 namespace lemon { … … 85 80 SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { } 86 81 82 typedef True NodeNumTag; 83 typedef True EdgeNumTag; 84 87 85 ///Number of nodes. 88 86 int nodeNum() const { return nodes.size(); } … … 324 322 }; 325 323 326 template <>327 int countNodes<SmartGraph>(const SmartGraph& graph) {328 return graph.nodeNum();329 }330 331 template <>332 int countEdges<SmartGraph>(const SmartGraph& graph) {333 return graph.edgeNum();334 }335 336 324 /// @} 337 325 } //namespace lemon 338 326 339 327 340 341 342 328 #endif //LEMON_SMART_GRAPH_H -
src/test/graph_utils_test.cc
r946 r977 3 3 #include <iostream> 4 4 #include <vector> 5 6 #include <lemon/graph_utils.h> 5 7 6 8 #include <lemon/list_graph.h> … … 23 25 checkGraphCounters<SmartGraph>(); 24 26 } 27 { 28 int num = 5; 29 FullGraph fg(num); 30 check(countNodes(fg) == num, "FullGraph: wrong node number."); 31 check(countEdges(fg) == num*num, "FullGraph: wrong edge number."); 32 } 25 33 26 34 std::cout << __FILE__ ": All tests passed.\n"; -
src/test/graph_utils_test.h
r946 r977 31 31 addPetersen(graph, num); 32 32 bidirGraph(graph); 33 check(countNodes(graph) == 2*num, "Wrong node counter.");34 check(countEdges(graph) == 6*num, "Wrong edge counter.");33 check(countNodes(graph) == 2*num, "Wrong node number."); 34 check(countEdges(graph) == 6*num, "Wrong edge number."); 35 35 for (typename Graph::NodeIt it(graph); it != INVALID; ++it) { 36 check(countOutEdges(graph, it) == 3, "Wrong out degree counter.");37 check(countInEdges(graph, it) == 3, "Wrong in degree counter.");36 check(countOutEdges(graph, it) == 3, "Wrong out degree number."); 37 check(countInEdges(graph, it) == 3, "Wrong in degree number."); 38 38 } 39 39 }
Note: See TracChangeset
for help on using the changeset viewer.