deba@1186: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@1186: * deba@1186: * This file is a part of LEMON, a generic C++ optimization library. deba@1186: * alpar@1270: * Copyright (C) 2003-2013 deba@1186: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1186: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1186: * deba@1186: * Permission to use, modify and distribute this software is granted deba@1186: * provided that this copyright notice appears in all copies. For deba@1186: * precise terms see the accompanying LICENSE file. deba@1186: * deba@1186: * This software is provided "AS IS" with no warranty of any kind, deba@1186: * express or implied, and with no claim as to its suitability for any deba@1186: * purpose. deba@1186: * deba@1186: */ deba@1186: deba@1186: #include deba@1189: #include deba@1187: #include deba@1188: #include deba@1186: deba@1186: #include "test_tools.h" deba@1186: #include "graph_test.h" deba@1186: deba@1186: using namespace lemon; deba@1186: using namespace lemon::concepts; deba@1186: deba@1187: template deba@1187: void checkBpGraphBuild() { deba@1187: TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph); deba@1187: deba@1187: BpGraph G; deba@1187: checkGraphNodeList(G, 0); deba@1187: checkGraphRedNodeList(G, 0); deba@1187: checkGraphBlueNodeList(G, 0); deba@1187: checkGraphEdgeList(G, 0); deba@1187: checkGraphArcList(G, 0); deba@1187: deba@1187: G.reserveNode(3); deba@1187: G.reserveEdge(3); deba@1187: deba@1193: RedNode deba@1187: rn1 = G.addRedNode(); deba@1187: checkGraphNodeList(G, 1); deba@1187: checkGraphRedNodeList(G, 1); deba@1187: checkGraphBlueNodeList(G, 0); deba@1187: checkGraphEdgeList(G, 0); deba@1187: checkGraphArcList(G, 0); deba@1187: deba@1193: BlueNode deba@1187: bn1 = G.addBlueNode(), deba@1187: bn2 = G.addBlueNode(); deba@1187: checkGraphNodeList(G, 3); deba@1187: checkGraphRedNodeList(G, 1); deba@1187: checkGraphBlueNodeList(G, 2); deba@1187: checkGraphEdgeList(G, 0); deba@1187: checkGraphArcList(G, 0); deba@1187: deba@1187: Edge e1 = G.addEdge(rn1, bn2); deba@1187: check(G.redNode(e1) == rn1 && G.blueNode(e1) == bn2, "Wrong edge"); deba@1187: check(G.u(e1) == rn1 && G.v(e1) == bn2, "Wrong edge"); deba@1187: deba@1187: checkGraphNodeList(G, 3); deba@1187: checkGraphRedNodeList(G, 1); deba@1187: checkGraphBlueNodeList(G, 2); deba@1187: checkGraphEdgeList(G, 1); deba@1187: checkGraphArcList(G, 2); deba@1187: deba@1187: checkGraphIncEdgeArcLists(G, rn1, 1); deba@1187: checkGraphIncEdgeArcLists(G, bn1, 0); deba@1187: checkGraphIncEdgeArcLists(G, bn2, 1); deba@1187: deba@1187: checkGraphConEdgeList(G, 1); deba@1187: checkGraphConArcList(G, 2); deba@1187: deba@1187: Edge deba@1193: e2 = G.addEdge(bn1, rn1), deba@1187: e3 = G.addEdge(rn1, bn2); alpar@1292: ::lemon::ignore_unused_variable_warning(e2,e3); deba@1187: deba@1187: checkGraphNodeList(G, 3); deba@1187: checkGraphRedNodeList(G, 1); deba@1187: checkGraphBlueNodeList(G, 2); deba@1187: checkGraphEdgeList(G, 3); deba@1187: checkGraphArcList(G, 6); deba@1187: deba@1187: checkGraphIncEdgeArcLists(G, rn1, 3); deba@1187: checkGraphIncEdgeArcLists(G, bn1, 1); deba@1187: checkGraphIncEdgeArcLists(G, bn2, 2); deba@1187: deba@1187: checkGraphConEdgeList(G, 3); deba@1187: checkGraphConArcList(G, 6); deba@1187: deba@1187: checkArcDirections(G); deba@1187: deba@1187: checkNodeIds(G); deba@1187: checkRedNodeIds(G); deba@1187: checkBlueNodeIds(G); deba@1187: checkArcIds(G); deba@1187: checkEdgeIds(G); deba@1187: deba@1187: checkGraphNodeMap(G); deba@1194: checkGraphRedNodeMap(G); deba@1194: checkGraphBlueNodeMap(G); deba@1187: checkGraphArcMap(G); deba@1187: checkGraphEdgeMap(G); deba@1187: } deba@1187: deba@1189: template deba@1189: void checkBpGraphErase() { deba@1189: TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph); deba@1189: deba@1189: BpGraph G; deba@1193: RedNode alpar@1270: n1 = G.addRedNode(), n4 = G.addRedNode(); deba@1193: BlueNode deba@1193: n2 = G.addBlueNode(), n3 = G.addBlueNode(); deba@1189: Edge deba@1189: e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3), deba@1189: e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3); alpar@1292: ::lemon::ignore_unused_variable_warning(e1,e3,e4); deba@1189: deba@1189: // Check edge deletion deba@1189: G.erase(e2); deba@1189: deba@1189: checkGraphNodeList(G, 4); deba@1189: checkGraphRedNodeList(G, 2); deba@1189: checkGraphBlueNodeList(G, 2); deba@1189: checkGraphEdgeList(G, 3); deba@1189: checkGraphArcList(G, 6); deba@1189: deba@1189: checkGraphIncEdgeArcLists(G, n1, 1); deba@1189: checkGraphIncEdgeArcLists(G, n2, 2); deba@1189: checkGraphIncEdgeArcLists(G, n3, 1); deba@1189: checkGraphIncEdgeArcLists(G, n4, 2); deba@1189: deba@1189: checkGraphConEdgeList(G, 3); deba@1189: checkGraphConArcList(G, 6); deba@1189: deba@1189: // Check node deletion deba@1189: G.erase(n3); deba@1189: deba@1189: checkGraphNodeList(G, 3); deba@1189: checkGraphRedNodeList(G, 2); deba@1189: checkGraphBlueNodeList(G, 1); deba@1189: checkGraphEdgeList(G, 2); deba@1189: checkGraphArcList(G, 4); deba@1189: deba@1189: checkGraphIncEdgeArcLists(G, n1, 1); deba@1189: checkGraphIncEdgeArcLists(G, n2, 2); deba@1189: checkGraphIncEdgeArcLists(G, n4, 1); deba@1189: deba@1189: checkGraphConEdgeList(G, 2); deba@1189: checkGraphConArcList(G, 4); deba@1189: deba@1189: } deba@1189: deba@1189: template deba@1189: void checkBpGraphAlter() { deba@1189: TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph); deba@1189: deba@1189: BpGraph G; deba@1193: RedNode alpar@1270: n1 = G.addRedNode(), n4 = G.addRedNode(); deba@1193: BlueNode deba@1193: n2 = G.addBlueNode(), n3 = G.addBlueNode(); deba@1189: Edge deba@1189: e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3), deba@1189: e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3); alpar@1292: ::lemon::ignore_unused_variable_warning(e1,e3,e4); deba@1189: deba@1189: G.changeRed(e2, n4); deba@1189: check(G.redNode(e2) == n4, "Wrong red node"); deba@1189: check(G.blueNode(e2) == n3, "Wrong blue node"); deba@1189: deba@1189: checkGraphNodeList(G, 4); deba@1189: checkGraphRedNodeList(G, 2); deba@1189: checkGraphBlueNodeList(G, 2); deba@1189: checkGraphEdgeList(G, 4); deba@1189: checkGraphArcList(G, 8); deba@1189: deba@1189: checkGraphIncEdgeArcLists(G, n1, 1); deba@1189: checkGraphIncEdgeArcLists(G, n2, 2); deba@1189: checkGraphIncEdgeArcLists(G, n3, 2); deba@1189: checkGraphIncEdgeArcLists(G, n4, 3); deba@1189: deba@1189: checkGraphConEdgeList(G, 4); deba@1189: checkGraphConArcList(G, 8); deba@1189: deba@1189: G.changeBlue(e2, n2); deba@1189: check(G.redNode(e2) == n4, "Wrong red node"); deba@1189: check(G.blueNode(e2) == n2, "Wrong blue node"); deba@1189: deba@1189: checkGraphNodeList(G, 4); deba@1189: checkGraphRedNodeList(G, 2); deba@1189: checkGraphBlueNodeList(G, 2); deba@1189: checkGraphEdgeList(G, 4); deba@1189: checkGraphArcList(G, 8); deba@1189: deba@1189: checkGraphIncEdgeArcLists(G, n1, 1); deba@1189: checkGraphIncEdgeArcLists(G, n2, 3); deba@1189: checkGraphIncEdgeArcLists(G, n3, 1); deba@1189: checkGraphIncEdgeArcLists(G, n4, 3); deba@1189: deba@1189: checkGraphConEdgeList(G, 4); deba@1189: checkGraphConArcList(G, 8); deba@1189: } deba@1189: deba@1189: deba@1189: template deba@1187: void checkBpGraphSnapshot() { deba@1189: TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph); deba@1187: deba@1189: BpGraph G; deba@1193: RedNode deba@1193: n1 = G.addRedNode(); deba@1193: BlueNode deba@1187: n2 = G.addBlueNode(), deba@1187: n3 = G.addBlueNode(); alpar@1270: Edge deba@1187: e1 = G.addEdge(n1, n2), deba@1187: e2 = G.addEdge(n1, n3); alpar@1292: ::lemon::ignore_unused_variable_warning(e1,e2); deba@1187: deba@1187: checkGraphNodeList(G, 3); deba@1187: checkGraphRedNodeList(G, 1); deba@1187: checkGraphBlueNodeList(G, 2); deba@1187: checkGraphEdgeList(G, 2); deba@1187: checkGraphArcList(G, 4); deba@1187: deba@1189: typename BpGraph::Snapshot snapshot(G); deba@1187: deba@1193: RedNode n4 = G.addRedNode(); deba@1187: G.addEdge(n4, n2); deba@1187: G.addEdge(n4, n3); deba@1187: deba@1187: checkGraphNodeList(G, 4); deba@1187: checkGraphRedNodeList(G, 2); deba@1187: checkGraphBlueNodeList(G, 2); deba@1187: checkGraphEdgeList(G, 4); deba@1187: checkGraphArcList(G, 8); deba@1187: deba@1187: snapshot.restore(); deba@1187: deba@1187: checkGraphNodeList(G, 3); deba@1187: checkGraphRedNodeList(G, 1); deba@1187: checkGraphBlueNodeList(G, 2); deba@1187: checkGraphEdgeList(G, 2); deba@1187: checkGraphArcList(G, 4); deba@1187: deba@1187: checkGraphIncEdgeArcLists(G, n1, 2); deba@1187: checkGraphIncEdgeArcLists(G, n2, 1); deba@1187: checkGraphIncEdgeArcLists(G, n3, 1); deba@1187: deba@1187: checkGraphConEdgeList(G, 2); deba@1187: checkGraphConArcList(G, 4); deba@1187: deba@1187: checkNodeIds(G); deba@1187: checkRedNodeIds(G); deba@1187: checkBlueNodeIds(G); deba@1187: checkArcIds(G); deba@1187: checkEdgeIds(G); deba@1187: deba@1187: checkGraphNodeMap(G); deba@1194: checkGraphRedNodeMap(G); deba@1194: checkGraphBlueNodeMap(G); deba@1187: checkGraphArcMap(G); deba@1187: checkGraphEdgeMap(G); deba@1187: deba@1187: G.addRedNode(); deba@1187: snapshot.save(G); deba@1187: deba@1187: G.addEdge(G.addRedNode(), G.addBlueNode()); deba@1187: deba@1187: snapshot.restore(); deba@1187: snapshot.save(G); deba@1187: deba@1187: checkGraphNodeList(G, 4); deba@1187: checkGraphRedNodeList(G, 2); deba@1187: checkGraphBlueNodeList(G, 2); deba@1187: checkGraphEdgeList(G, 2); deba@1187: checkGraphArcList(G, 4); deba@1187: deba@1187: G.addEdge(G.addRedNode(), G.addBlueNode()); deba@1187: deba@1187: snapshot.restore(); deba@1187: deba@1187: checkGraphNodeList(G, 4); deba@1187: checkGraphRedNodeList(G, 2); deba@1187: checkGraphBlueNodeList(G, 2); deba@1187: checkGraphEdgeList(G, 2); deba@1187: checkGraphArcList(G, 4); deba@1187: } deba@1187: deba@1189: template deba@1187: void checkBpGraphValidity() { deba@1189: TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph); deba@1189: BpGraph g; deba@1187: deba@1193: RedNode deba@1193: n1 = g.addRedNode(); deba@1193: BlueNode deba@1187: n2 = g.addBlueNode(), deba@1187: n3 = g.addBlueNode(); deba@1187: deba@1187: Edge deba@1187: e1 = g.addEdge(n1, n2), deba@1187: e2 = g.addEdge(n1, n3); alpar@1292: ::lemon::ignore_unused_variable_warning(e2); deba@1187: deba@1187: check(g.valid(n1), "Wrong validity check"); deba@1187: check(g.valid(e1), "Wrong validity check"); deba@1187: check(g.valid(g.direct(e1, true)), "Wrong validity check"); deba@1187: deba@1187: check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); deba@1187: check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); deba@1187: check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); deba@1187: } deba@1187: deba@1186: void checkConcepts() { deba@1186: { // Checking graph components deba@1186: checkConcept(); deba@1186: deba@1186: checkConcept, deba@1186: IDableBpGraphComponent<> >(); deba@1186: deba@1186: checkConcept, deba@1186: IterableBpGraphComponent<> >(); deba@1186: deba@1186: checkConcept, deba@1186: AlterableBpGraphComponent<> >(); deba@1186: deba@1186: checkConcept, deba@1186: MappableBpGraphComponent<> >(); deba@1186: deba@1186: checkConcept, deba@1186: ExtendableBpGraphComponent<> >(); deba@1186: deba@1186: checkConcept, deba@1186: ErasableBpGraphComponent<> >(); deba@1186: deba@1187: checkConcept, deba@1187: ClearableBpGraphComponent<> >(); deba@1186: deba@1186: } deba@1186: { // Checking skeleton graph deba@1186: checkConcept(); deba@1186: } deba@1187: { // Checking SmartBpGraph deba@1187: checkConcept(); deba@1187: checkConcept, SmartBpGraph>(); deba@1187: checkConcept, SmartBpGraph>(); deba@1187: checkConcept, SmartBpGraph>(); deba@1187: } deba@1186: } deba@1186: deba@1188: void checkFullBpGraph(int redNum, int blueNum) { deba@1188: typedef FullBpGraph BpGraph; deba@1188: BPGRAPH_TYPEDEFS(BpGraph); deba@1188: deba@1188: BpGraph G(redNum, blueNum); deba@1188: checkGraphNodeList(G, redNum + blueNum); deba@1188: checkGraphRedNodeList(G, redNum); deba@1188: checkGraphBlueNodeList(G, blueNum); deba@1188: checkGraphEdgeList(G, redNum * blueNum); deba@1188: checkGraphArcList(G, 2 * redNum * blueNum); deba@1188: deba@1188: G.resize(redNum, blueNum); deba@1188: checkGraphNodeList(G, redNum + blueNum); deba@1188: checkGraphRedNodeList(G, redNum); deba@1188: checkGraphBlueNodeList(G, blueNum); deba@1188: checkGraphEdgeList(G, redNum * blueNum); deba@1188: checkGraphArcList(G, 2 * redNum * blueNum); deba@1188: deba@1194: for (RedNodeIt n(G); n != INVALID; ++n) { deba@1188: checkGraphOutArcList(G, n, blueNum); deba@1188: checkGraphInArcList(G, n, blueNum); deba@1188: checkGraphIncEdgeList(G, n, blueNum); deba@1188: } deba@1188: deba@1194: for (BlueNodeIt n(G); n != INVALID; ++n) { deba@1188: checkGraphOutArcList(G, n, redNum); deba@1188: checkGraphInArcList(G, n, redNum); deba@1188: checkGraphIncEdgeList(G, n, redNum); deba@1188: } deba@1188: deba@1188: checkGraphConArcList(G, 2 * redNum * blueNum); deba@1188: checkGraphConEdgeList(G, redNum * blueNum); deba@1188: deba@1188: checkArcDirections(G); deba@1188: deba@1188: checkNodeIds(G); deba@1188: checkRedNodeIds(G); deba@1188: checkBlueNodeIds(G); deba@1188: checkArcIds(G); deba@1188: checkEdgeIds(G); deba@1188: deba@1188: checkGraphNodeMap(G); deba@1194: checkGraphRedNodeMap(G); deba@1194: checkGraphBlueNodeMap(G); deba@1188: checkGraphArcMap(G); deba@1188: checkGraphEdgeMap(G); deba@1188: deba@1188: for (int i = 0; i < G.redNum(); ++i) { deba@1188: check(G.red(G.redNode(i)), "Wrong node"); deba@1193: check(G.index(G.redNode(i)) == i, "Wrong index"); deba@1188: } deba@1188: deba@1188: for (int i = 0; i < G.blueNum(); ++i) { deba@1188: check(G.blue(G.blueNode(i)), "Wrong node"); deba@1193: check(G.index(G.blueNode(i)) == i, "Wrong index"); deba@1188: } deba@1188: deba@1188: for (NodeIt u(G); u != INVALID; ++u) { deba@1188: for (NodeIt v(G); v != INVALID; ++v) { deba@1188: Edge e = G.edge(u, v); deba@1188: Arc a = G.arc(u, v); deba@1188: if (G.red(u) == G.red(v)) { deba@1188: check(e == INVALID, "Wrong edge lookup"); deba@1188: check(a == INVALID, "Wrong arc lookup"); deba@1188: } else { deba@1188: check((G.u(e) == u && G.v(e) == v) || deba@1188: (G.u(e) == v && G.v(e) == u), "Wrong edge lookup"); deba@1188: check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup"); deba@1188: } deba@1188: } deba@1188: } deba@1188: deba@1188: } deba@1188: deba@1186: void checkGraphs() { deba@1189: { // Checking ListGraph deba@1189: checkBpGraphBuild(); deba@1189: checkBpGraphErase(); deba@1189: checkBpGraphAlter(); deba@1189: checkBpGraphSnapshot(); deba@1189: checkBpGraphValidity(); deba@1189: } deba@1187: { // Checking SmartGraph deba@1187: checkBpGraphBuild(); deba@1187: checkBpGraphSnapshot(); deba@1187: checkBpGraphValidity(); deba@1187: } deba@1188: { // Checking FullBpGraph deba@1188: checkFullBpGraph(6, 8); deba@1188: checkFullBpGraph(7, 4); deba@1188: } deba@1186: } deba@1186: deba@1186: int main() { deba@1186: checkConcepts(); deba@1186: checkGraphs(); deba@1186: return 0; deba@1186: }