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