alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- kpeter@171: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. kpeter@171: * alpar@440: * Copyright (C) 2003-2009 kpeter@171: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport kpeter@171: * (Egervary Research Group on Combinatorial Optimization, EGRES). kpeter@171: * kpeter@171: * Permission to use, modify and distribute this software is granted kpeter@171: * provided that this copyright notice appears in all copies. For kpeter@171: * precise terms see the accompanying LICENSE file. kpeter@171: * kpeter@171: * This software is provided "AS IS" with no warranty of any kind, kpeter@171: * express or implied, and with no claim as to its suitability for any kpeter@171: * purpose. kpeter@171: * kpeter@171: */ kpeter@171: kpeter@171: #ifndef LEMON_TEST_GRAPH_TEST_H kpeter@171: #define LEMON_TEST_GRAPH_TEST_H kpeter@171: deba@228: #include deba@228: deba@220: #include deba@228: #include deba@228: kpeter@171: #include "test_tools.h" kpeter@171: kpeter@171: namespace lemon { kpeter@171: kpeter@171: template kpeter@171: void checkGraphNodeList(const Graph &G, int cnt) kpeter@171: { kpeter@171: typename Graph::NodeIt n(G); kpeter@171: for(int i=0;i deba@1019: void checkGraphRedNodeList(const Graph &G, int cnt) deba@1019: { deba@1026: typename Graph::RedNodeIt n(G); deba@1019: for(int i=0;i deba@1019: void checkGraphBlueNodeList(const Graph &G, int cnt) deba@1019: { deba@1026: typename Graph::BlueNodeIt n(G); deba@1019: for(int i=0;i kpeter@171: void checkGraphArcList(const Graph &G, int cnt) kpeter@171: { kpeter@171: typename Graph::ArcIt e(G); kpeter@171: for(int i=0;i kpeter@171: void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt) kpeter@171: { kpeter@171: typename Graph::OutArcIt e(G,n); kpeter@171: for(int i=0;i kpeter@171: void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt) kpeter@171: { kpeter@171: typename Graph::InArcIt e(G,n); kpeter@171: for(int i=0;i kpeter@171: void checkGraphEdgeList(const Graph &G, int cnt) kpeter@171: { kpeter@171: typename Graph::EdgeIt e(G); kpeter@171: for(int i=0;i kpeter@171: void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt) kpeter@171: { kpeter@171: typename Graph::IncEdgeIt e(G,n); kpeter@171: for(int i=0;i kpeter@374: void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n, kpeter@374: int cnt) kpeter@374: { kpeter@374: checkGraphIncEdgeList(G, n, cnt); kpeter@374: checkGraphOutArcList(G, n, cnt); kpeter@374: checkGraphInArcList(G, n, cnt); kpeter@374: } kpeter@374: kpeter@374: template deba@228: void checkGraphConArcList(const Graph &G, int cnt) { deba@228: int i = 0; deba@228: for (typename Graph::NodeIt u(G); u != INVALID; ++u) { deba@228: for (typename Graph::NodeIt v(G); v != INVALID; ++v) { deba@228: for (ConArcIt a(G, u, v); a != INVALID; ++a) { deba@228: check(G.source(a) == u, "Wrong iterator."); deba@228: check(G.target(a) == v, "Wrong iterator."); deba@228: ++i; deba@228: } deba@228: } deba@228: } deba@228: check(cnt == i, "Wrong iterator."); kpeter@171: } kpeter@171: kpeter@171: template deba@228: void checkGraphConEdgeList(const Graph &G, int cnt) { deba@228: int i = 0; deba@228: for (typename Graph::NodeIt u(G); u != INVALID; ++u) { deba@228: for (typename Graph::NodeIt v(G); v != INVALID; ++v) { deba@228: for (ConEdgeIt e(G, u, v); e != INVALID; ++e) { deba@228: check((G.u(e) == u && G.v(e) == v) || deba@228: (G.u(e) == v && G.v(e) == u), "Wrong iterator."); deba@228: i += u == v ? 2 : 1; deba@228: } deba@228: } deba@228: } deba@228: check(2 * cnt == i, "Wrong iterator."); kpeter@171: } kpeter@171: deba@228: template deba@228: void checkArcDirections(const Graph& G) { deba@228: for (typename Graph::ArcIt a(G); a != INVALID; ++a) { deba@228: check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction"); deba@228: check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction"); deba@228: check(G.direct(a, G.direction(a)) == a, "Wrong direction"); kpeter@171: } kpeter@171: } kpeter@171: deba@228: template deba@228: void checkNodeIds(const Graph& G) { deba@1019: typedef typename Graph::Node Node; deba@228: std::set values; deba@228: for (typename Graph::NodeIt n(G); n != INVALID; ++n) { deba@228: check(G.nodeFromId(G.id(n)) == n, "Wrong id"); deba@228: check(values.find(G.id(n)) == values.end(), "Wrong id"); deba@228: check(G.id(n) <= G.maxNodeId(), "Wrong maximum id"); deba@228: values.insert(G.id(n)); kpeter@171: } deba@1019: check(G.maxId(Node()) <= G.maxNodeId(), "Wrong maximum id"); deba@1019: } deba@1019: deba@1019: template deba@1019: void checkRedNodeIds(const Graph& G) { deba@1019: typedef typename Graph::RedNode RedNode; deba@1019: std::set values; deba@1026: for (typename Graph::RedNodeIt n(G); n != INVALID; ++n) { deba@1019: check(G.red(n), "Wrong partition"); deba@1025: check(values.find(G.id(n)) == values.end(), "Wrong id"); deba@1025: check(G.id(n) <= G.maxRedId(), "Wrong maximum id"); deba@1019: values.insert(G.id(n)); deba@1019: } deba@1019: check(G.maxId(RedNode()) == G.maxRedId(), "Wrong maximum id"); deba@1019: } deba@1019: deba@1019: template deba@1019: void checkBlueNodeIds(const Graph& G) { deba@1019: typedef typename Graph::BlueNode BlueNode; deba@1019: std::set values; deba@1026: for (typename Graph::BlueNodeIt n(G); n != INVALID; ++n) { deba@1019: check(G.blue(n), "Wrong partition"); deba@1025: check(values.find(G.id(n)) == values.end(), "Wrong id"); deba@1025: check(G.id(n) <= G.maxBlueId(), "Wrong maximum id"); deba@1019: values.insert(G.id(n)); deba@1019: } deba@1019: check(G.maxId(BlueNode()) == G.maxBlueId(), "Wrong maximum id"); kpeter@171: } kpeter@171: deba@228: template deba@228: void checkArcIds(const Graph& G) { deba@1019: typedef typename Graph::Arc Arc; deba@228: std::set values; deba@228: for (typename Graph::ArcIt a(G); a != INVALID; ++a) { deba@228: check(G.arcFromId(G.id(a)) == a, "Wrong id"); deba@228: check(values.find(G.id(a)) == values.end(), "Wrong id"); deba@228: check(G.id(a) <= G.maxArcId(), "Wrong maximum id"); deba@228: values.insert(G.id(a)); deba@228: } deba@1019: check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id"); kpeter@171: } alpar@209: deba@228: template deba@228: void checkEdgeIds(const Graph& G) { deba@1019: typedef typename Graph::Edge Edge; deba@228: std::set values; deba@228: for (typename Graph::EdgeIt e(G); e != INVALID; ++e) { deba@228: check(G.edgeFromId(G.id(e)) == e, "Wrong id"); deba@228: check(values.find(G.id(e)) == values.end(), "Wrong id"); deba@228: check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id"); deba@228: values.insert(G.id(e)); deba@228: } deba@1019: check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id"); kpeter@171: } kpeter@171: deba@228: template deba@228: void checkGraphNodeMap(const Graph& G) { deba@228: typedef typename Graph::Node Node; deba@228: typedef typename Graph::NodeIt NodeIt; deba@228: deba@228: typedef typename Graph::template NodeMap IntNodeMap; deba@228: IntNodeMap map(G, 42); deba@228: for (NodeIt it(G); it != INVALID; ++it) { deba@228: check(map[it] == 42, "Wrong map constructor."); deba@228: } deba@228: int s = 0; deba@228: for (NodeIt it(G); it != INVALID; ++it) { deba@228: map[it] = 0; deba@228: check(map[it] == 0, "Wrong operator[]."); deba@228: map.set(it, s); deba@228: check(map[it] == s, "Wrong set."); deba@228: ++s; deba@228: } deba@228: s = s * (s - 1) / 2; deba@228: for (NodeIt it(G); it != INVALID; ++it) { deba@228: s -= map[it]; deba@228: } deba@228: check(s == 0, "Wrong sum."); deba@228: kpeter@263: // map = constMap(12); kpeter@263: // for (NodeIt it(G); it != INVALID; ++it) { kpeter@263: // check(map[it] == 12, "Wrong operator[]."); kpeter@263: // } deba@228: } deba@228: deba@228: template deba@1026: void checkGraphRedNodeMap(const Graph& G) { deba@1019: typedef typename Graph::Node Node; deba@1026: typedef typename Graph::RedNodeIt RedNodeIt; deba@1019: deba@1026: typedef typename Graph::template RedNodeMap IntRedNodeMap; deba@1026: IntRedNodeMap map(G, 42); deba@1026: for (RedNodeIt it(G); it != INVALID; ++it) { deba@1019: check(map[it] == 42, "Wrong map constructor."); deba@1019: } deba@1019: int s = 0; deba@1026: for (RedNodeIt it(G); it != INVALID; ++it) { deba@1019: map[it] = 0; deba@1019: check(map[it] == 0, "Wrong operator[]."); deba@1019: map.set(it, s); deba@1019: check(map[it] == s, "Wrong set."); deba@1019: ++s; deba@1019: } deba@1019: s = s * (s - 1) / 2; deba@1026: for (RedNodeIt it(G); it != INVALID; ++it) { deba@1019: s -= map[it]; deba@1019: } deba@1019: check(s == 0, "Wrong sum."); deba@1019: deba@1019: // map = constMap(12); deba@1019: // for (NodeIt it(G); it != INVALID; ++it) { deba@1019: // check(map[it] == 12, "Wrong operator[]."); deba@1019: // } deba@1019: } deba@1019: deba@1019: template deba@1026: void checkGraphBlueNodeMap(const Graph& G) { deba@1019: typedef typename Graph::Node Node; deba@1026: typedef typename Graph::BlueNodeIt BlueNodeIt; deba@1019: deba@1026: typedef typename Graph::template BlueNodeMap IntBlueNodeMap; deba@1026: IntBlueNodeMap map(G, 42); deba@1026: for (BlueNodeIt it(G); it != INVALID; ++it) { deba@1019: check(map[it] == 42, "Wrong map constructor."); deba@1019: } deba@1019: int s = 0; deba@1026: for (BlueNodeIt it(G); it != INVALID; ++it) { deba@1019: map[it] = 0; deba@1019: check(map[it] == 0, "Wrong operator[]."); deba@1019: map.set(it, s); deba@1019: check(map[it] == s, "Wrong set."); deba@1019: ++s; deba@1019: } deba@1019: s = s * (s - 1) / 2; deba@1026: for (BlueNodeIt it(G); it != INVALID; ++it) { deba@1019: s -= map[it]; deba@1019: } deba@1019: check(s == 0, "Wrong sum."); deba@1019: deba@1019: // map = constMap(12); deba@1019: // for (NodeIt it(G); it != INVALID; ++it) { deba@1019: // check(map[it] == 12, "Wrong operator[]."); deba@1019: // } deba@1019: } deba@1019: deba@1019: template deba@228: void checkGraphArcMap(const Graph& G) { deba@228: typedef typename Graph::Arc Arc; deba@228: typedef typename Graph::ArcIt ArcIt; deba@228: deba@228: typedef typename Graph::template ArcMap IntArcMap; deba@228: IntArcMap map(G, 42); deba@228: for (ArcIt it(G); it != INVALID; ++it) { deba@228: check(map[it] == 42, "Wrong map constructor."); deba@228: } deba@228: int s = 0; deba@228: for (ArcIt it(G); it != INVALID; ++it) { deba@228: map[it] = 0; deba@228: check(map[it] == 0, "Wrong operator[]."); deba@228: map.set(it, s); deba@228: check(map[it] == s, "Wrong set."); deba@228: ++s; deba@228: } deba@228: s = s * (s - 1) / 2; deba@228: for (ArcIt it(G); it != INVALID; ++it) { deba@228: s -= map[it]; deba@228: } deba@228: check(s == 0, "Wrong sum."); deba@228: kpeter@263: // map = constMap(12); kpeter@263: // for (ArcIt it(G); it != INVALID; ++it) { kpeter@263: // check(map[it] == 12, "Wrong operator[]."); kpeter@263: // } deba@228: } deba@228: deba@228: template deba@228: void checkGraphEdgeMap(const Graph& G) { deba@228: typedef typename Graph::Edge Edge; deba@228: typedef typename Graph::EdgeIt EdgeIt; deba@228: deba@228: typedef typename Graph::template EdgeMap IntEdgeMap; deba@228: IntEdgeMap map(G, 42); deba@228: for (EdgeIt it(G); it != INVALID; ++it) { deba@228: check(map[it] == 42, "Wrong map constructor."); deba@228: } deba@228: int s = 0; deba@228: for (EdgeIt it(G); it != INVALID; ++it) { deba@228: map[it] = 0; deba@228: check(map[it] == 0, "Wrong operator[]."); deba@228: map.set(it, s); deba@228: check(map[it] == s, "Wrong set."); deba@228: ++s; deba@228: } deba@228: s = s * (s - 1) / 2; deba@228: for (EdgeIt it(G); it != INVALID; ++it) { deba@228: s -= map[it]; deba@228: } deba@228: check(s == 0, "Wrong sum."); deba@228: kpeter@263: // map = constMap(12); kpeter@263: // for (EdgeIt it(G); it != INVALID; ++it) { kpeter@263: // check(map[it] == 12, "Wrong operator[]."); kpeter@263: // } deba@228: } deba@228: deba@228: kpeter@171: } //namespace lemon kpeter@171: kpeter@171: #endif