33 namespace lemon { |
34 namespace lemon { |
34 |
35 |
35 /// \addtogroup gutils |
36 /// \addtogroup gutils |
36 /// @{ |
37 /// @{ |
37 |
38 |
38 // counters in the graph |
|
39 /// \brief Function to count the items in the graph. |
39 /// \brief Function to count the items in the graph. |
40 /// |
40 /// |
41 /// This function counts the items in the graph. |
41 /// This function counts the items in the graph. |
42 /// The complexity of the function is O(n) because |
42 /// The complexity of the function is O(n) because |
43 /// it iterates on all of the items. |
43 /// it iterates on all of the items. |
44 |
44 |
45 template <typename Graph, typename ItemIt> |
45 template <typename Graph, typename ItemIt> |
46 inline int countItems(const Graph& _g) { |
46 inline int countItems(const Graph& g) { |
47 int num = 0; |
47 int num = 0; |
48 for (ItemIt it(_g); it != INVALID; ++it) { |
48 for (ItemIt it(g); it != INVALID; ++it) { |
49 ++num; |
49 ++num; |
50 } |
50 } |
51 return num; |
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 |
54 /// \brief Function to count the nodes in the graph. |
68 /// \brief Function to count the nodes in the graph. |
55 /// |
69 /// |
56 /// This function counts the nodes in the graph. |
70 /// This function counts the nodes in the graph. |
57 /// The complexity of the function is O(n) but for some |
71 /// The complexity of the function is O(n) but for some |
58 /// graph structure it is specialized to run in O(1). |
72 /// graph structure it is specialized to run in O(1). |
59 |
73 /// |
60 template <typename Graph> |
74 /// \todo refer how to specialize it |
61 inline int countNodes(const Graph& _g) { |
75 |
62 return countItems<Graph, typename Graph::NodeIt>(_g); |
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 |
65 /// \brief Function to count the edges in the graph. |
95 /// \brief Function to count the edges in the graph. |
66 /// |
96 /// |
67 /// This function counts the edges in the graph. |
97 /// This function counts the edges in the graph. |
68 /// The complexity of the function is O(e) but for some |
98 /// The complexity of the function is O(e) but for some |
69 /// graph structure it is specialized to run in O(1). |
99 /// graph structure it is specialized to run in O(1). |
70 template <typename Graph> |
100 |
71 inline int countEdges(const Graph& _g) { |
101 template <typename Graph> |
72 return countItems<Graph, typename Graph::EdgeIt>(_g); |
102 inline int countEdges(const Graph& g) { |
|
103 return _countEdges<Graph>(g); |
73 } |
104 } |
74 |
105 |
75 /// \brief Function to count the symmetric edges in the graph. |
106 /// \brief Function to count the symmetric edges in the graph. |
76 /// |
107 /// |
77 /// This function counts the symmetric edges in the graph. |
108 /// This function counts the symmetric edges in the graph. |
79 /// graph structure it is specialized to run in O(1). |
110 /// graph structure it is specialized to run in O(1). |
80 template <typename Graph> |
111 template <typename Graph> |
81 inline int countSymEdges(const Graph& _g) { |
112 inline int countSymEdges(const Graph& _g) { |
82 return countItems<Graph, typename Graph::SymEdgeIt>(_g); |
113 return countItems<Graph, typename Graph::SymEdgeIt>(_g); |
83 } |
114 } |
|
115 |
84 |
116 |
85 template <typename Graph, typename DegIt> |
117 template <typename Graph, typename DegIt> |
86 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { |
118 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { |
87 int num = 0; |
119 int num = 0; |
88 for (DegIt it(_g, _n); it != INVALID; ++it) { |
120 for (DegIt it(_g, _n); it != INVALID; ++it) { |