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