alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@57: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. deba@57: * alpar@463: * Copyright (C) 2003-2009 deba@57: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@57: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@57: * deba@57: * Permission to use, modify and distribute this software is granted deba@57: * provided that this copyright notice appears in all copies. For deba@57: * precise terms see the accompanying LICENSE file. deba@57: * deba@57: * This software is provided "AS IS" with no warranty of any kind, deba@57: * express or implied, and with no claim as to its suitability for any deba@57: * purpose. deba@57: * deba@57: */ deba@57: deba@57: #include deba@57: #include kpeter@171: #include kpeter@821: #include deba@365: #include deba@57: deba@57: #include "test_tools.h" kpeter@171: #include "graph_test.h" deba@57: deba@57: using namespace lemon; deba@57: using namespace lemon::concepts; deba@57: deba@228: template kpeter@387: void checkDigraphBuild() { deba@228: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); deba@228: Digraph G; deba@228: deba@228: checkGraphNodeList(G, 0); deba@228: checkGraphArcList(G, 0); deba@228: kpeter@783: G.reserveNode(3); kpeter@783: G.reserveArc(4); kpeter@783: deba@228: Node deba@228: n1 = G.addNode(), deba@228: n2 = G.addNode(), deba@228: n3 = G.addNode(); deba@228: checkGraphNodeList(G, 3); deba@228: checkGraphArcList(G, 0); deba@228: deba@228: Arc a1 = G.addArc(n1, n2); deba@228: check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc"); deba@228: checkGraphNodeList(G, 3); deba@228: checkGraphArcList(G, 1); deba@228: deba@228: checkGraphOutArcList(G, n1, 1); deba@228: checkGraphOutArcList(G, n2, 0); deba@228: checkGraphOutArcList(G, n3, 0); deba@228: deba@228: checkGraphInArcList(G, n1, 0); deba@228: checkGraphInArcList(G, n2, 1); deba@228: checkGraphInArcList(G, n3, 0); deba@228: deba@228: checkGraphConArcList(G, 1); deba@228: kpeter@387: Arc a2 = G.addArc(n2, n1), kpeter@387: a3 = G.addArc(n2, n3), kpeter@387: a4 = G.addArc(n2, n3); kpeter@387: kpeter@387: checkGraphNodeList(G, 3); kpeter@387: checkGraphArcList(G, 4); kpeter@387: kpeter@387: checkGraphOutArcList(G, n1, 1); kpeter@387: checkGraphOutArcList(G, n2, 3); kpeter@387: checkGraphOutArcList(G, n3, 0); kpeter@387: kpeter@387: checkGraphInArcList(G, n1, 1); kpeter@387: checkGraphInArcList(G, n2, 1); kpeter@387: checkGraphInArcList(G, n3, 2); kpeter@387: kpeter@387: checkGraphConArcList(G, 4); kpeter@387: kpeter@387: checkNodeIds(G); kpeter@387: checkArcIds(G); kpeter@387: checkGraphNodeMap(G); kpeter@387: checkGraphArcMap(G); kpeter@387: } kpeter@387: kpeter@387: template kpeter@387: void checkDigraphSplit() { kpeter@387: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); kpeter@387: kpeter@387: Digraph G; kpeter@387: Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); kpeter@387: Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), kpeter@387: a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); kpeter@387: kpeter@387: Node n4 = G.split(n2); kpeter@387: kpeter@387: check(G.target(OutArcIt(G, n2)) == n4 && kpeter@387: G.source(InArcIt(G, n4)) == n2, kpeter@387: "Wrong split."); kpeter@387: kpeter@387: checkGraphNodeList(G, 4); kpeter@387: checkGraphArcList(G, 5); kpeter@387: kpeter@387: checkGraphOutArcList(G, n1, 1); kpeter@387: checkGraphOutArcList(G, n2, 1); kpeter@387: checkGraphOutArcList(G, n3, 0); kpeter@387: checkGraphOutArcList(G, n4, 3); kpeter@387: kpeter@387: checkGraphInArcList(G, n1, 1); kpeter@387: checkGraphInArcList(G, n2, 1); kpeter@387: checkGraphInArcList(G, n3, 2); kpeter@387: checkGraphInArcList(G, n4, 1); kpeter@387: kpeter@387: checkGraphConArcList(G, 5); kpeter@387: } kpeter@387: kpeter@387: template kpeter@387: void checkDigraphAlter() { kpeter@387: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); kpeter@387: kpeter@387: Digraph G; kpeter@387: Node n1 = G.addNode(), n2 = G.addNode(), kpeter@387: n3 = G.addNode(), n4 = G.addNode(); kpeter@387: Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), kpeter@387: a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3), kpeter@387: a5 = G.addArc(n2, n4); kpeter@387: kpeter@387: checkGraphNodeList(G, 4); kpeter@387: checkGraphArcList(G, 5); kpeter@387: kpeter@387: // Check changeSource() and changeTarget() kpeter@387: G.changeTarget(a4, n1); kpeter@387: kpeter@387: checkGraphNodeList(G, 4); kpeter@387: checkGraphArcList(G, 5); kpeter@387: kpeter@387: checkGraphOutArcList(G, n1, 1); kpeter@387: checkGraphOutArcList(G, n2, 1); kpeter@387: checkGraphOutArcList(G, n3, 0); kpeter@387: checkGraphOutArcList(G, n4, 3); kpeter@387: kpeter@387: checkGraphInArcList(G, n1, 2); kpeter@387: checkGraphInArcList(G, n2, 1); kpeter@387: checkGraphInArcList(G, n3, 1); kpeter@387: checkGraphInArcList(G, n4, 1); kpeter@387: kpeter@387: checkGraphConArcList(G, 5); kpeter@387: kpeter@387: G.changeSource(a4, n3); kpeter@387: kpeter@387: checkGraphNodeList(G, 4); kpeter@387: checkGraphArcList(G, 5); kpeter@387: kpeter@387: checkGraphOutArcList(G, n1, 1); kpeter@387: checkGraphOutArcList(G, n2, 1); kpeter@387: checkGraphOutArcList(G, n3, 1); kpeter@387: checkGraphOutArcList(G, n4, 2); kpeter@387: kpeter@387: checkGraphInArcList(G, n1, 2); kpeter@387: checkGraphInArcList(G, n2, 1); kpeter@387: checkGraphInArcList(G, n3, 1); kpeter@387: checkGraphInArcList(G, n4, 1); kpeter@387: kpeter@387: checkGraphConArcList(G, 5); kpeter@387: kpeter@387: // Check contract() kpeter@387: G.contract(n2, n4, false); kpeter@387: kpeter@387: checkGraphNodeList(G, 3); kpeter@387: checkGraphArcList(G, 5); kpeter@387: kpeter@387: checkGraphOutArcList(G, n1, 1); kpeter@387: checkGraphOutArcList(G, n2, 3); kpeter@387: checkGraphOutArcList(G, n3, 1); kpeter@387: kpeter@387: checkGraphInArcList(G, n1, 2); kpeter@387: checkGraphInArcList(G, n2, 2); kpeter@387: checkGraphInArcList(G, n3, 1); kpeter@387: kpeter@387: checkGraphConArcList(G, 5); kpeter@387: kpeter@387: G.contract(n2, n1); kpeter@387: kpeter@387: checkGraphNodeList(G, 2); kpeter@387: checkGraphArcList(G, 3); kpeter@387: kpeter@387: checkGraphOutArcList(G, n2, 2); kpeter@387: checkGraphOutArcList(G, n3, 1); kpeter@387: kpeter@387: checkGraphInArcList(G, n2, 2); kpeter@387: checkGraphInArcList(G, n3, 1); kpeter@387: kpeter@387: checkGraphConArcList(G, 3); kpeter@387: } kpeter@387: kpeter@387: template kpeter@387: void checkDigraphErase() { kpeter@387: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); kpeter@387: kpeter@387: Digraph G; kpeter@387: Node n1 = G.addNode(), n2 = G.addNode(), kpeter@387: n3 = G.addNode(), n4 = G.addNode(); kpeter@387: Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), kpeter@387: a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1), kpeter@387: a5 = G.addArc(n2, n4); kpeter@387: kpeter@387: // Check arc deletion kpeter@387: G.erase(a1); kpeter@387: kpeter@387: checkGraphNodeList(G, 4); kpeter@387: checkGraphArcList(G, 4); kpeter@387: kpeter@387: checkGraphOutArcList(G, n1, 0); kpeter@387: checkGraphOutArcList(G, n2, 1); kpeter@387: checkGraphOutArcList(G, n3, 1); kpeter@387: checkGraphOutArcList(G, n4, 2); kpeter@387: kpeter@387: checkGraphInArcList(G, n1, 2); kpeter@387: checkGraphInArcList(G, n2, 0); kpeter@387: checkGraphInArcList(G, n3, 1); kpeter@387: checkGraphInArcList(G, n4, 1); kpeter@387: kpeter@387: checkGraphConArcList(G, 4); kpeter@387: kpeter@387: // Check node deletion kpeter@387: G.erase(n4); kpeter@387: kpeter@387: checkGraphNodeList(G, 3); kpeter@387: checkGraphArcList(G, 1); kpeter@387: kpeter@387: checkGraphOutArcList(G, n1, 0); kpeter@387: checkGraphOutArcList(G, n2, 0); kpeter@387: checkGraphOutArcList(G, n3, 1); kpeter@387: checkGraphOutArcList(G, n4, 0); kpeter@387: kpeter@387: checkGraphInArcList(G, n1, 1); kpeter@387: checkGraphInArcList(G, n2, 0); kpeter@387: checkGraphInArcList(G, n3, 0); kpeter@387: checkGraphInArcList(G, n4, 0); kpeter@387: kpeter@387: checkGraphConArcList(G, 1); kpeter@387: } kpeter@387: kpeter@387: kpeter@387: template kpeter@387: void checkDigraphSnapshot() { kpeter@387: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); kpeter@387: kpeter@387: Digraph G; kpeter@387: Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); kpeter@387: Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), kpeter@387: a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); kpeter@387: kpeter@387: typename Digraph::Snapshot snapshot(G); kpeter@387: kpeter@387: Node n = G.addNode(); kpeter@387: G.addArc(n3, n); kpeter@387: G.addArc(n, n3); kpeter@387: kpeter@387: checkGraphNodeList(G, 4); kpeter@387: checkGraphArcList(G, 6); kpeter@387: kpeter@387: snapshot.restore(); kpeter@387: deba@228: checkGraphNodeList(G, 3); deba@228: checkGraphArcList(G, 4); deba@228: deba@228: checkGraphOutArcList(G, n1, 1); deba@228: checkGraphOutArcList(G, n2, 3); deba@228: checkGraphOutArcList(G, n3, 0); deba@228: deba@228: checkGraphInArcList(G, n1, 1); deba@228: checkGraphInArcList(G, n2, 1); deba@228: checkGraphInArcList(G, n3, 2); deba@228: deba@228: checkGraphConArcList(G, 4); deba@228: deba@228: checkNodeIds(G); deba@228: checkArcIds(G); deba@228: checkGraphNodeMap(G); deba@228: checkGraphArcMap(G); deba@228: kpeter@387: G.addNode(); kpeter@387: snapshot.save(G); kpeter@387: kpeter@387: G.addArc(G.addNode(), G.addNode()); kpeter@387: kpeter@387: snapshot.restore(); kpeter@787: snapshot.save(G); kpeter@787: kpeter@787: checkGraphNodeList(G, 4); kpeter@787: checkGraphArcList(G, 4); kpeter@787: kpeter@787: G.addArc(G.addNode(), G.addNode()); kpeter@787: kpeter@787: snapshot.restore(); kpeter@387: kpeter@387: checkGraphNodeList(G, 4); kpeter@387: checkGraphArcList(G, 4); deba@228: } deba@228: deba@228: void checkConcepts() { kpeter@171: { // Checking digraph components deba@57: checkConcept(); deba@57: alpar@209: checkConcept, deba@57: IDableDigraphComponent<> >(); deba@57: alpar@209: checkConcept, deba@57: IterableDigraphComponent<> >(); deba@57: alpar@209: checkConcept, deba@57: MappableDigraphComponent<> >(); deba@57: } kpeter@171: { // Checking skeleton digraph deba@57: checkConcept(); deba@57: } kpeter@171: { // Checking ListDigraph kpeter@171: checkConcept(); deba@57: checkConcept, ListDigraph>(); deba@57: checkConcept, ListDigraph>(); deba@57: checkConcept, ListDigraph>(); deba@57: checkConcept, ListDigraph>(); kpeter@171: } kpeter@171: { // Checking SmartDigraph kpeter@171: checkConcept(); kpeter@171: checkConcept, SmartDigraph>(); kpeter@171: checkConcept, SmartDigraph>(); kpeter@171: checkConcept, SmartDigraph>(); kpeter@171: } kpeter@821: { // Checking StaticDigraph kpeter@821: checkConcept(); kpeter@821: checkConcept, StaticDigraph>(); kpeter@821: } kpeter@366: { // Checking FullDigraph kpeter@366: checkConcept(); kpeter@366: } kpeter@171: } deba@57: kpeter@171: template deba@228: void checkDigraphValidity() { kpeter@171: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); kpeter@171: Digraph g; kpeter@171: kpeter@171: Node kpeter@171: n1 = g.addNode(), kpeter@171: n2 = g.addNode(), kpeter@171: n3 = g.addNode(); kpeter@171: kpeter@171: Arc kpeter@171: e1 = g.addArc(n1, n2), kpeter@171: e2 = g.addArc(n2, n3); kpeter@171: kpeter@171: check(g.valid(n1), "Wrong validity check"); kpeter@171: check(g.valid(e1), "Wrong validity check"); kpeter@171: kpeter@171: check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); kpeter@171: check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); kpeter@171: } kpeter@171: kpeter@171: template deba@228: void checkDigraphValidityErase() { kpeter@171: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); kpeter@171: Digraph g; kpeter@171: kpeter@171: Node kpeter@171: n1 = g.addNode(), kpeter@171: n2 = g.addNode(), kpeter@171: n3 = g.addNode(); kpeter@171: kpeter@171: Arc kpeter@171: e1 = g.addArc(n1, n2), kpeter@171: e2 = g.addArc(n2, n3); kpeter@171: kpeter@171: check(g.valid(n1), "Wrong validity check"); kpeter@171: check(g.valid(e1), "Wrong validity check"); kpeter@171: kpeter@171: g.erase(n1); kpeter@171: kpeter@171: check(!g.valid(n1), "Wrong validity check"); kpeter@171: check(g.valid(n2), "Wrong validity check"); kpeter@171: check(g.valid(n3), "Wrong validity check"); kpeter@171: check(!g.valid(e1), "Wrong validity check"); kpeter@171: check(g.valid(e2), "Wrong validity check"); kpeter@171: kpeter@171: check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); kpeter@171: check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); kpeter@171: } kpeter@171: kpeter@821: void checkStaticDigraph() { kpeter@821: SmartDigraph g; kpeter@821: SmartDigraph::NodeMap nref(g); kpeter@821: SmartDigraph::ArcMap aref(g); kpeter@821: kpeter@821: StaticDigraph G; kpeter@821: kpeter@821: checkGraphNodeList(G, 0); kpeter@821: checkGraphArcList(G, 0); kpeter@821: kpeter@821: G.build(g, nref, aref); kpeter@821: kpeter@821: checkGraphNodeList(G, 0); kpeter@821: checkGraphArcList(G, 0); kpeter@821: kpeter@821: SmartDigraph::Node kpeter@821: n1 = g.addNode(), kpeter@821: n2 = g.addNode(), kpeter@821: n3 = g.addNode(); kpeter@821: kpeter@821: G.build(g, nref, aref); kpeter@821: kpeter@821: checkGraphNodeList(G, 3); kpeter@821: checkGraphArcList(G, 0); kpeter@821: kpeter@821: SmartDigraph::Arc a1 = g.addArc(n1, n2); kpeter@821: kpeter@821: G.build(g, nref, aref); kpeter@821: kpeter@821: check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2], kpeter@821: "Wrong arc or wrong references"); kpeter@821: checkGraphNodeList(G, 3); kpeter@821: checkGraphArcList(G, 1); kpeter@821: kpeter@821: checkGraphOutArcList(G, nref[n1], 1); kpeter@821: checkGraphOutArcList(G, nref[n2], 0); kpeter@821: checkGraphOutArcList(G, nref[n3], 0); kpeter@821: kpeter@821: checkGraphInArcList(G, nref[n1], 0); kpeter@821: checkGraphInArcList(G, nref[n2], 1); kpeter@821: checkGraphInArcList(G, nref[n3], 0); kpeter@821: kpeter@821: checkGraphConArcList(G, 1); kpeter@821: kpeter@821: SmartDigraph::Arc kpeter@821: a2 = g.addArc(n2, n1), kpeter@821: a3 = g.addArc(n2, n3), kpeter@821: a4 = g.addArc(n2, n3); kpeter@821: kpeter@821: digraphCopy(g, G).nodeRef(nref).run(); kpeter@821: kpeter@821: checkGraphNodeList(G, 3); kpeter@821: checkGraphArcList(G, 4); kpeter@821: kpeter@821: checkGraphOutArcList(G, nref[n1], 1); kpeter@821: checkGraphOutArcList(G, nref[n2], 3); kpeter@821: checkGraphOutArcList(G, nref[n3], 0); kpeter@821: kpeter@821: checkGraphInArcList(G, nref[n1], 1); kpeter@821: checkGraphInArcList(G, nref[n2], 1); kpeter@821: checkGraphInArcList(G, nref[n3], 2); kpeter@821: kpeter@821: checkGraphConArcList(G, 4); kpeter@821: kpeter@824: std::vector > arcs; kpeter@824: arcs.push_back(std::make_pair(0,1)); kpeter@824: arcs.push_back(std::make_pair(0,2)); kpeter@824: arcs.push_back(std::make_pair(1,3)); kpeter@824: arcs.push_back(std::make_pair(1,2)); kpeter@824: arcs.push_back(std::make_pair(3,0)); kpeter@824: arcs.push_back(std::make_pair(3,3)); kpeter@824: arcs.push_back(std::make_pair(4,2)); kpeter@824: arcs.push_back(std::make_pair(4,3)); kpeter@824: arcs.push_back(std::make_pair(4,1)); kpeter@824: kpeter@824: G.build(6, arcs.begin(), arcs.end()); kpeter@824: kpeter@824: checkGraphNodeList(G, 6); kpeter@824: checkGraphArcList(G, 9); kpeter@824: kpeter@824: checkGraphOutArcList(G, G.node(0), 2); kpeter@824: checkGraphOutArcList(G, G.node(1), 2); kpeter@824: checkGraphOutArcList(G, G.node(2), 0); kpeter@824: checkGraphOutArcList(G, G.node(3), 2); kpeter@824: checkGraphOutArcList(G, G.node(4), 3); kpeter@824: checkGraphOutArcList(G, G.node(5), 0); kpeter@824: kpeter@824: checkGraphInArcList(G, G.node(0), 1); kpeter@824: checkGraphInArcList(G, G.node(1), 2); kpeter@824: checkGraphInArcList(G, G.node(2), 3); kpeter@824: checkGraphInArcList(G, G.node(3), 3); kpeter@824: checkGraphInArcList(G, G.node(4), 0); kpeter@824: checkGraphInArcList(G, G.node(5), 0); kpeter@824: kpeter@824: checkGraphConArcList(G, 9); kpeter@824: kpeter@821: checkNodeIds(G); kpeter@821: checkArcIds(G); kpeter@821: checkGraphNodeMap(G); kpeter@821: checkGraphArcMap(G); kpeter@823: kpeter@823: int n = G.nodeNum(); kpeter@823: int m = G.arcNum(); kpeter@823: check(G.index(G.node(n-1)) == n-1, "Wrong index."); kpeter@823: check(G.index(G.arc(m-1)) == m-1, "Wrong index."); kpeter@821: } kpeter@821: alpar@388: void checkFullDigraph(int num) { alpar@388: typedef FullDigraph Digraph; alpar@388: DIGRAPH_TYPEDEFS(Digraph); kpeter@784: alpar@388: Digraph G(num); kpeter@784: check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size"); kpeter@784: kpeter@784: G.resize(num); kpeter@784: check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size"); alpar@388: alpar@388: checkGraphNodeList(G, num); alpar@388: checkGraphArcList(G, num * num); alpar@388: alpar@388: for (NodeIt n(G); n != INVALID; ++n) { alpar@388: checkGraphOutArcList(G, n, num); alpar@388: checkGraphInArcList(G, n, num); alpar@388: } alpar@388: alpar@388: checkGraphConArcList(G, num * num); alpar@388: alpar@388: checkNodeIds(G); alpar@388: checkArcIds(G); alpar@388: checkGraphNodeMap(G); alpar@388: checkGraphArcMap(G); alpar@388: alpar@388: for (int i = 0; i < G.nodeNum(); ++i) { alpar@388: check(G.index(G(i)) == i, "Wrong index"); alpar@388: } alpar@388: alpar@388: for (NodeIt s(G); s != INVALID; ++s) { alpar@388: for (NodeIt t(G); t != INVALID; ++t) { alpar@388: Arc a = G.arc(s, t); alpar@388: check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup"); alpar@388: } alpar@388: } alpar@388: } alpar@388: deba@228: void checkDigraphs() { kpeter@171: { // Checking ListDigraph kpeter@387: checkDigraphBuild(); kpeter@387: checkDigraphSplit(); kpeter@387: checkDigraphAlter(); kpeter@387: checkDigraphErase(); kpeter@387: checkDigraphSnapshot(); deba@228: checkDigraphValidityErase(); deba@57: } kpeter@171: { // Checking SmartDigraph kpeter@387: checkDigraphBuild(); kpeter@387: checkDigraphSplit(); kpeter@387: checkDigraphSnapshot(); deba@228: checkDigraphValidity(); kpeter@171: } kpeter@821: { // Checking StaticDigraph kpeter@821: checkStaticDigraph(); kpeter@821: } deba@365: { // Checking FullDigraph deba@365: checkFullDigraph(8); deba@365: } kpeter@171: } deba@57: kpeter@171: int main() { deba@228: checkDigraphs(); deba@228: checkConcepts(); deba@57: return 0; deba@57: }