kpeter@745: /* -*- mode: C++; indent-tabs-mode: nil; -*- kpeter@745: * kpeter@745: * This file is a part of LEMON, a generic C++ optimization library. kpeter@745: * alpar@956: * Copyright (C) 2003-2010 kpeter@745: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport kpeter@745: * (Egervary Research Group on Combinatorial Optimization, EGRES). kpeter@745: * kpeter@745: * Permission to use, modify and distribute this software is granted kpeter@745: * provided that this copyright notice appears in all copies. For kpeter@745: * precise terms see the accompanying LICENSE file. kpeter@745: * kpeter@745: * This software is provided "AS IS" with no warranty of any kind, kpeter@745: * express or implied, and with no claim as to its suitability for any kpeter@745: * purpose. kpeter@745: * kpeter@745: */ kpeter@745: kpeter@745: #include kpeter@745: #include kpeter@745: #include kpeter@745: #include kpeter@745: #include kpeter@745: #include kpeter@745: kpeter@745: #include "graph_test.h" kpeter@745: #include "test_tools.h" kpeter@745: kpeter@745: using namespace lemon; kpeter@745: kpeter@745: char test_lgf[] = kpeter@745: "@nodes\n" kpeter@745: "label\n" kpeter@745: "0\n" kpeter@745: "1\n" kpeter@745: "2\n" kpeter@745: "3\n" kpeter@745: "4\n" kpeter@745: "@arcs\n" kpeter@745: " length\n" kpeter@745: "0 1 3\n" kpeter@745: "1 2 -3\n" kpeter@745: "1 2 -5\n" kpeter@745: "1 3 -2\n" kpeter@745: "0 2 -1\n" kpeter@745: "1 2 -4\n" kpeter@745: "0 3 2\n" kpeter@745: "4 2 -5\n" kpeter@745: "2 3 1\n" kpeter@745: "@attributes\n" kpeter@745: "source 0\n" kpeter@745: "target 3\n"; kpeter@745: kpeter@745: kpeter@745: void checkBellmanFordCompile() kpeter@745: { kpeter@745: typedef int Value; kpeter@745: typedef concepts::Digraph Digraph; kpeter@745: typedef concepts::ReadMap LengthMap; kpeter@745: typedef BellmanFord BF; kpeter@745: typedef Digraph::Node Node; kpeter@745: typedef Digraph::Arc Arc; kpeter@745: kpeter@745: Digraph gr; kpeter@745: Node s, t, n; kpeter@745: Arc e; kpeter@745: Value l; alpar@837: int k=3; kpeter@745: bool b; kpeter@745: BF::DistMap d(gr); kpeter@745: BF::PredMap p(gr); kpeter@745: LengthMap length; kpeter@745: concepts::Path pp; kpeter@745: kpeter@745: { kpeter@745: BF bf_test(gr,length); kpeter@745: const BF& const_bf_test = bf_test; kpeter@745: kpeter@745: bf_test.run(s); kpeter@745: bf_test.run(s,k); kpeter@745: kpeter@745: bf_test.init(); kpeter@745: bf_test.addSource(s); kpeter@745: bf_test.addSource(s, 1); kpeter@745: b = bf_test.processNextRound(); kpeter@745: b = bf_test.processNextWeakRound(); kpeter@745: kpeter@745: bf_test.start(); kpeter@745: bf_test.checkedStart(); kpeter@745: bf_test.limitedStart(k); kpeter@745: kpeter@745: l = const_bf_test.dist(t); kpeter@745: e = const_bf_test.predArc(t); kpeter@745: s = const_bf_test.predNode(t); kpeter@745: b = const_bf_test.reached(t); kpeter@745: d = const_bf_test.distMap(); kpeter@745: p = const_bf_test.predMap(); kpeter@745: pp = const_bf_test.path(t); kpeter@828: pp = const_bf_test.negativeCycle(); alpar@956: kpeter@745: for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {} kpeter@745: } kpeter@745: { kpeter@745: BF::SetPredMap > kpeter@745: ::SetDistMap > kpeter@745: ::SetOperationTraits > kpeter@917: ::SetOperationTraits > kpeter@745: ::Create bf_test(gr,length); kpeter@745: kpeter@745: LengthMap length_map; kpeter@745: concepts::ReadWriteMap pred_map; kpeter@745: concepts::ReadWriteMap dist_map; alpar@956: kpeter@745: bf_test kpeter@745: .lengthMap(length_map) kpeter@745: .predMap(pred_map) kpeter@745: .distMap(dist_map); kpeter@745: kpeter@745: bf_test.run(s); kpeter@745: bf_test.run(s,k); kpeter@745: kpeter@745: bf_test.init(); kpeter@745: bf_test.addSource(s); kpeter@745: bf_test.addSource(s, 1); kpeter@745: b = bf_test.processNextRound(); kpeter@745: b = bf_test.processNextWeakRound(); kpeter@745: kpeter@745: bf_test.start(); kpeter@745: bf_test.checkedStart(); kpeter@745: bf_test.limitedStart(k); kpeter@745: kpeter@745: l = bf_test.dist(t); kpeter@745: e = bf_test.predArc(t); kpeter@745: s = bf_test.predNode(t); kpeter@745: b = bf_test.reached(t); kpeter@745: pp = bf_test.path(t); kpeter@828: pp = bf_test.negativeCycle(); kpeter@745: } kpeter@745: } kpeter@745: kpeter@745: void checkBellmanFordFunctionCompile() kpeter@745: { kpeter@745: typedef int Value; kpeter@745: typedef concepts::Digraph Digraph; kpeter@745: typedef Digraph::Arc Arc; kpeter@745: typedef Digraph::Node Node; kpeter@745: typedef concepts::ReadMap LengthMap; kpeter@745: kpeter@745: Digraph g; kpeter@745: bool b; kpeter@745: bellmanFord(g,LengthMap()).run(Node()); kpeter@745: b = bellmanFord(g,LengthMap()).run(Node(),Node()); kpeter@745: bellmanFord(g,LengthMap()) kpeter@745: .predMap(concepts::ReadWriteMap()) kpeter@745: .distMap(concepts::ReadWriteMap()) kpeter@745: .run(Node()); kpeter@745: b=bellmanFord(g,LengthMap()) kpeter@745: .predMap(concepts::ReadWriteMap()) kpeter@745: .distMap(concepts::ReadWriteMap()) kpeter@745: .path(concepts::Path()) kpeter@745: .dist(Value()) kpeter@745: .run(Node(),Node()); kpeter@745: } kpeter@745: kpeter@745: kpeter@745: template kpeter@745: void checkBellmanFord() { kpeter@745: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); kpeter@745: typedef typename Digraph::template ArcMap LengthMap; kpeter@745: kpeter@745: Digraph gr; kpeter@745: Node s, t; kpeter@745: LengthMap length(gr); kpeter@745: kpeter@745: std::istringstream input(test_lgf); kpeter@745: digraphReader(gr, input). kpeter@745: arcMap("length", length). kpeter@745: node("source", s). kpeter@745: node("target", t). kpeter@745: run(); kpeter@745: kpeter@745: BellmanFord kpeter@745: bf(gr, length); kpeter@745: bf.run(s); kpeter@745: Path p = bf.path(t); kpeter@745: kpeter@745: check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path."); kpeter@745: check(p.length() == 3, "path() found a wrong path."); kpeter@745: check(checkPath(gr, p), "path() found a wrong path."); kpeter@745: check(pathSource(gr, p) == s, "path() found a wrong path."); kpeter@745: check(pathTarget(gr, p) == t, "path() found a wrong path."); alpar@956: kpeter@745: ListPath path; kpeter@745: Value dist; kpeter@745: bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t); kpeter@745: kpeter@745: check(reached && dist == -1, "Bellman-Ford found a wrong path."); kpeter@745: check(path.length() == 3, "path() found a wrong path."); kpeter@745: check(checkPath(gr, path), "path() found a wrong path."); kpeter@745: check(pathSource(gr, path) == s, "path() found a wrong path."); kpeter@745: check(pathTarget(gr, path) == t, "path() found a wrong path."); kpeter@745: kpeter@745: for(ArcIt e(gr); e!=INVALID; ++e) { kpeter@745: Node u=gr.source(e); kpeter@745: Node v=gr.target(e); kpeter@745: check(!bf.reached(u) || (bf.dist(v) - bf.dist(u) <= length[e]), kpeter@745: "Wrong output. dist(target)-dist(source)-arc_length=" << kpeter@745: bf.dist(v) - bf.dist(u) - length[e]); kpeter@745: } kpeter@745: kpeter@745: for(NodeIt v(gr); v!=INVALID; ++v) { kpeter@745: if (bf.reached(v)) { kpeter@745: check(v==s || bf.predArc(v)!=INVALID, "Wrong tree."); kpeter@745: if (bf.predArc(v)!=INVALID ) { kpeter@745: Arc e=bf.predArc(v); kpeter@745: Node u=gr.source(e); kpeter@745: check(u==bf.predNode(v),"Wrong tree."); kpeter@745: check(bf.dist(v) - bf.dist(u) == length[e], kpeter@745: "Wrong distance! Difference: " << kpeter@745: bf.dist(v) - bf.dist(u) - length[e]); kpeter@745: } kpeter@745: } kpeter@745: } kpeter@745: } kpeter@745: kpeter@746: void checkBellmanFordNegativeCycle() { kpeter@746: DIGRAPH_TYPEDEFS(SmartDigraph); kpeter@746: kpeter@746: SmartDigraph gr; kpeter@746: IntArcMap length(gr); alpar@956: kpeter@746: Node n1 = gr.addNode(); kpeter@746: Node n2 = gr.addNode(); kpeter@746: Node n3 = gr.addNode(); kpeter@746: Node n4 = gr.addNode(); alpar@956: kpeter@746: Arc a1 = gr.addArc(n1, n2); kpeter@746: Arc a2 = gr.addArc(n2, n2); alpar@956: kpeter@746: length[a1] = 2; kpeter@746: length[a2] = -1; alpar@956: kpeter@746: { kpeter@746: BellmanFord bf(gr, length); kpeter@746: bf.run(n1); kpeter@746: StaticPath p = bf.negativeCycle(); kpeter@746: check(p.length() == 1 && p.front() == p.back() && p.front() == a2, kpeter@746: "Wrong negative cycle."); kpeter@746: } alpar@956: kpeter@746: length[a2] = 0; alpar@956: kpeter@746: { kpeter@746: BellmanFord bf(gr, length); kpeter@746: bf.run(n1); kpeter@746: check(bf.negativeCycle().empty(), kpeter@746: "Negative cycle should not be found."); kpeter@746: } alpar@956: kpeter@746: length[gr.addArc(n1, n3)] = 5; kpeter@746: length[gr.addArc(n4, n3)] = 1; kpeter@746: length[gr.addArc(n2, n4)] = 2; kpeter@746: length[gr.addArc(n3, n2)] = -4; alpar@956: kpeter@746: { kpeter@746: BellmanFord bf(gr, length); kpeter@746: bf.init(); kpeter@746: bf.addSource(n1); kpeter@746: for (int i = 0; i < 4; ++i) { kpeter@746: check(bf.negativeCycle().empty(), kpeter@746: "Negative cycle should not be found."); kpeter@746: bf.processNextRound(); kpeter@746: } kpeter@746: StaticPath p = bf.negativeCycle(); kpeter@746: check(p.length() == 3, "Wrong negative cycle."); kpeter@746: check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1, kpeter@746: "Wrong negative cycle."); kpeter@746: } kpeter@746: } kpeter@746: kpeter@745: int main() { kpeter@745: checkBellmanFord(); kpeter@745: checkBellmanFord(); kpeter@746: checkBellmanFordNegativeCycle(); kpeter@745: return 0; kpeter@745: }