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