COIN-OR::LEMON - Graph Library

Changeset 1053:90f8696360b2 in lemon-0.x


Ignore:
Timestamp:
01/05/05 15:34:00 (15 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1447
Message:

UndirGraphs?: invalid edge bug

Location:
src
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/graph_utils.h

    r986 r1053  
    104104  }
    105105
    106   /// \brief Function to count the symmetric edges in the graph.
    107   ///
    108   /// This function counts the symmetric edges in the graph.
     106  // Undirected edge counting:
     107
     108  template <typename Graph>
     109  inline
     110  typename enable_if<typename Graph::EdgeNumTag, int>::type
     111  _countUndirEdges(const Graph &g) {
     112    return g.undirEdgeNum();
     113  }
     114
     115  template <typename Graph>
     116  inline int _countUndirEdges(Wrap<Graph> w) {
     117    return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
     118  }
     119
     120  /// \brief Function to count the edges in the graph.
     121  ///
     122  /// This function counts the edges in the graph.
    109123  /// The complexity of the function is O(e) but for some
    110124  /// graph structure it is specialized to run in O(1).
    111   template <typename Graph>
    112   inline int countSymEdges(const Graph& _g) {
    113     return countItems<Graph, typename Graph::SymEdgeIt>(_g);
    114   }
     125
     126  template <typename Graph>
     127  inline int countUndirEdges(const Graph& g) {
     128    return _countUndirEdges<Graph>(g);
     129  }
     130
    115131
    116132
  • src/lemon/undir_graph_extender.h

    r1030 r1053  
    4949        UndirEdge(ue), forward(_forward) {}
    5050      /// Invalid edge constructor
    51       Edge(Invalid i) : UndirEdge(i), forward(false) {}
     51      Edge(Invalid i) : UndirEdge(i), forward(true) {}
    5252
    5353      bool operator==(const Edge &that) const {
  • src/test/undir_graph_test.cc

    r1034 r1053  
    77#include <lemon/full_graph.h>
    88
     9#include <lemon/graph_utils.h>
     10
    911#include "test_tools.h"
    1012
     
    1315using namespace lemon::concept;
    1416
    15 
    16 int main() {
     17void check_concepts() {
    1718  typedef UndirGraphExtender<ListGraphBase> UndirListGraphBase;
    1819
     
    4142
    4243  checkConcept<UndirGraph, UndirGraph>();
     44}
     45
     46typedef UndirListGraph Graph;
     47typedef Graph::Node Node;
     48typedef Graph::UndirEdge UEdge;
     49typedef Graph::Edge Edge;
     50typedef Graph::NodeIt NodeIt;
     51typedef Graph::UndirEdgeIt UEdgeIt;
     52typedef Graph::EdgeIt EdgeIt;
     53
     54void check_item_counts(Graph &g, int n, int e) {
     55  check(countNodes(g)==n, "Wrong node number.");
     56  check(countEdges(g)==2*e, "Wrong edge number.");
     57}
     58
     59void print_items(Graph &g) {
     60  cout << "Nodes" << endl;
     61  int i=0;
     62  for(NodeIt it(g); it!=INVALID; ++it, ++i) {
     63    cout << "  " << i << ": " << g.id(it) << endl;
     64  }
     65
     66  cout << "UndirEdge" << endl;
     67  i=0;
     68  for(UEdgeIt it(g); it!=INVALID; ++it, ++i) {
     69    cout << "  " << i << ": " << g.id(it)
     70         << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
     71         << ")" << endl;
     72  }
     73
     74  cout << "Edge" << endl;
     75  i=0;
     76  for(EdgeIt it(g); it!=INVALID; ++it, ++i) {
     77    cout << "  " << i << ": " << g.id(it)
     78         << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
     79         << ")" << endl;
     80  }
     81
     82}
     83
     84int main() {
     85  check_concepts();
     86
     87
     88  Graph g;
     89
     90  check_item_counts(g,0,0);
     91
     92  Node
     93    n1 = g.addNode(),
     94    n2 = g.addNode(),
     95    n3 = g.addNode();
     96
     97  UEdge
     98    e1 = g.addEdge(n1, n2),
     99    e2 = g.addEdge(n2, n3);
     100
     101  // print_items(g);
     102
     103  check_item_counts(g,3,2);
    43104
    44105  return 0;
Note: See TracChangeset for help on using the changeset viewer.