1.1 --- a/src/lemon/Makefile.am Wed Nov 10 19:59:14 2004 +0000
1.2 +++ b/src/lemon/Makefile.am Wed Nov 10 20:14:32 2004 +0000
1.3 @@ -29,6 +29,7 @@
1.4 concept_check.h \
1.5 map_defines.h \
1.6 map_bits.h \
1.7 + utility.h \
1.8 iterable_graph_extender.h \
1.9 idmappable_graph_extender.h \
1.10 extendable_graph_extender.h \
2.1 --- a/src/lemon/bfs.h Wed Nov 10 19:59:14 2004 +0000
2.2 +++ b/src/lemon/bfs.h Wed Nov 10 20:14:32 2004 +0000
2.3 @@ -25,6 +25,7 @@
2.4
2.5 #include <lemon/bin_heap.h>
2.6 #include <lemon/invalid.h>
2.7 +#include <lemon/graph_utils.h>
2.8
2.9 namespace lemon {
2.10
3.1 --- a/src/lemon/full_graph.h Wed Nov 10 19:59:14 2004 +0000
3.2 +++ b/src/lemon/full_graph.h Wed Nov 10 20:14:32 2004 +0000
3.3 @@ -19,19 +19,19 @@
3.4
3.5
3.6 #include <lemon/idmappable_graph_extender.h>
3.7 -
3.8 #include <lemon/iterable_graph_extender.h>
3.9 -
3.10 #include <lemon/alteration_observer_registry.h>
3.11 #include <lemon/default_map.h>
3.12
3.13 +#include <lemon/invalid.h>
3.14 +#include <lemon/utility.h>
3.15 +
3.16 +
3.17 ///\ingroup graphs
3.18 ///\file
3.19 ///\brief FullGraph and SymFullGraph classes.
3.20
3.21
3.22 -#include <lemon/invalid.h>
3.23 -
3.24 namespace lemon {
3.25
3.26 /// \addtogroup graphs
3.27 @@ -58,6 +58,9 @@
3.28 // FullGraphBase(const FullGraphBase &_g)
3.29 // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
3.30
3.31 + typedef True NodeNumTag;
3.32 + typedef True EdgeNumTag;
3.33 +
3.34 ///Number of nodes.
3.35 int nodeNum() const { return NodeNum; }
3.36 ///Number of edges.
3.37 @@ -206,21 +209,9 @@
3.38 FullGraph(int n) { construct(n); }
3.39 };
3.40
3.41 - template <>
3.42 - int countNodes<FullGraph>(const FullGraph& graph) {
3.43 - return graph.nodeNum();
3.44 - }
3.45 -
3.46 - template <>
3.47 - int countEdges<FullGraph>(const FullGraph& graph) {
3.48 - return graph.edgeNum();
3.49 - }
3.50 -
3.51 /// @}
3.52
3.53 } //namespace lemon
3.54
3.55
3.56 -
3.57 -
3.58 #endif //LEMON_FULL_GRAPH_H
4.1 --- a/src/lemon/graph_utils.h Wed Nov 10 19:59:14 2004 +0000
4.2 +++ b/src/lemon/graph_utils.h Wed Nov 10 20:14:32 2004 +0000
4.3 @@ -20,6 +20,7 @@
4.4 #include <iterator>
4.5
4.6 #include <lemon/invalid.h>
4.7 +#include <lemon/utility.h>
4.8
4.9 ///\ingroup gutils
4.10 ///\file
4.11 @@ -35,7 +36,6 @@
4.12 /// \addtogroup gutils
4.13 /// @{
4.14
4.15 - // counters in the graph
4.16 /// \brief Function to count the items in the graph.
4.17 ///
4.18 /// This function counts the items in the graph.
4.19 @@ -43,23 +43,53 @@
4.20 /// it iterates on all of the items.
4.21
4.22 template <typename Graph, typename ItemIt>
4.23 - inline int countItems(const Graph& _g) {
4.24 + inline int countItems(const Graph& g) {
4.25 int num = 0;
4.26 - for (ItemIt it(_g); it != INVALID; ++it) {
4.27 + for (ItemIt it(g); it != INVALID; ++it) {
4.28 ++num;
4.29 }
4.30 return num;
4.31 }
4.32
4.33 + // Node counting:
4.34 +
4.35 + template <typename Graph>
4.36 + inline
4.37 + typename enable_if<typename Graph::NodeNumTag, int>::type
4.38 + _countNodes(const Graph &g) {
4.39 + return g.nodeNum();
4.40 + }
4.41 +
4.42 + template <typename Graph>
4.43 + inline int _countNodes(Wrap<Graph> w) {
4.44 + return countItems<Graph, typename Graph::NodeIt>(w.value);
4.45 + }
4.46 +
4.47 /// \brief Function to count the nodes in the graph.
4.48 ///
4.49 /// This function counts the nodes in the graph.
4.50 /// The complexity of the function is O(n) but for some
4.51 /// graph structure it is specialized to run in O(1).
4.52 + ///
4.53 + /// \todo refer how to specialize it
4.54
4.55 template <typename Graph>
4.56 - inline int countNodes(const Graph& _g) {
4.57 - return countItems<Graph, typename Graph::NodeIt>(_g);
4.58 + inline int countNodes(const Graph& g) {
4.59 + return _countNodes<Graph>(g);
4.60 + }
4.61 +
4.62 + // Edge counting:
4.63 +
4.64 + template <typename Graph>
4.65 + inline
4.66 + typename enable_if<typename Graph::EdgeNumTag, int>::type
4.67 + _countEdges(const Graph &g) {
4.68 + return g.edgeNum();
4.69 + }
4.70 +
4.71 + template <typename Graph>
4.72 + inline int _countEdges(Wrap<Graph> w) {
4.73 + return countItems<Graph, typename Graph::EdgeIt>(w.value);
4.74 }
4.75
4.76 /// \brief Function to count the edges in the graph.
4.77 @@ -67,9 +97,10 @@
4.78 /// This function counts the edges in the graph.
4.79 /// The complexity of the function is O(e) but for some
4.80 /// graph structure it is specialized to run in O(1).
4.81 +
4.82 template <typename Graph>
4.83 - inline int countEdges(const Graph& _g) {
4.84 - return countItems<Graph, typename Graph::EdgeIt>(_g);
4.85 + inline int countEdges(const Graph& g) {
4.86 + return _countEdges<Graph>(g);
4.87 }
4.88
4.89 /// \brief Function to count the symmetric edges in the graph.
4.90 @@ -82,6 +113,7 @@
4.91 return countItems<Graph, typename Graph::SymEdgeIt>(_g);
4.92 }
4.93
4.94 +
4.95 template <typename Graph, typename DegIt>
4.96 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
4.97 int num = 0;
5.1 --- a/src/lemon/maps.h Wed Nov 10 19:59:14 2004 +0000
5.2 +++ b/src/lemon/maps.h Wed Nov 10 20:14:32 2004 +0000
5.3 @@ -104,9 +104,6 @@
5.4 V operator[](const K&) const { return v; }
5.5 void set(const K&, const V&) { }
5.6 };
5.7 - //to document later
5.8 - typedef Const<bool, true> True;
5.9 - typedef Const<bool, false> False;
5.10
5.11 /// \c std::map wrapper
5.12
6.1 --- a/src/lemon/preflow.h Wed Nov 10 19:59:14 2004 +0000
6.2 +++ b/src/lemon/preflow.h Wed Nov 10 20:14:32 2004 +0000
6.3 @@ -22,6 +22,7 @@
6.4
6.5 #include <lemon/invalid.h>
6.6 #include <lemon/maps.h>
6.7 +#include <lemon/graph_utils.h>
6.8
6.9 /// \file
6.10 /// \ingroup flowalgs
7.1 --- a/src/lemon/smart_graph.h Wed Nov 10 19:59:14 2004 +0000
7.2 +++ b/src/lemon/smart_graph.h Wed Nov 10 20:14:32 2004 +0000
7.3 @@ -27,17 +27,12 @@
7.4
7.5 #include <lemon/clearable_graph_extender.h>
7.6 #include <lemon/extendable_graph_extender.h>
7.7 -
7.8 #include <lemon/idmappable_graph_extender.h>
7.9 -
7.10 #include <lemon/iterable_graph_extender.h>
7.11 -
7.12 #include <lemon/alteration_observer_registry.h>
7.13 #include <lemon/default_map.h>
7.14
7.15 -
7.16 -#include <lemon/graph_utils.h>
7.17 -
7.18 +#include <lemon/utility.h>
7.19
7.20 namespace lemon {
7.21
7.22 @@ -84,6 +79,9 @@
7.23 SmartGraphBase() : nodes(), edges() { }
7.24 SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { }
7.25
7.26 + typedef True NodeNumTag;
7.27 + typedef True EdgeNumTag;
7.28 +
7.29 ///Number of nodes.
7.30 int nodeNum() const { return nodes.size(); }
7.31 ///Number of edges.
7.32 @@ -323,20 +321,8 @@
7.33 }
7.34 };
7.35
7.36 - template <>
7.37 - int countNodes<SmartGraph>(const SmartGraph& graph) {
7.38 - return graph.nodeNum();
7.39 - }
7.40 -
7.41 - template <>
7.42 - int countEdges<SmartGraph>(const SmartGraph& graph) {
7.43 - return graph.edgeNum();
7.44 - }
7.45 -
7.46 /// @}
7.47 } //namespace lemon
7.48
7.49
7.50 -
7.51 -
7.52 #endif //LEMON_SMART_GRAPH_H
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/src/lemon/utility.h Wed Nov 10 20:14:32 2004 +0000
8.3 @@ -0,0 +1,110 @@
8.4 +/* -*- C++ -*-
8.5 + *
8.6 + * src/lemon/utility.h - Part of LEMON, a generic C++ optimization library
8.7 + *
8.8 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
8.9 + * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
8.10 + * EGRES).
8.11 + *
8.12 + * Permission to use, modify and distribute this software is granted
8.13 + * provided that this copyright notice appears in all copies. For
8.14 + * precise terms see the accompanying LICENSE file.
8.15 + *
8.16 + * This software is provided "AS IS" with no warranty of any kind,
8.17 + * express or implied, and with no claim as to its suitability for any
8.18 + * purpose.
8.19 + *
8.20 + * This file contains a modified version of the enable_if library from BOOST.
8.21 + * See the appropriate copyright notice below.
8.22 + */
8.23 +
8.24 +// Boost enable_if library
8.25 +
8.26 +// Copyright 2003 © The Trustees of Indiana University.
8.27 +
8.28 +// Use, modification, and distribution is subject to the Boost Software
8.29 +// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
8.30 +// http://www.boost.org/LICENSE_1_0.txt)
8.31 +
8.32 +// Authors: Jaakko Järvi (jajarvi at osl.iu.edu)
8.33 +// Jeremiah Willcock (jewillco at osl.iu.edu)
8.34 +// Andrew Lumsdaine (lums at osl.iu.edu)
8.35 +
8.36 +
8.37 +#ifndef LEMON_UTILITY_H
8.38 +#define LEMON_UTILITY_H
8.39 +
8.40 +namespace lemon
8.41 +{
8.42 +
8.43 + /// Basic type for defining "tags". A "YES" condidion for enable_if.
8.44 +
8.45 + /// \todo This should go to a separate "basic_types.h" (or something)
8.46 + /// file.
8.47 + struct True {
8.48 + static const bool value = true;
8.49 + };
8.50 +
8.51 + /// Basic type for defining "tags". A "NO" condidion for enable_if.
8.52 + struct False {
8.53 + static const bool value = false;
8.54 + };
8.55 +
8.56 + template <typename T>
8.57 + struct Wrap {
8.58 + const T &value;
8.59 + Wrap(const T &t) : value(t) {}
8.60 + };
8.61 +
8.62 +
8.63 +
8.64 + /**************** enable_if from BOOST ****************/
8.65 +
8.66 + template <bool B, class T = void>
8.67 + struct enable_if_c {
8.68 + typedef T type;
8.69 + };
8.70 +
8.71 + template <class T>
8.72 + struct enable_if_c<false, T> {};
8.73 +
8.74 + template <class Cond, class T = void>
8.75 + struct enable_if : public enable_if_c<Cond::value, T> {};
8.76 +
8.77 + template <bool B, class T>
8.78 + struct lazy_enable_if_c {
8.79 + typedef typename T::type type;
8.80 + };
8.81 +
8.82 + template <class T>
8.83 + struct lazy_enable_if_c<false, T> {};
8.84 +
8.85 + template <class Cond, class T>
8.86 + struct lazy_enable_if : public lazy_enable_if_c<Cond::value, T> {};
8.87 +
8.88 +
8.89 + template <bool B, class T = void>
8.90 + struct disable_if_c {
8.91 + typedef T type;
8.92 + };
8.93 +
8.94 + template <class T>
8.95 + struct disable_if_c<true, T> {};
8.96 +
8.97 + template <class Cond, class T = void>
8.98 + struct disable_if : public disable_if_c<Cond::value, T> {};
8.99 +
8.100 + template <bool B, class T>
8.101 + struct lazy_disable_if_c {
8.102 + typedef typename T::type type;
8.103 + };
8.104 +
8.105 + template <class T>
8.106 + struct lazy_disable_if_c<true, T> {};
8.107 +
8.108 + template <class Cond, class T>
8.109 + struct lazy_disable_if : public lazy_disable_if_c<Cond::value, T> {};
8.110 +
8.111 +} // namespace lemon
8.112 +
8.113 +#endif
9.1 --- a/src/test/graph_utils_test.cc Wed Nov 10 19:59:14 2004 +0000
9.2 +++ b/src/test/graph_utils_test.cc Wed Nov 10 20:14:32 2004 +0000
9.3 @@ -3,6 +3,8 @@
9.4 #include <iostream>
9.5 #include <vector>
9.6
9.7 +#include <lemon/graph_utils.h>
9.8 +
9.9 #include <lemon/list_graph.h>
9.10 #include <lemon/smart_graph.h>
9.11 #include <lemon/full_graph.h>
9.12 @@ -22,6 +24,12 @@
9.13 { // checking smart graph
9.14 checkGraphCounters<SmartGraph>();
9.15 }
9.16 + {
9.17 + int num = 5;
9.18 + FullGraph fg(num);
9.19 + check(countNodes(fg) == num, "FullGraph: wrong node number.");
9.20 + check(countEdges(fg) == num*num, "FullGraph: wrong edge number.");
9.21 + }
9.22
9.23 std::cout << __FILE__ ": All tests passed.\n";
9.24
10.1 --- a/src/test/graph_utils_test.h Wed Nov 10 19:59:14 2004 +0000
10.2 +++ b/src/test/graph_utils_test.h Wed Nov 10 20:14:32 2004 +0000
10.3 @@ -30,11 +30,11 @@
10.4 Graph graph;
10.5 addPetersen(graph, num);
10.6 bidirGraph(graph);
10.7 - check(countNodes(graph) == 2*num, "Wrong node counter.");
10.8 - check(countEdges(graph) == 6*num, "Wrong edge counter.");
10.9 + check(countNodes(graph) == 2*num, "Wrong node number.");
10.10 + check(countEdges(graph) == 6*num, "Wrong edge number.");
10.11 for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
10.12 - check(countOutEdges(graph, it) == 3, "Wrong out degree counter.");
10.13 - check(countInEdges(graph, it) == 3, "Wrong in degree counter.");
10.14 + check(countOutEdges(graph, it) == 3, "Wrong out degree number.");
10.15 + check(countInEdges(graph, it) == 3, "Wrong in degree number.");
10.16 }
10.17 }
10.18