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