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