deba@491: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@491: * deba@491: * This file is a part of LEMON, a generic C++ optimization library. deba@491: * deba@491: * Copyright (C) 2003-2008 deba@491: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@491: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@491: * deba@491: * Permission to use, modify and distribute this software is granted deba@491: * provided that this copyright notice appears in all copies. For deba@491: * precise terms see the accompanying LICENSE file. deba@491: * deba@491: * This software is provided "AS IS" with no warranty of any kind, deba@491: * express or implied, and with no claim as to its suitability for any deba@491: * purpose. deba@491: * deba@491: */ deba@491: deba@491: #include deba@491: #include deba@491: deba@491: #include deba@491: #include deba@491: #include deba@491: deba@491: #include deba@491: deba@491: #include deba@491: deba@491: #include "graph_test.h" deba@491: #include "test_tools.h" deba@491: deba@491: using namespace lemon; deba@491: deba@491: void checkSmartArcSet() { deba@491: checkConcept >(); deba@491: deba@491: typedef ListDigraph Digraph; deba@491: typedef SmartArcSet ArcSet; deba@491: deba@491: Digraph digraph; deba@491: Digraph::Node deba@491: n1 = digraph.addNode(), deba@491: n2 = digraph.addNode(); deba@491: deba@491: Digraph::Arc ga1 = digraph.addArc(n1, n2); deba@491: deba@491: ArcSet arc_set(digraph); deba@491: deba@491: Digraph::Arc ga2 = digraph.addArc(n2, n1); deba@491: deba@491: checkGraphNodeList(arc_set, 2); deba@491: checkGraphArcList(arc_set, 0); deba@491: deba@491: Digraph::Node deba@491: n3 = digraph.addNode(); deba@491: checkGraphNodeList(arc_set, 3); deba@491: checkGraphArcList(arc_set, 0); deba@491: deba@491: ArcSet::Arc a1 = arc_set.addArc(n1, n2); deba@491: check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc"); deba@491: checkGraphNodeList(arc_set, 3); deba@491: checkGraphArcList(arc_set, 1); deba@491: deba@491: checkGraphOutArcList(arc_set, n1, 1); deba@491: checkGraphOutArcList(arc_set, n2, 0); deba@491: checkGraphOutArcList(arc_set, n3, 0); deba@491: deba@491: checkGraphInArcList(arc_set, n1, 0); deba@491: checkGraphInArcList(arc_set, n2, 1); deba@491: checkGraphInArcList(arc_set, n3, 0); deba@491: deba@491: checkGraphConArcList(arc_set, 1); deba@491: deba@491: ArcSet::Arc a2 = arc_set.addArc(n2, n1), deba@491: a3 = arc_set.addArc(n2, n3), deba@491: a4 = arc_set.addArc(n2, n3); deba@491: checkGraphNodeList(arc_set, 3); deba@491: checkGraphArcList(arc_set, 4); deba@491: deba@491: checkGraphOutArcList(arc_set, n1, 1); deba@491: checkGraphOutArcList(arc_set, n2, 3); deba@491: checkGraphOutArcList(arc_set, n3, 0); deba@491: deba@491: checkGraphInArcList(arc_set, n1, 1); deba@491: checkGraphInArcList(arc_set, n2, 1); deba@491: checkGraphInArcList(arc_set, n3, 2); deba@491: deba@491: checkGraphConArcList(arc_set, 4); deba@491: deba@491: checkNodeIds(arc_set); deba@491: checkArcIds(arc_set); deba@491: checkGraphNodeMap(arc_set); deba@491: checkGraphArcMap(arc_set); deba@491: deba@491: check(arc_set.valid(), "Wrong validity"); deba@491: digraph.erase(n1); deba@491: check(!arc_set.valid(), "Wrong validity"); deba@491: } deba@491: deba@491: void checkListArcSet() { deba@491: checkConcept >(); deba@491: deba@491: typedef ListDigraph Digraph; deba@491: typedef ListArcSet ArcSet; deba@491: deba@491: Digraph digraph; deba@491: Digraph::Node deba@491: n1 = digraph.addNode(), deba@491: n2 = digraph.addNode(); deba@491: deba@491: Digraph::Arc ga1 = digraph.addArc(n1, n2); deba@491: deba@491: ArcSet arc_set(digraph); deba@491: deba@491: Digraph::Arc ga2 = digraph.addArc(n2, n1); deba@491: deba@491: checkGraphNodeList(arc_set, 2); deba@491: checkGraphArcList(arc_set, 0); deba@491: deba@491: Digraph::Node deba@491: n3 = digraph.addNode(); deba@491: checkGraphNodeList(arc_set, 3); deba@491: checkGraphArcList(arc_set, 0); deba@491: deba@491: ArcSet::Arc a1 = arc_set.addArc(n1, n2); deba@491: check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc"); deba@491: checkGraphNodeList(arc_set, 3); deba@491: checkGraphArcList(arc_set, 1); deba@491: deba@491: checkGraphOutArcList(arc_set, n1, 1); deba@491: checkGraphOutArcList(arc_set, n2, 0); deba@491: checkGraphOutArcList(arc_set, n3, 0); deba@491: deba@491: checkGraphInArcList(arc_set, n1, 0); deba@491: checkGraphInArcList(arc_set, n2, 1); deba@491: checkGraphInArcList(arc_set, n3, 0); deba@491: deba@491: checkGraphConArcList(arc_set, 1); deba@491: deba@491: ArcSet::Arc a2 = arc_set.addArc(n2, n1), deba@491: a3 = arc_set.addArc(n2, n3), deba@491: a4 = arc_set.addArc(n2, n3); deba@491: checkGraphNodeList(arc_set, 3); deba@491: checkGraphArcList(arc_set, 4); deba@491: deba@491: checkGraphOutArcList(arc_set, n1, 1); deba@491: checkGraphOutArcList(arc_set, n2, 3); deba@491: checkGraphOutArcList(arc_set, n3, 0); deba@491: deba@491: checkGraphInArcList(arc_set, n1, 1); deba@491: checkGraphInArcList(arc_set, n2, 1); deba@491: checkGraphInArcList(arc_set, n3, 2); deba@491: deba@491: checkGraphConArcList(arc_set, 4); deba@491: deba@491: checkNodeIds(arc_set); deba@491: checkArcIds(arc_set); deba@491: checkGraphNodeMap(arc_set); deba@491: checkGraphArcMap(arc_set); deba@491: deba@491: digraph.erase(n1); deba@491: deba@491: checkGraphNodeList(arc_set, 2); deba@491: checkGraphArcList(arc_set, 2); deba@491: deba@491: checkGraphOutArcList(arc_set, n2, 2); deba@491: checkGraphOutArcList(arc_set, n3, 0); deba@491: deba@491: checkGraphInArcList(arc_set, n2, 0); deba@491: checkGraphInArcList(arc_set, n3, 2); deba@491: deba@491: checkNodeIds(arc_set); deba@491: checkArcIds(arc_set); deba@491: checkGraphNodeMap(arc_set); deba@491: checkGraphArcMap(arc_set); deba@491: deba@491: checkGraphConArcList(arc_set, 2); deba@491: } deba@491: deba@491: void checkSmartEdgeSet() { deba@491: checkConcept >(); deba@491: deba@491: typedef ListDigraph Digraph; deba@491: typedef SmartEdgeSet EdgeSet; deba@491: deba@491: Digraph digraph; deba@491: Digraph::Node deba@491: n1 = digraph.addNode(), deba@491: n2 = digraph.addNode(); deba@491: deba@491: Digraph::Arc ga1 = digraph.addArc(n1, n2); deba@491: deba@491: EdgeSet edge_set(digraph); deba@491: deba@491: Digraph::Arc ga2 = digraph.addArc(n2, n1); deba@491: deba@491: checkGraphNodeList(edge_set, 2); deba@491: checkGraphArcList(edge_set, 0); deba@491: checkGraphEdgeList(edge_set, 0); deba@491: deba@491: Digraph::Node deba@491: n3 = digraph.addNode(); deba@491: checkGraphNodeList(edge_set, 3); deba@491: checkGraphArcList(edge_set, 0); deba@491: checkGraphEdgeList(edge_set, 0); deba@491: deba@491: EdgeSet::Edge e1 = edge_set.addEdge(n1, n2); deba@491: check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) || deba@491: (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge"); deba@491: checkGraphNodeList(edge_set, 3); deba@491: checkGraphArcList(edge_set, 2); deba@491: checkGraphEdgeList(edge_set, 1); deba@491: deba@491: checkGraphOutArcList(edge_set, n1, 1); deba@491: checkGraphOutArcList(edge_set, n2, 1); deba@491: checkGraphOutArcList(edge_set, n3, 0); deba@491: deba@491: checkGraphInArcList(edge_set, n1, 1); deba@491: checkGraphInArcList(edge_set, n2, 1); deba@491: checkGraphInArcList(edge_set, n3, 0); deba@491: deba@491: checkGraphIncEdgeList(edge_set, n1, 1); deba@491: checkGraphIncEdgeList(edge_set, n2, 1); deba@491: checkGraphIncEdgeList(edge_set, n3, 0); deba@491: deba@491: checkGraphConEdgeList(edge_set, 1); deba@491: checkGraphConArcList(edge_set, 2); deba@491: deba@491: EdgeSet::Edge e2 = edge_set.addEdge(n2, n1), deba@491: e3 = edge_set.addEdge(n2, n3), deba@491: e4 = edge_set.addEdge(n2, n3); deba@491: checkGraphNodeList(edge_set, 3); deba@491: checkGraphEdgeList(edge_set, 4); deba@491: deba@491: checkGraphOutArcList(edge_set, n1, 2); deba@491: checkGraphOutArcList(edge_set, n2, 4); deba@491: checkGraphOutArcList(edge_set, n3, 2); deba@491: deba@491: checkGraphInArcList(edge_set, n1, 2); deba@491: checkGraphInArcList(edge_set, n2, 4); deba@491: checkGraphInArcList(edge_set, n3, 2); deba@491: deba@491: checkGraphIncEdgeList(edge_set, n1, 2); deba@491: checkGraphIncEdgeList(edge_set, n2, 4); deba@491: checkGraphIncEdgeList(edge_set, n3, 2); deba@491: deba@491: checkGraphConEdgeList(edge_set, 4); deba@491: checkGraphConArcList(edge_set, 8); deba@491: deba@491: checkArcDirections(edge_set); deba@491: deba@491: checkNodeIds(edge_set); deba@491: checkArcIds(edge_set); deba@491: checkEdgeIds(edge_set); deba@491: checkGraphNodeMap(edge_set); deba@491: checkGraphArcMap(edge_set); deba@491: checkGraphEdgeMap(edge_set); deba@491: deba@491: check(edge_set.valid(), "Wrong validity"); deba@491: digraph.erase(n1); deba@491: check(!edge_set.valid(), "Wrong validity"); deba@491: } deba@491: deba@491: void checkListEdgeSet() { deba@491: checkConcept >(); deba@491: deba@491: typedef ListDigraph Digraph; deba@491: typedef ListEdgeSet EdgeSet; deba@491: deba@491: Digraph digraph; deba@491: Digraph::Node deba@491: n1 = digraph.addNode(), deba@491: n2 = digraph.addNode(); deba@491: deba@491: Digraph::Arc ga1 = digraph.addArc(n1, n2); deba@491: deba@491: EdgeSet edge_set(digraph); deba@491: deba@491: Digraph::Arc ga2 = digraph.addArc(n2, n1); deba@491: deba@491: checkGraphNodeList(edge_set, 2); deba@491: checkGraphArcList(edge_set, 0); deba@491: checkGraphEdgeList(edge_set, 0); deba@491: deba@491: Digraph::Node deba@491: n3 = digraph.addNode(); deba@491: checkGraphNodeList(edge_set, 3); deba@491: checkGraphArcList(edge_set, 0); deba@491: checkGraphEdgeList(edge_set, 0); deba@491: deba@491: EdgeSet::Edge e1 = edge_set.addEdge(n1, n2); deba@491: check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) || deba@491: (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge"); deba@491: checkGraphNodeList(edge_set, 3); deba@491: checkGraphArcList(edge_set, 2); deba@491: checkGraphEdgeList(edge_set, 1); deba@491: deba@491: checkGraphOutArcList(edge_set, n1, 1); deba@491: checkGraphOutArcList(edge_set, n2, 1); deba@491: checkGraphOutArcList(edge_set, n3, 0); deba@491: deba@491: checkGraphInArcList(edge_set, n1, 1); deba@491: checkGraphInArcList(edge_set, n2, 1); deba@491: checkGraphInArcList(edge_set, n3, 0); deba@491: deba@491: checkGraphIncEdgeList(edge_set, n1, 1); deba@491: checkGraphIncEdgeList(edge_set, n2, 1); deba@491: checkGraphIncEdgeList(edge_set, n3, 0); deba@491: deba@491: checkGraphConEdgeList(edge_set, 1); deba@491: checkGraphConArcList(edge_set, 2); deba@491: deba@491: EdgeSet::Edge e2 = edge_set.addEdge(n2, n1), deba@491: e3 = edge_set.addEdge(n2, n3), deba@491: e4 = edge_set.addEdge(n2, n3); deba@491: checkGraphNodeList(edge_set, 3); deba@491: checkGraphEdgeList(edge_set, 4); deba@491: deba@491: checkGraphOutArcList(edge_set, n1, 2); deba@491: checkGraphOutArcList(edge_set, n2, 4); deba@491: checkGraphOutArcList(edge_set, n3, 2); deba@491: deba@491: checkGraphInArcList(edge_set, n1, 2); deba@491: checkGraphInArcList(edge_set, n2, 4); deba@491: checkGraphInArcList(edge_set, n3, 2); deba@491: deba@491: checkGraphIncEdgeList(edge_set, n1, 2); deba@491: checkGraphIncEdgeList(edge_set, n2, 4); deba@491: checkGraphIncEdgeList(edge_set, n3, 2); deba@491: deba@491: checkGraphConEdgeList(edge_set, 4); deba@491: checkGraphConArcList(edge_set, 8); deba@491: deba@491: checkArcDirections(edge_set); deba@491: deba@491: checkNodeIds(edge_set); deba@491: checkArcIds(edge_set); deba@491: checkEdgeIds(edge_set); deba@491: checkGraphNodeMap(edge_set); deba@491: checkGraphArcMap(edge_set); deba@491: checkGraphEdgeMap(edge_set); deba@491: deba@491: digraph.erase(n1); deba@491: deba@491: checkGraphNodeList(edge_set, 2); deba@491: checkGraphArcList(edge_set, 4); deba@491: checkGraphEdgeList(edge_set, 2); deba@491: deba@491: checkGraphOutArcList(edge_set, n2, 2); deba@491: checkGraphOutArcList(edge_set, n3, 2); deba@491: deba@491: checkGraphInArcList(edge_set, n2, 2); deba@491: checkGraphInArcList(edge_set, n3, 2); deba@491: deba@491: checkGraphIncEdgeList(edge_set, n2, 2); deba@491: checkGraphIncEdgeList(edge_set, n3, 2); deba@491: deba@491: checkNodeIds(edge_set); deba@491: checkArcIds(edge_set); deba@491: checkEdgeIds(edge_set); deba@491: checkGraphNodeMap(edge_set); deba@491: checkGraphArcMap(edge_set); deba@491: checkGraphEdgeMap(edge_set); deba@491: deba@491: checkGraphConEdgeList(edge_set, 2); deba@491: checkGraphConArcList(edge_set, 4); deba@491: deba@491: } deba@491: deba@491: deba@491: int main() { deba@491: deba@491: checkSmartArcSet(); deba@491: checkListArcSet(); deba@491: checkSmartEdgeSet(); deba@491: checkListEdgeSet(); deba@491: deba@491: return 0; deba@491: }