COIN-OR::LEMON - Graph Library

Changeset 821:f4b5c2d5449d in lemon


Ignore:
Timestamp:
08/25/09 13:58:43 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Small improvements + add tests for StaticDigraph? (#68)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/static_graph.h

    r820 r821  
    3333
    3434    StaticDigraphBase()
    35       : node_num(-1), arc_num(0),
     35      : built(false), node_num(0), arc_num(0),
    3636        node_first_out(NULL), node_first_in(NULL),
    3737        arc_source(NULL), arc_target(NULL),
     
    3939   
    4040    ~StaticDigraphBase() {
    41       if (node_num != -1) {
     41      if (built) {
    4242        delete[] node_first_out;
    4343        delete[] node_first_in;
     
    129129    typedef True BuildTag;
    130130   
    131     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
    132     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
    133 
    134       if (node_num != -1) {
     131    void clear() {
     132      if (built) {
    135133        delete[] node_first_out;
    136134        delete[] node_first_in;
     
    140138        delete[] arc_next_in;
    141139      }
    142 
     140      built = false;
     141      node_num = 0;
     142      arc_num = 0;
     143    }
     144   
     145    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
     146    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
    143147      typedef typename Digraph::Node GNode;
    144148      typedef typename Digraph::Arc GArc;
     149
     150      built = true;
    145151
    146152      node_num = countNodes(digraph);
     
    206212    }
    207213
    208   private:
     214  protected:
     215    bool built;
    209216    int node_num;
    210217    int arc_num;
     
    224231
    225232    typedef ExtendedStaticDigraphBase Parent;
     233 
     234  public:
     235 
     236    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
     237    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
     238      if (built) Parent::clear();
     239      Parent::build(digraph, nodeRef, arcRef);
     240    }
     241 
    226242
    227243  protected:
     
    262278    };
    263279
     280    Node baseNode(const OutArcIt &arc) const {
     281      return Parent::source(static_cast<const Arc&>(arc));
     282    }
     283
     284    Node runningNode(const OutArcIt &arc) const {
     285      return Parent::target(static_cast<const Arc&>(arc));
     286    }
     287
     288    Node baseNode(const InArcIt &arc) const {
     289      return Parent::target(static_cast<const Arc&>(arc));
     290    }
     291
     292    Node runningNode(const InArcIt &arc) const {
     293      return Parent::source(static_cast<const Arc&>(arc));
     294    }
     295
    264296  };
    265297
  • test/digraph_test.cc

    r463 r821  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
     22#include <lemon/static_graph.h>
    2223#include <lemon/full_graph.h>
    2324
     
    318319    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    319320  }
     321  { // Checking StaticDigraph
     322    checkConcept<Digraph, StaticDigraph>();
     323    checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
     324  }
    320325  { // Checking FullDigraph
    321326    checkConcept<Digraph, FullDigraph>();
     
    371376  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
    372377  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
     378}
     379
     380void checkStaticDigraph() {
     381  SmartDigraph g;
     382  SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
     383  SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
     384 
     385  StaticDigraph G;
     386 
     387  checkGraphNodeList(G, 0);
     388  checkGraphArcList(G, 0);
     389
     390  G.build(g, nref, aref);
     391
     392  checkGraphNodeList(G, 0);
     393  checkGraphArcList(G, 0);
     394
     395  SmartDigraph::Node
     396    n1 = g.addNode(),
     397    n2 = g.addNode(),
     398    n3 = g.addNode();
     399
     400  G.build(g, nref, aref);
     401
     402  checkGraphNodeList(G, 3);
     403  checkGraphArcList(G, 0);
     404
     405  SmartDigraph::Arc a1 = g.addArc(n1, n2);
     406
     407  G.build(g, nref, aref);
     408
     409  check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],
     410        "Wrong arc or wrong references");
     411  checkGraphNodeList(G, 3);
     412  checkGraphArcList(G, 1);
     413
     414  checkGraphOutArcList(G, nref[n1], 1);
     415  checkGraphOutArcList(G, nref[n2], 0);
     416  checkGraphOutArcList(G, nref[n3], 0);
     417
     418  checkGraphInArcList(G, nref[n1], 0);
     419  checkGraphInArcList(G, nref[n2], 1);
     420  checkGraphInArcList(G, nref[n3], 0);
     421
     422  checkGraphConArcList(G, 1);
     423
     424  SmartDigraph::Arc
     425    a2 = g.addArc(n2, n1),
     426    a3 = g.addArc(n2, n3),
     427    a4 = g.addArc(n2, n3);
     428
     429  digraphCopy(g, G).nodeRef(nref).run();
     430
     431  checkGraphNodeList(G, 3);
     432  checkGraphArcList(G, 4);
     433
     434  checkGraphOutArcList(G, nref[n1], 1);
     435  checkGraphOutArcList(G, nref[n2], 3);
     436  checkGraphOutArcList(G, nref[n3], 0);
     437
     438  checkGraphInArcList(G, nref[n1], 1);
     439  checkGraphInArcList(G, nref[n2], 1);
     440  checkGraphInArcList(G, nref[n3], 2);
     441
     442  checkGraphConArcList(G, 4);
     443
     444  checkNodeIds(G);
     445  checkArcIds(G);
     446  checkGraphNodeMap(G);
     447  checkGraphArcMap(G);
    373448}
    374449
     
    420495    checkDigraphValidity<SmartDigraph>();
    421496  }
     497  { // Checking StaticDigraph
     498    checkStaticDigraph();
     499  }
    422500  { // Checking FullDigraph
    423501    checkFullDigraph(8);
Note: See TracChangeset for help on using the changeset viewer.