ladanyi@569: /* -*- mode: C++; indent-tabs-mode: nil; -*- ladanyi@569: * ladanyi@569: * This file is a part of LEMON, a generic C++ optimization library. ladanyi@569: * ladanyi@569: * Copyright (C) 2003-2009 ladanyi@569: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport ladanyi@569: * (Egervary Research Group on Combinatorial Optimization, EGRES). ladanyi@569: * ladanyi@569: * Permission to use, modify and distribute this software is granted ladanyi@569: * provided that this copyright notice appears in all copies. For ladanyi@569: * precise terms see the accompanying LICENSE file. ladanyi@569: * ladanyi@569: * This software is provided "AS IS" with no warranty of any kind, ladanyi@569: * express or implied, and with no claim as to its suitability for any ladanyi@569: * purpose. ladanyi@569: * ladanyi@569: */ ladanyi@569: ladanyi@569: #include ladanyi@569: #include kpeter@639: #include kpeter@639: #include "test_tools.h" ladanyi@569: ladanyi@569: using namespace lemon; ladanyi@569: ladanyi@569: template kpeter@639: void checkDiEulerIt(const Digraph& g, kpeter@639: const typename Digraph::Node& start = INVALID) ladanyi@569: { kpeter@578: typename Digraph::template ArcMap visitationNumber(g, 0); ladanyi@569: kpeter@639: DiEulerIt e(g, start); kpeter@639: if (e == INVALID) return; ladanyi@569: typename Digraph::Node firstNode = g.source(e); kpeter@578: typename Digraph::Node lastNode = g.target(e); kpeter@639: if (start != INVALID) { kpeter@639: check(firstNode == start, "checkDiEulerIt: Wrong first node"); kpeter@639: } ladanyi@569: kpeter@639: for (; e != INVALID; ++e) { kpeter@639: if (e != INVALID) lastNode = g.target(e); ladanyi@569: ++visitationNumber[e]; ladanyi@569: } ladanyi@569: ladanyi@569: check(firstNode == lastNode, kpeter@639: "checkDiEulerIt: First and last nodes are not the same"); ladanyi@569: ladanyi@569: for (typename Digraph::ArcIt a(g); a != INVALID; ++a) ladanyi@569: { ladanyi@569: check(visitationNumber[a] == 1, kpeter@639: "checkDiEulerIt: Not visited or multiple times visited arc found"); ladanyi@569: } ladanyi@569: } ladanyi@569: ladanyi@569: template kpeter@639: void checkEulerIt(const Graph& g, kpeter@639: const typename Graph::Node& start = INVALID) ladanyi@569: { kpeter@578: typename Graph::template EdgeMap visitationNumber(g, 0); ladanyi@569: kpeter@639: EulerIt e(g, start); kpeter@639: if (e == INVALID) return; kpeter@639: typename Graph::Node firstNode = g.source(typename Graph::Arc(e)); kpeter@639: typename Graph::Node lastNode = g.target(typename Graph::Arc(e)); kpeter@639: if (start != INVALID) { kpeter@639: check(firstNode == start, "checkEulerIt: Wrong first node"); kpeter@639: } ladanyi@569: kpeter@639: for (; e != INVALID; ++e) { kpeter@639: if (e != INVALID) lastNode = g.target(typename Graph::Arc(e)); ladanyi@569: ++visitationNumber[e]; ladanyi@569: } ladanyi@569: ladanyi@569: check(firstNode == lastNode, kpeter@639: "checkEulerIt: First and last nodes are not the same"); ladanyi@569: ladanyi@569: for (typename Graph::EdgeIt e(g); e != INVALID; ++e) ladanyi@569: { ladanyi@569: check(visitationNumber[e] == 1, kpeter@639: "checkEulerIt: Not visited or multiple times visited edge found"); ladanyi@569: } ladanyi@569: } ladanyi@569: ladanyi@569: int main() ladanyi@569: { ladanyi@569: typedef ListDigraph Digraph; kpeter@639: typedef Undirector Graph; kpeter@639: kpeter@639: { kpeter@639: Digraph d; kpeter@639: Graph g(d); kpeter@639: kpeter@639: checkDiEulerIt(d); kpeter@639: checkDiEulerIt(g); kpeter@639: checkEulerIt(g); ladanyi@569: kpeter@639: check(eulerian(d), "This graph is Eulerian"); kpeter@639: check(eulerian(g), "This graph is Eulerian"); kpeter@639: } ladanyi@569: { kpeter@639: Digraph d; kpeter@639: Graph g(d); kpeter@639: Digraph::Node n = d.addNode(); ladanyi@569: kpeter@639: checkDiEulerIt(d); kpeter@639: checkDiEulerIt(g); kpeter@639: checkEulerIt(g); ladanyi@569: kpeter@639: check(eulerian(d), "This graph is Eulerian"); kpeter@639: check(eulerian(g), "This graph is Eulerian"); ladanyi@569: } kpeter@639: { kpeter@639: Digraph d; kpeter@639: Graph g(d); kpeter@639: Digraph::Node n = d.addNode(); kpeter@639: d.addArc(n, n); ladanyi@569: kpeter@639: checkDiEulerIt(d); kpeter@639: checkDiEulerIt(g); kpeter@639: checkEulerIt(g); kpeter@639: kpeter@639: check(eulerian(d), "This graph is Eulerian"); kpeter@639: check(eulerian(g), "This graph is Eulerian"); kpeter@639: } ladanyi@569: { kpeter@639: Digraph d; kpeter@639: Graph g(d); kpeter@639: Digraph::Node n1 = d.addNode(); kpeter@639: Digraph::Node n2 = d.addNode(); kpeter@639: Digraph::Node n3 = d.addNode(); kpeter@639: kpeter@639: d.addArc(n1, n2); kpeter@639: d.addArc(n2, n1); kpeter@639: d.addArc(n2, n3); kpeter@639: d.addArc(n3, n2); ladanyi@569: kpeter@639: checkDiEulerIt(d); kpeter@639: checkDiEulerIt(d, n2); kpeter@639: checkDiEulerIt(g); kpeter@639: checkDiEulerIt(g, n2); kpeter@639: checkEulerIt(g); kpeter@639: checkEulerIt(g, n2); ladanyi@569: kpeter@639: check(eulerian(d), "This graph is Eulerian"); kpeter@639: check(eulerian(g), "This graph is Eulerian"); ladanyi@569: } kpeter@639: { kpeter@639: Digraph d; kpeter@639: Graph g(d); kpeter@639: Digraph::Node n1 = d.addNode(); kpeter@639: Digraph::Node n2 = d.addNode(); kpeter@639: Digraph::Node n3 = d.addNode(); kpeter@639: Digraph::Node n4 = d.addNode(); kpeter@639: Digraph::Node n5 = d.addNode(); kpeter@639: Digraph::Node n6 = d.addNode(); kpeter@639: kpeter@639: d.addArc(n1, n2); kpeter@639: d.addArc(n2, n4); kpeter@639: d.addArc(n1, n3); kpeter@639: d.addArc(n3, n4); kpeter@639: d.addArc(n4, n1); kpeter@639: d.addArc(n3, n5); kpeter@639: d.addArc(n5, n2); kpeter@639: d.addArc(n4, n6); kpeter@639: d.addArc(n2, n6); kpeter@639: d.addArc(n6, n1); kpeter@639: d.addArc(n6, n3); ladanyi@569: kpeter@639: checkDiEulerIt(d); kpeter@639: checkDiEulerIt(d, n1); kpeter@639: checkDiEulerIt(d, n5); kpeter@639: kpeter@639: checkDiEulerIt(g); kpeter@639: checkDiEulerIt(g, n1); kpeter@639: checkDiEulerIt(g, n5); kpeter@639: checkEulerIt(g); kpeter@639: checkEulerIt(g, n1); kpeter@639: checkEulerIt(g, n5); kpeter@639: kpeter@639: check(eulerian(d), "This graph is Eulerian"); kpeter@639: check(eulerian(g), "This graph is Eulerian"); kpeter@639: } ladanyi@569: { kpeter@639: Digraph d; kpeter@639: Graph g(d); kpeter@639: Digraph::Node n0 = d.addNode(); kpeter@639: Digraph::Node n1 = d.addNode(); kpeter@639: Digraph::Node n2 = d.addNode(); kpeter@639: Digraph::Node n3 = d.addNode(); kpeter@639: Digraph::Node n4 = d.addNode(); kpeter@639: Digraph::Node n5 = d.addNode(); kpeter@639: kpeter@639: d.addArc(n1, n2); kpeter@639: d.addArc(n2, n3); kpeter@639: d.addArc(n3, n1); ladanyi@569: kpeter@639: checkDiEulerIt(d); kpeter@639: checkDiEulerIt(d, n2); ladanyi@569: kpeter@639: checkDiEulerIt(g); kpeter@639: checkDiEulerIt(g, n2); kpeter@639: checkEulerIt(g); kpeter@639: checkEulerIt(g, n2); kpeter@639: kpeter@639: check(!eulerian(d), "This graph is not Eulerian"); kpeter@639: check(!eulerian(g), "This graph is not Eulerian"); ladanyi@569: } kpeter@639: { kpeter@639: Digraph d; kpeter@639: Graph g(d); kpeter@639: Digraph::Node n1 = d.addNode(); kpeter@639: Digraph::Node n2 = d.addNode(); kpeter@639: Digraph::Node n3 = d.addNode(); kpeter@639: kpeter@639: d.addArc(n1, n2); kpeter@639: d.addArc(n2, n3); ladanyi@569: kpeter@639: check(!eulerian(d), "This graph is not Eulerian"); kpeter@639: check(!eulerian(g), "This graph is not Eulerian"); ladanyi@569: } ladanyi@569: ladanyi@569: return 0; ladanyi@569: }