UndirGraphs: invalid edge bug
authorklao
Wed, 05 Jan 2005 14:34:00 +0000
changeset 105390f8696360b2
parent 1052 172ce6c3ac6e
child 1054 6a62b1b4cf23
UndirGraphs: invalid edge bug
src/lemon/graph_utils.h
src/lemon/undir_graph_extender.h
src/test/undir_graph_test.cc
     1.1 --- a/src/lemon/graph_utils.h	Wed Jan 05 12:26:59 2005 +0000
     1.2 +++ b/src/lemon/graph_utils.h	Wed Jan 05 14:34:00 2005 +0000
     1.3 @@ -103,17 +103,33 @@
     1.4      return _countEdges<Graph>(g);
     1.5    }
     1.6  
     1.7 -  /// \brief Function to count the symmetric edges in the graph.
     1.8 +  // Undirected edge counting:
     1.9 +
    1.10 +  template <typename Graph>
    1.11 +  inline
    1.12 +  typename enable_if<typename Graph::EdgeNumTag, int>::type
    1.13 +  _countUndirEdges(const Graph &g) {
    1.14 +    return g.undirEdgeNum();
    1.15 +  }
    1.16 +
    1.17 +  template <typename Graph>
    1.18 +  inline int _countUndirEdges(Wrap<Graph> w) {
    1.19 +    return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
    1.20 +  }
    1.21 +
    1.22 +  /// \brief Function to count the edges in the graph.
    1.23    ///
    1.24 -  /// This function counts the symmetric edges in the graph.
    1.25 +  /// This function counts the edges in the graph.
    1.26    /// The complexity of the function is O(e) but for some
    1.27    /// graph structure it is specialized to run in O(1).
    1.28 +
    1.29    template <typename Graph>
    1.30 -  inline int countSymEdges(const Graph& _g) {
    1.31 -    return countItems<Graph, typename Graph::SymEdgeIt>(_g);
    1.32 +  inline int countUndirEdges(const Graph& g) {
    1.33 +    return _countUndirEdges<Graph>(g);
    1.34    }
    1.35  
    1.36  
    1.37 +
    1.38    template <typename Graph, typename DegIt>
    1.39    inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
    1.40      int num = 0;
     2.1 --- a/src/lemon/undir_graph_extender.h	Wed Jan 05 12:26:59 2005 +0000
     2.2 +++ b/src/lemon/undir_graph_extender.h	Wed Jan 05 14:34:00 2005 +0000
     2.3 @@ -48,7 +48,7 @@
     2.4        Edge(const UndirEdge &ue, bool _forward) :
     2.5  	UndirEdge(ue), forward(_forward) {}
     2.6        /// Invalid edge constructor
     2.7 -      Edge(Invalid i) : UndirEdge(i), forward(false) {}
     2.8 +      Edge(Invalid i) : UndirEdge(i), forward(true) {}
     2.9  
    2.10        bool operator==(const Edge &that) const {
    2.11  	return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
     3.1 --- a/src/test/undir_graph_test.cc	Wed Jan 05 12:26:59 2005 +0000
     3.2 +++ b/src/test/undir_graph_test.cc	Wed Jan 05 14:34:00 2005 +0000
     3.3 @@ -6,14 +6,15 @@
     3.4  #include <lemon/smart_graph.h>
     3.5  #include <lemon/full_graph.h>
     3.6  
     3.7 +#include <lemon/graph_utils.h>
     3.8 +
     3.9  #include "test_tools.h"
    3.10  
    3.11  
    3.12  using namespace lemon;
    3.13  using namespace lemon::concept;
    3.14  
    3.15 -
    3.16 -int main() {
    3.17 +void check_concepts() {
    3.18    typedef UndirGraphExtender<ListGraphBase> UndirListGraphBase;
    3.19  
    3.20    typedef IterableUndirGraphExtender<
    3.21 @@ -40,6 +41,66 @@
    3.22    checkConcept<ExtendableUndirGraph, UndirSmartGraph>();
    3.23  
    3.24    checkConcept<UndirGraph, UndirGraph>();
    3.25 +}
    3.26 +
    3.27 +typedef UndirListGraph Graph;
    3.28 +typedef Graph::Node Node;
    3.29 +typedef Graph::UndirEdge UEdge;
    3.30 +typedef Graph::Edge Edge;
    3.31 +typedef Graph::NodeIt NodeIt;
    3.32 +typedef Graph::UndirEdgeIt UEdgeIt;
    3.33 +typedef Graph::EdgeIt EdgeIt;
    3.34 +
    3.35 +void check_item_counts(Graph &g, int n, int e) {
    3.36 +  check(countNodes(g)==n, "Wrong node number.");
    3.37 +  check(countEdges(g)==2*e, "Wrong edge number.");
    3.38 +}
    3.39 +
    3.40 +void print_items(Graph &g) {
    3.41 +  cout << "Nodes" << endl;
    3.42 +  int i=0;
    3.43 +  for(NodeIt it(g); it!=INVALID; ++it, ++i) {
    3.44 +    cout << "  " << i << ": " << g.id(it) << endl;
    3.45 +  }
    3.46 +
    3.47 +  cout << "UndirEdge" << endl;
    3.48 +  i=0;
    3.49 +  for(UEdgeIt it(g); it!=INVALID; ++it, ++i) {
    3.50 +    cout << "  " << i << ": " << g.id(it) 
    3.51 +	 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) 
    3.52 +	 << ")" << endl;
    3.53 +  }
    3.54 +
    3.55 +  cout << "Edge" << endl;
    3.56 +  i=0;
    3.57 +  for(EdgeIt it(g); it!=INVALID; ++it, ++i) {
    3.58 +    cout << "  " << i << ": " << g.id(it)
    3.59 +	 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) 
    3.60 +	 << ")" << endl;
    3.61 +  }
    3.62 +
    3.63 +}
    3.64 +
    3.65 +int main() {
    3.66 +  check_concepts();
    3.67 +
    3.68 +
    3.69 +  Graph g;
    3.70 +
    3.71 +  check_item_counts(g,0,0);
    3.72 +
    3.73 +  Node
    3.74 +    n1 = g.addNode(),
    3.75 +    n2 = g.addNode(),
    3.76 +    n3 = g.addNode();
    3.77 +
    3.78 +  UEdge
    3.79 +    e1 = g.addEdge(n1, n2),
    3.80 +    e2 = g.addEdge(n2, n3);
    3.81 +
    3.82 +  // print_items(g);
    3.83 +
    3.84 +  check_item_counts(g,3,2);
    3.85  
    3.86    return 0;
    3.87  }