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 ladanyi@569: #include ladanyi@569: ladanyi@569: using namespace lemon; ladanyi@569: ladanyi@569: template ladanyi@569: void checkDiEulerIt(const Digraph& g) ladanyi@569: { ladanyi@569: typename Digraph::template ArcMap visitationNumber(g); ladanyi@569: ladanyi@569: DiEulerIt e(g); ladanyi@569: typename Digraph::Node firstNode = g.source(e); ladanyi@569: typename Digraph::Node lastNode; ladanyi@569: ladanyi@569: for (; e != INVALID; ++e) ladanyi@569: { ladanyi@569: if (e != INVALID) ladanyi@569: { ladanyi@569: lastNode = g.target(e); ladanyi@569: } ladanyi@569: ++visitationNumber[e]; ladanyi@569: } ladanyi@569: ladanyi@569: check(firstNode == lastNode, ladanyi@569: "checkDiEulerIt: first and last node 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, ladanyi@569: "checkDiEulerIt: not visited or multiple times visited arc found"); ladanyi@569: } ladanyi@569: } ladanyi@569: ladanyi@569: template ladanyi@569: void checkEulerIt(const Graph& g) ladanyi@569: { ladanyi@569: typename Graph::template EdgeMap visitationNumber(g); ladanyi@569: ladanyi@569: EulerIt e(g); ladanyi@569: typename Graph::Node firstNode = g.u(e); ladanyi@569: typename Graph::Node lastNode; ladanyi@569: ladanyi@569: for (; e != INVALID; ++e) ladanyi@569: { ladanyi@569: if (e != INVALID) ladanyi@569: { ladanyi@569: lastNode = g.v(e); ladanyi@569: } ladanyi@569: ++visitationNumber[e]; ladanyi@569: } ladanyi@569: ladanyi@569: check(firstNode == lastNode, ladanyi@569: "checkEulerIt: first and last node 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, ladanyi@569: "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; ladanyi@569: typedef ListGraph Graph; ladanyi@569: ladanyi@569: Digraph digraphWithEulerianCircuit; ladanyi@569: { ladanyi@569: Digraph& g = digraphWithEulerianCircuit; ladanyi@569: ladanyi@569: Digraph::Node n0 = g.addNode(); ladanyi@569: Digraph::Node n1 = g.addNode(); ladanyi@569: Digraph::Node n2 = g.addNode(); ladanyi@569: ladanyi@569: g.addArc(n0, n1); ladanyi@569: g.addArc(n1, n0); ladanyi@569: g.addArc(n1, n2); ladanyi@569: g.addArc(n2, n1); ladanyi@569: } ladanyi@569: ladanyi@569: Digraph digraphWithoutEulerianCircuit; ladanyi@569: { ladanyi@569: Digraph& g = digraphWithoutEulerianCircuit; ladanyi@569: ladanyi@569: Digraph::Node n0 = g.addNode(); ladanyi@569: Digraph::Node n1 = g.addNode(); ladanyi@569: Digraph::Node n2 = g.addNode(); ladanyi@569: ladanyi@569: g.addArc(n0, n1); ladanyi@569: g.addArc(n1, n0); ladanyi@569: g.addArc(n1, n2); ladanyi@569: } ladanyi@569: ladanyi@569: Graph graphWithEulerianCircuit; ladanyi@569: { ladanyi@569: Graph& g = graphWithEulerianCircuit; ladanyi@569: ladanyi@569: Graph::Node n0 = g.addNode(); ladanyi@569: Graph::Node n1 = g.addNode(); ladanyi@569: Graph::Node n2 = g.addNode(); ladanyi@569: ladanyi@569: g.addEdge(n0, n1); ladanyi@569: g.addEdge(n1, n2); ladanyi@569: g.addEdge(n2, n0); ladanyi@569: } ladanyi@569: ladanyi@569: Graph graphWithoutEulerianCircuit; ladanyi@569: { ladanyi@569: Graph& g = graphWithoutEulerianCircuit; ladanyi@569: ladanyi@569: Graph::Node n0 = g.addNode(); ladanyi@569: Graph::Node n1 = g.addNode(); ladanyi@569: Graph::Node n2 = g.addNode(); ladanyi@569: ladanyi@569: g.addEdge(n0, n1); ladanyi@569: g.addEdge(n1, n2); ladanyi@569: } ladanyi@569: ladanyi@569: checkDiEulerIt(digraphWithEulerianCircuit); ladanyi@569: ladanyi@569: checkEulerIt(graphWithEulerianCircuit); ladanyi@569: ladanyi@569: check(eulerian(digraphWithEulerianCircuit), ladanyi@569: "this graph should have an Eulerian circuit"); ladanyi@569: check(!eulerian(digraphWithoutEulerianCircuit), ladanyi@569: "this graph should not have an Eulerian circuit"); ladanyi@569: ladanyi@569: check(eulerian(graphWithEulerianCircuit), ladanyi@569: "this graph should have an Eulerian circuit"); ladanyi@569: check(!eulerian(graphWithoutEulerianCircuit), ladanyi@569: "this graph should have an Eulerian circuit"); ladanyi@569: ladanyi@569: return 0; ladanyi@569: }