/* -*- mode: C++; indent-tabs-mode: nil; -*- * * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #include #include #include #include #include #include #include "graph_test.h" #include "test_tools.h" using namespace lemon; template void checkFindArcs() { TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); { Digraph digraph; for (int i = 0; i < 10; ++i) { digraph.addNode(); } RangeIdMap nodes(digraph); typename RangeIdMap::InverseMap invNodes(nodes); for (int i = 0; i < 100; ++i) { int src = rnd[invNodes.size()]; int trg = rnd[invNodes.size()]; digraph.addArc(invNodes[src], invNodes[trg]); } typename Digraph::template ArcMap found(digraph, false); RangeIdMap arcs(digraph); for (NodeIt src(digraph); src != INVALID; ++src) { for (NodeIt trg(digraph); trg != INVALID; ++trg) { for (ConArcIt con(digraph, src, trg); con != INVALID; ++con) { check(digraph.source(con) == src, "Wrong source."); check(digraph.target(con) == trg, "Wrong target."); check(found[con] == false, "The arc found already."); found[con] = true; } } } for (ArcIt it(digraph); it != INVALID; ++it) { check(found[it] == true, "The arc is not found."); } } { int num = 5; Digraph fg; std::vector nodes; for (int i = 0; i < num; ++i) { nodes.push_back(fg.addNode()); } for (int i = 0; i < num * num; ++i) { fg.addArc(nodes[i / num], nodes[i % num]); } check(countNodes(fg) == num, "Wrong node number."); check(countArcs(fg) == num*num, "Wrong arc number."); for (NodeIt src(fg); src != INVALID; ++src) { for (NodeIt trg(fg); trg != INVALID; ++trg) { ConArcIt con(fg, src, trg); check(con != INVALID, "There is no connecting arc."); check(fg.source(con) == src, "Wrong source."); check(fg.target(con) == trg, "Wrong target."); check(++con == INVALID, "There is more connecting arc."); } } ArcLookUp al1(fg); DynArcLookUp al2(fg); AllArcLookUp al3(fg); for (NodeIt src(fg); src != INVALID; ++src) { for (NodeIt trg(fg); trg != INVALID; ++trg) { Arc con1 = al1(src, trg); Arc con2 = al2(src, trg); Arc con3 = al3(src, trg); Arc con4 = findArc(fg, src, trg); check(con1 == con2 && con2 == con3 && con3 == con4, "Different results.") check(con1 != INVALID, "There is no connecting arc."); check(fg.source(con1) == src, "Wrong source."); check(fg.target(con1) == trg, "Wrong target."); check(al3(src, trg, con3) == INVALID, "There is more connecting arc."); check(findArc(fg, src, trg, con4) == INVALID, "There is more connecting arc."); } } } } template void checkFindEdges() { TEMPLATE_GRAPH_TYPEDEFS(Graph); Graph graph; for (int i = 0; i < 10; ++i) { graph.addNode(); } RangeIdMap nodes(graph); typename RangeIdMap::InverseMap invNodes(nodes); for (int i = 0; i < 100; ++i) { int src = rnd[invNodes.size()]; int trg = rnd[invNodes.size()]; graph.addEdge(invNodes[src], invNodes[trg]); } typename Graph::template EdgeMap found(graph, 0); RangeIdMap edges(graph); for (NodeIt src(graph); src != INVALID; ++src) { for (NodeIt trg(graph); trg != INVALID; ++trg) { for (ConEdgeIt con(graph, src, trg); con != INVALID; ++con) { check( (graph.u(con) == src && graph.v(con) == trg) || (graph.v(con) == src && graph.u(con) == trg), "Wrong end nodes."); ++found[con]; check(found[con] <= 2, "The edge found more than twice."); } } } for (EdgeIt it(graph); it != INVALID; ++it) { check( (graph.u(it) != graph.v(it) && found[it] == 2) || (graph.u(it) == graph.v(it) && found[it] == 1), "The edge is not found correctly."); } } template void checkDeg() { TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); const int nodeNum = 10; const int arcNum = 100; Digraph digraph; InDegMap inDeg(digraph); OutDegMap outDeg(digraph); std::vector nodes(nodeNum); for (int i = 0; i < nodeNum; ++i) { nodes[i] = digraph.addNode(); } std::vector arcs(arcNum); for (int i = 0; i < arcNum; ++i) { arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]); } for (int i = 0; i < nodeNum; ++i) { check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), "Wrong in degree map"); } for (int i = 0; i < nodeNum; ++i) { check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), "Wrong out degree map"); } } template void checkSnapDeg() { TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); Digraph g; Node n1=g.addNode(); Node n2=g.addNode(); InDegMap ind(g); g.addArc(n1,n2); typename Digraph::Snapshot snap(g); OutDegMap outd(g); check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); g.addArc(n1,n2); g.addArc(n2,n1); check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value."); check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value."); snap.restore(); check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); } int main() { // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp checkFindArcs(); checkFindArcs(); checkFindEdges(); checkFindEdges(); // Checking In/OutDegMap (and Snapshot feature) checkDeg(); checkDeg(); checkSnapDeg(); checkSnapDeg(); return 0; }