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