Index: test/CMakeLists.txt =================================================================== --- test/CMakeLists.txt (revision 993) +++ test/CMakeLists.txt (revision 1088) @@ -15,5 +15,7 @@ adaptors_test arc_look_up_test + bellman_ford_test bfs_test + bpgraph_test circulation_test connectivity_test @@ -26,4 +28,5 @@ error_test euler_test + fractional_matching_test gomory_hu_test graph_copy_test @@ -33,15 +36,22 @@ heap_test kruskal_test + lgf_reader_writer_test lgf_test maps_test matching_test + max_cardinality_search_test + max_clique_test + max_flow_test min_cost_arborescence_test min_cost_flow_test + min_mean_cycle_test + nagamochi_ibaraki_test path_test - preflow_test + planarity_test radix_sort_test random_test suurballe_test time_measure_test + tsp_test unionfind_test ) @@ -60,8 +70,11 @@ ENDIF() IF(LEMON_HAVE_CPLEX) - SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES}) + SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${ILOG_LIBRARIES}) ENDIF() IF(LEMON_HAVE_CLP) SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES}) + ENDIF() + IF(LEMON_HAVE_SOPLEX) + SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${SOPLEX_LIBRARIES}) ENDIF() @@ -84,5 +97,5 @@ GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD - COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH} + COMMAND ${CMAKE_COMMAND} -E copy ${ILOG_CPLEX_DLL} ${TARGET_PATH} ) ENDIF() @@ -102,5 +115,5 @@ ENDIF() IF(LEMON_HAVE_CPLEX) - SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES}) + SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${ILOG_LIBRARIES}) ENDIF() IF(LEMON_HAVE_CBC) @@ -126,5 +139,5 @@ GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD - COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH} + COMMAND ${CMAKE_COMMAND} -E copy ${ILOG_CPLEX_DLL} ${TARGET_PATH} ) ENDIF() Index: test/Makefile.am =================================================================== --- test/Makefile.am (revision 959) +++ (revision ) @@ -1,89 +1,0 @@ -EXTRA_DIST += \ - test/CMakeLists.txt - -noinst_HEADERS += \ - test/graph_test.h \ - test/test_tools.h - -check_PROGRAMS += \ - test/adaptors_test \ - test/bfs_test \ - test/circulation_test \ - test/connectivity_test \ - test/counter_test \ - test/dfs_test \ - test/digraph_test \ - test/dijkstra_test \ - test/dim_test \ - test/edge_set_test \ - test/error_test \ - test/euler_test \ - test/gomory_hu_test \ - test/graph_copy_test \ - test/graph_test \ - test/graph_utils_test \ - test/hao_orlin_test \ - test/heap_test \ - test/kruskal_test \ - test/lgf_test \ - test/maps_test \ - test/matching_test \ - test/min_cost_arborescence_test \ - test/min_cost_flow_test \ - test/path_test \ - test/preflow_test \ - test/radix_sort_test \ - test/random_test \ - test/suurballe_test \ - test/test_tools_fail \ - test/test_tools_pass \ - test/time_measure_test \ - test/unionfind_test - -test_test_tools_pass_DEPENDENCIES = demo - -if HAVE_LP -check_PROGRAMS += test/lp_test -endif HAVE_LP -if HAVE_MIP -check_PROGRAMS += test/mip_test -endif HAVE_MIP - -TESTS += $(check_PROGRAMS) -XFAIL_TESTS += test/test_tools_fail$(EXEEXT) - -test_adaptors_test_SOURCES = test/adaptors_test.cc -test_bfs_test_SOURCES = test/bfs_test.cc -test_circulation_test_SOURCES = test/circulation_test.cc -test_counter_test_SOURCES = test/counter_test.cc -test_connectivity_test_SOURCES = test/connectivity_test.cc -test_dfs_test_SOURCES = test/dfs_test.cc -test_digraph_test_SOURCES = test/digraph_test.cc -test_dijkstra_test_SOURCES = test/dijkstra_test.cc -test_dim_test_SOURCES = test/dim_test.cc -test_edge_set_test_SOURCES = test/edge_set_test.cc -test_error_test_SOURCES = test/error_test.cc -test_euler_test_SOURCES = test/euler_test.cc -test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc -test_graph_copy_test_SOURCES = test/graph_copy_test.cc -test_graph_test_SOURCES = test/graph_test.cc -test_graph_utils_test_SOURCES = test/graph_utils_test.cc -test_heap_test_SOURCES = test/heap_test.cc -test_kruskal_test_SOURCES = test/kruskal_test.cc -test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc -test_lgf_test_SOURCES = test/lgf_test.cc -test_lp_test_SOURCES = test/lp_test.cc -test_maps_test_SOURCES = test/maps_test.cc -test_mip_test_SOURCES = test/mip_test.cc -test_matching_test_SOURCES = test/matching_test.cc -test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc -test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc -test_path_test_SOURCES = test/path_test.cc -test_preflow_test_SOURCES = test/preflow_test.cc -test_radix_sort_test_SOURCES = test/radix_sort_test.cc -test_suurballe_test_SOURCES = test/suurballe_test.cc -test_random_test_SOURCES = test/random_test.cc -test_test_tools_fail_SOURCES = test/test_tools_fail.cc -test_test_tools_pass_SOURCES = test/test_tools_pass.cc -test_time_measure_test_SOURCES = test/time_measure_test.cc -test_unionfind_test_SOURCES = test/unionfind_test.cc Index: test/adaptors_test.cc =================================================================== --- test/adaptors_test.cc (revision 1083) +++ test/adaptors_test.cc (revision 1084) @@ -1375,26 +1375,20 @@ GridGraph::EdgeMap dir_map(graph); - dir_map[graph.right(n1)] = graph.u(graph.right(n1)) == n1; - dir_map[graph.up(n1)] = graph.u(graph.up(n1)) != n1; - dir_map[graph.left(n4)] = graph.u(graph.left(n4)) != n4; - dir_map[graph.down(n4)] = graph.u(graph.down(n4)) != n4; + dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1; + dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1; + dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4; + dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4; // Apply several adaptors on the grid graph - typedef SplitNodes< ReverseDigraph< const Orienter< - const GridGraph, GridGraph::EdgeMap > > > - RevSplitGridGraph; - typedef ReverseDigraph SplitGridGraph; + typedef Orienter< const GridGraph, GridGraph::EdgeMap > + OrientedGridGraph; + typedef SplitNodes SplitGridGraph; typedef Undirector USplitGridGraph; - typedef Undirector UUSplitGridGraph; - checkConcept(); checkConcept(); checkConcept(); - checkConcept(); - - RevSplitGridGraph rev_adaptor = - splitNodes(reverseDigraph(orienter(graph, dir_map))); - SplitGridGraph adaptor = reverseDigraph(rev_adaptor); + + OrientedGridGraph oadaptor = orienter(graph, dir_map); + SplitGridGraph adaptor = splitNodes(oadaptor); USplitGridGraph uadaptor = undirector(adaptor); - UUSplitGridGraph uuadaptor = undirector(uadaptor); // Check adaptor @@ -1403,21 +1397,21 @@ checkGraphConArcList(adaptor, 8); - checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1); - checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1); - checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2); - checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1); - checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1); - checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1); - checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0); - checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1); - - checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1); - checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1); - checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1); - checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0); - checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1); - checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1); - checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1); - checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2); + checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1); + checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1); + checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1); + checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0); + checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1); + checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1); + checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1); + checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2); + + checkGraphInArcList(adaptor, adaptor.inNode(n1), 1); + checkGraphInArcList(adaptor, adaptor.outNode(n1), 1); + checkGraphInArcList(adaptor, adaptor.inNode(n2), 2); + checkGraphInArcList(adaptor, adaptor.outNode(n2), 1); + checkGraphInArcList(adaptor, adaptor.inNode(n3), 1); + checkGraphInArcList(adaptor, adaptor.outNode(n3), 1); + checkGraphInArcList(adaptor, adaptor.inNode(n4), 0); + checkGraphInArcList(adaptor, adaptor.outNode(n4), 1); checkNodeIds(adaptor); @@ -1442,27 +1436,12 @@ checkGraphArcMap(uadaptor); - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2); - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2); - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3); - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1); - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2); - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2); - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1); - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3); - - // Check uuadaptor - checkGraphNodeList(uuadaptor, 8); - checkGraphEdgeList(uuadaptor, 16); - checkGraphArcList(uuadaptor, 32); - checkGraphConEdgeList(uuadaptor, 16); - checkGraphConArcList(uuadaptor, 32); - - checkNodeIds(uuadaptor); - checkEdgeIds(uuadaptor); - checkArcIds(uuadaptor); - - checkGraphNodeMap(uuadaptor); - checkGraphEdgeMap(uuadaptor); - checkGraphArcMap(uuadaptor); + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2); + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2); + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3); + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1); + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2); + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2); + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1); + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3); } Index: test/bellman_ford_test.cc =================================================================== --- test/bellman_ford_test.cc (revision 1085) +++ test/bellman_ford_test.cc (revision 1085) @@ -0,0 +1,289 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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; + +char test_lgf[] = + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "@arcs\n" + " length\n" + "0 1 3\n" + "1 2 -3\n" + "1 2 -5\n" + "1 3 -2\n" + "0 2 -1\n" + "1 2 -4\n" + "0 3 2\n" + "4 2 -5\n" + "2 3 1\n" + "@attributes\n" + "source 0\n" + "target 3\n"; + + +void checkBellmanFordCompile() +{ + typedef int Value; + typedef concepts::Digraph Digraph; + typedef concepts::ReadMap LengthMap; + typedef BellmanFord BF; + typedef Digraph::Node Node; + typedef Digraph::Arc Arc; + + Digraph gr; + Node s, t, n; + Arc e; + Value l; + ::lemon::ignore_unused_variable_warning(l); + int k=3; + bool b; + ::lemon::ignore_unused_variable_warning(b); + BF::DistMap d(gr); + BF::PredMap p(gr); + LengthMap length; + concepts::Path pp; + + { + BF bf_test(gr,length); + const BF& const_bf_test = bf_test; + + bf_test.run(s); + bf_test.run(s,k); + + bf_test.init(); + bf_test.addSource(s); + bf_test.addSource(s, 1); + b = bf_test.processNextRound(); + b = bf_test.processNextWeakRound(); + + bf_test.start(); + bf_test.checkedStart(); + bf_test.limitedStart(k); + + l = const_bf_test.dist(t); + e = const_bf_test.predArc(t); + s = const_bf_test.predNode(t); + b = const_bf_test.reached(t); + d = const_bf_test.distMap(); + p = const_bf_test.predMap(); + pp = const_bf_test.path(t); + pp = const_bf_test.negativeCycle(); + + for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {} + } + { + BF::SetPredMap > + ::SetDistMap > + ::SetOperationTraits > + ::Create bf_test(gr,length); + + LengthMap length_map; + concepts::ReadWriteMap pred_map; + concepts::ReadWriteMap dist_map; + + bf_test + .lengthMap(length_map) + .predMap(pred_map) + .distMap(dist_map); + + bf_test.run(s); + bf_test.run(s,k); + + bf_test.init(); + bf_test.addSource(s); + bf_test.addSource(s, 1); + b = bf_test.processNextRound(); + b = bf_test.processNextWeakRound(); + + bf_test.start(); + bf_test.checkedStart(); + bf_test.limitedStart(k); + + l = bf_test.dist(t); + e = bf_test.predArc(t); + s = bf_test.predNode(t); + b = bf_test.reached(t); + pp = bf_test.path(t); + pp = bf_test.negativeCycle(); + } +} + +void checkBellmanFordFunctionCompile() +{ + typedef int Value; + typedef concepts::Digraph Digraph; + typedef Digraph::Arc Arc; + typedef Digraph::Node Node; + typedef concepts::ReadMap LengthMap; + + Digraph g; + bool b; + ::lemon::ignore_unused_variable_warning(b); + + bellmanFord(g,LengthMap()).run(Node()); + b = bellmanFord(g,LengthMap()).run(Node(),Node()); + bellmanFord(g,LengthMap()) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) + .run(Node()); + b=bellmanFord(g,LengthMap()) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) + .path(concepts::Path()) + .dist(Value()) + .run(Node(),Node()); +} + + +template +void checkBellmanFord() { + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); + typedef typename Digraph::template ArcMap LengthMap; + + Digraph gr; + Node s, t; + LengthMap length(gr); + + std::istringstream input(test_lgf); + digraphReader(gr, input). + arcMap("length", length). + node("source", s). + node("target", t). + run(); + + BellmanFord + bf(gr, length); + bf.run(s); + Path p = bf.path(t); + + check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path."); + check(p.length() == 3, "path() found a wrong path."); + check(checkPath(gr, p), "path() found a wrong path."); + check(pathSource(gr, p) == s, "path() found a wrong path."); + check(pathTarget(gr, p) == t, "path() found a wrong path."); + + ListPath path; + Value dist = 0; + bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t); + + check(reached && dist == -1, "Bellman-Ford found a wrong path."); + check(path.length() == 3, "path() found a wrong path."); + check(checkPath(gr, path), "path() found a wrong path."); + check(pathSource(gr, path) == s, "path() found a wrong path."); + check(pathTarget(gr, path) == t, "path() found a wrong path."); + + for(ArcIt e(gr); e!=INVALID; ++e) { + Node u=gr.source(e); + Node v=gr.target(e); + check(!bf.reached(u) || (bf.dist(v) - bf.dist(u) <= length[e]), + "Wrong output. dist(target)-dist(source)-arc_length=" << + bf.dist(v) - bf.dist(u) - length[e]); + } + + for(NodeIt v(gr); v!=INVALID; ++v) { + if (bf.reached(v)) { + check(v==s || bf.predArc(v)!=INVALID, "Wrong tree."); + if (bf.predArc(v)!=INVALID ) { + Arc e=bf.predArc(v); + Node u=gr.source(e); + check(u==bf.predNode(v),"Wrong tree."); + check(bf.dist(v) - bf.dist(u) == length[e], + "Wrong distance! Difference: " << + bf.dist(v) - bf.dist(u) - length[e]); + } + } + } +} + +void checkBellmanFordNegativeCycle() { + DIGRAPH_TYPEDEFS(SmartDigraph); + + SmartDigraph gr; + IntArcMap length(gr); + + Node n1 = gr.addNode(); + Node n2 = gr.addNode(); + Node n3 = gr.addNode(); + Node n4 = gr.addNode(); + + Arc a1 = gr.addArc(n1, n2); + Arc a2 = gr.addArc(n2, n2); + + length[a1] = 2; + length[a2] = -1; + + { + BellmanFord bf(gr, length); + bf.run(n1); + StaticPath p = bf.negativeCycle(); + check(p.length() == 1 && p.front() == p.back() && p.front() == a2, + "Wrong negative cycle."); + } + + length[a2] = 0; + + { + BellmanFord bf(gr, length); + bf.run(n1); + check(bf.negativeCycle().empty(), + "Negative cycle should not be found."); + } + + length[gr.addArc(n1, n3)] = 5; + length[gr.addArc(n4, n3)] = 1; + length[gr.addArc(n2, n4)] = 2; + length[gr.addArc(n3, n2)] = -4; + + { + BellmanFord bf(gr, length); + bf.init(); + bf.addSource(n1); + for (int i = 0; i < 4; ++i) { + check(bf.negativeCycle().empty(), + "Negative cycle should not be found."); + bf.processNextRound(); + } + StaticPath p = bf.negativeCycle(); + check(p.length() == 3, "Wrong negative cycle."); + check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1, + "Wrong negative cycle."); + } +} + +int main() { + checkBellmanFord(); + checkBellmanFord(); + checkBellmanFordNegativeCycle(); + return 0; +} Index: test/bfs_test.cc =================================================================== --- test/bfs_test.cc (revision 1083) +++ test/bfs_test.cc (revision 1084) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -85,5 +85,5 @@ b = const_bfs_test.emptyQueue(); i = const_bfs_test.queueSize(); - + bfs_test.start(); bfs_test.start(t); @@ -106,10 +106,10 @@ ::SetProcessedMap > ::Create bfs_test(G); - + concepts::ReadWriteMap pred_map; concepts::ReadWriteMap dist_map; concepts::ReadWriteMap reached_map; concepts::WriteMap processed_map; - + bfs_test .predMap(pred_map) @@ -121,5 +121,5 @@ bfs_test.run(s,t); bfs_test.run(); - + bfs_test.init(); bfs_test.addSource(s); @@ -130,5 +130,5 @@ b = bfs_test.emptyQueue(); i = bfs_test.queueSize(); - + bfs_test.start(); bfs_test.start(t); Index: test/bpgraph_test.cc =================================================================== --- test/bpgraph_test.cc (revision 1026) +++ test/bpgraph_test.cc (revision 1026) @@ -0,0 +1,451 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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 "test_tools.h" +#include "graph_test.h" + +using namespace lemon; +using namespace lemon::concepts; + +template +void checkBpGraphBuild() { + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph); + + BpGraph G; + checkGraphNodeList(G, 0); + checkGraphRedNodeList(G, 0); + checkGraphBlueNodeList(G, 0); + checkGraphEdgeList(G, 0); + checkGraphArcList(G, 0); + + G.reserveNode(3); + G.reserveEdge(3); + + RedNode + rn1 = G.addRedNode(); + checkGraphNodeList(G, 1); + checkGraphRedNodeList(G, 1); + checkGraphBlueNodeList(G, 0); + checkGraphEdgeList(G, 0); + checkGraphArcList(G, 0); + + BlueNode + bn1 = G.addBlueNode(), + bn2 = G.addBlueNode(); + checkGraphNodeList(G, 3); + checkGraphRedNodeList(G, 1); + checkGraphBlueNodeList(G, 2); + checkGraphEdgeList(G, 0); + checkGraphArcList(G, 0); + + Edge e1 = G.addEdge(rn1, bn2); + check(G.redNode(e1) == rn1 && G.blueNode(e1) == bn2, "Wrong edge"); + check(G.u(e1) == rn1 && G.v(e1) == bn2, "Wrong edge"); + + checkGraphNodeList(G, 3); + checkGraphRedNodeList(G, 1); + checkGraphBlueNodeList(G, 2); + checkGraphEdgeList(G, 1); + checkGraphArcList(G, 2); + + checkGraphIncEdgeArcLists(G, rn1, 1); + checkGraphIncEdgeArcLists(G, bn1, 0); + checkGraphIncEdgeArcLists(G, bn2, 1); + + checkGraphConEdgeList(G, 1); + checkGraphConArcList(G, 2); + + Edge + e2 = G.addEdge(bn1, rn1), + e3 = G.addEdge(rn1, bn2); + + checkGraphNodeList(G, 3); + checkGraphRedNodeList(G, 1); + checkGraphBlueNodeList(G, 2); + checkGraphEdgeList(G, 3); + checkGraphArcList(G, 6); + + checkGraphIncEdgeArcLists(G, rn1, 3); + checkGraphIncEdgeArcLists(G, bn1, 1); + checkGraphIncEdgeArcLists(G, bn2, 2); + + checkGraphConEdgeList(G, 3); + checkGraphConArcList(G, 6); + + checkArcDirections(G); + + checkNodeIds(G); + checkRedNodeIds(G); + checkBlueNodeIds(G); + checkArcIds(G); + checkEdgeIds(G); + + checkGraphNodeMap(G); + checkGraphRedNodeMap(G); + checkGraphBlueNodeMap(G); + checkGraphArcMap(G); + checkGraphEdgeMap(G); +} + +template +void checkBpGraphErase() { + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph); + + BpGraph G; + RedNode + n1 = G.addRedNode(), n4 = G.addRedNode(); + BlueNode + n2 = G.addBlueNode(), n3 = G.addBlueNode(); + Edge + e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3), + e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3); + + // Check edge deletion + G.erase(e2); + + checkGraphNodeList(G, 4); + checkGraphRedNodeList(G, 2); + checkGraphBlueNodeList(G, 2); + checkGraphEdgeList(G, 3); + checkGraphArcList(G, 6); + + checkGraphIncEdgeArcLists(G, n1, 1); + checkGraphIncEdgeArcLists(G, n2, 2); + checkGraphIncEdgeArcLists(G, n3, 1); + checkGraphIncEdgeArcLists(G, n4, 2); + + checkGraphConEdgeList(G, 3); + checkGraphConArcList(G, 6); + + // Check node deletion + G.erase(n3); + + checkGraphNodeList(G, 3); + checkGraphRedNodeList(G, 2); + checkGraphBlueNodeList(G, 1); + checkGraphEdgeList(G, 2); + checkGraphArcList(G, 4); + + checkGraphIncEdgeArcLists(G, n1, 1); + checkGraphIncEdgeArcLists(G, n2, 2); + checkGraphIncEdgeArcLists(G, n4, 1); + + checkGraphConEdgeList(G, 2); + checkGraphConArcList(G, 4); + +} + +template +void checkBpGraphAlter() { + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph); + + BpGraph G; + RedNode + n1 = G.addRedNode(), n4 = G.addRedNode(); + BlueNode + n2 = G.addBlueNode(), n3 = G.addBlueNode(); + Edge + e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3), + e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3); + + G.changeRed(e2, n4); + check(G.redNode(e2) == n4, "Wrong red node"); + check(G.blueNode(e2) == n3, "Wrong blue node"); + + checkGraphNodeList(G, 4); + checkGraphRedNodeList(G, 2); + checkGraphBlueNodeList(G, 2); + checkGraphEdgeList(G, 4); + checkGraphArcList(G, 8); + + checkGraphIncEdgeArcLists(G, n1, 1); + checkGraphIncEdgeArcLists(G, n2, 2); + checkGraphIncEdgeArcLists(G, n3, 2); + checkGraphIncEdgeArcLists(G, n4, 3); + + checkGraphConEdgeList(G, 4); + checkGraphConArcList(G, 8); + + G.changeBlue(e2, n2); + check(G.redNode(e2) == n4, "Wrong red node"); + check(G.blueNode(e2) == n2, "Wrong blue node"); + + checkGraphNodeList(G, 4); + checkGraphRedNodeList(G, 2); + checkGraphBlueNodeList(G, 2); + checkGraphEdgeList(G, 4); + checkGraphArcList(G, 8); + + checkGraphIncEdgeArcLists(G, n1, 1); + checkGraphIncEdgeArcLists(G, n2, 3); + checkGraphIncEdgeArcLists(G, n3, 1); + checkGraphIncEdgeArcLists(G, n4, 3); + + checkGraphConEdgeList(G, 4); + checkGraphConArcList(G, 8); +} + + +template +void checkBpGraphSnapshot() { + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph); + + BpGraph G; + RedNode + n1 = G.addRedNode(); + BlueNode + n2 = G.addBlueNode(), + n3 = G.addBlueNode(); + Edge + e1 = G.addEdge(n1, n2), + e2 = G.addEdge(n1, n3); + + checkGraphNodeList(G, 3); + checkGraphRedNodeList(G, 1); + checkGraphBlueNodeList(G, 2); + checkGraphEdgeList(G, 2); + checkGraphArcList(G, 4); + + typename BpGraph::Snapshot snapshot(G); + + RedNode n4 = G.addRedNode(); + G.addEdge(n4, n2); + G.addEdge(n4, n3); + + checkGraphNodeList(G, 4); + checkGraphRedNodeList(G, 2); + checkGraphBlueNodeList(G, 2); + checkGraphEdgeList(G, 4); + checkGraphArcList(G, 8); + + snapshot.restore(); + + checkGraphNodeList(G, 3); + checkGraphRedNodeList(G, 1); + checkGraphBlueNodeList(G, 2); + checkGraphEdgeList(G, 2); + checkGraphArcList(G, 4); + + checkGraphIncEdgeArcLists(G, n1, 2); + checkGraphIncEdgeArcLists(G, n2, 1); + checkGraphIncEdgeArcLists(G, n3, 1); + + checkGraphConEdgeList(G, 2); + checkGraphConArcList(G, 4); + + checkNodeIds(G); + checkRedNodeIds(G); + checkBlueNodeIds(G); + checkArcIds(G); + checkEdgeIds(G); + + checkGraphNodeMap(G); + checkGraphRedNodeMap(G); + checkGraphBlueNodeMap(G); + checkGraphArcMap(G); + checkGraphEdgeMap(G); + + G.addRedNode(); + snapshot.save(G); + + G.addEdge(G.addRedNode(), G.addBlueNode()); + + snapshot.restore(); + snapshot.save(G); + + checkGraphNodeList(G, 4); + checkGraphRedNodeList(G, 2); + checkGraphBlueNodeList(G, 2); + checkGraphEdgeList(G, 2); + checkGraphArcList(G, 4); + + G.addEdge(G.addRedNode(), G.addBlueNode()); + + snapshot.restore(); + + checkGraphNodeList(G, 4); + checkGraphRedNodeList(G, 2); + checkGraphBlueNodeList(G, 2); + checkGraphEdgeList(G, 2); + checkGraphArcList(G, 4); +} + +template +void checkBpGraphValidity() { + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph); + BpGraph g; + + RedNode + n1 = g.addRedNode(); + BlueNode + n2 = g.addBlueNode(), + n3 = g.addBlueNode(); + + Edge + e1 = g.addEdge(n1, n2), + e2 = g.addEdge(n1, n3); + + check(g.valid(n1), "Wrong validity check"); + check(g.valid(e1), "Wrong validity check"); + check(g.valid(g.direct(e1, true)), "Wrong validity check"); + + check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); + check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); + check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); +} + +void checkConcepts() { + { // Checking graph components + checkConcept(); + + checkConcept, + IDableBpGraphComponent<> >(); + + checkConcept, + IterableBpGraphComponent<> >(); + + checkConcept, + AlterableBpGraphComponent<> >(); + + checkConcept, + MappableBpGraphComponent<> >(); + + checkConcept, + ExtendableBpGraphComponent<> >(); + + checkConcept, + ErasableBpGraphComponent<> >(); + + checkConcept, + ClearableBpGraphComponent<> >(); + + } + { // Checking skeleton graph + checkConcept(); + } + { // Checking SmartBpGraph + checkConcept(); + checkConcept, SmartBpGraph>(); + checkConcept, SmartBpGraph>(); + checkConcept, SmartBpGraph>(); + } +} + +void checkFullBpGraph(int redNum, int blueNum) { + typedef FullBpGraph BpGraph; + BPGRAPH_TYPEDEFS(BpGraph); + + BpGraph G(redNum, blueNum); + checkGraphNodeList(G, redNum + blueNum); + checkGraphRedNodeList(G, redNum); + checkGraphBlueNodeList(G, blueNum); + checkGraphEdgeList(G, redNum * blueNum); + checkGraphArcList(G, 2 * redNum * blueNum); + + G.resize(redNum, blueNum); + checkGraphNodeList(G, redNum + blueNum); + checkGraphRedNodeList(G, redNum); + checkGraphBlueNodeList(G, blueNum); + checkGraphEdgeList(G, redNum * blueNum); + checkGraphArcList(G, 2 * redNum * blueNum); + + for (RedNodeIt n(G); n != INVALID; ++n) { + checkGraphOutArcList(G, n, blueNum); + checkGraphInArcList(G, n, blueNum); + checkGraphIncEdgeList(G, n, blueNum); + } + + for (BlueNodeIt n(G); n != INVALID; ++n) { + checkGraphOutArcList(G, n, redNum); + checkGraphInArcList(G, n, redNum); + checkGraphIncEdgeList(G, n, redNum); + } + + checkGraphConArcList(G, 2 * redNum * blueNum); + checkGraphConEdgeList(G, redNum * blueNum); + + checkArcDirections(G); + + checkNodeIds(G); + checkRedNodeIds(G); + checkBlueNodeIds(G); + checkArcIds(G); + checkEdgeIds(G); + + checkGraphNodeMap(G); + checkGraphRedNodeMap(G); + checkGraphBlueNodeMap(G); + checkGraphArcMap(G); + checkGraphEdgeMap(G); + + for (int i = 0; i < G.redNum(); ++i) { + check(G.red(G.redNode(i)), "Wrong node"); + check(G.index(G.redNode(i)) == i, "Wrong index"); + } + + for (int i = 0; i < G.blueNum(); ++i) { + check(G.blue(G.blueNode(i)), "Wrong node"); + check(G.index(G.blueNode(i)) == i, "Wrong index"); + } + + for (NodeIt u(G); u != INVALID; ++u) { + for (NodeIt v(G); v != INVALID; ++v) { + Edge e = G.edge(u, v); + Arc a = G.arc(u, v); + if (G.red(u) == G.red(v)) { + check(e == INVALID, "Wrong edge lookup"); + check(a == INVALID, "Wrong arc lookup"); + } else { + check((G.u(e) == u && G.v(e) == v) || + (G.u(e) == v && G.v(e) == u), "Wrong edge lookup"); + check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup"); + } + } + } + +} + +void checkGraphs() { + { // Checking ListGraph + checkBpGraphBuild(); + checkBpGraphErase(); + checkBpGraphAlter(); + checkBpGraphSnapshot(); + checkBpGraphValidity(); + } + { // Checking SmartGraph + checkBpGraphBuild(); + checkBpGraphSnapshot(); + checkBpGraphValidity(); + } + { // Checking FullBpGraph + checkFullBpGraph(6, 8); + checkFullBpGraph(7, 4); + } +} + +int main() { + checkConcepts(); + checkGraphs(); + return 0; +} Index: test/circulation_test.cc =================================================================== --- test/circulation_test.cc (revision 1083) +++ test/circulation_test.cc (revision 1084) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -83,5 +83,5 @@ CirculationType circ_test(g, lcap, ucap, supply); const CirculationType& const_circ_test = circ_test; - + circ_test .lowerMap(lcap) @@ -89,4 +89,9 @@ .supplyMap(supply) .flowMap(flow); + + const CirculationType::Elevator& elev = const_circ_test.elevator(); + circ_test.elevator(const_cast(elev)); + CirculationType::Tolerance tol = const_circ_test.tolerance(); + circ_test.tolerance(tol); circ_test.init(); @@ -99,5 +104,5 @@ b = const_circ_test.barrier(n); const_circ_test.barrierMap(bar); - + ::lemon::ignore_unused_variable_warning(fm); } Index: test/connectivity_test.cc =================================================================== --- test/connectivity_test.cc (revision 1089) +++ test/connectivity_test.cc (revision 1091) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -30,10 +30,10 @@ typedef ListDigraph Digraph; typedef Undirector Graph; - + { Digraph d; Digraph::NodeMap order(d); Graph g(d); - + check(stronglyConnected(d), "The empty digraph is strongly connected"); check(countStronglyConnectedComponents(d) == 0, @@ -49,5 +49,5 @@ check(countBiEdgeConnectedComponents(g) == 0, "The empty graph has 0 bi-edge-connected component"); - + check(dag(d), "The empty digraph is DAG."); check(checkedTopologicalSort(d, order), "The empty digraph is DAG."); @@ -84,5 +84,5 @@ check(countBiEdgeConnectedComponents(g) == 1, "This graph has 1 bi-edge-connected component"); - + check(dag(d), "This digraph is DAG."); check(checkedTopologicalSort(d, order), "This digraph is DAG."); @@ -120,5 +120,5 @@ Digraph::NodeMap order(d); Graph g(d); - + Digraph::Node n1 = d.addNode(); Digraph::Node n2 = d.addNode(); @@ -127,5 +127,5 @@ Digraph::Node n5 = d.addNode(); Digraph::Node n6 = d.addNode(); - + d.addArc(n1, n3); d.addArc(n3, n2); @@ -155,21 +155,21 @@ check(!parallelFree(g), "This graph is not parallel-free."); check(!simpleGraph(g), "This graph is not simple."); - + d.addArc(n3, n3); - + check(!loopFree(d), "This digraph is not loop-free."); check(!loopFree(g), "This graph is not loop-free."); check(!simpleGraph(d), "This digraph is not simple."); - + d.addArc(n3, n2); - + check(!parallelFree(d), "This digraph is not parallel-free."); } - + { Digraph d; Digraph::ArcMap cutarcs(d, false); Graph g(d); - + Digraph::Node n1 = d.addNode(); Digraph::Node n2 = d.addNode(); @@ -191,5 +191,5 @@ d.addArc(n6, n7); d.addArc(n7, n6); - + check(!stronglyConnected(d), "This digraph is not strongly connected"); check(countStronglyConnectedComponents(d) == 3, @@ -254,5 +254,5 @@ Digraph d; Digraph::NodeMap order(d); - + Digraph::Node belt = d.addNode(); Digraph::Node trousers = d.addNode(); @@ -275,5 +275,5 @@ d.addArc(shirt, necktie); d.addArc(necktie, coat); - + check(dag(d), "This digraph is DAG."); topologicalSort(d, order); @@ -287,5 +287,5 @@ ListGraph g; ListGraph::NodeMap map(g); - + ListGraph::Node n1 = g.addNode(); ListGraph::Node n2 = g.addNode(); @@ -303,8 +303,8 @@ g.addEdge(n4, n7); g.addEdge(n5, n7); - + check(bipartite(g), "This graph is bipartite"); check(bipartitePartitions(g, map), "This graph is bipartite"); - + check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7], "Wrong bipartitePartitions()"); Index: test/dfs_test.cc =================================================================== --- test/dfs_test.cc (revision 1083) +++ test/dfs_test.cc (revision 1086) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -89,5 +89,5 @@ b = const_dfs_test.emptyQueue(); i = const_dfs_test.queueSize(); - + dfs_test.start(); dfs_test.start(t); @@ -115,5 +115,5 @@ concepts::ReadWriteMap reached_map; concepts::WriteMap processed_map; - + dfs_test .predMap(pred_map) @@ -132,5 +132,5 @@ b = dfs_test.emptyQueue(); i = dfs_test.queueSize(); - + dfs_test.start(); dfs_test.start(t); Index: test/digraph_test.cc =================================================================== --- test/digraph_test.cc (revision 1083) +++ test/digraph_test.cc (revision 1085) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -20,4 +20,5 @@ #include #include +#include #include @@ -35,4 +36,7 @@ checkGraphNodeList(G, 0); checkGraphArcList(G, 0); + + G.reserveNode(3); + G.reserveArc(4); Node @@ -289,4 +293,12 @@ snapshot.restore(); + snapshot.save(G); + + checkGraphNodeList(G, 4); + checkGraphArcList(G, 4); + + G.addArc(G.addNode(), G.addNode()); + + snapshot.restore(); checkGraphNodeList(G, 4); @@ -323,4 +335,8 @@ checkConcept, SmartDigraph>(); } + { // Checking StaticDigraph + checkConcept(); + checkConcept, StaticDigraph>(); + } { // Checking FullDigraph checkConcept(); @@ -379,8 +395,121 @@ } +void checkStaticDigraph() { + SmartDigraph g; + SmartDigraph::NodeMap nref(g); + SmartDigraph::ArcMap aref(g); + + StaticDigraph G; + + checkGraphNodeList(G, 0); + checkGraphArcList(G, 0); + + G.build(g, nref, aref); + + checkGraphNodeList(G, 0); + checkGraphArcList(G, 0); + + SmartDigraph::Node + n1 = g.addNode(), + n2 = g.addNode(), + n3 = g.addNode(); + + G.build(g, nref, aref); + + checkGraphNodeList(G, 3); + checkGraphArcList(G, 0); + + SmartDigraph::Arc a1 = g.addArc(n1, n2); + + G.build(g, nref, aref); + + check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2], + "Wrong arc or wrong references"); + checkGraphNodeList(G, 3); + checkGraphArcList(G, 1); + + checkGraphOutArcList(G, nref[n1], 1); + checkGraphOutArcList(G, nref[n2], 0); + checkGraphOutArcList(G, nref[n3], 0); + + checkGraphInArcList(G, nref[n1], 0); + checkGraphInArcList(G, nref[n2], 1); + checkGraphInArcList(G, nref[n3], 0); + + checkGraphConArcList(G, 1); + + SmartDigraph::Arc + a2 = g.addArc(n2, n1), + a3 = g.addArc(n2, n3), + a4 = g.addArc(n2, n3); + ::lemon::ignore_unused_variable_warning(a2,a3,a4); + + digraphCopy(g, G).nodeRef(nref).run(); + + checkGraphNodeList(G, 3); + checkGraphArcList(G, 4); + + checkGraphOutArcList(G, nref[n1], 1); + checkGraphOutArcList(G, nref[n2], 3); + checkGraphOutArcList(G, nref[n3], 0); + + checkGraphInArcList(G, nref[n1], 1); + checkGraphInArcList(G, nref[n2], 1); + checkGraphInArcList(G, nref[n3], 2); + + checkGraphConArcList(G, 4); + + std::vector > arcs; + arcs.push_back(std::make_pair(0,1)); + arcs.push_back(std::make_pair(0,2)); + arcs.push_back(std::make_pair(1,3)); + arcs.push_back(std::make_pair(1,2)); + arcs.push_back(std::make_pair(3,0)); + arcs.push_back(std::make_pair(3,3)); + arcs.push_back(std::make_pair(4,2)); + arcs.push_back(std::make_pair(4,3)); + arcs.push_back(std::make_pair(4,1)); + + G.build(6, arcs.begin(), arcs.end()); + + checkGraphNodeList(G, 6); + checkGraphArcList(G, 9); + + checkGraphOutArcList(G, G.node(0), 2); + checkGraphOutArcList(G, G.node(1), 2); + checkGraphOutArcList(G, G.node(2), 0); + checkGraphOutArcList(G, G.node(3), 2); + checkGraphOutArcList(G, G.node(4), 3); + checkGraphOutArcList(G, G.node(5), 0); + + checkGraphInArcList(G, G.node(0), 1); + checkGraphInArcList(G, G.node(1), 2); + checkGraphInArcList(G, G.node(2), 3); + checkGraphInArcList(G, G.node(3), 3); + checkGraphInArcList(G, G.node(4), 0); + checkGraphInArcList(G, G.node(5), 0); + + checkGraphConArcList(G, 9); + + checkNodeIds(G); + checkArcIds(G); + checkGraphNodeMap(G); + checkGraphArcMap(G); + + int n = G.nodeNum(); + int m = G.arcNum(); + check(G.index(G.node(n-1)) == n-1, "Wrong index."); + check(G.index(G.arc(m-1)) == m-1, "Wrong index."); +} + void checkFullDigraph(int num) { typedef FullDigraph Digraph; DIGRAPH_TYPEDEFS(Digraph); + Digraph G(num); + check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size"); + + G.resize(num); + check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size"); checkGraphNodeList(G, num); @@ -426,4 +555,7 @@ checkDigraphValidity(); } + { // Checking StaticDigraph + checkStaticDigraph(); + } { // Checking FullDigraph checkFullDigraph(8); Index: test/dijkstra_test.cc =================================================================== --- test/dijkstra_test.cc (revision 1083) +++ test/dijkstra_test.cc (revision 1084) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -88,5 +88,5 @@ b = const_dijkstra_test.emptyQueue(); i = const_dijkstra_test.queueSize(); - + dijkstra_test.start(); dijkstra_test.start(t); @@ -112,5 +112,5 @@ ::SetHeap > > ::SetStandardHeap > > - ::SetHeap >, + ::SetHeap >, concepts::ReadWriteMap > ::Create dijkstra_test(G,length); @@ -122,5 +122,5 @@ concepts::ReadWriteMap heap_cross_ref; BinHeap > heap(heap_cross_ref); - + dijkstra_test .lengthMap(length_map) @@ -139,5 +139,5 @@ b = dijkstra_test.emptyQueue(); i = dijkstra_test.queueSize(); - + dijkstra_test.start(); dijkstra_test.start(t); Index: test/edge_set_test.cc =================================================================== --- test/edge_set_test.cc (revision 1083) +++ test/edge_set_test.cc (revision 1084) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/euler_test.cc =================================================================== --- test/euler_test.cc (revision 1083) +++ test/euler_test.cc (revision 1084) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -86,9 +86,9 @@ typedef ListDigraph Digraph; typedef Undirector Graph; - - { - Digraph d; - Graph g(d); - + + { + Digraph d; + Graph g(d); + checkDiEulerIt(d); checkDiEulerIt(g); @@ -130,5 +130,5 @@ Digraph::Node n2 = d.addNode(); Digraph::Node n3 = d.addNode(); - + d.addArc(n1, n2); d.addArc(n2, n1); @@ -155,5 +155,5 @@ Digraph::Node n5 = d.addNode(); Digraph::Node n6 = d.addNode(); - + d.addArc(n1, n2); d.addArc(n2, n4); @@ -214,5 +214,5 @@ Digraph::Node n2 = d.addNode(); Digraph::Node n3 = d.addNode(); - + d.addArc(n1, n2); d.addArc(n2, n3); Index: test/fractional_matching_test.cc =================================================================== --- test/fractional_matching_test.cc (revision 1085) +++ test/fractional_matching_test.cc (revision 1085) @@ -0,0 +1,527 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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 +#include +#include +#include +#include + +#include "test_tools.h" + +using namespace std; +using namespace lemon; + +GRAPH_TYPEDEFS(SmartGraph); + + +const int lgfn = 4; +const std::string lgf[lgfn] = { + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "@edges\n" + " label weight\n" + "7 4 0 984\n" + "0 7 1 73\n" + "7 1 2 204\n" + "2 3 3 583\n" + "2 7 4 565\n" + "2 1 5 582\n" + "0 4 6 551\n" + "2 5 7 385\n" + "1 5 8 561\n" + "5 3 9 484\n" + "7 5 10 904\n" + "3 6 11 47\n" + "7 6 12 888\n" + "3 0 13 747\n" + "6 1 14 310\n", + + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "@edges\n" + " label weight\n" + "2 5 0 710\n" + "0 5 1 241\n" + "2 4 2 856\n" + "2 6 3 762\n" + "4 1 4 747\n" + "6 1 5 962\n" + "4 7 6 723\n" + "1 7 7 661\n" + "2 3 8 376\n" + "1 0 9 416\n" + "6 7 10 391\n", + + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "@edges\n" + " label weight\n" + "6 2 0 553\n" + "0 7 1 653\n" + "6 3 2 22\n" + "4 7 3 846\n" + "7 2 4 981\n" + "7 6 5 250\n" + "5 2 6 539\n", + + "@nodes\n" + "label\n" + "0\n" + "@edges\n" + " label weight\n" + "0 0 0 100\n" +}; + +void checkMaxFractionalMatchingCompile() +{ + typedef concepts::Graph Graph; + typedef Graph::Node Node; + typedef Graph::Edge Edge; + + Graph g; + Node n; + Edge e; + + MaxFractionalMatching mat_test(g); + const MaxFractionalMatching& + const_mat_test = mat_test; + + mat_test.init(); + mat_test.start(); + mat_test.start(true); + mat_test.startPerfect(); + mat_test.startPerfect(true); + mat_test.run(); + mat_test.run(true); + mat_test.runPerfect(); + mat_test.runPerfect(true); + + const_mat_test.matchingSize(); + const_mat_test.matching(e); + const_mat_test.matching(n); + const MaxFractionalMatching::MatchingMap& mmap = + const_mat_test.matchingMap(); + e = mmap[n]; + + const_mat_test.barrier(n); +} + +void checkMaxWeightedFractionalMatchingCompile() +{ + typedef concepts::Graph Graph; + typedef Graph::Node Node; + typedef Graph::Edge Edge; + typedef Graph::EdgeMap WeightMap; + + Graph g; + Node n; + Edge e; + WeightMap w(g); + + MaxWeightedFractionalMatching mat_test(g, w); + const MaxWeightedFractionalMatching& + const_mat_test = mat_test; + + mat_test.init(); + mat_test.start(); + mat_test.run(); + + const_mat_test.matchingWeight(); + const_mat_test.matchingSize(); + const_mat_test.matching(e); + const_mat_test.matching(n); + const MaxWeightedFractionalMatching::MatchingMap& mmap = + const_mat_test.matchingMap(); + e = mmap[n]; + + const_mat_test.dualValue(); + const_mat_test.nodeValue(n); +} + +void checkMaxWeightedPerfectFractionalMatchingCompile() +{ + typedef concepts::Graph Graph; + typedef Graph::Node Node; + typedef Graph::Edge Edge; + typedef Graph::EdgeMap WeightMap; + + Graph g; + Node n; + Edge e; + WeightMap w(g); + + MaxWeightedPerfectFractionalMatching mat_test(g, w); + const MaxWeightedPerfectFractionalMatching& + const_mat_test = mat_test; + + mat_test.init(); + mat_test.start(); + mat_test.run(); + + const_mat_test.matchingWeight(); + const_mat_test.matching(e); + const_mat_test.matching(n); + const MaxWeightedPerfectFractionalMatching::MatchingMap& mmap = + const_mat_test.matchingMap(); + e = mmap[n]; + + const_mat_test.dualValue(); + const_mat_test.nodeValue(n); +} + +void checkFractionalMatching(const SmartGraph& graph, + const MaxFractionalMatching& mfm, + bool allow_loops = true) { + int pv = 0; + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + int indeg = 0; + for (InArcIt a(graph, n); a != INVALID; ++a) { + if (mfm.matching(graph.source(a)) == a) { + ++indeg; + } + } + if (mfm.matching(n) != INVALID) { + check(indeg == 1, "Invalid matching"); + ++pv; + } else { + check(indeg == 0, "Invalid matching"); + } + } + check(pv == mfm.matchingSize(), "Wrong matching size"); + + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { + check((e == mfm.matching(graph.u(e)) ? 1 : 0) + + (e == mfm.matching(graph.v(e)) ? 1 : 0) == + mfm.matching(e), "Invalid matching"); + } + + SmartGraph::NodeMap processed(graph, false); + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + if (processed[n]) continue; + processed[n] = true; + if (mfm.matching(n) == INVALID) continue; + int num = 1; + Node v = graph.target(mfm.matching(n)); + while (v != n) { + processed[v] = true; + ++num; + v = graph.target(mfm.matching(v)); + } + check(num == 2 || num % 2 == 1, "Wrong cycle size"); + check(allow_loops || num != 1, "Wrong cycle size"); + } + + int anum = 0, bnum = 0; + SmartGraph::NodeMap neighbours(graph, false); + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + if (!mfm.barrier(n)) continue; + ++anum; + for (SmartGraph::InArcIt a(graph, n); a != INVALID; ++a) { + Node u = graph.source(a); + if (!allow_loops && u == n) continue; + if (!neighbours[u]) { + neighbours[u] = true; + ++bnum; + } + } + } + check(anum - bnum + mfm.matchingSize() == countNodes(graph), + "Wrong barrier"); +} + +void checkPerfectFractionalMatching(const SmartGraph& graph, + const MaxFractionalMatching& mfm, + bool perfect, bool allow_loops = true) { + if (perfect) { + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + int indeg = 0; + for (InArcIt a(graph, n); a != INVALID; ++a) { + if (mfm.matching(graph.source(a)) == a) { + ++indeg; + } + } + check(mfm.matching(n) != INVALID, "Invalid matching"); + check(indeg == 1, "Invalid matching"); + } + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { + check((e == mfm.matching(graph.u(e)) ? 1 : 0) + + (e == mfm.matching(graph.v(e)) ? 1 : 0) == + mfm.matching(e), "Invalid matching"); + } + } else { + int anum = 0, bnum = 0; + SmartGraph::NodeMap neighbours(graph, false); + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + if (!mfm.barrier(n)) continue; + ++anum; + for (SmartGraph::InArcIt a(graph, n); a != INVALID; ++a) { + Node u = graph.source(a); + if (!allow_loops && u == n) continue; + if (!neighbours[u]) { + neighbours[u] = true; + ++bnum; + } + } + } + check(anum - bnum > 0, "Wrong barrier"); + } +} + +void checkWeightedFractionalMatching(const SmartGraph& graph, + const SmartGraph::EdgeMap& weight, + const MaxWeightedFractionalMatching& mwfm, + bool allow_loops = true) { + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { + if (graph.u(e) == graph.v(e) && !allow_loops) continue; + int rw = mwfm.nodeValue(graph.u(e)) + mwfm.nodeValue(graph.v(e)) + - weight[e] * mwfm.dualScale; + + check(rw >= 0, "Negative reduced weight"); + check(rw == 0 || !mwfm.matching(e), + "Non-zero reduced weight on matching edge"); + } + + int pv = 0; + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + int indeg = 0; + for (InArcIt a(graph, n); a != INVALID; ++a) { + if (mwfm.matching(graph.source(a)) == a) { + ++indeg; + } + } + check(indeg <= 1, "Invalid matching"); + if (mwfm.matching(n) != INVALID) { + check(mwfm.nodeValue(n) >= 0, "Invalid node value"); + check(indeg == 1, "Invalid matching"); + pv += weight[mwfm.matching(n)]; + SmartGraph::Node o = graph.target(mwfm.matching(n)); + ::lemon::ignore_unused_variable_warning(o); + } else { + check(mwfm.nodeValue(n) == 0, "Invalid matching"); + check(indeg == 0, "Invalid matching"); + } + } + + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { + check((e == mwfm.matching(graph.u(e)) ? 1 : 0) + + (e == mwfm.matching(graph.v(e)) ? 1 : 0) == + mwfm.matching(e), "Invalid matching"); + } + + int dv = 0; + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + dv += mwfm.nodeValue(n); + } + + check(pv * mwfm.dualScale == dv * 2, "Wrong duality"); + + SmartGraph::NodeMap processed(graph, false); + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + if (processed[n]) continue; + processed[n] = true; + if (mwfm.matching(n) == INVALID) continue; + int num = 1; + Node v = graph.target(mwfm.matching(n)); + while (v != n) { + processed[v] = true; + ++num; + v = graph.target(mwfm.matching(v)); + } + check(num == 2 || num % 2 == 1, "Wrong cycle size"); + check(allow_loops || num != 1, "Wrong cycle size"); + } + + return; +} + +void checkWeightedPerfectFractionalMatching(const SmartGraph& graph, + const SmartGraph::EdgeMap& weight, + const MaxWeightedPerfectFractionalMatching& mwpfm, + bool allow_loops = true) { + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { + if (graph.u(e) == graph.v(e) && !allow_loops) continue; + int rw = mwpfm.nodeValue(graph.u(e)) + mwpfm.nodeValue(graph.v(e)) + - weight[e] * mwpfm.dualScale; + + check(rw >= 0, "Negative reduced weight"); + check(rw == 0 || !mwpfm.matching(e), + "Non-zero reduced weight on matching edge"); + } + + int pv = 0; + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + int indeg = 0; + for (InArcIt a(graph, n); a != INVALID; ++a) { + if (mwpfm.matching(graph.source(a)) == a) { + ++indeg; + } + } + check(mwpfm.matching(n) != INVALID, "Invalid perfect matching"); + check(indeg == 1, "Invalid perfect matching"); + pv += weight[mwpfm.matching(n)]; + SmartGraph::Node o = graph.target(mwpfm.matching(n)); + ::lemon::ignore_unused_variable_warning(o); + } + + for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { + check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) + + (e == mwpfm.matching(graph.v(e)) ? 1 : 0) == + mwpfm.matching(e), "Invalid matching"); + } + + int dv = 0; + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + dv += mwpfm.nodeValue(n); + } + + check(pv * mwpfm.dualScale == dv * 2, "Wrong duality"); + + SmartGraph::NodeMap processed(graph, false); + for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { + if (processed[n]) continue; + processed[n] = true; + if (mwpfm.matching(n) == INVALID) continue; + int num = 1; + Node v = graph.target(mwpfm.matching(n)); + while (v != n) { + processed[v] = true; + ++num; + v = graph.target(mwpfm.matching(v)); + } + check(num == 2 || num % 2 == 1, "Wrong cycle size"); + check(allow_loops || num != 1, "Wrong cycle size"); + } + + return; +} + + +int main() { + + for (int i = 0; i < lgfn; ++i) { + SmartGraph graph; + SmartGraph::EdgeMap weight(graph); + + istringstream lgfs(lgf[i]); + graphReader(graph, lgfs). + edgeMap("weight", weight).run(); + + bool perfect_with_loops; + { + MaxFractionalMatching mfm(graph, true); + mfm.run(); + checkFractionalMatching(graph, mfm, true); + perfect_with_loops = mfm.matchingSize() == countNodes(graph); + } + + bool perfect_without_loops; + { + MaxFractionalMatching mfm(graph, false); + mfm.run(); + checkFractionalMatching(graph, mfm, false); + perfect_without_loops = mfm.matchingSize() == countNodes(graph); + } + + { + MaxFractionalMatching mfm(graph, true); + bool result = mfm.runPerfect(); + checkPerfectFractionalMatching(graph, mfm, result, true); + check(result == perfect_with_loops, "Wrong perfect matching"); + } + + { + MaxFractionalMatching mfm(graph, false); + bool result = mfm.runPerfect(); + checkPerfectFractionalMatching(graph, mfm, result, false); + check(result == perfect_without_loops, "Wrong perfect matching"); + } + + { + MaxWeightedFractionalMatching mwfm(graph, weight, true); + mwfm.run(); + checkWeightedFractionalMatching(graph, weight, mwfm, true); + } + + { + MaxWeightedFractionalMatching mwfm(graph, weight, false); + mwfm.run(); + checkWeightedFractionalMatching(graph, weight, mwfm, false); + } + + { + MaxWeightedPerfectFractionalMatching mwpfm(graph, weight, + true); + bool perfect = mwpfm.run(); + check(perfect == (mwpfm.matchingSize() == countNodes(graph)), + "Perfect matching found"); + check(perfect == perfect_with_loops, "Wrong perfect matching"); + + if (perfect) { + checkWeightedPerfectFractionalMatching(graph, weight, mwpfm, true); + } + } + + { + MaxWeightedPerfectFractionalMatching mwpfm(graph, weight, + false); + bool perfect = mwpfm.run(); + check(perfect == (mwpfm.matchingSize() == countNodes(graph)), + "Perfect matching found"); + check(perfect == perfect_without_loops, "Wrong perfect matching"); + + if (perfect) { + checkWeightedPerfectFractionalMatching(graph, weight, mwpfm, false); + } + } + + } + + return 0; +} Index: test/gomory_hu_test.cc =================================================================== --- test/gomory_hu_test.cc (revision 1083) +++ test/gomory_hu_test.cc (revision 1084) @@ -1,2 +1,20 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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 @@ -34,5 +52,5 @@ "source 0\n" "target 3\n"; - + void checkGomoryHuCompile() { @@ -71,5 +89,5 @@ int cutValue(const Graph& graph, const BoolNodeMap& cut, - const IntEdgeMap& capacity) { + const IntEdgeMap& capacity) { int sum = 0; @@ -109,5 +127,5 @@ int sum=0; for(GomoryHu::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) - sum+=capacity[a]; + sum+=capacity[a]; check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); @@ -120,5 +138,5 @@ } } - + return 0; } Index: test/graph_copy_test.cc =================================================================== --- test/graph_copy_test.cc (revision 893) +++ test/graph_copy_test.cc (revision 1026) @@ -19,4 +19,5 @@ #include #include +#include #include #include @@ -27,4 +28,5 @@ using namespace lemon; +template void digraph_copy_test() { const int nn = 10; @@ -52,17 +54,17 @@ } } - + // Test digraph copy - ListDigraph to; - ListDigraph::NodeMap tnm(to); - ListDigraph::ArcMap tam(to); - ListDigraph::Node tn; - ListDigraph::Arc ta; - - SmartDigraph::NodeMap nr(from); - SmartDigraph::ArcMap er(from); - - ListDigraph::NodeMap ncr(to); - ListDigraph::ArcMap ecr(to); + GR to; + typename GR::template NodeMap tnm(to); + typename GR::template ArcMap tam(to); + typename GR::Node tn; + typename GR::Arc ta; + + SmartDigraph::NodeMap nr(from); + SmartDigraph::ArcMap er(from); + + typename GR::template NodeMap ncr(to); + typename GR::template ArcMap ecr(to); digraphCopy(from, to). @@ -87,9 +89,9 @@ } - for (ListDigraph::NodeIt it(to); it != INVALID; ++it) { + for (typename GR::NodeIt it(to); it != INVALID; ++it) { check(nr[ncr[it]] == it, "Wrong copy."); } - for (ListDigraph::ArcIt it(to); it != INVALID; ++it) { + for (typename GR::ArcIt it(to); it != INVALID; ++it) { check(er[ecr[it]] == it, "Wrong copy."); } @@ -104,4 +106,5 @@ } +template void graph_copy_test() { const int nn = 10; @@ -136,19 +139,19 @@ // Test graph copy - ListGraph to; - ListGraph::NodeMap tnm(to); - ListGraph::ArcMap tam(to); - ListGraph::EdgeMap tem(to); - ListGraph::Node tn; - ListGraph::Arc ta; - ListGraph::Edge te; - - SmartGraph::NodeMap nr(from); - SmartGraph::ArcMap ar(from); - SmartGraph::EdgeMap er(from); - - ListGraph::NodeMap ncr(to); - ListGraph::ArcMap acr(to); - ListGraph::EdgeMap ecr(to); + GR to; + typename GR::template NodeMap tnm(to); + typename GR::template ArcMap tam(to); + typename GR::template EdgeMap tem(to); + typename GR::Node tn; + typename GR::Arc ta; + typename GR::Edge te; + + SmartGraph::NodeMap nr(from); + SmartGraph::ArcMap ar(from); + SmartGraph::EdgeMap er(from); + + typename GR::template NodeMap ncr(to); + typename GR::template ArcMap acr(to); + typename GR::template EdgeMap ecr(to); graphCopy(from, to). @@ -185,12 +188,12 @@ } - for (ListGraph::NodeIt it(to); it != INVALID; ++it) { + for (typename GR::NodeIt it(to); it != INVALID; ++it) { check(nr[ncr[it]] == it, "Wrong copy."); } - for (ListGraph::ArcIt it(to); it != INVALID; ++it) { + for (typename GR::ArcIt it(to); it != INVALID; ++it) { check(ar[acr[it]] == it, "Wrong copy."); } - for (ListGraph::EdgeIt it(to); it != INVALID; ++it) { + for (typename GR::EdgeIt it(to); it != INVALID; ++it) { check(er[ecr[it]] == it, "Wrong copy."); } @@ -207,8 +210,178 @@ } +template +void bpgraph_copy_test() { + const int nn = 10; + + // Build a graph + SmartBpGraph from; + SmartBpGraph::NodeMap fnm(from); + SmartBpGraph::RedNodeMap frnm(from); + SmartBpGraph::BlueNodeMap fbnm(from); + SmartBpGraph::ArcMap fam(from); + SmartBpGraph::EdgeMap fem(from); + SmartBpGraph::Node fn = INVALID; + SmartBpGraph::RedNode frn = INVALID; + SmartBpGraph::BlueNode fbn = INVALID; + SmartBpGraph::Arc fa = INVALID; + SmartBpGraph::Edge fe = INVALID; + + std::vector frnv; + for (int i = 0; i < nn; ++i) { + SmartBpGraph::RedNode node = from.addRedNode(); + frnv.push_back(node); + fnm[node] = i * i; + frnm[node] = i + i; + if (i == 0) { + fn = node; + frn = node; + } + } + + std::vector fbnv; + for (int i = 0; i < nn; ++i) { + SmartBpGraph::BlueNode node = from.addBlueNode(); + fbnv.push_back(node); + fnm[node] = i * i; + fbnm[node] = i + i; + if (i == 0) fbn = node; + } + + for (int i = 0; i < nn; ++i) { + for (int j = 0; j < nn; ++j) { + SmartBpGraph::Edge edge = from.addEdge(frnv[i], fbnv[j]); + fem[edge] = i * i + j * j; + fam[from.direct(edge, true)] = i + j * j; + fam[from.direct(edge, false)] = i * i + j; + if (i == 0 && j == 0) fa = from.direct(edge, true); + if (i == 0 && j == 0) fe = edge; + } + } + + // Test graph copy + GR to; + typename GR::template NodeMap tnm(to); + typename GR::template RedNodeMap trnm(to); + typename GR::template BlueNodeMap tbnm(to); + typename GR::template ArcMap tam(to); + typename GR::template EdgeMap tem(to); + typename GR::Node tn; + typename GR::RedNode trn; + typename GR::BlueNode tbn; + typename GR::Arc ta; + typename GR::Edge te; + + SmartBpGraph::NodeMap nr(from); + SmartBpGraph::RedNodeMap rnr(from); + SmartBpGraph::BlueNodeMap bnr(from); + SmartBpGraph::ArcMap ar(from); + SmartBpGraph::EdgeMap er(from); + + typename GR::template NodeMap ncr(to); + typename GR::template RedNodeMap rncr(to); + typename GR::template BlueNodeMap bncr(to); + typename GR::template ArcMap acr(to); + typename GR::template EdgeMap ecr(to); + + bpGraphCopy(from, to). + nodeMap(fnm, tnm). + redNodeMap(frnm, trnm).blueNodeMap(fbnm, tbnm). + arcMap(fam, tam).edgeMap(fem, tem). + nodeRef(nr).redRef(rnr).blueRef(bnr). + arcRef(ar).edgeRef(er). + nodeCrossRef(ncr).redCrossRef(rncr).blueCrossRef(bncr). + arcCrossRef(acr).edgeCrossRef(ecr). + node(fn, tn).redNode(frn, trn).blueNode(fbn, tbn). + arc(fa, ta).edge(fe, te).run(); + + check(countNodes(from) == countNodes(to), "Wrong copy."); + check(countRedNodes(from) == countRedNodes(to), "Wrong copy."); + check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy."); + check(countEdges(from) == countEdges(to), "Wrong copy."); + check(countArcs(from) == countArcs(to), "Wrong copy."); + + for (SmartBpGraph::NodeIt it(from); it != INVALID; ++it) { + check(ncr[nr[it]] == it, "Wrong copy."); + check(fnm[it] == tnm[nr[it]], "Wrong copy."); + } + + for (SmartBpGraph::RedNodeIt it(from); it != INVALID; ++it) { + check(ncr[nr[it]] == it, "Wrong copy."); + check(fnm[it] == tnm[nr[it]], "Wrong copy."); + check(rnr[it] == nr[it], "Wrong copy."); + check(rncr[rnr[it]] == it, "Wrong copy."); + check(frnm[it] == trnm[rnr[it]], "Wrong copy."); + check(to.red(rnr[it]), "Wrong copy."); + } + + for (SmartBpGraph::BlueNodeIt it(from); it != INVALID; ++it) { + check(ncr[nr[it]] == it, "Wrong copy."); + check(fnm[it] == tnm[nr[it]], "Wrong copy."); + check(bnr[it] == nr[it], "Wrong copy."); + check(bncr[bnr[it]] == it, "Wrong copy."); + check(fbnm[it] == tbnm[bnr[it]], "Wrong copy."); + check(to.blue(bnr[it]), "Wrong copy."); + } + + for (SmartBpGraph::ArcIt it(from); it != INVALID; ++it) { + check(acr[ar[it]] == it, "Wrong copy."); + check(fam[it] == tam[ar[it]], "Wrong copy."); + check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy."); + check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy."); + } + + for (SmartBpGraph::EdgeIt it(from); it != INVALID; ++it) { + check(ecr[er[it]] == it, "Wrong copy."); + check(fem[it] == tem[er[it]], "Wrong copy."); + check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]), + "Wrong copy."); + check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]), + "Wrong copy."); + check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])), + "Wrong copy."); + } + + for (typename GR::NodeIt it(to); it != INVALID; ++it) { + check(nr[ncr[it]] == it, "Wrong copy."); + } + for (typename GR::RedNodeIt it(to); it != INVALID; ++it) { + check(rncr[it] == ncr[it], "Wrong copy."); + check(rnr[rncr[it]] == it, "Wrong copy."); + } + for (typename GR::BlueNodeIt it(to); it != INVALID; ++it) { + check(bncr[it] == ncr[it], "Wrong copy."); + check(bnr[bncr[it]] == it, "Wrong copy."); + } + for (typename GR::ArcIt it(to); it != INVALID; ++it) { + check(ar[acr[it]] == it, "Wrong copy."); + } + for (typename GR::EdgeIt it(to); it != INVALID; ++it) { + check(er[ecr[it]] == it, "Wrong copy."); + } + check(tn == nr[fn], "Wrong copy."); + check(trn == rnr[frn], "Wrong copy."); + check(tbn == bnr[fbn], "Wrong copy."); + check(ta == ar[fa], "Wrong copy."); + check(te == er[fe], "Wrong copy."); + + // Test repeated copy + bpGraphCopy(from, to).run(); + + check(countNodes(from) == countNodes(to), "Wrong copy."); + check(countRedNodes(from) == countRedNodes(to), "Wrong copy."); + check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy."); + check(countEdges(from) == countEdges(to), "Wrong copy."); + check(countArcs(from) == countArcs(to), "Wrong copy."); +} + int main() { - digraph_copy_test(); - graph_copy_test(); + digraph_copy_test(); + digraph_copy_test(); + digraph_copy_test(); + graph_copy_test(); + graph_copy_test(); + bpgraph_copy_test(); + bpgraph_copy_test(); return 0; Index: test/graph_test.cc =================================================================== --- test/graph_test.cc (revision 1083) +++ test/graph_test.cc (revision 1084) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -39,4 +39,7 @@ checkGraphArcList(G, 0); + G.reserveNode(3); + G.reserveEdge(3); + Node n1 = G.addNode(), @@ -261,8 +264,17 @@ snapshot.restore(); + snapshot.save(G); checkGraphNodeList(G, 4); checkGraphEdgeList(G, 3); checkGraphArcList(G, 6); + + G.addEdge(G.addNode(), G.addNode()); + + snapshot.restore(); + + checkGraphNodeList(G, 4); + checkGraphEdgeList(G, 3); + checkGraphArcList(G, 6); } @@ -272,4 +284,11 @@ Graph G(num); + check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2, + "Wrong size"); + + G.resize(num); + check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2, + "Wrong size"); + checkGraphNodeList(G, num); checkGraphEdgeList(G, num * (num - 1) / 2); @@ -417,4 +436,8 @@ check(G.height() == height, "Wrong row number"); + G.resize(width, height); + check(G.width() == width, "Wrong column number"); + check(G.height() == height, "Wrong row number"); + for (int i = 0; i < width; ++i) { for (int j = 0; j < height; ++j) { @@ -492,4 +515,9 @@ HypercubeGraph G(dim); + check(G.dimension() == dim, "Wrong dimension"); + + G.resize(dim); + check(G.dimension() == dim, "Wrong dimension"); + checkGraphNodeList(G, 1 << dim); checkGraphEdgeList(G, dim * (1 << (dim-1))); Index: test/graph_test.h =================================================================== --- test/graph_test.h (revision 440) +++ test/graph_test.h (revision 1027) @@ -42,4 +42,40 @@ template + void checkGraphRedNodeList(const Graph &G, int cnt) + { + typename Graph::RedNodeIt n(G); + for(int i=0;i + void checkGraphBlueNodeList(const Graph &G, int cnt) + { + typename Graph::BlueNodeIt n(G); + for(int i=0;i void checkGraphArcList(const Graph &G, int cnt) { @@ -167,4 +203,5 @@ template void checkNodeIds(const Graph& G) { + typedef typename Graph::Node Node; std::set values; for (typename Graph::NodeIt n(G); n != INVALID; ++n) { @@ -174,8 +211,36 @@ values.insert(G.id(n)); } + check(G.maxId(Node()) <= G.maxNodeId(), "Wrong maximum id"); + } + + template + void checkRedNodeIds(const Graph& G) { + typedef typename Graph::RedNode RedNode; + std::set values; + for (typename Graph::RedNodeIt n(G); n != INVALID; ++n) { + check(G.red(n), "Wrong partition"); + check(values.find(G.id(n)) == values.end(), "Wrong id"); + check(G.id(n) <= G.maxRedId(), "Wrong maximum id"); + values.insert(G.id(n)); + } + check(G.maxId(RedNode()) == G.maxRedId(), "Wrong maximum id"); + } + + template + void checkBlueNodeIds(const Graph& G) { + typedef typename Graph::BlueNode BlueNode; + std::set values; + for (typename Graph::BlueNodeIt n(G); n != INVALID; ++n) { + check(G.blue(n), "Wrong partition"); + check(values.find(G.id(n)) == values.end(), "Wrong id"); + check(G.id(n) <= G.maxBlueId(), "Wrong maximum id"); + values.insert(G.id(n)); + } + check(G.maxId(BlueNode()) == G.maxBlueId(), "Wrong maximum id"); } template void checkArcIds(const Graph& G) { + typedef typename Graph::Arc Arc; std::set values; for (typename Graph::ArcIt a(G); a != INVALID; ++a) { @@ -185,8 +250,10 @@ values.insert(G.id(a)); } + check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id"); } template void checkEdgeIds(const Graph& G) { + typedef typename Graph::Edge Edge; std::set values; for (typename Graph::EdgeIt e(G); e != INVALID; ++e) { @@ -196,4 +263,5 @@ values.insert(G.id(e)); } + check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id"); } @@ -229,4 +297,64 @@ template + void checkGraphRedNodeMap(const Graph& G) { + typedef typename Graph::Node Node; + typedef typename Graph::RedNodeIt RedNodeIt; + + typedef typename Graph::template RedNodeMap IntRedNodeMap; + IntRedNodeMap map(G, 42); + for (RedNodeIt it(G); it != INVALID; ++it) { + check(map[it] == 42, "Wrong map constructor."); + } + int s = 0; + for (RedNodeIt it(G); it != INVALID; ++it) { + map[it] = 0; + check(map[it] == 0, "Wrong operator[]."); + map.set(it, s); + check(map[it] == s, "Wrong set."); + ++s; + } + s = s * (s - 1) / 2; + for (RedNodeIt it(G); it != INVALID; ++it) { + s -= map[it]; + } + check(s == 0, "Wrong sum."); + + // map = constMap(12); + // for (NodeIt it(G); it != INVALID; ++it) { + // check(map[it] == 12, "Wrong operator[]."); + // } + } + + template + void checkGraphBlueNodeMap(const Graph& G) { + typedef typename Graph::Node Node; + typedef typename Graph::BlueNodeIt BlueNodeIt; + + typedef typename Graph::template BlueNodeMap IntBlueNodeMap; + IntBlueNodeMap map(G, 42); + for (BlueNodeIt it(G); it != INVALID; ++it) { + check(map[it] == 42, "Wrong map constructor."); + } + int s = 0; + for (BlueNodeIt it(G); it != INVALID; ++it) { + map[it] = 0; + check(map[it] == 0, "Wrong operator[]."); + map.set(it, s); + check(map[it] == s, "Wrong set."); + ++s; + } + s = s * (s - 1) / 2; + for (BlueNodeIt it(G); it != INVALID; ++it) { + s -= map[it]; + } + check(s == 0, "Wrong sum."); + + // map = constMap(12); + // for (NodeIt it(G); it != INVALID; ++it) { + // check(map[it] == 12, "Wrong operator[]."); + // } + } + + template void checkGraphArcMap(const Graph& G) { typedef typename Graph::Arc Arc; Index: test/hao_orlin_test.cc =================================================================== --- test/hao_orlin_test.cc (revision 1083) +++ test/hao_orlin_test.cc (revision 1084) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -85,5 +85,5 @@ template -typename CapMap::Value +typename CapMap::Value cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) { @@ -112,5 +112,5 @@ ho.run(); ho.minCutMap(cut); - + check(ho.minCutValue() == 1, "Wrong cut value"); check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); @@ -128,17 +128,17 @@ ho.run(); ho.minCutMap(cut); - + check(ho.minCutValue() == 1, "Wrong cut value"); check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); } - + typedef Undirector UGraph; UGraph ugraph(graph); - + { HaoOrlin > ho(ugraph, cap1); ho.run(); ho.minCutMap(cut); - + check(ho.minCutValue() == 2, "Wrong cut value"); check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); @@ -148,5 +148,5 @@ ho.run(); ho.minCutMap(cut); - + check(ho.minCutValue() == 5, "Wrong cut value"); check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); @@ -156,5 +156,5 @@ ho.run(); ho.minCutMap(cut); - + check(ho.minCutValue() == 5, "Wrong cut value"); check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); Index: test/heap_test.cc =================================================================== --- test/heap_test.cc (revision 681) +++ test/heap_test.cc (revision 948) @@ -26,5 +26,4 @@ #include - #include #include @@ -32,6 +31,10 @@ #include +#include +#include #include +#include #include +#include #include @@ -90,9 +93,7 @@ void heapSortTest() { RangeMap map(test_len, -1); - Heap heap(map); std::vector v(test_len); - for (int i = 0; i < test_len; ++i) { v[i] = test_seq[i]; @@ -101,5 +102,5 @@ std::sort(v.begin(), v.end()); for (int i = 0; i < test_len; ++i) { - check(v[i] == heap.prio() ,"Wrong order in heap sort."); + check(v[i] == heap.prio(), "Wrong order in heap sort."); heap.pop(); } @@ -113,5 +114,4 @@ std::vector v(test_len); - for (int i = 0; i < test_len; ++i) { v[i] = test_seq[i]; @@ -124,10 +124,8 @@ std::sort(v.begin(), v.end()); for (int i = 0; i < test_len; ++i) { - check(v[i] == heap.prio() ,"Wrong order in heap increase test."); + check(v[i] == heap.prio(), "Wrong order in heap increase test."); heap.pop(); } } - - template @@ -145,5 +143,5 @@ if (dijkstra.reached(s)) { check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], - "Error in a shortest path tree!"); + "Error in shortest path tree."); } } @@ -154,5 +152,5 @@ Node s = digraph.source(a); check( dijkstra.dist(n) - dijkstra.dist(s) == length[a], - "Error in a shortest path tree!"); + "Error in shortest path tree."); } } @@ -176,4 +174,5 @@ run(); + // BinHeap { typedef BinHeap IntHeap; @@ -185,4 +184,91 @@ checkConcept, NodeHeap>(); dijkstraHeapTest(digraph, length, source); + } + + // QuadHeap + { + typedef QuadHeap IntHeap; + checkConcept, IntHeap>(); + heapSortTest(); + heapIncreaseTest(); + + typedef QuadHeap NodeHeap; + checkConcept, NodeHeap>(); + dijkstraHeapTest(digraph, length, source); + } + + // DHeap + { + typedef DHeap IntHeap; + checkConcept, IntHeap>(); + heapSortTest(); + heapIncreaseTest(); + + typedef DHeap NodeHeap; + checkConcept, NodeHeap>(); + dijkstraHeapTest(digraph, length, source); + } + + // FibHeap + { + typedef FibHeap IntHeap; + checkConcept, IntHeap>(); + heapSortTest(); + heapIncreaseTest(); + + typedef FibHeap NodeHeap; + checkConcept, NodeHeap>(); + dijkstraHeapTest(digraph, length, source); + } + + // PairingHeap + { + typedef PairingHeap IntHeap; + checkConcept, IntHeap>(); + heapSortTest(); + heapIncreaseTest(); + + typedef PairingHeap NodeHeap; + checkConcept, NodeHeap>(); + dijkstraHeapTest(digraph, length, source); + } + + // RadixHeap + { + typedef RadixHeap IntHeap; + checkConcept, IntHeap>(); + heapSortTest(); + heapIncreaseTest(); + + typedef RadixHeap NodeHeap; + checkConcept, NodeHeap>(); + dijkstraHeapTest(digraph, length, source); + } + + // BinomialHeap + { + typedef BinomialHeap IntHeap; + checkConcept, IntHeap>(); + heapSortTest(); + heapIncreaseTest(); + + typedef BinomialHeap NodeHeap; + checkConcept, NodeHeap>(); + dijkstraHeapTest(digraph, length, source); + } + + // BucketHeap, SimpleBucketHeap + { + typedef BucketHeap IntHeap; + checkConcept, IntHeap>(); + heapSortTest(); + heapIncreaseTest(); + + typedef BucketHeap NodeHeap; + checkConcept, NodeHeap>(); + dijkstraHeapTest(digraph, length, source); + + typedef SimpleBucketHeap SimpleIntHeap; + heapSortTest(); } Index: test/lgf_reader_writer_test.cc =================================================================== --- test/lgf_reader_writer_test.cc (revision 1030) +++ test/lgf_reader_writer_test.cc (revision 1030) @@ -0,0 +1,578 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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 + +#include "test_tools.h" + +struct ReaderConverter { + int operator()(const std::string& str) const { + return str.length(); + } +}; + +struct WriterConverter { + std::string operator()(int value) const { + return std::string(value, '*'); + } +}; + +void checkDigraphReaderCompile() { + typedef lemon::concepts::ExtendableDigraphComponent< + lemon::concepts::Digraph> Digraph; + Digraph digraph; + Digraph::NodeMap node_map(digraph); + Digraph::ArcMap arc_map(digraph); + Digraph::Node node; + Digraph::Arc arc; + int attr; + + lemon::DigraphReader reader(digraph, "filename"); + reader.nodeMap("node_map", node_map); + reader.nodeMap("node_map", node_map, ReaderConverter()); + reader.arcMap("arc_map", arc_map); + reader.arcMap("arc_map", arc_map, ReaderConverter()); + reader.attribute("attr", attr); + reader.attribute("attr", attr, ReaderConverter()); + reader.node("node", node); + reader.arc("arc", arc); + + reader.nodes("alt_nodes_caption"); + reader.arcs("alt_arcs_caption"); + reader.attributes("alt_attrs_caption"); + + reader.useNodes(node_map); + reader.useNodes(node_map, WriterConverter()); + reader.useArcs(arc_map); + reader.useArcs(arc_map, WriterConverter()); + + reader.skipNodes(); + reader.skipArcs(); + + reader.run(); + + lemon::DigraphReader reader2(digraph, std::cin); +} + +void checkDigraphWriterCompile() { + typedef lemon::concepts::Digraph Digraph; + Digraph digraph; + Digraph::NodeMap node_map(digraph); + Digraph::ArcMap arc_map(digraph); + Digraph::Node node; + Digraph::Arc arc; + int attr; + + lemon::DigraphWriter writer(digraph, "filename"); + writer.nodeMap("node_map", node_map); + writer.nodeMap("node_map", node_map, WriterConverter()); + writer.arcMap("arc_map", arc_map); + writer.arcMap("arc_map", arc_map, WriterConverter()); + writer.attribute("attr", attr); + writer.attribute("attr", attr, WriterConverter()); + writer.node("node", node); + writer.arc("arc", arc); + + writer.nodes("alt_nodes_caption"); + writer.arcs("alt_arcs_caption"); + writer.attributes("alt_attrs_caption"); + + writer.skipNodes(); + writer.skipArcs(); + + writer.run(); +} + +void checkGraphReaderCompile() { + typedef lemon::concepts::ExtendableGraphComponent< + lemon::concepts::Graph> Graph; + Graph graph; + Graph::NodeMap node_map(graph); + Graph::ArcMap arc_map(graph); + Graph::EdgeMap edge_map(graph); + Graph::Node node; + Graph::Arc arc; + Graph::Edge edge; + int attr; + + lemon::GraphReader reader(graph, "filename"); + reader.nodeMap("node_map", node_map); + reader.nodeMap("node_map", node_map, ReaderConverter()); + reader.arcMap("arc_map", arc_map); + reader.arcMap("arc_map", arc_map, ReaderConverter()); + reader.edgeMap("edge_map", edge_map); + reader.edgeMap("edge_map", edge_map, ReaderConverter()); + reader.attribute("attr", attr); + reader.attribute("attr", attr, ReaderConverter()); + reader.node("node", node); + reader.arc("arc", arc); + + reader.nodes("alt_nodes_caption"); + reader.edges("alt_edges_caption"); + reader.attributes("alt_attrs_caption"); + + reader.useNodes(node_map); + reader.useNodes(node_map, WriterConverter()); + reader.useEdges(edge_map); + reader.useEdges(edge_map, WriterConverter()); + + reader.skipNodes(); + reader.skipEdges(); + + reader.run(); + + lemon::GraphReader reader2(graph, std::cin); +} + +void checkGraphWriterCompile() { + typedef lemon::concepts::Graph Graph; + Graph graph; + Graph::NodeMap node_map(graph); + Graph::ArcMap arc_map(graph); + Graph::EdgeMap edge_map(graph); + Graph::Node node; + Graph::Arc arc; + Graph::Edge edge; + int attr; + + lemon::GraphWriter writer(graph, "filename"); + writer.nodeMap("node_map", node_map); + writer.nodeMap("node_map", node_map, WriterConverter()); + writer.arcMap("arc_map", arc_map); + writer.arcMap("arc_map", arc_map, WriterConverter()); + writer.edgeMap("edge_map", edge_map); + writer.edgeMap("edge_map", edge_map, WriterConverter()); + writer.attribute("attr", attr); + writer.attribute("attr", attr, WriterConverter()); + writer.node("node", node); + writer.arc("arc", arc); + writer.edge("edge", edge); + + writer.nodes("alt_nodes_caption"); + writer.edges("alt_edges_caption"); + writer.attributes("alt_attrs_caption"); + + writer.skipNodes(); + writer.skipEdges(); + + writer.run(); + + lemon::GraphWriter writer2(graph, std::cout); +} + +void checkBpGraphReaderCompile() { + typedef lemon::concepts::ExtendableBpGraphComponent< + lemon::concepts::BpGraph> BpGraph; + BpGraph graph; + BpGraph::NodeMap node_map(graph); + BpGraph::RedNodeMap red_node_map(graph); + BpGraph::BlueNodeMap blue_node_map(graph); + BpGraph::ArcMap arc_map(graph); + BpGraph::EdgeMap edge_map(graph); + BpGraph::Node node; + BpGraph::RedNode red_node; + BpGraph::BlueNode blue_node; + BpGraph::Arc arc; + BpGraph::Edge edge; + int attr; + + lemon::BpGraphReader reader(graph, "filename"); + reader.nodeMap("node_map", node_map); + reader.nodeMap("node_map", node_map, ReaderConverter()); + reader.redNodeMap("red_node_map", red_node_map); + reader.redNodeMap("red_node_map", red_node_map, ReaderConverter()); + reader.blueNodeMap("blue_node_map", blue_node_map); + reader.blueNodeMap("blue_node_map", blue_node_map, ReaderConverter()); + reader.arcMap("arc_map", arc_map); + reader.arcMap("arc_map", arc_map, ReaderConverter()); + reader.edgeMap("edge_map", edge_map); + reader.edgeMap("edge_map", edge_map, ReaderConverter()); + reader.attribute("attr", attr); + reader.attribute("attr", attr, ReaderConverter()); + reader.node("node", node); + reader.redNode("red_node", red_node); + reader.blueNode("blue_node", blue_node); + reader.arc("arc", arc); + + reader.nodes("alt_nodes_caption"); + reader.edges("alt_edges_caption"); + reader.attributes("alt_attrs_caption"); + + reader.useNodes(node_map); + reader.useNodes(node_map, WriterConverter()); + reader.useEdges(edge_map); + reader.useEdges(edge_map, WriterConverter()); + + reader.skipNodes(); + reader.skipEdges(); + + reader.run(); + + lemon::BpGraphReader reader2(graph, std::cin); +} + +void checkBpGraphWriterCompile() { + typedef lemon::concepts::BpGraph BpGraph; + BpGraph graph; + BpGraph::NodeMap node_map(graph); + BpGraph::RedNodeMap red_node_map(graph); + BpGraph::BlueNodeMap blue_node_map(graph); + BpGraph::ArcMap arc_map(graph); + BpGraph::EdgeMap edge_map(graph); + BpGraph::Node node; + BpGraph::RedNode red_node; + BpGraph::BlueNode blue_node; + BpGraph::Arc arc; + BpGraph::Edge edge; + int attr; + + lemon::BpGraphWriter writer(graph, "filename"); + writer.nodeMap("node_map", node_map); + writer.nodeMap("node_map", node_map, WriterConverter()); + writer.redNodeMap("red_node_map", red_node_map); + writer.redNodeMap("red_node_map", red_node_map, WriterConverter()); + writer.blueNodeMap("blue_node_map", blue_node_map); + writer.blueNodeMap("blue_node_map", blue_node_map, WriterConverter()); + writer.arcMap("arc_map", arc_map); + writer.arcMap("arc_map", arc_map, WriterConverter()); + writer.edgeMap("edge_map", edge_map); + writer.edgeMap("edge_map", edge_map, WriterConverter()); + writer.attribute("attr", attr); + writer.attribute("attr", attr, WriterConverter()); + writer.node("node", node); + writer.redNode("red_node", red_node); + writer.blueNode("blue_node", blue_node); + writer.arc("arc", arc); + + writer.nodes("alt_nodes_caption"); + writer.edges("alt_edges_caption"); + writer.attributes("alt_attrs_caption"); + + writer.skipNodes(); + writer.skipEdges(); + + writer.run(); + + lemon::BpGraphWriter writer2(graph, std::cout); +} + +void checkDigraphReaderWriter() { + typedef lemon::SmartDigraph Digraph; + Digraph digraph; + Digraph::Node n1 = digraph.addNode(); + Digraph::Node n2 = digraph.addNode(); + Digraph::Node n3 = digraph.addNode(); + + Digraph::Arc a1 = digraph.addArc(n1, n2); + Digraph::Arc a2 = digraph.addArc(n2, n3); + + Digraph::NodeMap node_map(digraph); + node_map[n1] = 11; + node_map[n2] = 12; + node_map[n3] = 13; + + Digraph::ArcMap arc_map(digraph); + arc_map[a1] = 21; + arc_map[a2] = 22; + + int attr = 100; + + std::ostringstream os; + lemon::DigraphWriter writer(digraph, os); + + writer.nodeMap("node_map1", node_map); + writer.nodeMap("node_map2", node_map, WriterConverter()); + writer.arcMap("arc_map1", arc_map); + writer.arcMap("arc_map2", arc_map, WriterConverter()); + writer.node("node", n2); + writer.arc("arc", a1); + writer.attribute("attr1", attr); + writer.attribute("attr2", attr, WriterConverter()); + + writer.run(); + + typedef lemon::ListDigraph ExpDigraph; + ExpDigraph exp_digraph; + ExpDigraph::NodeMap exp_node_map1(exp_digraph); + ExpDigraph::NodeMap exp_node_map2(exp_digraph); + ExpDigraph::ArcMap exp_arc_map1(exp_digraph); + ExpDigraph::ArcMap exp_arc_map2(exp_digraph); + ExpDigraph::Node exp_n2; + ExpDigraph::Arc exp_a1; + int exp_attr1; + int exp_attr2; + + std::istringstream is(os.str()); + lemon::DigraphReader reader(exp_digraph, is); + + reader.nodeMap("node_map1", exp_node_map1); + reader.nodeMap("node_map2", exp_node_map2, ReaderConverter()); + reader.arcMap("arc_map1", exp_arc_map1); + reader.arcMap("arc_map2", exp_arc_map2, ReaderConverter()); + reader.node("node", exp_n2); + reader.arc("arc", exp_a1); + reader.attribute("attr1", exp_attr1); + reader.attribute("attr2", exp_attr2, ReaderConverter()); + + reader.run(); + + check(lemon::countNodes(exp_digraph) == 3, "Wrong number of nodes"); + check(lemon::countArcs(exp_digraph) == 2, "Wrong number of arcs"); + check(exp_node_map1[exp_n2] == 12, "Wrong map value"); + check(exp_node_map2[exp_n2] == 12, "Wrong map value"); + check(exp_arc_map1[exp_a1] == 21, "Wrong map value"); + check(exp_arc_map2[exp_a1] == 21, "Wrong map value"); + check(exp_attr1 == 100, "Wrong attr value"); + check(exp_attr2 == 100, "Wrong attr value"); +} + +void checkGraphReaderWriter() { + typedef lemon::SmartGraph Graph; + Graph graph; + Graph::Node n1 = graph.addNode(); + Graph::Node n2 = graph.addNode(); + Graph::Node n3 = graph.addNode(); + + Graph::Edge e1 = graph.addEdge(n1, n2); + Graph::Edge e2 = graph.addEdge(n2, n3); + + Graph::NodeMap node_map(graph); + node_map[n1] = 11; + node_map[n2] = 12; + node_map[n3] = 13; + + Graph::EdgeMap edge_map(graph); + edge_map[e1] = 21; + edge_map[e2] = 22; + + Graph::ArcMap arc_map(graph); + arc_map[graph.direct(e1, true)] = 211; + arc_map[graph.direct(e1, false)] = 212; + arc_map[graph.direct(e2, true)] = 221; + arc_map[graph.direct(e2, false)] = 222; + + int attr = 100; + + std::ostringstream os; + lemon::GraphWriter writer(graph, os); + + writer.nodeMap("node_map1", node_map); + writer.nodeMap("node_map2", node_map, WriterConverter()); + writer.edgeMap("edge_map1", edge_map); + writer.edgeMap("edge_map2", edge_map, WriterConverter()); + writer.arcMap("arc_map1", arc_map); + writer.arcMap("arc_map2", arc_map, WriterConverter()); + writer.node("node", n2); + writer.edge("edge", e1); + writer.arc("arc", graph.direct(e1, false)); + writer.attribute("attr1", attr); + writer.attribute("attr2", attr, WriterConverter()); + + writer.run(); + + typedef lemon::ListGraph ExpGraph; + ExpGraph exp_graph; + ExpGraph::NodeMap exp_node_map1(exp_graph); + ExpGraph::NodeMap exp_node_map2(exp_graph); + ExpGraph::EdgeMap exp_edge_map1(exp_graph); + ExpGraph::EdgeMap exp_edge_map2(exp_graph); + ExpGraph::ArcMap exp_arc_map1(exp_graph); + ExpGraph::ArcMap exp_arc_map2(exp_graph); + ExpGraph::Node exp_n2; + ExpGraph::Edge exp_e1; + ExpGraph::Arc exp_a1; + int exp_attr1; + int exp_attr2; + + std::istringstream is(os.str()); + lemon::GraphReader reader(exp_graph, is); + + reader.nodeMap("node_map1", exp_node_map1); + reader.nodeMap("node_map2", exp_node_map2, ReaderConverter()); + reader.edgeMap("edge_map1", exp_edge_map1); + reader.edgeMap("edge_map2", exp_edge_map2, ReaderConverter()); + reader.arcMap("arc_map1", exp_arc_map1); + reader.arcMap("arc_map2", exp_arc_map2, ReaderConverter()); + reader.node("node", exp_n2); + reader.edge("edge", exp_e1); + reader.arc("arc", exp_a1); + reader.attribute("attr1", exp_attr1); + reader.attribute("attr2", exp_attr2, ReaderConverter()); + + reader.run(); + + check(lemon::countNodes(exp_graph) == 3, "Wrong number of nodes"); + check(lemon::countEdges(exp_graph) == 2, "Wrong number of edges"); + check(lemon::countArcs(exp_graph) == 4, "Wrong number of arcs"); + check(exp_node_map1[exp_n2] == 12, "Wrong map value"); + check(exp_node_map2[exp_n2] == 12, "Wrong map value"); + check(exp_edge_map1[exp_e1] == 21, "Wrong map value"); + check(exp_edge_map2[exp_e1] == 21, "Wrong map value"); + check(exp_arc_map1[exp_a1] == 212, "Wrong map value"); + check(exp_arc_map2[exp_a1] == 212, "Wrong map value"); + check(exp_attr1 == 100, "Wrong attr value"); + check(exp_attr2 == 100, "Wrong attr value"); +} + +void checkBpGraphReaderWriter() { + typedef lemon::SmartBpGraph Graph; + Graph graph; + Graph::RedNode rn1 = graph.addRedNode(); + Graph::RedNode rn2 = graph.addRedNode(); + Graph::RedNode rn3 = graph.addRedNode(); + Graph::BlueNode bn1 = graph.addBlueNode(); + Graph::BlueNode bn2 = graph.addBlueNode(); + Graph::Node n = bn1; + + Graph::Edge e1 = graph.addEdge(rn1, bn1); + Graph::Edge e2 = graph.addEdge(rn2, bn1); + + Graph::NodeMap node_map(graph); + node_map[rn1] = 11; + node_map[rn2] = 12; + node_map[rn3] = 13; + node_map[bn1] = 14; + node_map[bn2] = 15; + + Graph::NodeMap red_node_map(graph); + red_node_map[rn1] = 411; + red_node_map[rn2] = 412; + red_node_map[rn3] = 413; + + Graph::NodeMap blue_node_map(graph); + blue_node_map[bn1] = 414; + blue_node_map[bn2] = 415; + + Graph::EdgeMap edge_map(graph); + edge_map[e1] = 21; + edge_map[e2] = 22; + + Graph::ArcMap arc_map(graph); + arc_map[graph.direct(e1, true)] = 211; + arc_map[graph.direct(e1, false)] = 212; + arc_map[graph.direct(e2, true)] = 221; + arc_map[graph.direct(e2, false)] = 222; + + int attr = 100; + + std::ostringstream os; + lemon::BpGraphWriter writer(graph, os); + + writer.nodeMap("node_map1", node_map); + writer.nodeMap("node_map2", node_map, WriterConverter()); + writer.nodeMap("red_node_map1", red_node_map); + writer.nodeMap("red_node_map2", red_node_map, WriterConverter()); + writer.nodeMap("blue_node_map1", blue_node_map); + writer.nodeMap("blue_node_map2", blue_node_map, WriterConverter()); + writer.edgeMap("edge_map1", edge_map); + writer.edgeMap("edge_map2", edge_map, WriterConverter()); + writer.arcMap("arc_map1", arc_map); + writer.arcMap("arc_map2", arc_map, WriterConverter()); + writer.node("node", n); + writer.redNode("red_node", rn1); + writer.blueNode("blue_node", bn2); + writer.edge("edge", e1); + writer.arc("arc", graph.direct(e1, false)); + writer.attribute("attr1", attr); + writer.attribute("attr2", attr, WriterConverter()); + + writer.run(); + + typedef lemon::ListBpGraph ExpGraph; + ExpGraph exp_graph; + ExpGraph::NodeMap exp_node_map1(exp_graph); + ExpGraph::NodeMap exp_node_map2(exp_graph); + ExpGraph::RedNodeMap exp_red_node_map1(exp_graph); + ExpGraph::RedNodeMap exp_red_node_map2(exp_graph); + ExpGraph::BlueNodeMap exp_blue_node_map1(exp_graph); + ExpGraph::BlueNodeMap exp_blue_node_map2(exp_graph); + ExpGraph::EdgeMap exp_edge_map1(exp_graph); + ExpGraph::EdgeMap exp_edge_map2(exp_graph); + ExpGraph::ArcMap exp_arc_map1(exp_graph); + ExpGraph::ArcMap exp_arc_map2(exp_graph); + ExpGraph::Node exp_n; + ExpGraph::RedNode exp_rn1; + ExpGraph::BlueNode exp_bn2; + ExpGraph::Edge exp_e1; + ExpGraph::Arc exp_a1; + int exp_attr1; + int exp_attr2; + + std::istringstream is(os.str()); + lemon::BpGraphReader reader(exp_graph, is); + + reader.nodeMap("node_map1", exp_node_map1); + reader.nodeMap("node_map2", exp_node_map2, ReaderConverter()); + reader.redNodeMap("red_node_map1", exp_red_node_map1); + reader.redNodeMap("red_node_map2", exp_red_node_map2, ReaderConverter()); + reader.blueNodeMap("blue_node_map1", exp_blue_node_map1); + reader.blueNodeMap("blue_node_map2", exp_blue_node_map2, ReaderConverter()); + reader.edgeMap("edge_map1", exp_edge_map1); + reader.edgeMap("edge_map2", exp_edge_map2, ReaderConverter()); + reader.arcMap("arc_map1", exp_arc_map1); + reader.arcMap("arc_map2", exp_arc_map2, ReaderConverter()); + reader.node("node", exp_n); + reader.redNode("red_node", exp_rn1); + reader.blueNode("blue_node", exp_bn2); + reader.edge("edge", exp_e1); + reader.arc("arc", exp_a1); + reader.attribute("attr1", exp_attr1); + reader.attribute("attr2", exp_attr2, ReaderConverter()); + + reader.run(); + + check(lemon::countNodes(exp_graph) == 5, "Wrong number of nodes"); + check(lemon::countRedNodes(exp_graph) == 3, "Wrong number of red nodes"); + check(lemon::countBlueNodes(exp_graph) == 2, "Wrong number of blue nodes"); + check(lemon::countEdges(exp_graph) == 2, "Wrong number of edges"); + check(lemon::countArcs(exp_graph) == 4, "Wrong number of arcs"); + check(exp_node_map1[exp_n] == 14, "Wrong map value"); + check(exp_node_map2[exp_n] == 14, "Wrong map value"); + check(exp_red_node_map1[exp_rn1] == 411, "Wrong map value"); + check(exp_red_node_map2[exp_rn1] == 411, "Wrong map value"); + check(exp_blue_node_map1[exp_bn2] == 415, "Wrong map value"); + check(exp_blue_node_map2[exp_bn2] == 415, "Wrong map value"); + check(exp_edge_map1[exp_e1] == 21, "Wrong map value"); + check(exp_edge_map2[exp_e1] == 21, "Wrong map value"); + check(exp_arc_map1[exp_a1] == 212, "Wrong map value"); + check(exp_arc_map2[exp_a1] == 212, "Wrong map value"); + check(exp_attr1 == 100, "Wrong attr value"); + check(exp_attr2 == 100, "Wrong attr value"); +} + + +int main() { + { // Check digrpah + checkDigraphReaderWriter(); + } + { // Check graph + checkGraphReaderWriter(); + } + { // Check bipartite graph + checkBpGraphReaderWriter(); + } + return 0; +} Index: test/maps_test.cc =================================================================== --- test/maps_test.cc (revision 1083) +++ test/maps_test.cc (revision 1086) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -24,4 +24,8 @@ #include #include +#include +#include +#include +#include #include "test_tools.h" @@ -35,7 +39,20 @@ class C { - int x; + int _x; public: - C(int _x) : x(_x) {} + C(int x) : _x(x) {} + int get() const { return _x; } +}; +inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); } +inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); } + +C createC(int x) { return C(x); } + +template +class Less { + T _t; +public: + Less(T t): _t(t) {} + bool operator()(const T& t) const { return t < _t; } }; @@ -53,4 +70,12 @@ int binc(int a, B) { return a+1; } + +template +class Sum { + T& _sum; +public: + Sum(T& sum) : _sum(sum) {} + void operator()(const T& t) { _sum += t; } +}; typedef ReadMap DoubleMap; @@ -349,4 +374,8 @@ { typedef std::vector vec; + checkConcept, LoggerBoolMap >(); + checkConcept, + LoggerBoolMap > >(); + vec v1; vec v2(10); @@ -368,23 +397,241 @@ it != map2.end(); ++it ) check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); - } - - // CrossRefMap - { + typedef ListDigraph Graph; DIGRAPH_TYPEDEFS(Graph); + Graph gr; + + Node n0 = gr.addNode(); + Node n1 = gr.addNode(); + Node n2 = gr.addNode(); + Node n3 = gr.addNode(); + + gr.addArc(n3, n0); + gr.addArc(n3, n2); + gr.addArc(n0, n2); + gr.addArc(n2, n1); + gr.addArc(n0, n1); + + { + std::vector v; + dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run(); + + check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3, + "Something is wrong with LoggerBoolMap"); + } + { + std::vector v(countNodes(gr)); + dfs(gr).processedMap(loggerBoolMap(v.begin())).run(); + + check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3, + "Something is wrong with LoggerBoolMap"); + } + } + + // IdMap, RangeIdMap + { + typedef ListDigraph Graph; + DIGRAPH_TYPEDEFS(Graph); + + checkConcept, IdMap >(); + checkConcept, IdMap >(); + checkConcept, RangeIdMap >(); + checkConcept, RangeIdMap >(); + + Graph gr; + IdMap nmap(gr); + IdMap amap(gr); + RangeIdMap nrmap(gr); + RangeIdMap armap(gr); + + Node n0 = gr.addNode(); + Node n1 = gr.addNode(); + Node n2 = gr.addNode(); + + Arc a0 = gr.addArc(n0, n1); + Arc a1 = gr.addArc(n0, n2); + Arc a2 = gr.addArc(n2, n1); + Arc a3 = gr.addArc(n2, n0); + + check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap"); + check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap"); + check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap"); + + check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap"); + check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap"); + check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap"); + check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap"); + + check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap"); + check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap"); + + check(nrmap.size() == 3 && armap.size() == 4, + "Wrong RangeIdMap::size()"); + + check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap"); + check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap"); + check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap"); + + check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap"); + check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); + check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap"); + check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap"); + + check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap"); + check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap"); + + gr.erase(n1); + + if (nrmap[n0] == 1) nrmap.swap(n0, n2); + nrmap.swap(n2, n0); + if (armap[a1] == 1) armap.swap(a1, a3); + armap.swap(a3, a1); + + check(nrmap.size() == 2 && armap.size() == 2, + "Wrong RangeIdMap::size()"); + + check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap"); + check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap"); + + check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); + check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap"); + + check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap"); + check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap"); + } + + // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap + { + typedef ListGraph Graph; + GRAPH_TYPEDEFS(Graph); + + checkConcept, SourceMap >(); + checkConcept, TargetMap >(); + checkConcept, ForwardMap >(); + checkConcept, BackwardMap >(); + checkConcept, InDegMap >(); + checkConcept, OutDegMap >(); + + Graph gr; + Node n0 = gr.addNode(); + Node n1 = gr.addNode(); + Node n2 = gr.addNode(); + + gr.addEdge(n0,n1); + gr.addEdge(n1,n2); + gr.addEdge(n0,n2); + gr.addEdge(n2,n1); + gr.addEdge(n1,n2); + gr.addEdge(n0,n1); + + for (EdgeIt e(gr); e != INVALID; ++e) { + check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap"); + check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap"); + } + + check(mapCompare(gr, + sourceMap(orienter(gr, constMap(true))), + targetMap(orienter(gr, constMap(false)))), + "Wrong SourceMap or TargetMap"); + + typedef Orienter > Digraph; + ConstMap true_edge_map(true); + Digraph dgr(gr, true_edge_map); + OutDegMap odm(dgr); + InDegMap idm(dgr); + + check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap"); + check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap"); + + gr.addEdge(n2, n0); + + check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap"); + check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap"); + } + + // CrossRefMap + { + typedef ListDigraph Graph; + DIGRAPH_TYPEDEFS(Graph); checkConcept, CrossRefMap >(); - + checkConcept, + CrossRefMap >(); + checkConcept, + CrossRefMap >(); + + Graph gr; + typedef CrossRefMap CRMap; + CRMap map(gr); + + Node n0 = gr.addNode(); + Node n1 = gr.addNode(); + Node n2 = gr.addNode(); + + map.set(n0, 'A'); + map.set(n1, 'B'); + map.set(n2, 'C'); + + check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0, + "Wrong CrossRefMap"); + check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1, + "Wrong CrossRefMap"); + check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2, + "Wrong CrossRefMap"); + check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1, + "Wrong CrossRefMap::count()"); + + CRMap::ValueIt it = map.beginValue(); + check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && + it == map.endValue(), "Wrong value iterator"); + + map.set(n2, 'A'); + + check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A', + "Wrong CrossRefMap"); + check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap"); + check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap"); + check(map('C') == INVALID && map.inverse()['C'] == INVALID, + "Wrong CrossRefMap"); + check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0, + "Wrong CrossRefMap::count()"); + + it = map.beginValue(); + check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' && + it == map.endValue(), "Wrong value iterator"); + + map.set(n0, 'C'); + + check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A', + "Wrong CrossRefMap"); + check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap"); + check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap"); + check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap"); + check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1, + "Wrong CrossRefMap::count()"); + + it = map.beginValue(); + check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && + it == map.endValue(), "Wrong value iterator"); + } + + // CrossRefMap + { + typedef SmartDigraph Graph; + DIGRAPH_TYPEDEFS(Graph); + + checkConcept, + CrossRefMap >(); + Graph gr; typedef CrossRefMap CRMap; typedef CRMap::ValueIterator ValueIt; CRMap map(gr); - + Node n0 = gr.addNode(); Node n1 = gr.addNode(); Node n2 = gr.addNode(); - + map.set(n0, 'A'); map.set(n1, 'B'); @@ -404,4 +651,372 @@ } + // Iterable bool map + { + typedef SmartGraph Graph; + typedef SmartGraph::Node Item; + + typedef IterableBoolMap Ibm; + checkConcept, Ibm>(); + + const int num = 10; + Graph g; + Ibm map0(g, true); + std::vector items; + for (int i = 0; i < num; ++i) { + items.push_back(g.addNode()); + } + + Ibm map1(g, true); + int n = 0; + for (Ibm::TrueIt it(map1); it != INVALID; ++it) { + check(map1[static_cast(it)], "Wrong TrueIt"); + ++n; + } + check(n == num, "Wrong number"); + + n = 0; + for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) { + check(map1[static_cast(it)], "Wrong ItemIt for true"); + ++n; + } + check(n == num, "Wrong number"); + check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt"); + check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false"); + + map1[items[5]] = true; + + n = 0; + for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) { + check(map1[static_cast(it)], "Wrong ItemIt for true"); + ++n; + } + check(n == num, "Wrong number"); + + map1[items[num / 2]] = false; + check(map1[items[num / 2]] == false, "Wrong map value"); + + n = 0; + for (Ibm::TrueIt it(map1); it != INVALID; ++it) { + check(map1[static_cast(it)], "Wrong TrueIt for true"); + ++n; + } + check(n == num - 1, "Wrong number"); + + n = 0; + for (Ibm::FalseIt it(map1); it != INVALID; ++it) { + check(!map1[static_cast(it)], "Wrong FalseIt for true"); + ++n; + } + check(n == 1, "Wrong number"); + + map1[items[0]] = false; + check(map1[items[0]] == false, "Wrong map value"); + + map1[items[num - 1]] = false; + check(map1[items[num - 1]] == false, "Wrong map value"); + + n = 0; + for (Ibm::TrueIt it(map1); it != INVALID; ++it) { + check(map1[static_cast(it)], "Wrong TrueIt for true"); + ++n; + } + check(n == num - 3, "Wrong number"); + check(map1.trueNum() == num - 3, "Wrong number"); + + n = 0; + for (Ibm::FalseIt it(map1); it != INVALID; ++it) { + check(!map1[static_cast(it)], "Wrong FalseIt for true"); + ++n; + } + check(n == 3, "Wrong number"); + check(map1.falseNum() == 3, "Wrong number"); + } + + // Iterable int map + { + typedef SmartGraph Graph; + typedef SmartGraph::Node Item; + typedef IterableIntMap Iim; + + checkConcept, Iim>(); + + const int num = 10; + Graph g; + Iim map0(g, 0); + std::vector items; + for (int i = 0; i < num; ++i) { + items.push_back(g.addNode()); + } + + Iim map1(g); + check(map1.size() == 0, "Wrong size"); + + for (int i = 0; i < num; ++i) { + map1[items[i]] = i; + } + check(map1.size() == num, "Wrong size"); + + for (int i = 0; i < num; ++i) { + Iim::ItemIt it(map1, i); + check(static_cast(it) == items[i], "Wrong value"); + ++it; + check(static_cast(it) == INVALID, "Wrong value"); + } + + for (int i = 0; i < num; ++i) { + map1[items[i]] = i % 2; + } + check(map1.size() == 2, "Wrong size"); + + int n = 0; + for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) { + check(map1[static_cast(it)] == 0, "Wrong value"); + ++n; + } + check(n == (num + 1) / 2, "Wrong number"); + + for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) { + check(map1[static_cast(it)] == 1, "Wrong value"); + ++n; + } + check(n == num, "Wrong number"); + + } + + // Iterable value map + { + typedef SmartGraph Graph; + typedef SmartGraph::Node Item; + typedef IterableValueMap Ivm; + + checkConcept, Ivm>(); + + const int num = 10; + Graph g; + Ivm map0(g, 0.0); + std::vector items; + for (int i = 0; i < num; ++i) { + items.push_back(g.addNode()); + } + + Ivm map1(g, 0.0); + check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size"); + check(*map1.beginValue() == 0.0, "Wrong value"); + + for (int i = 0; i < num; ++i) { + map1.set(items[i], static_cast(i)); + } + check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size"); + + for (int i = 0; i < num; ++i) { + Ivm::ItemIt it(map1, static_cast(i)); + check(static_cast(it) == items[i], "Wrong value"); + ++it; + check(static_cast(it) == INVALID, "Wrong value"); + } + + for (Ivm::ValueIt vit = map1.beginValue(); + vit != map1.endValue(); ++vit) { + check(map1[static_cast(Ivm::ItemIt(map1, *vit))] == *vit, + "Wrong ValueIt"); + } + + for (int i = 0; i < num; ++i) { + map1.set(items[i], static_cast(i % 2)); + } + check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size"); + + int n = 0; + for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) { + check(map1[static_cast(it)] == 0.0, "Wrong value"); + ++n; + } + check(n == (num + 1) / 2, "Wrong number"); + + for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) { + check(map1[static_cast(it)] == 1.0, "Wrong value"); + ++n; + } + check(n == num, "Wrong number"); + + } + + // Graph map utilities: + // mapMin(), mapMax(), mapMinValue(), mapMaxValue() + // mapFind(), mapFindIf(), mapCount(), mapCountIf() + // mapCopy(), mapCompare(), mapFill() + { + DIGRAPH_TYPEDEFS(SmartDigraph); + + SmartDigraph g; + Node n1 = g.addNode(); + Node n2 = g.addNode(); + Node n3 = g.addNode(); + + SmartDigraph::NodeMap map1(g); + SmartDigraph::ArcMap map2(g); + ConstMap cmap1 = A(); + ConstMap cmap2 = C(0); + + map1[n1] = 10; + map1[n2] = 5; + map1[n3] = 12; + + // mapMin(), mapMax(), mapMinValue(), mapMaxValue() + check(mapMin(g, map1) == n2, "Wrong mapMin()"); + check(mapMax(g, map1) == n3, "Wrong mapMax()"); + check(mapMin(g, map1, std::greater()) == n3, "Wrong mapMin()"); + check(mapMax(g, map1, std::greater()) == n2, "Wrong mapMax()"); + check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()"); + check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()"); + + check(mapMin(g, map2) == INVALID, "Wrong mapMin()"); + check(mapMax(g, map2) == INVALID, "Wrong mapMax()"); + + check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()"); + check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()"); + + Arc a1 = g.addArc(n1, n2); + Arc a2 = g.addArc(n1, n3); + Arc a3 = g.addArc(n2, n3); + Arc a4 = g.addArc(n3, n1); + + map2[a1] = 'b'; + map2[a2] = 'a'; + map2[a3] = 'b'; + map2[a4] = 'c'; + + // mapMin(), mapMax(), mapMinValue(), mapMaxValue() + check(mapMin(g, map2) == a2, "Wrong mapMin()"); + check(mapMax(g, map2) == a4, "Wrong mapMax()"); + check(mapMin(g, map2, std::greater()) == a4, "Wrong mapMin()"); + check(mapMax(g, map2, std::greater()) == a2, "Wrong mapMax()"); + check(mapMinValue(g, map2, std::greater()) == 'c', + "Wrong mapMinValue()"); + check(mapMaxValue(g, map2, std::greater()) == 'a', + "Wrong mapMaxValue()"); + + check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()"); + check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()"); + check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()"); + + check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2, + "Wrong mapMin()"); + check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4, + "Wrong mapMax()"); + check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'), + "Wrong mapMinValue()"); + check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'), + "Wrong mapMaxValue()"); + + // mapFind(), mapFindIf() + check(mapFind(g, map1, 5) == n2, "Wrong mapFind()"); + check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()"); + check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()"); + check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()"); + check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()"); + check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()"); + + check(mapFindIf(g, map1, Less(7)) == n2, + "Wrong mapFindIf()"); + check(mapFindIf(g, map1, Less(5)) == INVALID, + "Wrong mapFindIf()"); + check(mapFindIf(g, map2, Less('d')) == ArcIt(g), + "Wrong mapFindIf()"); + check(mapFindIf(g, map2, Less('a')) == INVALID, + "Wrong mapFindIf()"); + + // mapCount(), mapCountIf() + check(mapCount(g, map1, 5) == 1, "Wrong mapCount()"); + check(mapCount(g, map1, 6) == 0, "Wrong mapCount()"); + check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()"); + check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()"); + check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()"); + check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()"); + check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()"); + + check(mapCountIf(g, map1, Less(11)) == 2, + "Wrong mapCountIf()"); + check(mapCountIf(g, map1, Less(13)) == 3, + "Wrong mapCountIf()"); + check(mapCountIf(g, map1, Less(5)) == 0, + "Wrong mapCountIf()"); + check(mapCountIf(g, map2, Less('d')) == 4, + "Wrong mapCountIf()"); + check(mapCountIf(g, map2, Less('c')) == 3, + "Wrong mapCountIf()"); + check(mapCountIf(g, map2, Less('a')) == 0, + "Wrong mapCountIf()"); + + // MapIt, ConstMapIt +/* +These tests can be used after applying bugfix #330 + typedef SmartDigraph::NodeMap::MapIt MapIt; + typedef SmartDigraph::NodeMap::ConstMapIt ConstMapIt; + check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5, + "Wrong NodeMap<>::MapIt"); + check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12, + "Wrong NodeMap<>::MapIt"); + + int sum = 0; + std::for_each(MapIt(map1), MapIt(INVALID), Sum(sum)); + check(sum == 27, "Wrong NodeMap<>::MapIt"); + std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum(sum)); + check(sum == 54, "Wrong NodeMap<>::ConstMapIt"); +*/ + + // mapCopy(), mapCompare(), mapFill() + check(mapCompare(g, map1, map1), "Wrong mapCompare()"); + check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()"); + check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()"); + check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()"); + check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()"); + + SmartDigraph::NodeMap map3(g, 0); + SmartDigraph::ArcMap map4(g, 'a'); + + check(!mapCompare(g, map1, map3), "Wrong mapCompare()"); + check(!mapCompare(g, map2, map4), "Wrong mapCompare()"); + + mapCopy(g, map1, map3); + mapCopy(g, map2, map4); + + check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()"); + check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()"); + + Undirector ug(g); + Undirector::EdgeMap umap1(ug, 'x'); + Undirector::ArcMap umap2(ug, 3.14); + + check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()"); + check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()"); + check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()"); + check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()"); + + mapCopy(g, map2, umap1); + + check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()"); + check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()"); + check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()"); + check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()"); + + mapCopy(g, map2, umap1); + mapCopy(g, umap1, map2); + mapCopy(ug, map2, umap1); + mapCopy(ug, umap1, map2); + + check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()"); + mapCopy(ug, umap1, umap2); + check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()"); + + check(!mapCompare(g, map1, constMap(2)), "Wrong mapCompare()"); + mapFill(g, map1, 2); + check(mapCompare(g, constMap(2), map1), "Wrong mapFill()"); + + check(!mapCompare(g, map2, constMap('z')), "Wrong mapCompare()"); + mapCopy(g, constMap('z'), map2); + check(mapCompare(g, constMap('z'), map2), "Wrong mapCopy()"); + } + return 0; } Index: test/matching_test.cc =================================================================== --- test/matching_test.cc (revision 1083) +++ test/matching_test.cc (revision 1084) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -135,5 +135,5 @@ mat_test.startDense(); mat_test.run(); - + const_mat_test.matchingSize(); const_mat_test.matching(e); @@ -144,5 +144,5 @@ const_mat_test.mate(n); - MaxMatching::Status stat = + MaxMatching::Status stat = const_mat_test.status(n); ::lemon::ignore_unused_variable_warning(stat); @@ -172,5 +172,5 @@ mat_test.start(); mat_test.run(); - + const_mat_test.matchingWeight(); const_mat_test.matchingSize(); @@ -181,5 +181,5 @@ e = mmap[n]; const_mat_test.mate(n); - + int k = 0; const_mat_test.dualValue(); @@ -209,5 +209,5 @@ mat_test.start(); mat_test.run(); - + const_mat_test.matchingWeight(); const_mat_test.matching(e); @@ -217,5 +217,5 @@ e = mmap[n]; const_mat_test.mate(n); - + int k = 0; const_mat_test.dualValue(); @@ -403,20 +403,44 @@ edgeMap("weight", weight).run(); - MaxMatching mm(graph); - mm.run(); - checkMatching(graph, mm); - - MaxWeightedMatching mwm(graph, weight); - mwm.run(); - checkWeightedMatching(graph, weight, mwm); - - MaxWeightedPerfectMatching mwpm(graph, weight); - bool perfect = mwpm.run(); - - check(perfect == (mm.matchingSize() * 2 == countNodes(graph)), - "Perfect matching found"); - - if (perfect) { - checkWeightedPerfectMatching(graph, weight, mwpm); + bool perfect; + { + MaxMatching mm(graph); + mm.run(); + checkMatching(graph, mm); + perfect = 2 * mm.matchingSize() == countNodes(graph); + } + + { + MaxWeightedMatching mwm(graph, weight); + mwm.run(); + checkWeightedMatching(graph, weight, mwm); + } + + { + MaxWeightedMatching mwm(graph, weight); + mwm.init(); + mwm.start(); + checkWeightedMatching(graph, weight, mwm); + } + + { + MaxWeightedPerfectMatching mwpm(graph, weight); + bool result = mwpm.run(); + + check(result == perfect, "Perfect matching found"); + if (perfect) { + checkWeightedPerfectMatching(graph, weight, mwpm); + } + } + + { + MaxWeightedPerfectMatching mwpm(graph, weight); + mwpm.init(); + bool result = mwpm.start(); + + check(result == perfect, "Perfect matching found"); + if (perfect) { + checkWeightedPerfectMatching(graph, weight, mwpm); + } } } Index: test/max_cardinality_search_test.cc =================================================================== --- test/max_cardinality_search_test.cc (revision 955) +++ test/max_cardinality_search_test.cc (revision 955) @@ -0,0 +1,162 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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 "test_tools.h" +#include +#include +#include +#include +#include +#include + +using namespace lemon; +using namespace std; + +char test_lgf[] = + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "@arcs\n" + " label capacity\n" + "0 1 0 2\n" + "1 0 1 2\n" + "2 1 2 1\n" + "2 3 3 3\n" + "3 2 4 3\n" + "3 1 5 5\n" + "@attributes\n" + "s 0\n" + "x 1\n" + "y 2\n" + "z 3\n"; + +void checkMaxCardSearchCompile() { + + typedef concepts::Digraph Digraph; + typedef int Value; + typedef Digraph::Node Node; + typedef Digraph::Arc Arc; + typedef concepts::ReadMap CapMap; + typedef concepts::ReadWriteMap CardMap; + typedef concepts::ReadWriteMap ProcMap; + typedef Digraph::NodeMap HeapCrossRef; + + Digraph g; + Node n,s; + CapMap cap; + CardMap card; + ProcMap proc; + HeapCrossRef crossref(g); + + typedef MaxCardinalitySearch + ::SetCapacityMap + ::SetCardinalityMap + ::SetProcessedMap + ::SetStandardHeap > + ::Create MaxCardType; + + MaxCardType maxcard(g,cap); + const MaxCardType& const_maxcard = maxcard; + + const MaxCardType::Heap& heap_const = const_maxcard.heap(); + MaxCardType::Heap& heap = const_cast(heap_const); + maxcard.heap(heap,crossref); + + maxcard.capacityMap(cap).cardinalityMap(card).processedMap(proc); + + maxcard.init(); + maxcard.addSource(s); + n = maxcard.nextNode(); + maxcard.processNextNode(); + maxcard.start(); + maxcard.run(s); + maxcard.run(); + } + + void checkWithIntMap( std::istringstream& input) + { + typedef SmartDigraph Digraph; + typedef Digraph::Node Node; + typedef Digraph::ArcMap CapMap; + + Digraph g; + Node s,x,y,z,a; + CapMap cap(g); + + DigraphReader(g,input). + arcMap("capacity", cap). + node("s",s). + node("x",x). + node("y",y). + node("z",z). + run(); + + MaxCardinalitySearch maxcard(g,cap); + + maxcard.init(); + maxcard.addSource(s); + maxcard.start(x); + + check(maxcard.processed(s) && !maxcard.processed(x) && + !maxcard.processed(y), "Wrong processed()!"); + + a=maxcard.nextNode(); + check(maxcard.processNextNode()==a, + "Wrong nextNode() or processNextNode() return value!"); + + check(maxcard.processed(a), "Wrong processNextNode()!"); + + maxcard.start(); + check(maxcard.cardinality(x)==2 && maxcard.cardinality(y)>=4, + "Wrong cardinalities!"); + } + + void checkWithConst1Map(std::istringstream &input) { + typedef SmartDigraph Digraph; + typedef Digraph::Node Node; + + Digraph g; + Node s,x,y,z; + + DigraphReader(g,input). + node("s",s). + node("x",x). + node("y",y). + node("z",z). + run(); + + MaxCardinalitySearch maxcard(g); + maxcard.run(s); + check(maxcard.cardinality(x)==1 && + maxcard.cardinality(y)+maxcard.cardinality(z)==3, + "Wrong cardinalities!"); +} + +int main() { + + std::istringstream input1(test_lgf); + checkWithIntMap(input1); + + std::istringstream input2(test_lgf); + checkWithConst1Map(input2); +} Index: test/max_clique_test.cc =================================================================== --- test/max_clique_test.cc (revision 918) +++ test/max_clique_test.cc (revision 918) @@ -0,0 +1,188 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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 "test_tools.h" + +using namespace lemon; + +char test_lgf[] = + "@nodes\n" + "label max_clique\n" + "1 0\n" + "2 0\n" + "3 0\n" + "4 1\n" + "5 1\n" + "6 1\n" + "7 1\n" + "@edges\n" + " label\n" + "1 2 1\n" + "1 3 2\n" + "1 4 3\n" + "1 6 4\n" + "2 3 5\n" + "2 5 6\n" + "2 7 7\n" + "3 4 8\n" + "3 5 9\n" + "4 5 10\n" + "4 6 11\n" + "4 7 12\n" + "5 6 13\n" + "5 7 14\n" + "6 7 15\n"; + + +// Check with general graphs +template +void checkMaxCliqueGeneral(Param rule) { + typedef ListGraph GR; + typedef GrossoLocatelliPullanMc McAlg; + typedef McAlg::CliqueNodeIt CliqueIt; + + // Basic tests + { + GR g; + GR::NodeMap map(g); + McAlg mc(g); + mc.iterationLimit(50); + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause"); + check(mc.cliqueSize() == 0, "Wrong clique size"); + check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt"); + + GR::Node u = g.addNode(); + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause"); + check(mc.cliqueSize() == 1, "Wrong clique size"); + mc.cliqueMap(map); + check(map[u], "Wrong clique map"); + CliqueIt it1(mc); + check(static_cast(it1) == u && ++it1 == INVALID, + "Wrong CliqueNodeIt"); + + GR::Node v = g.addNode(); + check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause"); + check(mc.cliqueSize() == 1, "Wrong clique size"); + mc.cliqueMap(map); + check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map"); + CliqueIt it2(mc); + check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt"); + + g.addEdge(u, v); + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause"); + check(mc.cliqueSize() == 2, "Wrong clique size"); + mc.cliqueMap(map); + check(map[u] && map[v], "Wrong clique map"); + CliqueIt it3(mc); + check(it3 != INVALID && ++it3 != INVALID && ++it3 == INVALID, + "Wrong CliqueNodeIt"); + } + + // Test graph + { + GR g; + GR::NodeMap max_clique(g); + GR::NodeMap map(g); + std::istringstream input(test_lgf); + graphReader(g, input) + .nodeMap("max_clique", max_clique) + .run(); + + McAlg mc(g); + mc.iterationLimit(50); + check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause"); + check(mc.cliqueSize() == 4, "Wrong clique size"); + mc.cliqueMap(map); + for (GR::NodeIt n(g); n != INVALID; ++n) { + check(map[n] == max_clique[n], "Wrong clique map"); + } + int cnt = 0; + for (CliqueIt n(mc); n != INVALID; ++n) { + cnt++; + check(map[n] && max_clique[n], "Wrong CliqueNodeIt"); + } + check(cnt == 4, "Wrong CliqueNodeIt"); + } +} + +// Check with full graphs +template +void checkMaxCliqueFullGraph(Param rule) { + typedef FullGraph GR; + typedef GrossoLocatelliPullanMc McAlg; + typedef McAlg::CliqueNodeIt CliqueIt; + + for (int size = 0; size <= 40; size = size * 3 + 1) { + GR g(size); + GR::NodeMap map(g); + McAlg mc(g); + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause"); + check(mc.cliqueSize() == size, "Wrong clique size"); + mc.cliqueMap(map); + for (GR::NodeIt n(g); n != INVALID; ++n) { + check(map[n], "Wrong clique map"); + } + int cnt = 0; + for (CliqueIt n(mc); n != INVALID; ++n) cnt++; + check(cnt == size, "Wrong CliqueNodeIt"); + } +} + +// Check with grid graphs +template +void checkMaxCliqueGridGraph(Param rule) { + GridGraph g(5, 7); + GridGraph::NodeMap map(g); + GrossoLocatelliPullanMc mc(g); + + mc.iterationLimit(100); + check(mc.run(rule) == mc.ITERATION_LIMIT, "Wrong termination cause"); + check(mc.cliqueSize() == 2, "Wrong clique size"); + + mc.stepLimit(100); + check(mc.run(rule) == mc.STEP_LIMIT, "Wrong termination cause"); + check(mc.cliqueSize() == 2, "Wrong clique size"); + + mc.sizeLimit(2); + check(mc.run(rule) == mc.SIZE_LIMIT, "Wrong termination cause"); + check(mc.cliqueSize() == 2, "Wrong clique size"); +} + + +int main() { + checkMaxCliqueGeneral(GrossoLocatelliPullanMc::RANDOM); + checkMaxCliqueGeneral(GrossoLocatelliPullanMc::DEGREE_BASED); + checkMaxCliqueGeneral(GrossoLocatelliPullanMc::PENALTY_BASED); + + checkMaxCliqueFullGraph(GrossoLocatelliPullanMc::RANDOM); + checkMaxCliqueFullGraph(GrossoLocatelliPullanMc::DEGREE_BASED); + checkMaxCliqueFullGraph(GrossoLocatelliPullanMc::PENALTY_BASED); + + checkMaxCliqueGridGraph(GrossoLocatelliPullanMc::RANDOM); + checkMaxCliqueGridGraph(GrossoLocatelliPullanMc::DEGREE_BASED); + checkMaxCliqueGridGraph(GrossoLocatelliPullanMc::PENALTY_BASED); + + return 0; +} Index: test/max_flow_test.cc =================================================================== --- test/max_flow_test.cc (revision 1087) +++ test/max_flow_test.cc (revision 1087) @@ -0,0 +1,395 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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 "test_tools.h" +#include +#include +#include +#include +#include +#include +#include + +using namespace lemon; + +char test_lgf[] = + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "8\n" + "9\n" + "@arcs\n" + " label capacity\n" + "0 1 0 20\n" + "0 2 1 0\n" + "1 1 2 3\n" + "1 2 3 8\n" + "1 3 4 8\n" + "2 5 5 5\n" + "3 2 6 5\n" + "3 5 7 5\n" + "3 6 8 5\n" + "4 3 9 3\n" + "5 7 10 3\n" + "5 6 11 10\n" + "5 8 12 10\n" + "6 8 13 8\n" + "8 9 14 20\n" + "8 1 15 5\n" + "9 5 16 5\n" + "@attributes\n" + "source 1\n" + "target 8\n"; + + +// Checks the general interface of a max flow algorithm +template +struct MaxFlowClassConcept +{ + + template + struct Constraints { + + typedef typename GR::Node Node; + typedef typename GR::Arc Arc; + typedef typename CAP::Value Value; + typedef concepts::ReadWriteMap FlowMap; + typedef concepts::WriteMap CutMap; + + GR g; + Node n; + Arc e; + CAP cap; + FlowMap flow; + CutMap cut; + Value v; + bool b; + + void constraints() { + checkConcept(); + + const Constraints& me = *this; + + typedef typename MF + ::template SetFlowMap + ::Create MaxFlowType; + typedef typename MF::Create MaxFlowType2; + MaxFlowType max_flow(me.g, me.cap, me.n, me.n); + const MaxFlowType& const_max_flow = max_flow; + + max_flow + .capacityMap(cap) + .flowMap(flow) + .source(n) + .target(n); + + typename MaxFlowType::Tolerance tol = const_max_flow.tolerance(); + max_flow.tolerance(tol); + + max_flow.init(); + max_flow.init(cap); + max_flow.run(); + + v = const_max_flow.flowValue(); + v = const_max_flow.flow(e); + const FlowMap& fm = const_max_flow.flowMap(); + + b = const_max_flow.minCut(n); + const_max_flow.minCutMap(cut); + + ::lemon::ignore_unused_variable_warning(fm); + } + + }; + +}; + +// Checks the specific parts of Preflow's interface +void checkPreflowCompile() +{ + typedef int Value; + typedef concepts::Digraph Digraph; + typedef concepts::ReadMap CapMap; + typedef Elevator Elev; + typedef LinkedElevator LinkedElev; + + Digraph g; + Digraph::Node n; + CapMap cap; + + typedef Preflow + ::SetElevator + ::SetStandardElevator + ::Create PreflowType; + PreflowType preflow_test(g, cap, n, n); + const PreflowType& const_preflow_test = preflow_test; + + const PreflowType::Elevator& elev = const_preflow_test.elevator(); + preflow_test.elevator(const_cast(elev)); + + bool b = preflow_test.init(cap); + preflow_test.startFirstPhase(); + preflow_test.startSecondPhase(); + preflow_test.runMinCut(); + + ::lemon::ignore_unused_variable_warning(b); +} + +// Checks the specific parts of EdmondsKarp's interface +void checkEdmondsKarpCompile() +{ + typedef int Value; + typedef concepts::Digraph Digraph; + typedef concepts::ReadMap CapMap; + typedef Elevator Elev; + typedef LinkedElevator LinkedElev; + + Digraph g; + Digraph::Node n; + CapMap cap; + + EdmondsKarp ek_test(g, cap, n, n); + + ek_test.init(cap); + bool b = ek_test.checkedInit(cap); + b = ek_test.augment(); + ek_test.start(); + + ::lemon::ignore_unused_variable_warning(b); +} + + +template +T cutValue (const SmartDigraph& g, + const SmartDigraph::NodeMap& cut, + const SmartDigraph::ArcMap& cap) { + + T c=0; + for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { + if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; + } + return c; +} + +template +bool checkFlow(const SmartDigraph& g, + const SmartDigraph::ArcMap& flow, + const SmartDigraph::ArcMap& cap, + SmartDigraph::Node s, SmartDigraph::Node t) { + + for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { + if (flow[e] < 0 || flow[e] > cap[e]) return false; + } + + for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { + if (n == s || n == t) continue; + T sum = 0; + for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { + sum += flow[e]; + } + for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { + sum -= flow[e]; + } + if (sum != 0) return false; + } + return true; +} + +void initFlowTest() +{ + DIGRAPH_TYPEDEFS(SmartDigraph); + + SmartDigraph g; + SmartDigraph::ArcMap cap(g),iflow(g); + Node s=g.addNode(); Node t=g.addNode(); + Node n1=g.addNode(); Node n2=g.addNode(); + Arc a; + a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; + a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; + a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; + + Preflow pre(g,cap,s,t); + pre.init(iflow); + pre.startFirstPhase(); + check(pre.flowValue() == 10, "The incorrect max flow value."); + check(pre.minCut(s), "Wrong min cut (Node s)."); + check(pre.minCut(n1), "Wrong min cut (Node n1)."); + check(!pre.minCut(n2), "Wrong min cut (Node n2)."); + check(!pre.minCut(t), "Wrong min cut (Node t)."); +} + +template +void checkMaxFlowAlg() { + typedef SmartDigraph Digraph; + DIGRAPH_TYPEDEFS(Digraph); + + typedef typename MF::Value Value; + typedef Digraph::ArcMap CapMap; + typedef CapMap FlowMap; + typedef BoolNodeMap CutMap; + + Digraph g; + Node s, t; + CapMap cap(g); + std::istringstream input(test_lgf); + DigraphReader(g,input) + .arcMap("capacity", cap) + .node("source",s) + .node("target",t) + .run(); + + MF max_flow(g, cap, s, t); + max_flow.run(); + + check(checkFlow(g, max_flow.flowMap(), cap, s, t), + "The flow is not feasible."); + + CutMap min_cut(g); + max_flow.minCutMap(min_cut); + Value min_cut_value = cutValue(g, min_cut, cap); + + check(max_flow.flowValue() == min_cut_value, + "The max flow value is not equal to the min cut value."); + + FlowMap flow(g); + for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e]; + + Value flow_value = max_flow.flowValue(); + + for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e]; + max_flow.init(flow); + + SF::startFirstPhase(max_flow); // start first phase of the algorithm + + CutMap min_cut1(g); + max_flow.minCutMap(min_cut1); + min_cut_value = cutValue(g, min_cut1, cap); + + check(max_flow.flowValue() == min_cut_value && + min_cut_value == 2 * flow_value, + "The max flow value or the min cut value is wrong."); + + SF::startSecondPhase(max_flow); // start second phase of the algorithm + + check(checkFlow(g, max_flow.flowMap(), cap, s, t), + "The flow is not feasible."); + + CutMap min_cut2(g); + max_flow.minCutMap(min_cut2); + min_cut_value = cutValue(g, min_cut2, cap); + + check(max_flow.flowValue() == min_cut_value && + min_cut_value == 2 * flow_value, + "The max flow value or the min cut value was not doubled"); + + + max_flow.flowMap(flow); + + NodeIt tmp1(g, s); + ++tmp1; + if (tmp1 != INVALID) s = tmp1; + + NodeIt tmp2(g, t); + ++tmp2; + if (tmp2 != INVALID) t = tmp2; + + max_flow.source(s); + max_flow.target(t); + + max_flow.run(); + + CutMap min_cut3(g); + max_flow.minCutMap(min_cut3); + min_cut_value=cutValue(g, min_cut3, cap); + + check(max_flow.flowValue() == min_cut_value, + "The max flow value or the min cut value is wrong."); +} + +// Struct for calling start functions of a general max flow algorithm +template +struct GeneralStartFunctions { + + static void startFirstPhase(MF& mf) { + mf.start(); + } + + static void startSecondPhase(MF& mf) { + ::lemon::ignore_unused_variable_warning(mf); + } + +}; + +// Struct for calling start functions of Preflow +template +struct PreflowStartFunctions { + + static void startFirstPhase(MF& mf) { + mf.startFirstPhase(); + } + + static void startSecondPhase(MF& mf) { + mf.startSecondPhase(); + } + +}; + +int main() { + + typedef concepts::Digraph GR; + typedef concepts::ReadMap CM1; + typedef concepts::ReadMap CM2; + + // Check the interface of Preflow + checkConcept< MaxFlowClassConcept, + Preflow >(); + checkConcept< MaxFlowClassConcept, + Preflow >(); + + // Check the interface of EdmondsKarp + checkConcept< MaxFlowClassConcept, + EdmondsKarp >(); + checkConcept< MaxFlowClassConcept, + EdmondsKarp >(); + + // Check Preflow + typedef Preflow > PType1; + typedef Preflow > PType2; + checkMaxFlowAlg >(); + checkMaxFlowAlg >(); + initFlowTest(); + + // Check EdmondsKarp + typedef EdmondsKarp > EKType1; + typedef EdmondsKarp > EKType2; + checkMaxFlowAlg >(); + checkMaxFlowAlg >(); + + initFlowTest(); + + return 0; +} Index: test/min_cost_arborescence_test.cc =================================================================== --- test/min_cost_arborescence_test.cc (revision 1083) +++ test/min_cost_arborescence_test.cc (revision 1084) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -112,5 +112,5 @@ b = const_mcarb_test.emptyQueue(); i = const_mcarb_test.queueSize(); - + c = const_mcarb_test.arborescenceCost(); b = const_mcarb_test.arborescence(e); @@ -122,10 +122,10 @@ b = const_mcarb_test.reached(n); b = const_mcarb_test.processed(n); - + i = const_mcarb_test.dualNum(); c = const_mcarb_test.dualValue(); i = const_mcarb_test.dualSize(i); c = const_mcarb_test.dualValue(i); - + ::lemon::ignore_unused_variable_warning(am); ::lemon::ignore_unused_variable_warning(pm); Index: test/min_cost_flow_test.cc =================================================================== --- test/min_cost_flow_test.cc (revision 669) +++ test/min_cost_flow_test.cc (revision 877) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -25,6 +25,10 @@ #include +#include +#include +#include #include +#include #include @@ -33,4 +37,5 @@ using namespace lemon; +// Test networks char test_lgf[] = "@nodes\n" @@ -48,5 +53,5 @@ " 11 0 0 0 0 -10 0\n" " 12 -20 -27 0 -30 -30 -20\n" - "\n" + "\n" "@arcs\n" " cost cap low1 low2 low3\n" @@ -77,4 +82,56 @@ "target 12\n"; +char test_neg1_lgf[] = + "@nodes\n" + "label sup\n" + " 1 100\n" + " 2 0\n" + " 3 0\n" + " 4 -100\n" + " 5 0\n" + " 6 0\n" + " 7 0\n" + "@arcs\n" + " cost low1 low2\n" + "1 2 100 0 0\n" + "1 3 30 0 0\n" + "2 4 20 0 0\n" + "3 4 80 0 0\n" + "3 2 50 0 0\n" + "5 3 10 0 0\n" + "5 6 80 0 1000\n" + "6 7 30 0 -1000\n" + "7 5 -120 0 0\n"; + +char test_neg2_lgf[] = + "@nodes\n" + "label sup\n" + " 1 100\n" + " 2 -300\n" + "@arcs\n" + " cost\n" + "1 2 -1\n"; + + +// Test data +typedef ListDigraph Digraph; +DIGRAPH_TYPEDEFS(ListDigraph); + +Digraph gr; +Digraph::ArcMap c(gr), l1(gr), l2(gr), l3(gr), u(gr); +Digraph::NodeMap s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr); +ConstMap cc(1), cu(std::numeric_limits::max()); +Node v, w; + +Digraph neg1_gr; +Digraph::ArcMap neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr); +ConstMap neg1_u1(std::numeric_limits::max()), neg1_u2(5000); +Digraph::NodeMap neg1_s(neg1_gr); + +Digraph neg2_gr; +Digraph::ArcMap neg2_c(neg2_gr); +ConstMap neg2_l(0), neg2_u(1000); +Digraph::NodeMap neg2_s(neg2_gr); + enum SupplyType { @@ -84,4 +141,5 @@ }; + // Check the interface of an MCF algorithm template @@ -94,5 +152,5 @@ void constraints() { checkConcept(); - + const Constraints& me = *this; @@ -100,5 +158,5 @@ const MCF& const_mcf = mcf; - b = mcf.reset() + b = mcf.reset().resetParams() .lowerMap(me.lower) .upperMap(me.upper) @@ -123,5 +181,5 @@ typedef concepts::WriteMap FlowMap; typedef concepts::WriteMap PotMap; - + GR g; VAM lower; @@ -177,5 +235,5 @@ typename CM, typename SM, typename FM, typename PM > bool checkPotential( const GR& gr, const LM& lower, const UM& upper, - const CM& cost, const SM& supply, const FM& flow, + const CM& cost, const SM& supply, const FM& flow, const PM& pi, SupplyType type ) { @@ -190,5 +248,5 @@ (red_cost < 0 && flow[e] == upper[e]); } - + for (NodeIt n(gr); opt && n != INVALID; ++n) { typename SM::Value sum = 0; @@ -203,5 +261,5 @@ } } - + return opt; } @@ -228,5 +286,5 @@ } } - + for (NodeIt n(gr); n != INVALID; ++n) { dual_cost -= red_supply[n] * pi[n]; @@ -237,5 +295,5 @@ dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0); } - + return dual_cost == total; } @@ -269,28 +327,97 @@ } +template < typename MCF, typename Param > +void runMcfGeqTests( Param param, + const std::string &test_str = "", + bool full_neg_cost_support = false ) +{ + MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr); + + // Basic tests + mcf1.upperMap(u).costMap(c).supplyMap(s1); + checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1, + mcf1.OPTIMAL, true, 5240, test_str + "-1"); + mcf1.stSupply(v, w, 27); + checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s2, + mcf1.OPTIMAL, true, 7620, test_str + "-2"); + mcf1.lowerMap(l2).supplyMap(s1); + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s1, + mcf1.OPTIMAL, true, 5970, test_str + "-3"); + mcf1.stSupply(v, w, 27); + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2, + mcf1.OPTIMAL, true, 8010, test_str + "-4"); + mcf1.resetParams().supplyMap(s1); + checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1, + mcf1.OPTIMAL, true, 74, test_str + "-5"); + mcf1.lowerMap(l2).stSupply(v, w, 27); + checkMcf(mcf1, mcf1.run(param), gr, l2, cu, cc, s2, + mcf1.OPTIMAL, true, 94, test_str + "-6"); + mcf1.reset(); + checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s3, + mcf1.OPTIMAL, true, 0, test_str + "-7"); + mcf1.lowerMap(l2).upperMap(u); + checkMcf(mcf1, mcf1.run(param), gr, l2, u, cc, s3, + mcf1.INFEASIBLE, false, 0, test_str + "-8"); + mcf1.lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4); + checkMcf(mcf1, mcf1.run(param), gr, l3, u, c, s4, + mcf1.OPTIMAL, true, 6360, test_str + "-9"); + + // Tests for the GEQ form + mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5); + checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5, + mcf1.OPTIMAL, true, 3530, test_str + "-10", GEQ); + mcf1.lowerMap(l2); + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5, + mcf1.OPTIMAL, true, 4540, test_str + "-11", GEQ); + mcf1.supplyMap(s6); + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6, + mcf1.INFEASIBLE, false, 0, test_str + "-12", GEQ); + + // Tests with negative costs + mcf2.lowerMap(neg1_l1).costMap(neg1_c).supplyMap(neg1_s); + checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u1, neg1_c, neg1_s, + mcf2.UNBOUNDED, false, 0, test_str + "-13"); + mcf2.upperMap(neg1_u2); + checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s, + mcf2.OPTIMAL, true, -40000, test_str + "-14"); + mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s); + checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s, + mcf2.UNBOUNDED, false, 0, test_str + "-15"); + + mcf3.costMap(neg2_c).supplyMap(neg2_s); + if (full_neg_cost_support) { + checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, + mcf3.OPTIMAL, true, -300, test_str + "-16", GEQ); + } else { + checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, + mcf3.UNBOUNDED, false, 0, test_str + "-17", GEQ); + } + mcf3.upperMap(neg2_u); + checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, + mcf3.OPTIMAL, true, -300, test_str + "-18", GEQ); +} + +template < typename MCF, typename Param > +void runMcfLeqTests( Param param, + const std::string &test_str = "" ) +{ + // Tests for the LEQ form + MCF mcf1(gr); + mcf1.supplyType(mcf1.LEQ); + mcf1.upperMap(u).costMap(c).supplyMap(s6); + checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s6, + mcf1.OPTIMAL, true, 5080, test_str + "-19", LEQ); + mcf1.lowerMap(l2); + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6, + mcf1.OPTIMAL, true, 5930, test_str + "-20", LEQ); + mcf1.supplyMap(s5); + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5, + mcf1.INFEASIBLE, false, 0, test_str + "-21", LEQ); +} + + int main() { - // Check the interfaces - { - typedef concepts::Digraph GR; - checkConcept< McfClassConcept, - NetworkSimplex >(); - checkConcept< McfClassConcept, - NetworkSimplex >(); - checkConcept< McfClassConcept, - NetworkSimplex >(); - } - - // Run various MCF tests - typedef ListDigraph Digraph; - DIGRAPH_TYPEDEFS(ListDigraph); - - // Read the test digraph - Digraph gr; - Digraph::ArcMap c(gr), l1(gr), l2(gr), l3(gr), u(gr); - Digraph::NodeMap s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr); - ConstMap cc(1), cu(std::numeric_limits::max()); - Node v, w; - + // Read the test networks std::istringstream input(test_lgf); DigraphReader(gr, input) @@ -309,140 +436,105 @@ .node("target", w) .run(); - - // Build test digraphs with negative costs - Digraph neg_gr; - Node n1 = neg_gr.addNode(); - Node n2 = neg_gr.addNode(); - Node n3 = neg_gr.addNode(); - Node n4 = neg_gr.addNode(); - Node n5 = neg_gr.addNode(); - Node n6 = neg_gr.addNode(); - Node n7 = neg_gr.addNode(); - - Arc a1 = neg_gr.addArc(n1, n2); - Arc a2 = neg_gr.addArc(n1, n3); - Arc a3 = neg_gr.addArc(n2, n4); - Arc a4 = neg_gr.addArc(n3, n4); - Arc a5 = neg_gr.addArc(n3, n2); - Arc a6 = neg_gr.addArc(n5, n3); - Arc a7 = neg_gr.addArc(n5, n6); - Arc a8 = neg_gr.addArc(n6, n7); - Arc a9 = neg_gr.addArc(n7, n5); - - Digraph::ArcMap neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0); - ConstMap neg_u1(std::numeric_limits::max()), neg_u2(5000); - Digraph::NodeMap neg_s(neg_gr, 0); - - neg_l2[a7] = 1000; - neg_l2[a8] = -1000; - - neg_s[n1] = 100; - neg_s[n4] = -100; - - neg_c[a1] = 100; - neg_c[a2] = 30; - neg_c[a3] = 20; - neg_c[a4] = 80; - neg_c[a5] = 50; - neg_c[a6] = 10; - neg_c[a7] = 80; - neg_c[a8] = 30; - neg_c[a9] = -120; - - Digraph negs_gr; - Digraph::NodeMap negs_s(negs_gr); - Digraph::ArcMap negs_c(negs_gr); - ConstMap negs_l(0), negs_u(1000); - n1 = negs_gr.addNode(); - n2 = negs_gr.addNode(); - negs_s[n1] = 100; - negs_s[n2] = -300; - negs_c[negs_gr.addArc(n1, n2)] = -1; - - - // A. Test NetworkSimplex with the default pivot rule - { - NetworkSimplex mcf(gr); - - // Check the equality form - mcf.upperMap(u).costMap(c); - checkMcf(mcf, mcf.supplyMap(s1).run(), - gr, l1, u, c, s1, mcf.OPTIMAL, true, 5240, "#A1"); - checkMcf(mcf, mcf.stSupply(v, w, 27).run(), - gr, l1, u, c, s2, mcf.OPTIMAL, true, 7620, "#A2"); - mcf.lowerMap(l2); - checkMcf(mcf, mcf.supplyMap(s1).run(), - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#A3"); - checkMcf(mcf, mcf.stSupply(v, w, 27).run(), - gr, l2, u, c, s2, mcf.OPTIMAL, true, 8010, "#A4"); - mcf.reset(); - checkMcf(mcf, mcf.supplyMap(s1).run(), - gr, l1, cu, cc, s1, mcf.OPTIMAL, true, 74, "#A5"); - checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), - gr, l2, cu, cc, s2, mcf.OPTIMAL, true, 94, "#A6"); - mcf.reset(); - checkMcf(mcf, mcf.run(), - gr, l1, cu, cc, s3, mcf.OPTIMAL, true, 0, "#A7"); - checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(), - gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8"); - mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4); - checkMcf(mcf, mcf.run(), - gr, l3, u, c, s4, mcf.OPTIMAL, true, 6360, "#A9"); - - // Check the GEQ form - mcf.reset().upperMap(u).costMap(c).supplyMap(s5); - checkMcf(mcf, mcf.run(), - gr, l1, u, c, s5, mcf.OPTIMAL, true, 3530, "#A10", GEQ); - mcf.supplyType(mcf.GEQ); - checkMcf(mcf, mcf.lowerMap(l2).run(), - gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ); - mcf.supplyMap(s6); - checkMcf(mcf, mcf.run(), - gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ); - - // Check the LEQ form - mcf.reset().supplyType(mcf.LEQ); - mcf.upperMap(u).costMap(c).supplyMap(s6); - checkMcf(mcf, mcf.run(), - gr, l1, u, c, s6, mcf.OPTIMAL, true, 5080, "#A13", LEQ); - checkMcf(mcf, mcf.lowerMap(l2).run(), - gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ); - mcf.supplyMap(s5); - checkMcf(mcf, mcf.run(), - gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ); - - // Check negative costs - NetworkSimplex neg_mcf(neg_gr); - neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s); - checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1, - neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A16"); - neg_mcf.upperMap(neg_u2); - checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2, - neg_c, neg_s, neg_mcf.OPTIMAL, true, -40000, "#A17"); - neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s); - checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1, - neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A18"); - - NetworkSimplex negs_mcf(negs_gr); - negs_mcf.costMap(negs_c).supplyMap(negs_s); - checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u, - negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ); - } - - // B. Test NetworkSimplex with each pivot rule - { - NetworkSimplex mcf(gr); - mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2); - - checkMcf(mcf, mcf.run(NetworkSimplex::FIRST_ELIGIBLE), - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B1"); - checkMcf(mcf, mcf.run(NetworkSimplex::BEST_ELIGIBLE), - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B2"); - checkMcf(mcf, mcf.run(NetworkSimplex::BLOCK_SEARCH), - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B3"); - checkMcf(mcf, mcf.run(NetworkSimplex::CANDIDATE_LIST), - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B4"); - checkMcf(mcf, mcf.run(NetworkSimplex::ALTERING_LIST), - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B5"); + + std::istringstream neg_inp1(test_neg1_lgf); + DigraphReader(neg1_gr, neg_inp1) + .arcMap("cost", neg1_c) + .arcMap("low1", neg1_l1) + .arcMap("low2", neg1_l2) + .nodeMap("sup", neg1_s) + .run(); + + std::istringstream neg_inp2(test_neg2_lgf); + DigraphReader(neg2_gr, neg_inp2) + .arcMap("cost", neg2_c) + .nodeMap("sup", neg2_s) + .run(); + + // Check the interface of NetworkSimplex + { + typedef concepts::Digraph GR; + checkConcept< McfClassConcept, + NetworkSimplex >(); + checkConcept< McfClassConcept, + NetworkSimplex >(); + checkConcept< McfClassConcept, + NetworkSimplex >(); + } + + // Check the interface of CapacityScaling + { + typedef concepts::Digraph GR; + checkConcept< McfClassConcept, + CapacityScaling >(); + checkConcept< McfClassConcept, + CapacityScaling >(); + checkConcept< McfClassConcept, + CapacityScaling >(); + typedef CapacityScaling:: + SetHeap > >::Create CAS; + checkConcept< McfClassConcept, CAS >(); + } + + // Check the interface of CostScaling + { + typedef concepts::Digraph GR; + checkConcept< McfClassConcept, + CostScaling >(); + checkConcept< McfClassConcept, + CostScaling >(); + checkConcept< McfClassConcept, + CostScaling >(); + typedef CostScaling:: + SetLargeCost::Create COS; + checkConcept< McfClassConcept, COS >(); + } + + // Check the interface of CycleCanceling + { + typedef concepts::Digraph GR; + checkConcept< McfClassConcept, + CycleCanceling >(); + checkConcept< McfClassConcept, + CycleCanceling >(); + checkConcept< McfClassConcept, + CycleCanceling >(); + } + + // Test NetworkSimplex + { + typedef NetworkSimplex MCF; + runMcfGeqTests(MCF::FIRST_ELIGIBLE, "NS-FE", true); + runMcfLeqTests(MCF::FIRST_ELIGIBLE, "NS-FE"); + runMcfGeqTests(MCF::BEST_ELIGIBLE, "NS-BE", true); + runMcfLeqTests(MCF::BEST_ELIGIBLE, "NS-BE"); + runMcfGeqTests(MCF::BLOCK_SEARCH, "NS-BS", true); + runMcfLeqTests(MCF::BLOCK_SEARCH, "NS-BS"); + runMcfGeqTests(MCF::CANDIDATE_LIST, "NS-CL", true); + runMcfLeqTests(MCF::CANDIDATE_LIST, "NS-CL"); + runMcfGeqTests(MCF::ALTERING_LIST, "NS-AL", true); + runMcfLeqTests(MCF::ALTERING_LIST, "NS-AL"); + } + + // Test CapacityScaling + { + typedef CapacityScaling MCF; + runMcfGeqTests(0, "SSP"); + runMcfGeqTests(2, "CAS"); + } + + // Test CostScaling + { + typedef CostScaling MCF; + runMcfGeqTests(MCF::PUSH, "COS-PR"); + runMcfGeqTests(MCF::AUGMENT, "COS-AR"); + runMcfGeqTests(MCF::PARTIAL_AUGMENT, "COS-PAR"); + } + + // Test CycleCanceling + { + typedef CycleCanceling MCF; + runMcfGeqTests(MCF::SIMPLE_CYCLE_CANCELING, "SCC"); + runMcfGeqTests(MCF::MINIMUM_MEAN_CYCLE_CANCELING, "MMCC"); + runMcfGeqTests(MCF::CANCEL_AND_TIGHTEN, "CAT"); } Index: test/min_mean_cycle_test.cc =================================================================== --- test/min_mean_cycle_test.cc (revision 1012) +++ test/min_mean_cycle_test.cc (revision 1012) @@ -0,0 +1,223 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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 + +#include +#include +#include + +#include "test_tools.h" + +using namespace lemon; + +char test_lgf[] = + "@nodes\n" + "label\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "@arcs\n" + " len1 len2 len3 len4 c1 c2 c3 c4\n" + "1 2 1 1 1 1 0 0 0 0\n" + "2 4 5 5 5 5 1 0 0 0\n" + "2 3 8 8 8 8 0 0 0 0\n" + "3 2 -2 0 0 0 1 0 0 0\n" + "3 4 4 4 4 4 0 0 0 0\n" + "3 7 -4 -4 -4 -4 0 0 0 0\n" + "4 1 2 2 2 2 0 0 0 0\n" + "4 3 3 3 3 3 1 0 0 0\n" + "4 4 3 3 0 0 0 0 1 0\n" + "5 2 4 4 4 4 0 0 0 0\n" + "5 6 3 3 3 3 0 1 0 0\n" + "6 5 2 2 2 2 0 1 0 0\n" + "6 4 -1 -1 -1 -1 0 0 0 0\n" + "6 7 1 1 1 1 0 0 0 0\n" + "7 7 4 4 4 -1 0 0 0 1\n"; + + +// Check the interface of an MMC algorithm +template +struct MmcClassConcept +{ + template + struct Constraints { + void constraints() { + const Constraints& me = *this; + + typedef typename MMC + ::template SetPath > + ::template SetLargeCost + ::Create MmcAlg; + MmcAlg mmc(me.g, me.cost); + const MmcAlg& const_mmc = mmc; + + typename MmcAlg::Tolerance tol = const_mmc.tolerance(); + mmc.tolerance(tol); + + b = mmc.cycle(p).run(); + b = mmc.findCycleMean(); + b = mmc.findCycle(); + + v = const_mmc.cycleCost(); + i = const_mmc.cycleSize(); + d = const_mmc.cycleMean(); + p = const_mmc.cycle(); + } + + typedef concepts::ReadMap CM; + + GR g; + CM cost; + ListPath p; + Cost v; + int i; + double d; + bool b; + }; +}; + +// Perform a test with the given parameters +template +void checkMmcAlg(const SmartDigraph& gr, + const SmartDigraph::ArcMap& lm, + const SmartDigraph::ArcMap& cm, + int cost, int size) { + MMC alg(gr, lm); + check(alg.findCycleMean(), "Wrong result"); + check(alg.cycleMean() == static_cast(cost) / size, + "Wrong cycle mean"); + alg.findCycle(); + check(alg.cycleCost() == cost && alg.cycleSize() == size, + "Wrong path"); + SmartDigraph::ArcMap cycle(gr, 0); + for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) { + ++cycle[a]; + } + for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) { + check(cm[a] == cycle[a], "Wrong path"); + } +} + +// Class for comparing types +template +struct IsSameType { + static const int result = 0; +}; + +template +struct IsSameType { + static const int result = 1; +}; + + +int main() { + #ifdef LEMON_HAVE_LONG_LONG + typedef long long long_int; + #else + typedef long long_int; + #endif + + // Check the interface + { + typedef concepts::Digraph GR; + + // KarpMmc + checkConcept< MmcClassConcept, + KarpMmc > >(); + checkConcept< MmcClassConcept, + KarpMmc > >(); + + // HartmannOrlinMmc + checkConcept< MmcClassConcept, + HartmannOrlinMmc > >(); + checkConcept< MmcClassConcept, + HartmannOrlinMmc > >(); + + // HowardMmc + checkConcept< MmcClassConcept, + HowardMmc > >(); + checkConcept< MmcClassConcept, + HowardMmc > >(); + + check((IsSameType > + ::LargeCost, long_int>::result == 1), "Wrong LargeCost type"); + check((IsSameType > + ::LargeCost, double>::result == 1), "Wrong LargeCost type"); + } + + // Run various tests + { + typedef SmartDigraph GR; + DIGRAPH_TYPEDEFS(GR); + + GR gr; + IntArcMap l1(gr), l2(gr), l3(gr), l4(gr); + IntArcMap c1(gr), c2(gr), c3(gr), c4(gr); + + std::istringstream input(test_lgf); + digraphReader(gr, input). + arcMap("len1", l1). + arcMap("len2", l2). + arcMap("len3", l3). + arcMap("len4", l4). + arcMap("c1", c1). + arcMap("c2", c2). + arcMap("c3", c3). + arcMap("c4", c4). + run(); + + // Karp + checkMmcAlg >(gr, l1, c1, 6, 3); + checkMmcAlg >(gr, l2, c2, 5, 2); + checkMmcAlg >(gr, l3, c3, 0, 1); + checkMmcAlg >(gr, l4, c4, -1, 1); + + // HartmannOrlin + checkMmcAlg >(gr, l1, c1, 6, 3); + checkMmcAlg >(gr, l2, c2, 5, 2); + checkMmcAlg >(gr, l3, c3, 0, 1); + checkMmcAlg >(gr, l4, c4, -1, 1); + + // Howard + checkMmcAlg >(gr, l1, c1, 6, 3); + checkMmcAlg >(gr, l2, c2, 5, 2); + checkMmcAlg >(gr, l3, c3, 0, 1); + checkMmcAlg >(gr, l4, c4, -1, 1); + + // Howard with iteration limit + HowardMmc mmc(gr, l1); + check((mmc.findCycleMean(2) == HowardMmc::ITERATION_LIMIT), + "Wrong termination cause"); + check((mmc.findCycleMean(4) == HowardMmc::OPTIMAL), + "Wrong termination cause"); + } + + return 0; +} Index: test/nagamochi_ibaraki_test.cc =================================================================== --- test/nagamochi_ibaraki_test.cc (revision 1087) +++ test/nagamochi_ibaraki_test.cc (revision 1087) @@ -0,0 +1,142 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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 + +#include "test_tools.h" + +using namespace lemon; +using namespace std; + +const std::string lgf = + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "@edges\n" + " cap1 cap2 cap3\n" + "0 1 1 1 1 \n" + "0 2 2 2 4 \n" + "1 2 4 4 4 \n" + "3 4 1 1 1 \n" + "3 5 2 2 4 \n" + "4 5 4 4 4 \n" + "2 3 1 6 6 \n"; + +void checkNagamochiIbarakiCompile() +{ + typedef int Value; + typedef concepts::Graph Graph; + + typedef Graph::Node Node; + typedef Graph::Edge Edge; + typedef concepts::ReadMap CapMap; + typedef concepts::WriteMap CutMap; + + Graph g; + Node n; + CapMap cap; + CutMap cut; + Value v; + bool b; + ::lemon::ignore_unused_variable_warning(v,b); + + NagamochiIbaraki ni_test(g, cap); + const NagamochiIbaraki& const_ni_test = ni_test; + + ni_test.init(); + ni_test.start(); + b = ni_test.processNextPhase(); + ni_test.run(); + + v = const_ni_test.minCutValue(); + v = const_ni_test.minCutMap(cut); +} + +template +typename CapMap::Value + cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) +{ + typename CapMap::Value sum = 0; + for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) { + if (cut[graph.u(e)] != cut[graph.v(e)]) { + sum += cap[e]; + } + } + return sum; +} + +int main() { + SmartGraph graph; + SmartGraph::EdgeMap cap1(graph), cap2(graph), cap3(graph); + SmartGraph::NodeMap cut(graph); + + istringstream input(lgf); + graphReader(graph, input) + .edgeMap("cap1", cap1) + .edgeMap("cap2", cap2) + .edgeMap("cap3", cap3) + .run(); + + { + NagamochiIbaraki ni(graph, cap1); + ni.run(); + ni.minCutMap(cut); + + check(ni.minCutValue() == 1, "Wrong cut value"); + check(ni.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); + } + { + NagamochiIbaraki ni(graph, cap2); + ni.run(); + ni.minCutMap(cut); + + check(ni.minCutValue() == 3, "Wrong cut value"); + check(ni.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value"); + } + { + NagamochiIbaraki ni(graph, cap3); + ni.run(); + ni.minCutMap(cut); + + check(ni.minCutValue() == 5, "Wrong cut value"); + check(ni.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); + } + { + NagamochiIbaraki::SetUnitCapacity::Create ni(graph); + ni.run(); + ni.minCutMap(cut); + + ConstMap cap4(1); + check(ni.minCutValue() == 1, "Wrong cut value"); + check(ni.minCutValue() == cutValue(graph, cap4, cut), "Wrong cut value"); + } + + return 0; +} Index: test/path_test.cc =================================================================== --- test/path_test.cc (revision 990) +++ test/path_test.cc (revision 1044) @@ -22,4 +22,5 @@ #include #include +#include #include @@ -31,42 +32,307 @@ using namespace lemon; -void check_concepts() { - checkConcept, concepts::Path >(); - checkConcept, Path >(); - checkConcept, SimplePath >(); - checkConcept, StaticPath >(); - checkConcept, ListPath >(); +template +void checkConcepts() { + checkConcept, concepts::Path >(); + checkConcept, Path >(); + checkConcept, SimplePath >(); + checkConcept, StaticPath >(); + checkConcept, ListPath >(); +} + +// Conecpt checking for path structures +void checkPathConcepts() { + checkConcepts(); + checkConcepts(); } // Check if proper copy consructor is called (use valgrind for testing) -template -void checkCopy() -{ +template +void checkCopy(typename GR::Arc a) { + P1 p; + p.addBack(a); + P1 q; + q = p; + P1 r(p); + P2 q2; + q2 = p; + P2 r2(p); +} + +// Tests for copy constructors and assignment operators of paths +void checkPathCopy() { ListDigraph g; - ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); - - _Path p,q; - p.addBack(a); - q=p; - _Path r(p); - StaticPath s(r); -} - + ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); + + typedef Path Path1; + typedef SimplePath Path2; + typedef ListPath Path3; + typedef StaticPath Path4; + checkCopy(a); + checkCopy(a); + checkCopy(a); + checkCopy(a); + checkCopy(a); + checkCopy(a); + checkCopy(a); + checkCopy(a); + checkCopy(a); +} + +// Class for testing path functions +class CheckPathFunctions { + typedef ListDigraph GR; + DIGRAPH_TYPEDEFS(GR); + GR gr; + const GR& cgr; + Node n1, n2, n3, n4; + Node tmp_n; + Arc a1, a2, a3, a4; + Arc tmp_a; + +public: + + CheckPathFunctions() : cgr(gr) { + n1 = gr.addNode(); + n2 = gr.addNode(); + n3 = gr.addNode(); + n4 = gr.addNode(); + a1 = gr.addArc(n1, n2); + a2 = gr.addArc(n2, n3); + a3 = gr.addArc(n3, n4); + a4 = gr.addArc(n4, n1); + } + + void run() { + checkBackAndFrontInsertablePath >(); + checkBackAndFrontInsertablePath >(); + checkBackInsertablePath >(); + + checkListPathSplitAndSplice(); + } + +private: + + template + void checkBackInsertablePath() { + + // Create and check empty path + P p; + const P& cp = p; + check(cp.empty(), "The path is not empty"); + check(cp.length() == 0, "The path is not empty"); +// check(cp.front() == INVALID, "Wrong front()"); +// check(cp.back() == INVALID, "Wrong back()"); + typename P::ArcIt ai(cp); + check(ai == INVALID, "Wrong ArcIt"); + check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()"); + check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()"); + check(checkPath(cgr, cp), "Wrong checkPath()"); + PathNodeIt

ni(cgr, cp); + check(ni == INVALID, "Wrong PathNodeIt"); + + // Check single-arc path + p.addBack(a1); + check(!cp.empty(), "Wrong empty()"); + check(cp.length() == 1, "Wrong length"); + check(cp.front() == a1, "Wrong front()"); + check(cp.back() == a1, "Wrong back()"); + check(cp.nth(0) == a1, "Wrong nth()"); + ai = cp.nthIt(0); + check((tmp_a = ai) == a1, "Wrong nthIt()"); + check(++ai == INVALID, "Wrong nthIt()"); + typename P::ArcIt ai2(cp); + check((tmp_a = ai2) == a1, "Wrong ArcIt"); + check(++ai2 == INVALID, "Wrong ArcIt"); + check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); + check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); + check(checkPath(cgr, cp), "Wrong checkPath()"); + PathNodeIt

ni2(cgr, cp); + check((tmp_n = ni2) == n1, "Wrong PathNodeIt"); + check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt"); + check(++ni2 == INVALID, "Wrong PathNodeIt"); + + // Check adding more arcs + p.addBack(a2); + p.addBack(a3); + check(!cp.empty(), "Wrong empty()"); + check(cp.length() == 3, "Wrong length"); + check(cp.front() == a1, "Wrong front()"); + check(cp.back() == a3, "Wrong back()"); + check(cp.nth(0) == a1, "Wrong nth()"); + check(cp.nth(1) == a2, "Wrong nth()"); + check(cp.nth(2) == a3, "Wrong nth()"); + typename P::ArcIt ai3(cp); + check((tmp_a = ai3) == a1, "Wrong ArcIt"); + check((tmp_a = ++ai3) == a2, "Wrong nthIt()"); + check((tmp_a = ++ai3) == a3, "Wrong nthIt()"); + check(++ai3 == INVALID, "Wrong nthIt()"); + ai = cp.nthIt(0); + check((tmp_a = ai) == a1, "Wrong nthIt()"); + check((tmp_a = ++ai) == a2, "Wrong nthIt()"); + ai = cp.nthIt(2); + check((tmp_a = ai) == a3, "Wrong nthIt()"); + check(++ai == INVALID, "Wrong nthIt()"); + check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); + check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()"); + check(checkPath(cgr, cp), "Wrong checkPath()"); + PathNodeIt

ni3(cgr, cp); + check((tmp_n = ni3) == n1, "Wrong PathNodeIt"); + check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt"); + check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt"); + check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt"); + check(++ni3 == INVALID, "Wrong PathNodeIt"); + + // Check arc removal and addition + p.eraseBack(); + p.eraseBack(); + p.addBack(a2); + check(!cp.empty(), "Wrong empty()"); + check(cp.length() == 2, "Wrong length"); + check(cp.front() == a1, "Wrong front()"); + check(cp.back() == a2, "Wrong back()"); + check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); + check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()"); + check(checkPath(cgr, cp), "Wrong checkPath()"); + + // Check clear() + p.clear(); + check(cp.empty(), "The path is not empty"); + check(cp.length() == 0, "The path is not empty"); + + // Check inconsistent path + p.addBack(a4); + p.addBack(a2); + p.addBack(a1); + check(!cp.empty(), "Wrong empty()"); + check(cp.length() == 3, "Wrong length"); + check(cp.front() == a4, "Wrong front()"); + check(cp.back() == a1, "Wrong back()"); + check(pathSource(cgr, cp) == n4, "Wrong pathSource()"); + check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); + check(!checkPath(cgr, cp), "Wrong checkPath()"); + } + + template + void checkBackAndFrontInsertablePath() { + + // Include back insertable test cases + checkBackInsertablePath

(); + + // Check front and back insertion + P p; + const P& cp = p; + p.addFront(a4); + p.addBack(a1); + p.addFront(a3); + check(!cp.empty(), "Wrong empty()"); + check(cp.length() == 3, "Wrong length"); + check(cp.front() == a3, "Wrong front()"); + check(cp.back() == a1, "Wrong back()"); + check(cp.nth(0) == a3, "Wrong nth()"); + check(cp.nth(1) == a4, "Wrong nth()"); + check(cp.nth(2) == a1, "Wrong nth()"); + typename P::ArcIt ai(cp); + check((tmp_a = ai) == a3, "Wrong ArcIt"); + check((tmp_a = ++ai) == a4, "Wrong nthIt()"); + check((tmp_a = ++ai) == a1, "Wrong nthIt()"); + check(++ai == INVALID, "Wrong nthIt()"); + ai = cp.nthIt(0); + check((tmp_a = ai) == a3, "Wrong nthIt()"); + check((tmp_a = ++ai) == a4, "Wrong nthIt()"); + ai = cp.nthIt(2); + check((tmp_a = ai) == a1, "Wrong nthIt()"); + check(++ai == INVALID, "Wrong nthIt()"); + check(pathSource(cgr, cp) == n3, "Wrong pathSource()"); + check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); + check(checkPath(cgr, cp), "Wrong checkPath()"); + + // Check eraseFront() + p.eraseFront(); + p.addBack(a2); + check(!cp.empty(), "Wrong empty()"); + check(cp.length() == 3, "Wrong length"); + check(cp.front() == a4, "Wrong front()"); + check(cp.back() == a2, "Wrong back()"); + check(cp.nth(0) == a4, "Wrong nth()"); + check(cp.nth(1) == a1, "Wrong nth()"); + check(cp.nth(2) == a2, "Wrong nth()"); + typename P::ArcIt ai2(cp); + check((tmp_a = ai2) == a4, "Wrong ArcIt"); + check((tmp_a = ++ai2) == a1, "Wrong nthIt()"); + check((tmp_a = ++ai2) == a2, "Wrong nthIt()"); + check(++ai2 == INVALID, "Wrong nthIt()"); + ai = cp.nthIt(0); + check((tmp_a = ai) == a4, "Wrong nthIt()"); + check((tmp_a = ++ai) == a1, "Wrong nthIt()"); + ai = cp.nthIt(2); + check((tmp_a = ai) == a2, "Wrong nthIt()"); + check(++ai == INVALID, "Wrong nthIt()"); + check(pathSource(cgr, cp) == n4, "Wrong pathSource()"); + check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()"); + check(checkPath(cgr, cp), "Wrong checkPath()"); + } + + void checkListPathSplitAndSplice() { + + // Build a path with spliceFront() and spliceBack() + ListPath p1, p2, p3, p4; + p1.addBack(a3); + p1.addFront(a2); + p2.addBack(a1); + p1.spliceFront(p2); + p3.addFront(a4); + p1.spliceBack(p3); + check(p1.length() == 4, "Wrong length"); + check(p1.front() == a1, "Wrong front()"); + check(p1.back() == a4, "Wrong back()"); + ListPath::ArcIt ai(p1); + check((tmp_a = ai) == a1, "Wrong ArcIt"); + check((tmp_a = ++ai) == a2, "Wrong nthIt()"); + check((tmp_a = ++ai) == a3, "Wrong nthIt()"); + check((tmp_a = ++ai) == a4, "Wrong nthIt()"); + check(++ai == INVALID, "Wrong nthIt()"); + check(checkPath(cgr, p1), "Wrong checkPath()"); + + // Check split() + p1.split(p1.nthIt(2), p2); + check(p1.length() == 2, "Wrong length"); + ai = p1.nthIt(0); + check((tmp_a = ai) == a1, "Wrong ArcIt"); + check((tmp_a = ++ai) == a2, "Wrong nthIt()"); + check(++ai == INVALID, "Wrong nthIt()"); + check(checkPath(cgr, p1), "Wrong checkPath()"); + check(p2.length() == 2, "Wrong length"); + ai = p2.nthIt(0); + check((tmp_a = ai) == a3, "Wrong ArcIt"); + check((tmp_a = ++ai) == a4, "Wrong nthIt()"); + check(++ai == INVALID, "Wrong nthIt()"); + check(checkPath(cgr, p2), "Wrong checkPath()"); + + // Check split() and splice() + p1.spliceFront(p2); + p1.split(p1.nthIt(2), p2); + p2.split(p2.nthIt(1), p3); + p2.spliceBack(p1); + p2.splice(p2.nthIt(1), p3); + check(p2.length() == 4, "Wrong length"); + check(p2.front() == a1, "Wrong front()"); + check(p2.back() == a4, "Wrong back()"); + ai = p2.nthIt(0); + check((tmp_a = ai) == a1, "Wrong ArcIt"); + check((tmp_a = ++ai) == a2, "Wrong nthIt()"); + check((tmp_a = ++ai) == a3, "Wrong nthIt()"); + check((tmp_a = ++ai) == a4, "Wrong nthIt()"); + check(++ai == INVALID, "Wrong nthIt()"); + check(checkPath(cgr, p2), "Wrong checkPath()"); + } + +}; + int main() { - check_concepts(); - - checkCopy >(); - checkCopy >(); - checkCopy >(); - - ListDigraph g; - ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); - - Path p; - StaticPath q,r; - p.addBack(a); - q=p; - r=q; - StaticPath s(q); + checkPathConcepts(); + checkPathCopy(); + CheckPathFunctions cpf; + cpf.run(); return 0; Index: test/planarity_test.cc =================================================================== --- test/planarity_test.cc (revision 798) +++ test/planarity_test.cc (revision 798) @@ -0,0 +1,262 @@ +/* -*- 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 "test_tools.h" + +using namespace lemon; +using namespace lemon::dim2; + +const int lgfn = 4; +const std::string lgf[lgfn] = { + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "@edges\n" + " label\n" + "0 1 0\n" + "0 2 0\n" + "0 3 0\n" + "0 4 0\n" + "1 2 0\n" + "1 3 0\n" + "1 4 0\n" + "2 3 0\n" + "2 4 0\n" + "3 4 0\n", + + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "@edges\n" + " label\n" + "0 1 0\n" + "0 2 0\n" + "0 3 0\n" + "0 4 0\n" + "1 2 0\n" + "1 3 0\n" + "2 3 0\n" + "2 4 0\n" + "3 4 0\n", + + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "@edges\n" + " label\n" + "0 3 0\n" + "0 4 0\n" + "0 5 0\n" + "1 3 0\n" + "1 4 0\n" + "1 5 0\n" + "2 3 0\n" + "2 4 0\n" + "2 5 0\n", + + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "@edges\n" + " label\n" + "0 3 0\n" + "0 4 0\n" + "0 5 0\n" + "1 3 0\n" + "1 4 0\n" + "1 5 0\n" + "2 3 0\n" + "2 5 0\n" +}; + + + +typedef SmartGraph Graph; +GRAPH_TYPEDEFS(Graph); + +typedef PlanarEmbedding PE; +typedef PlanarDrawing PD; +typedef PlanarColoring PC; + +void checkEmbedding(const Graph& graph, PE& pe) { + int face_num = 0; + + Graph::ArcMap face(graph, -1); + + for (ArcIt a(graph); a != INVALID; ++a) { + if (face[a] == -1) { + Arc b = a; + while (face[b] == -1) { + face[b] = face_num; + b = pe.next(graph.oppositeArc(b)); + } + check(face[b] == face_num, "Wrong face"); + ++face_num; + } + } + check(face_num + countNodes(graph) - countConnectedComponents(graph) == + countEdges(graph) + 1, "Euler test does not passed"); +} + +void checkKuratowski(const Graph& graph, PE& pe) { + std::map degs; + for (NodeIt n(graph); n != INVALID; ++n) { + int deg = 0; + for (IncEdgeIt e(graph, n); e != INVALID; ++e) { + if (pe.kuratowski(e)) { + ++deg; + } + } + ++degs[deg]; + } + for (std::map::iterator it = degs.begin(); it != degs.end(); ++it) { + check(it->first == 0 || it->first == 2 || + (it->first == 3 && it->second == 6) || + (it->first == 4 && it->second == 5), + "Wrong degree in Kuratowski graph"); + } + + // Not full test + check((degs[3] == 0) != (degs[4] == 0), "Wrong Kuratowski graph"); +} + +bool intersect(Point e1, Point e2, Point f1, Point f2) { + int l, r; + if (std::min(e1.x, e2.x) > std::max(f1.x, f2.x)) return false; + if (std::max(e1.x, e2.x) < std::min(f1.x, f2.x)) return false; + if (std::min(e1.y, e2.y) > std::max(f1.y, f2.y)) return false; + if (std::max(e1.y, e2.y) < std::min(f1.y, f2.y)) return false; + + l = (e2.x - e1.x) * (f1.y - e1.y) - (e2.y - e1.y) * (f1.x - e1.x); + r = (e2.x - e1.x) * (f2.y - e1.y) - (e2.y - e1.y) * (f2.x - e1.x); + if (!((l >= 0 && r <= 0) || (l <= 0 && r >= 0))) return false; + l = (f2.x - f1.x) * (e1.y - f1.y) - (f2.y - f1.y) * (e1.x - f1.x); + r = (f2.x - f1.x) * (e2.y - f1.y) - (f2.y - f1.y) * (e2.x - f1.x); + if (!((l >= 0 && r <= 0) || (l <= 0 && r >= 0))) return false; + return true; +} + +bool collinear(Point p, Point q, Point r) { + int v; + v = (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x); + if (v != 0) return false; + v = (q.x - p.x) * (r.x - p.x) + (q.y - p.y) * (r.y - p.y); + if (v < 0) return false; + return true; +} + +void checkDrawing(const Graph& graph, PD& pd) { + for (Graph::NodeIt n(graph); n != INVALID; ++n) { + Graph::NodeIt m(n); + for (++m; m != INVALID; ++m) { + check(pd[m] != pd[n], "Two nodes with identical coordinates"); + } + } + + for (Graph::EdgeIt e(graph); e != INVALID; ++e) { + for (Graph::EdgeIt f(e); f != e; ++f) { + Point e1 = pd[graph.u(e)]; + Point e2 = pd[graph.v(e)]; + Point f1 = pd[graph.u(f)]; + Point f2 = pd[graph.v(f)]; + + if (graph.u(e) == graph.u(f)) { + check(!collinear(e1, e2, f2), "Wrong drawing"); + } else if (graph.u(e) == graph.v(f)) { + check(!collinear(e1, e2, f1), "Wrong drawing"); + } else if (graph.v(e) == graph.u(f)) { + check(!collinear(e2, e1, f2), "Wrong drawing"); + } else if (graph.v(e) == graph.v(f)) { + check(!collinear(e2, e1, f1), "Wrong drawing"); + } else { + check(!intersect(e1, e2, f1, f2), "Wrong drawing"); + } + } + } +} + +void checkColoring(const Graph& graph, PC& pc, int num) { + for (NodeIt n(graph); n != INVALID; ++n) { + check(pc.colorIndex(n) >= 0 && pc.colorIndex(n) < num, + "Wrong coloring"); + } + for (EdgeIt e(graph); e != INVALID; ++e) { + check(pc.colorIndex(graph.u(e)) != pc.colorIndex(graph.v(e)), + "Wrong coloring"); + } +} + +int main() { + + for (int i = 0; i < lgfn; ++i) { + std::istringstream lgfs(lgf[i]); + + SmartGraph graph; + graphReader(graph, lgfs).run(); + + check(simpleGraph(graph), "Test graphs must be simple"); + + PE pe(graph); + bool planar = pe.run(); + check(checkPlanarity(graph) == planar, "Planarity checking failed"); + + if (planar) { + checkEmbedding(graph, pe); + + PlanarDrawing pd(graph); + pd.run(pe.embeddingMap()); + checkDrawing(graph, pd); + + PlanarColoring pc(graph); + pc.runFiveColoring(pe.embeddingMap()); + checkColoring(graph, pc, 5); + + } else { + checkKuratowski(graph, pe); + } + } + + return 0; +} Index: test/preflow_test.cc =================================================================== --- test/preflow_test.cc (revision 1083) +++ (revision ) @@ -1,272 +1,0 @@ -/* -*- 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 "test_tools.h" -#include -#include -#include -#include -#include -#include - -using namespace lemon; - -char test_lgf[] = - "@nodes\n" - "label\n" - "0\n" - "1\n" - "2\n" - "3\n" - "4\n" - "5\n" - "6\n" - "7\n" - "8\n" - "9\n" - "@arcs\n" - " label capacity\n" - "0 1 0 20\n" - "0 2 1 0\n" - "1 1 2 3\n" - "1 2 3 8\n" - "1 3 4 8\n" - "2 5 5 5\n" - "3 2 6 5\n" - "3 5 7 5\n" - "3 6 8 5\n" - "4 3 9 3\n" - "5 7 10 3\n" - "5 6 11 10\n" - "5 8 12 10\n" - "6 8 13 8\n" - "8 9 14 20\n" - "8 1 15 5\n" - "9 5 16 5\n" - "@attributes\n" - "source 1\n" - "target 8\n"; - -void checkPreflowCompile() -{ - typedef int VType; - typedef concepts::Digraph Digraph; - - typedef Digraph::Node Node; - typedef Digraph::Arc Arc; - typedef concepts::ReadMap CapMap; - typedef concepts::ReadWriteMap FlowMap; - typedef concepts::WriteMap CutMap; - - typedef Elevator Elev; - typedef LinkedElevator LinkedElev; - - Digraph g; - Node n; - Arc e; - CapMap cap; - FlowMap flow; - CutMap cut; - VType v; - bool b; - ::lemon::ignore_unused_variable_warning(v,b); - - typedef Preflow - ::SetFlowMap - ::SetElevator - ::SetStandardElevator - ::Create PreflowType; - PreflowType preflow_test(g, cap, n, n); - const PreflowType& const_preflow_test = preflow_test; - - preflow_test - .capacityMap(cap) - .flowMap(flow) - .source(n) - .target(n); - - preflow_test.init(); - preflow_test.init(cap); - preflow_test.startFirstPhase(); - preflow_test.startSecondPhase(); - preflow_test.run(); - preflow_test.runMinCut(); - - v = const_preflow_test.flowValue(); - v = const_preflow_test.flow(e); - const FlowMap& fm = const_preflow_test.flowMap(); - b = const_preflow_test.minCut(n); - const_preflow_test.minCutMap(cut); - - ::lemon::ignore_unused_variable_warning(fm); -} - -int cutValue (const SmartDigraph& g, - const SmartDigraph::NodeMap& cut, - const SmartDigraph::ArcMap& cap) { - - int c=0; - for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { - if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; - } - return c; -} - -bool checkFlow(const SmartDigraph& g, - const SmartDigraph::ArcMap& flow, - const SmartDigraph::ArcMap& cap, - SmartDigraph::Node s, SmartDigraph::Node t) { - - for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { - if (flow[e] < 0 || flow[e] > cap[e]) return false; - } - - for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { - if (n == s || n == t) continue; - int sum = 0; - for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { - sum += flow[e]; - } - for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { - sum -= flow[e]; - } - if (sum != 0) return false; - } - return true; -} - -void initFlowTest() -{ - DIGRAPH_TYPEDEFS(SmartDigraph); - - SmartDigraph g; - SmartDigraph::ArcMap cap(g),iflow(g); - Node s=g.addNode(); Node t=g.addNode(); - Node n1=g.addNode(); Node n2=g.addNode(); - Arc a; - a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; - a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; - a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; - - Preflow pre(g,cap,s,t); - pre.init(iflow); - pre.startFirstPhase(); - check(pre.flowValue() == 10, "The incorrect max flow value."); - check(pre.minCut(s), "Wrong min cut (Node s)."); - check(pre.minCut(n1), "Wrong min cut (Node n1)."); - check(!pre.minCut(n2), "Wrong min cut (Node n2)."); - check(!pre.minCut(t), "Wrong min cut (Node t)."); -} - - -int main() { - - typedef SmartDigraph Digraph; - - typedef Digraph::Node Node; - typedef Digraph::NodeIt NodeIt; - typedef Digraph::ArcIt ArcIt; - typedef Digraph::ArcMap CapMap; - typedef Digraph::ArcMap FlowMap; - typedef Digraph::NodeMap CutMap; - - typedef Preflow PType; - - Digraph g; - Node s, t; - CapMap cap(g); - std::istringstream input(test_lgf); - DigraphReader(g,input). - arcMap("capacity", cap). - node("source",s). - node("target",t). - run(); - - PType preflow_test(g, cap, s, t); - preflow_test.run(); - - check(checkFlow(g, preflow_test.flowMap(), cap, s, t), - "The flow is not feasible."); - - CutMap min_cut(g); - preflow_test.minCutMap(min_cut); - int min_cut_value=cutValue(g,min_cut,cap); - - check(preflow_test.flowValue() == min_cut_value, - "The max flow value is not equal to the three min cut values."); - - FlowMap flow(g); - for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e]; - - int flow_value=preflow_test.flowValue(); - - for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; - preflow_test.init(flow); - preflow_test.startFirstPhase(); - - CutMap min_cut1(g); - preflow_test.minCutMap(min_cut1); - min_cut_value=cutValue(g,min_cut1,cap); - - check(preflow_test.flowValue() == min_cut_value && - min_cut_value == 2*flow_value, - "The max flow value or the min cut value is wrong."); - - preflow_test.startSecondPhase(); - - check(checkFlow(g, preflow_test.flowMap(), cap, s, t), - "The flow is not feasible."); - - CutMap min_cut2(g); - preflow_test.minCutMap(min_cut2); - min_cut_value=cutValue(g,min_cut2,cap); - - check(preflow_test.flowValue() == min_cut_value && - min_cut_value == 2*flow_value, - "The max flow value or the three min cut values were not doubled"); - - - preflow_test.flowMap(flow); - - NodeIt tmp1(g,s); - ++tmp1; - if ( tmp1 != INVALID ) s=tmp1; - - NodeIt tmp2(g,t); - ++tmp2; - if ( tmp2 != INVALID ) t=tmp2; - - preflow_test.source(s); - preflow_test.target(t); - - preflow_test.run(); - - CutMap min_cut3(g); - preflow_test.minCutMap(min_cut3); - min_cut_value=cutValue(g,min_cut3,cap); - - - check(preflow_test.flowValue() == min_cut_value, - "The max flow value or the three min cut values are incorrect."); - - initFlowTest(); - - return 0; -} Index: test/radix_sort_test.cc =================================================================== --- test/radix_sort_test.cc (revision 444) +++ test/radix_sort_test.cc (revision 1043) @@ -26,4 +26,5 @@ #include +#include #include @@ -40,6 +41,56 @@ int negate(int a) { return - a; } - -void generateIntSequence(int n, std::vector& data) { +template +bool isTheSame(T &a, T&b) +{ + typename T::iterator ai=a.begin(); + typename T::iterator bi=b.begin(); + for(;ai!=a.end()||bi!=b.end();++ai,++bi) + if(*ai!=*bi) return false; + return ai==a.end()&&bi==b.end(); +} + +template +T listsort(typename T::iterator b, typename T::iterator e) +{ + if(b==e) return T(); + typename T::iterator bn=b; + if(++bn==e) { + T l; + l.push_back(*b); + return l; + } + typename T::iterator m=b; + bool x=false; + for(typename T::iterator i=b;i!=e;++i,x=!x) + if(x) ++m; + T l1(listsort(b,m)); + T l2(listsort(m,e)); + T l; + while((!l1.empty())&&(!l2.empty())) + if(l1.front()<=l2.front()) + { + l.push_back(l1.front()); + l1.pop_front(); + } + else { + l.push_back(l2.front()); + l2.pop_front(); + } + while(!l1.empty()) + { + l.push_back(l1.front()); + l1.pop_front(); + } + while(!l2.empty()) + { + l.push_back(l2.front()); + l2.pop_front(); + } + return l; +} + +template +void generateIntSequence(int n, T & data) { int prime = 9973; int root = 136, value = 1; @@ -50,5 +101,6 @@ } -void generateCharSequence(int n, std::vector& data) { +template +void generateCharSequence(int n, T & data) { int prime = 251; int root = 3, value = root; @@ -72,14 +124,90 @@ } - radixSort(data2.begin(), data2.end(), Negate()); + // radixSort(data2.begin(), data2.end(), Negate()); + // for (int i = 0; i < n; ++i) { + // check(data1[i] == data2[n - 1 - i], "Test failed"); + // } + + // radixSort(data2.begin(), data2.end(), negate); + // for (int i = 0; i < n; ++i) { + // check(data1[i] == data2[n - 1 - i], "Test failed"); + // } + + } + + { + std::vector data1(n); + generateCharSequence(n, data1); + + std::vector data2(data1); + std::sort(data1.begin(), data1.end()); + + radixSort(data2.begin(), data2.end()); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[i], "Test failed"); + } + + } + { + std::list data1; + generateIntSequence(n, data1); + + std::list data2(listsort >(data1.begin(), data1.end())); + + radixSort(data1.begin(), data1.end()); + + check(isTheSame(data1,data2), "Test failed"); + + + // radixSort(data2.begin(), data2.end(), Negate()); + // check(isTheSame(data1,data2), "Test failed"); + // for (int i = 0; i < n; ++i) { + // check(data1[i] == data2[n - 1 - i], "Test failed"); + // } + + // radixSort(data2.begin(), data2.end(), negate); + // for (int i = 0; i < n; ++i) { + // check(data1[i] == data2[n - 1 - i], "Test failed"); + // } + + } + + { + std::list data1(n); + generateCharSequence(n, data1); + + std::list data2(listsort > + (data1.begin(), + data1.end())); + + radixSort(data1.begin(), data1.end()); + check(isTheSame(data1,data2), "Test failed"); + + } +} + + +void checkStableRadixSort() { + { + std::vector data1; + generateIntSequence(n, data1); + + std::vector data2(data1); + std::sort(data1.begin(), data1.end()); + + stableRadixSort(data2.begin(), data2.end()); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[i], "Test failed"); + } + + stableRadixSort(data2.begin(), data2.end(), Negate()); for (int i = 0; i < n; ++i) { check(data1[i] == data2[n - 1 - i], "Test failed"); } - radixSort(data2.begin(), data2.end(), negate); + stableRadixSort(data2.begin(), data2.end(), negate); for (int i = 0; i < n; ++i) { check(data1[i] == data2[n - 1 - i], "Test failed"); } - } @@ -97,42 +225,33 @@ } -} - - -void checkStableRadixSort() { - { - std::vector data1; - generateIntSequence(n, data1); - - std::vector data2(data1); - std::sort(data1.begin(), data1.end()); - - stableRadixSort(data2.begin(), data2.end()); - for (int i = 0; i < n; ++i) { - check(data1[i] == data2[i], "Test failed"); - } - - stableRadixSort(data2.begin(), data2.end(), Negate()); - for (int i = 0; i < n; ++i) { - check(data1[i] == data2[n - 1 - i], "Test failed"); - } - - stableRadixSort(data2.begin(), data2.end(), negate); - for (int i = 0; i < n; ++i) { - check(data1[i] == data2[n - 1 - i], "Test failed"); - } - } - - { - std::vector data1(n); - generateCharSequence(n, data1); - - std::vector data2(data1); - std::sort(data1.begin(), data1.end()); - - radixSort(data2.begin(), data2.end()); - for (int i = 0; i < n; ++i) { - check(data1[i] == data2[i], "Test failed"); - } + { + std::list data1; + generateIntSequence(n, data1); + + std::list data2(listsort >(data1.begin(), + data1.end())); + stableRadixSort(data1.begin(), data1.end()); + check(isTheSame(data1,data2), "Test failed"); + + // stableRadixSort(data2.begin(), data2.end(), Negate()); + // for (int i = 0; i < n; ++i) { + // check(data1[i] == data2[n - 1 - i], "Test failed"); + // } + + // stableRadixSort(data2.begin(), data2.end(), negate); + // for (int i = 0; i < n; ++i) { + // check(data1[i] == data2[n - 1 - i], "Test failed"); + // } + } + + { + std::list data1(n); + generateCharSequence(n, data1); + + std::list data2(listsort > + (data1.begin(), + data1.end())); + radixSort(data1.begin(), data1.end()); + check(isTheSame(data1,data2), "Test failed"); } Index: test/suurballe_test.cc =================================================================== --- test/suurballe_test.cc (revision 1083) +++ test/suurballe_test.cc (revision 1084) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -24,4 +24,5 @@ #include #include +#include #include "test_tools.h" @@ -81,6 +82,12 @@ typedef Digraph::Arc Arc; typedef concepts::ReadMap LengthMap; - - typedef Suurballe SuurballeType; + + typedef Suurballe ST; + typedef Suurballe + ::SetFlowMap + ::SetPotentialMap + ::SetPath > + ::SetHeap > > + ::Create SuurballeType; Digraph g; @@ -102,8 +109,11 @@ k = suurb_test.run(n, n, k); suurb_test.init(n); + suurb_test.fullInit(n); + suurb_test.start(n); + suurb_test.start(n, k); k = suurb_test.findFlow(n); k = suurb_test.findFlow(n, k); suurb_test.findPaths(); - + int f; VType c; @@ -119,5 +129,5 @@ k = const_suurb_test.pathNum(); Path p = const_suurb_test.path(k); - + ::lemon::ignore_unused_variable_warning(fm); ::lemon::ignore_unused_variable_warning(pm); @@ -198,7 +208,9 @@ run(); - // Find 2 paths + // Check run() { Suurballe suurballe(digraph, length); + + // Find 2 paths check(suurballe.run(s, t) == 2, "Wrong number of paths"); check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), @@ -210,9 +222,6 @@ for (int i = 0; i < suurballe.pathNum(); ++i) check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); - } - - // Find 3 paths - { - Suurballe suurballe(digraph, length); + + // Find 3 paths check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), @@ -224,9 +233,6 @@ for (int i = 0; i < suurballe.pathNum(); ++i) check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); - } - - // Find 5 paths (only 3 can be found) - { - Suurballe suurballe(digraph, length); + + // Find 5 paths (only 3 can be found) check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), @@ -240,4 +246,22 @@ } + // Check fullInit() + start() + { + Suurballe suurballe(digraph, length); + suurballe.fullInit(s); + + // Find 2 paths + check(suurballe.start(t) == 2, "Wrong number of paths"); + check(suurballe.totalLength() == 510, "The flow is not optimal"); + + // Find 3 paths + check(suurballe.start(t, 3) == 3, "Wrong number of paths"); + check(suurballe.totalLength() == 1040, "The flow is not optimal"); + + // Find 5 paths (only 3 can be found) + check(suurballe.start(t, 5) == 3, "Wrong number of paths"); + check(suurballe.totalLength() == 1040, "The flow is not optimal"); + } + return 0; } Index: test/test_tools.h =================================================================== --- test/test_tools.h (revision 440) +++ test/test_tools.h (revision 877) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -38,9 +38,13 @@ ///print something like this (and then exits). ///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim -#define check(rc, msg) \ - if(!(rc)) { \ - std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \ - abort(); \ - } else { } \ +#define check(rc, msg) \ + { \ + if(!(rc)) { \ + std::cerr << __FILE__ ":" << __LINE__ << ": error: " \ + << msg << std::endl; \ + abort(); \ + } else { } \ + } \ + #endif Index: test/tsp_test.cc =================================================================== --- test/tsp_test.cc (revision 1037) +++ test/tsp_test.cc (revision 1037) @@ -0,0 +1,283 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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 +#include +#include +#include +#include + +#include "test_tools.h" + +using namespace lemon; + +// // Tests checkMetricCost() function +// void metricCostTest() { +// GRAPH_TYPEDEFS(FullGraph); +// FullGraph g(10); +// check(checkMetricCost(g, constMap(0)), "Wrong checkMetricCost()"); +// check(checkMetricCost(g, constMap(1)), "Wrong checkMetricCost()"); +// check(!checkMetricCost(g, constMap(-1)), "Wrong checkMetricCost()"); +// +// FullGraph::EdgeMap cost(g); +// for (NodeIt u(g); u != INVALID; ++u) { +// for (NodeIt v(g); v != INVALID; ++v) { +// if (u == v) continue; +// float x1 = g.id(u), x2 = g.id(v); +// float y1 = x1 * x1, y2 = x2 * x2; +// cost[g.edge(u, v)] = std::sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)); +// } +// } +// check(checkMetricCost(g, cost), "Wrong checkMetricCost()"); +// float eps = Tolerance::defaultEpsilon(); +// cost[g.edge(g(0), g(9))] = +// cost[g.edge(g(0), g(8))] + cost[g.edge(g(8), g(9))] + eps * 2; +// check(!checkMetricCost(g, cost), "Wrong checkMetricCost()"); +// check(checkMetricCost(g, cost, Tolerance(eps * 4)), +// "Wrong checkMetricCost()"); +// } + +// Checks tour validity +template +bool checkTour(const FullGraph &gr, const Container &p) { + FullGraph::NodeMap used(gr, false); + + int node_cnt = 0; + for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) { + FullGraph::Node node = *it; + if (used[node]) return false; + used[node] = true; + ++node_cnt; + } + + return (node_cnt == gr.nodeNum()); +} + +// Checks tour validity +bool checkTourPath(const FullGraph &gr, const Path &p) { + FullGraph::NodeMap used(gr, false); + + if (!checkPath(gr, p)) return false; + if (gr.nodeNum() <= 1 && p.length() != 0) return false; + if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false; + + for (int i = 0; i < p.length(); ++i) { + if (used[gr.target(p.nth(i))]) return false; + used[gr.target(p.nth(i))] = true; + } + return true; +} + +// Checks tour cost +template +bool checkCost(const FullGraph &gr, const std::vector &p, + const CostMap &cost, typename CostMap::Value total) +{ + typedef typename CostMap::Value Cost; + + Cost s = 0; + for (int i = 0; i < int(p.size()) - 1; ++i) + s += cost[gr.edge(p[i], p[i+1])]; + if (int(p.size()) >= 2) + s += cost[gr.edge(p.back(), p.front())]; + + return !Tolerance().different(s, total); +} + +// Checks tour cost +template +bool checkCost(const FullGraph &, const Path &p, + const CostMap &cost, typename CostMap::Value total) +{ + typedef typename CostMap::Value Cost; + + Cost s = 0; + for (int i = 0; i < p.length(); ++i) + s += cost[p.nth(i)]; + + return !Tolerance().different(s, total); +} + +// Tests a TSP algorithm on small graphs +template +void tspTestSmall(const std::string &alg_name) { + GRAPH_TYPEDEFS(FullGraph); + + for (int n = 0; n <= 5; ++n) { + FullGraph g(n); + unsigned nsize = n; + int esize = n <= 1 ? 0 : n; + + TSP alg(g, constMap(1)); + + check(alg.run() == esize, alg_name + ": Wrong total cost"); + check(alg.tourCost() == esize, alg_name + ": Wrong total cost"); + + std::list list1(nsize), list2; + std::vector vec1(nsize), vec2; + alg.tourNodes(list1.begin()); + alg.tourNodes(vec1.begin()); + alg.tourNodes(std::front_inserter(list2)); + alg.tourNodes(std::back_inserter(vec2)); + check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence"); + check(checkTour(g, list1), alg_name + ": Wrong node sequence"); + check(checkTour(g, vec1), alg_name + ": Wrong node sequence"); + check(checkTour(g, list2), alg_name + ": Wrong node sequence"); + check(checkTour(g, vec2), alg_name + ": Wrong node sequence"); + check(checkCost(g, vec1, constMap(1), esize), + alg_name + ": Wrong tour cost"); + + SimplePath path; + alg.tour(path); + check(path.length() == esize, alg_name + ": Wrong tour"); + check(checkTourPath(g, path), alg_name + ": Wrong tour"); + check(checkCost(g, path, constMap(1), esize), + alg_name + ": Wrong tour cost"); + } +} + +// Tests a TSP algorithm on random graphs +template +void tspTestRandom(const std::string &alg_name) { + GRAPH_TYPEDEFS(FullGraph); + + FullGraph g(20); + FullGraph::NodeMap > pos(g); + DoubleEdgeMap cost(g); + + TSP alg(g, cost); + Opt2Tsp opt2(g, cost); + + for (int i = 1; i <= 3; i++) { + for (NodeIt u(g); u != INVALID; ++u) { + pos[u] = dim2::Point(rnd(), rnd()); + } + for (NodeIt u(g); u != INVALID; ++u) { + for (NodeIt v(g); v != INVALID; ++v) { + if (u == v) continue; + cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare(); + } + } + + check(alg.run() > 0, alg_name + ": Wrong total cost"); + + std::vector vec; + alg.tourNodes(std::back_inserter(vec)); + check(checkTour(g, vec), alg_name + ": Wrong node sequence"); + check(checkCost(g, vec, cost, alg.tourCost()), + alg_name + ": Wrong tour cost"); + + SimplePath path; + alg.tour(path); + check(checkTourPath(g, path), alg_name + ": Wrong tour"); + check(checkCost(g, path, cost, alg.tourCost()), + alg_name + ": Wrong tour cost"); + + check(!Tolerance().less(alg.tourCost(), opt2.run(alg.tourNodes())), + "2-opt improvement: Wrong total cost"); + check(checkTour(g, opt2.tourNodes()), + "2-opt improvement: Wrong node sequence"); + check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()), + "2-opt improvement: Wrong tour cost"); + + check(!Tolerance().less(alg.tourCost(), opt2.run(path)), + "2-opt improvement: Wrong total cost"); + check(checkTour(g, opt2.tourNodes()), + "2-opt improvement: Wrong node sequence"); + check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()), + "2-opt improvement: Wrong tour cost"); + } +} + +// Algorithm class for Nearest Insertion +template +class NearestInsertionTsp : public InsertionTsp { +public: + NearestInsertionTsp(const FullGraph &gr, const CM &cost) + : InsertionTsp(gr, cost) {} + typename CM::Value run() { + return InsertionTsp::run(InsertionTsp::NEAREST); + } +}; + +// Algorithm class for Farthest Insertion +template +class FarthestInsertionTsp : public InsertionTsp { +public: + FarthestInsertionTsp(const FullGraph &gr, const CM &cost) + : InsertionTsp(gr, cost) {} + typename CM::Value run() { + return InsertionTsp::run(InsertionTsp::FARTHEST); + } +}; + +// Algorithm class for Cheapest Insertion +template +class CheapestInsertionTsp : public InsertionTsp { +public: + CheapestInsertionTsp(const FullGraph &gr, const CM &cost) + : InsertionTsp(gr, cost) {} + typename CM::Value run() { + return InsertionTsp::run(InsertionTsp::CHEAPEST); + } +}; + +// Algorithm class for Random Insertion +template +class RandomInsertionTsp : public InsertionTsp { +public: + RandomInsertionTsp(const FullGraph &gr, const CM &cost) + : InsertionTsp(gr, cost) {} + typename CM::Value run() { + return InsertionTsp::run(InsertionTsp::RANDOM); + } +}; + +int main() { + GRAPH_TYPEDEFS(FullGraph); + + // metricCostTest(); + + tspTestSmall > >("Nearest Neighbor"); + tspTestSmall > >("Greedy"); + tspTestSmall > >("Nearest Insertion"); + tspTestSmall > >("Farthest Insertion"); + tspTestSmall > >("Cheapest Insertion"); + tspTestSmall > >("Random Insertion"); + tspTestSmall > >("Christofides"); + tspTestSmall > >("2-opt"); + + tspTestRandom >("Nearest Neighbor"); + tspTestRandom >("Greedy"); + tspTestRandom >("Nearest Insertion"); + tspTestRandom >("Farthest Insertion"); + tspTestRandom >("Cheapest Insertion"); + tspTestRandom >("Random Insertion"); + tspTestRandom >("Christofides"); + tspTestRandom >("2-opt"); + + return 0; +}