COIN-OR::LEMON - Graph Library

Changeset 977:48962802d168 in lemon-0.x


Ignore:
Timestamp:
11/10/04 21:14:32 (15 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1365
Message:
  • enable_if imported from BOOST
  • count{Nodes,Edges} implemented via graph tags
  • some #include bugs fixed
Location:
src
Files:
1 added
9 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/Makefile.am

    r962 r977  
    3030        map_defines.h                                                   \
    3131        map_bits.h                                                      \
     32        utility.h                                                       \
    3233        iterable_graph_extender.h                                       \
    3334        idmappable_graph_extender.h                                     \
  • src/lemon/bfs.h

    r946 r977  
    2626#include <lemon/bin_heap.h>
    2727#include <lemon/invalid.h>
     28#include <lemon/graph_utils.h>
    2829
    2930namespace lemon {
  • src/lemon/full_graph.h

    r959 r977  
    2020
    2121#include <lemon/idmappable_graph_extender.h>
    22 
    2322#include <lemon/iterable_graph_extender.h>
    24 
    2523#include <lemon/alteration_observer_registry.h>
    2624#include <lemon/default_map.h>
     25
     26#include <lemon/invalid.h>
     27#include <lemon/utility.h>
     28
    2729
    2830///\ingroup graphs
     
    3032///\brief FullGraph and SymFullGraph classes.
    3133
    32 
    33 #include <lemon/invalid.h>
    3434
    3535namespace lemon {
     
    5959    //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
    6060   
     61    typedef True NodeNumTag;
     62    typedef True EdgeNumTag;
     63
    6164    ///Number of nodes.
    6265    int nodeNum() const { return NodeNum; }
     
    207210  };
    208211
    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 
    219212  /// @} 
    220213
     
    222215
    223216
    224 
    225 
    226217#endif //LEMON_FULL_GRAPH_H
  • src/lemon/graph_utils.h

    r967 r977  
    2121
    2222#include <lemon/invalid.h>
     23#include <lemon/utility.h>
    2324
    2425///\ingroup gutils
     
    3637/// @{
    3738
    38   // counters in the graph
    3939  /// \brief Function to count the items in the graph.
    4040  ///
     
    4444
    4545  template <typename Graph, typename ItemIt>
    46   inline int countItems(const Graph& _g) {
     46  inline int countItems(const Graph& g) {
    4747    int num = 0;
    48     for (ItemIt it(_g); it != INVALID; ++it) {
     48    for (ItemIt it(g); it != INVALID; ++it) {
    4949      ++num;
    5050    }
    5151    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);
    5266  }
    5367
     
    5771  /// The complexity of the function is O(n) but for some
    5872  /// 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);
    6393  }
    6494
     
    6898  /// The complexity of the function is O(e) but for some
    6999  /// 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);
    73104  }
    74105
     
    82113    return countItems<Graph, typename Graph::SymEdgeIt>(_g);
    83114  }
     115
    84116
    85117  template <typename Graph, typename DegIt>
  • src/lemon/maps.h

    r959 r977  
    105105    void set(const K&, const V&) { }
    106106  };
    107   //to document later
    108   typedef Const<bool, true> True;
    109   typedef Const<bool, false> False;
    110107
    111108  /// \c std::map wrapper
  • src/lemon/preflow.h

    r946 r977  
    2323#include <lemon/invalid.h>
    2424#include <lemon/maps.h>
     25#include <lemon/graph_utils.h>
    2526
    2627/// \file
  • src/lemon/smart_graph.h

    r974 r977  
    2828#include <lemon/clearable_graph_extender.h>
    2929#include <lemon/extendable_graph_extender.h>
    30 
    3130#include <lemon/idmappable_graph_extender.h>
    32 
    3331#include <lemon/iterable_graph_extender.h>
    34 
    3532#include <lemon/alteration_observer_registry.h>
    3633#include <lemon/default_map.h>
    3734
    38 
    39 #include <lemon/graph_utils.h>
    40 
     35#include <lemon/utility.h>
    4136
    4237namespace lemon {
     
    8580    SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { }
    8681   
     82    typedef True NodeNumTag;
     83    typedef True EdgeNumTag;
     84
    8785    ///Number of nodes.
    8886    int nodeNum() const { return nodes.size(); }
     
    324322  };
    325323 
    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 
    336324  /// @} 
    337325} //namespace lemon
    338326
    339327
    340 
    341 
    342328#endif //LEMON_SMART_GRAPH_H
  • src/test/graph_utils_test.cc

    r946 r977  
    33#include <iostream>
    44#include <vector>
     5
     6#include <lemon/graph_utils.h>
    57
    68#include <lemon/list_graph.h>
     
    2325    checkGraphCounters<SmartGraph>();
    2426  }
     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  }
    2533
    2634  std::cout << __FILE__ ": All tests passed.\n";
  • src/test/graph_utils_test.h

    r946 r977  
    3131    addPetersen(graph, num);
    3232    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.");   
    3535    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.");
    3838    }
    3939  }
Note: See TracChangeset for help on using the changeset viewer.