deba@416: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@414: * deba@416: * This file is a part of LEMON, a generic C++ optimization library. deba@414: * deba@414: * Copyright (C) 2003-2008 deba@414: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@414: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@414: * deba@414: * Permission to use, modify and distribute this software is granted deba@414: * provided that this copyright notice appears in all copies. For deba@414: * precise terms see the accompanying LICENSE file. deba@414: * deba@414: * This software is provided "AS IS" with no warranty of any kind, deba@414: * express or implied, and with no claim as to its suitability for any deba@414: * purpose. deba@414: * deba@414: */ deba@414: deba@414: #include deba@414: #include deba@414: deba@414: #include deba@414: #include deba@414: deba@414: #include deba@414: #include deba@414: deba@416: #include deba@414: deba@414: #include deba@414: #include deba@414: #include deba@414: deba@414: #include"test/test_tools.h" deba@414: #include"test/graph_test.h" deba@414: deba@414: using namespace lemon; deba@414: deba@416: void checkReverseDigraph() { deba@416: checkConcept >(); deba@414: deba@414: typedef ListDigraph Digraph; deba@416: typedef ReverseDigraph Adaptor; deba@414: deba@414: Digraph digraph; deba@414: Adaptor adaptor(digraph); deba@414: deba@414: Digraph::Node n1 = digraph.addNode(); deba@414: Digraph::Node n2 = digraph.addNode(); deba@414: Digraph::Node n3 = digraph.addNode(); deba@414: deba@414: Digraph::Arc a1 = digraph.addArc(n1, n2); deba@414: Digraph::Arc a2 = digraph.addArc(n1, n3); deba@414: Digraph::Arc a3 = digraph.addArc(n2, n3); deba@416: deba@414: checkGraphNodeList(adaptor, 3); deba@414: checkGraphArcList(adaptor, 3); deba@414: checkGraphConArcList(adaptor, 3); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 0); deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 2); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 2); deba@414: checkGraphInArcList(adaptor, n2, 1); deba@414: checkGraphInArcList(adaptor, n3, 0); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: deba@414: for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { deba@414: check(adaptor.source(a) == digraph.target(a), "Wrong reverse"); deba@414: check(adaptor.target(a) == digraph.source(a), "Wrong reverse"); deba@414: } deba@414: } deba@414: deba@416: void checkSubDigraph() { deba@416: checkConcept, deba@414: concepts::Digraph::ArcMap > >(); deba@414: deba@414: typedef ListDigraph Digraph; deba@414: typedef Digraph::NodeMap NodeFilter; deba@414: typedef Digraph::ArcMap ArcFilter; deba@416: typedef SubDigraph Adaptor; deba@414: deba@414: Digraph digraph; deba@414: NodeFilter node_filter(digraph); deba@414: ArcFilter arc_filter(digraph); deba@414: Adaptor adaptor(digraph, node_filter, arc_filter); deba@414: deba@414: Digraph::Node n1 = digraph.addNode(); deba@414: Digraph::Node n2 = digraph.addNode(); deba@414: Digraph::Node n3 = digraph.addNode(); deba@414: deba@414: Digraph::Arc a1 = digraph.addArc(n1, n2); deba@414: Digraph::Arc a2 = digraph.addArc(n1, n3); deba@414: Digraph::Arc a3 = digraph.addArc(n2, n3); deba@414: deba@414: node_filter[n1] = node_filter[n2] = node_filter[n3] = true; deba@414: arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; deba@414: deba@414: checkGraphNodeList(adaptor, 3); deba@414: checkGraphArcList(adaptor, 3); deba@414: checkGraphConArcList(adaptor, 3); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 2); deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 0); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 0); deba@414: checkGraphInArcList(adaptor, n2, 1); deba@414: checkGraphInArcList(adaptor, n3, 2); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: deba@416: arc_filter[a2] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 3); deba@414: checkGraphArcList(adaptor, 2); deba@414: checkGraphConArcList(adaptor, 2); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 1); deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 0); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 0); deba@414: checkGraphInArcList(adaptor, n2, 1); deba@414: checkGraphInArcList(adaptor, n3, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: deba@416: node_filter[n1] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 2); deba@414: checkGraphArcList(adaptor, 1); deba@414: checkGraphConArcList(adaptor, 1); deba@414: deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 0); deba@414: deba@414: checkGraphInArcList(adaptor, n2, 0); deba@414: checkGraphInArcList(adaptor, n3, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: deba@414: node_filter[n1] = node_filter[n2] = node_filter[n3] = false; deba@414: arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 0); deba@414: checkGraphArcList(adaptor, 0); deba@414: checkGraphConArcList(adaptor, 0); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: } deba@414: deba@416: void checkFilterNodes1() { deba@416: checkConcept > >(); deba@414: deba@414: typedef ListDigraph Digraph; deba@414: typedef Digraph::NodeMap NodeFilter; deba@416: typedef FilterNodes Adaptor; deba@414: deba@414: Digraph digraph; deba@414: NodeFilter node_filter(digraph); deba@414: Adaptor adaptor(digraph, node_filter); deba@414: deba@414: Digraph::Node n1 = digraph.addNode(); deba@414: Digraph::Node n2 = digraph.addNode(); deba@414: Digraph::Node n3 = digraph.addNode(); deba@414: deba@414: Digraph::Arc a1 = digraph.addArc(n1, n2); deba@414: Digraph::Arc a2 = digraph.addArc(n1, n3); deba@414: Digraph::Arc a3 = digraph.addArc(n2, n3); deba@414: deba@414: node_filter[n1] = node_filter[n2] = node_filter[n3] = true; deba@414: deba@414: checkGraphNodeList(adaptor, 3); deba@414: checkGraphArcList(adaptor, 3); deba@414: checkGraphConArcList(adaptor, 3); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 2); deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 0); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 0); deba@414: checkGraphInArcList(adaptor, n2, 1); deba@414: checkGraphInArcList(adaptor, n3, 2); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: deba@416: node_filter[n1] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 2); deba@414: checkGraphArcList(adaptor, 1); deba@414: checkGraphConArcList(adaptor, 1); deba@414: deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 0); deba@414: deba@414: checkGraphInArcList(adaptor, n2, 0); deba@414: checkGraphInArcList(adaptor, n3, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: deba@414: node_filter[n1] = node_filter[n2] = node_filter[n3] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 0); deba@414: checkGraphArcList(adaptor, 0); deba@414: checkGraphConArcList(adaptor, 0); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: } deba@414: deba@416: void checkFilterArcs() { deba@416: checkConcept > >(); deba@414: deba@414: typedef ListDigraph Digraph; deba@414: typedef Digraph::ArcMap ArcFilter; deba@416: typedef FilterArcs Adaptor; deba@414: deba@414: Digraph digraph; deba@414: ArcFilter arc_filter(digraph); deba@414: Adaptor adaptor(digraph, arc_filter); deba@414: deba@414: Digraph::Node n1 = digraph.addNode(); deba@414: Digraph::Node n2 = digraph.addNode(); deba@414: Digraph::Node n3 = digraph.addNode(); deba@414: deba@414: Digraph::Arc a1 = digraph.addArc(n1, n2); deba@414: Digraph::Arc a2 = digraph.addArc(n1, n3); deba@414: Digraph::Arc a3 = digraph.addArc(n2, n3); deba@414: deba@414: arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; deba@414: deba@414: checkGraphNodeList(adaptor, 3); deba@414: checkGraphArcList(adaptor, 3); deba@414: checkGraphConArcList(adaptor, 3); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 2); deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 0); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 0); deba@414: checkGraphInArcList(adaptor, n2, 1); deba@414: checkGraphInArcList(adaptor, n3, 2); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: deba@416: arc_filter[a2] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 3); deba@414: checkGraphArcList(adaptor, 2); deba@414: checkGraphConArcList(adaptor, 2); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 1); deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 0); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 0); deba@414: checkGraphInArcList(adaptor, n2, 1); deba@414: checkGraphInArcList(adaptor, n3, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: deba@414: arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 3); deba@414: checkGraphArcList(adaptor, 0); deba@414: checkGraphConArcList(adaptor, 0); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: } deba@414: deba@416: void checkUndirector() { deba@416: checkConcept >(); deba@414: deba@414: typedef ListDigraph Digraph; deba@416: typedef Undirector Adaptor; deba@414: deba@414: Digraph digraph; deba@414: Adaptor adaptor(digraph); deba@414: deba@414: Digraph::Node n1 = digraph.addNode(); deba@414: Digraph::Node n2 = digraph.addNode(); deba@414: Digraph::Node n3 = digraph.addNode(); deba@414: deba@414: Digraph::Arc a1 = digraph.addArc(n1, n2); deba@414: Digraph::Arc a2 = digraph.addArc(n1, n3); deba@414: Digraph::Arc a3 = digraph.addArc(n2, n3); deba@416: deba@414: checkGraphNodeList(adaptor, 3); deba@414: checkGraphArcList(adaptor, 6); deba@414: checkGraphEdgeList(adaptor, 3); deba@414: checkGraphConArcList(adaptor, 6); deba@414: checkGraphConEdgeList(adaptor, 3); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 2); deba@414: checkGraphOutArcList(adaptor, n2, 2); deba@414: checkGraphOutArcList(adaptor, n3, 2); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 2); deba@414: checkGraphInArcList(adaptor, n2, 2); deba@414: checkGraphInArcList(adaptor, n3, 2); deba@414: deba@414: checkGraphIncEdgeList(adaptor, n1, 2); deba@414: checkGraphIncEdgeList(adaptor, n2, 2); deba@414: checkGraphIncEdgeList(adaptor, n3, 2); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: checkEdgeIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: checkGraphEdgeMap(adaptor); deba@414: deba@414: for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) { deba@414: check(adaptor.u(e) == digraph.source(e), "Wrong undir"); deba@414: check(adaptor.v(e) == digraph.target(e), "Wrong undir"); deba@414: } deba@414: deba@414: } deba@414: deba@416: void checkResidual() { deba@416: checkConcept, deba@414: concepts::Digraph::ArcMap > >(); deba@414: deba@414: typedef ListDigraph Digraph; deba@414: typedef Digraph::ArcMap IntArcMap; deba@416: typedef Residual Adaptor; deba@414: deba@414: Digraph digraph; deba@414: IntArcMap capacity(digraph), flow(digraph); deba@414: Adaptor adaptor(digraph, capacity, flow); deba@414: deba@414: Digraph::Node n1 = digraph.addNode(); deba@414: Digraph::Node n2 = digraph.addNode(); deba@414: Digraph::Node n3 = digraph.addNode(); deba@414: Digraph::Node n4 = digraph.addNode(); deba@414: deba@414: Digraph::Arc a1 = digraph.addArc(n1, n2); deba@414: Digraph::Arc a2 = digraph.addArc(n1, n3); deba@414: Digraph::Arc a3 = digraph.addArc(n1, n4); deba@414: Digraph::Arc a4 = digraph.addArc(n2, n3); deba@414: Digraph::Arc a5 = digraph.addArc(n2, n4); deba@414: Digraph::Arc a6 = digraph.addArc(n3, n4); deba@414: deba@414: capacity[a1] = 8; deba@414: capacity[a2] = 6; deba@414: capacity[a3] = 4; deba@414: capacity[a4] = 4; deba@414: capacity[a5] = 6; deba@414: capacity[a6] = 10; deba@414: deba@414: for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { deba@414: flow[a] = 0; deba@414: } deba@416: deba@414: checkGraphNodeList(adaptor, 4); deba@414: checkGraphArcList(adaptor, 6); deba@414: checkGraphConArcList(adaptor, 6); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 3); deba@414: checkGraphOutArcList(adaptor, n2, 2); deba@414: checkGraphOutArcList(adaptor, n3, 1); deba@414: checkGraphOutArcList(adaptor, n4, 0); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 0); deba@414: checkGraphInArcList(adaptor, n2, 1); deba@414: checkGraphInArcList(adaptor, n3, 2); deba@414: checkGraphInArcList(adaptor, n4, 3); deba@414: deba@414: for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { deba@414: flow[a] = capacity[a] / 2; deba@414: } deba@416: deba@414: checkGraphNodeList(adaptor, 4); deba@414: checkGraphArcList(adaptor, 12); deba@414: checkGraphConArcList(adaptor, 12); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 3); deba@414: checkGraphOutArcList(adaptor, n2, 3); deba@414: checkGraphOutArcList(adaptor, n3, 3); deba@414: checkGraphOutArcList(adaptor, n4, 3); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 3); deba@414: checkGraphInArcList(adaptor, n2, 3); deba@414: checkGraphInArcList(adaptor, n3, 3); deba@414: checkGraphInArcList(adaptor, n4, 3); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: deba@414: for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { deba@414: flow[a] = capacity[a]; deba@414: } deba@416: deba@414: checkGraphNodeList(adaptor, 4); deba@414: checkGraphArcList(adaptor, 6); deba@414: checkGraphConArcList(adaptor, 6); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 0); deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 2); deba@414: checkGraphOutArcList(adaptor, n4, 3); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 3); deba@414: checkGraphInArcList(adaptor, n2, 2); deba@414: checkGraphInArcList(adaptor, n3, 1); deba@414: checkGraphInArcList(adaptor, n4, 0); deba@414: deba@414: for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { deba@414: flow[a] = 0; deba@414: } deba@414: deba@414: int flow_value = 0; deba@414: while (true) { deba@416: deba@414: Bfs bfs(adaptor); deba@414: bfs.run(n1, n4); deba@416: deba@414: if (!bfs.reached(n4)) break; deba@414: deba@414: Path p = bfs.path(n4); deba@416: deba@414: int min = std::numeric_limits::max(); deba@414: for (Path::ArcIt a(p); a != INVALID; ++a) { deba@416: if (adaptor.residualCapacity(a) < min) deba@416: min = adaptor.residualCapacity(a); deba@414: } deba@414: deba@414: for (Path::ArcIt a(p); a != INVALID; ++a) { deba@414: adaptor.augment(a, min); deba@414: } deba@414: flow_value += min; deba@414: } deba@414: deba@414: check(flow_value == 18, "Wrong flow with res graph adaptor"); deba@414: deba@414: } deba@414: deba@416: void checkSplitNodes() { deba@416: checkConcept >(); deba@414: deba@414: typedef ListDigraph Digraph; deba@416: typedef SplitNodes Adaptor; deba@414: deba@414: Digraph digraph; deba@414: Adaptor adaptor(digraph); deba@414: deba@414: Digraph::Node n1 = digraph.addNode(); deba@414: Digraph::Node n2 = digraph.addNode(); deba@414: Digraph::Node n3 = digraph.addNode(); deba@414: deba@414: Digraph::Arc a1 = digraph.addArc(n1, n2); deba@414: Digraph::Arc a2 = digraph.addArc(n1, n3); deba@414: Digraph::Arc a3 = digraph.addArc(n2, n3); deba@416: deba@414: checkGraphNodeList(adaptor, 6); deba@414: checkGraphArcList(adaptor, 6); deba@414: checkGraphConArcList(adaptor, 6); deba@414: deba@414: checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1); deba@414: checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2); deba@414: checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1); deba@414: checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1); deba@414: checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1); deba@414: checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0); deba@414: deba@414: checkGraphInArcList(adaptor, adaptor.inNode(n1), 0); deba@414: checkGraphInArcList(adaptor, adaptor.outNode(n1), 1); deba@414: checkGraphInArcList(adaptor, adaptor.inNode(n2), 1); deba@414: checkGraphInArcList(adaptor, adaptor.outNode(n2), 1); deba@414: checkGraphInArcList(adaptor, adaptor.inNode(n3), 2); deba@414: checkGraphInArcList(adaptor, adaptor.outNode(n3), 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@416: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: deba@414: for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { deba@414: if (adaptor.origArc(a)) { deba@414: Digraph::Arc oa = a; deba@416: check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), deba@416: "Wrong split"); deba@416: check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), deba@416: "Wrong split"); deba@414: } else { deba@414: Digraph::Node on = a; deba@414: check(adaptor.source(a) == adaptor.inNode(on), "Wrong split"); deba@414: check(adaptor.target(a) == adaptor.outNode(on), "Wrong split"); deba@414: } deba@414: } deba@414: } deba@414: deba@416: void checkSubGraph() { deba@416: checkConcept, deba@414: concepts::Graph::EdgeMap > >(); deba@414: deba@414: typedef ListGraph Graph; deba@414: typedef Graph::NodeMap NodeFilter; deba@414: typedef Graph::EdgeMap EdgeFilter; deba@416: typedef SubGraph Adaptor; deba@414: deba@414: Graph graph; deba@414: NodeFilter node_filter(graph); deba@414: EdgeFilter edge_filter(graph); deba@414: Adaptor adaptor(graph, node_filter, edge_filter); deba@414: deba@414: Graph::Node n1 = graph.addNode(); deba@414: Graph::Node n2 = graph.addNode(); deba@414: Graph::Node n3 = graph.addNode(); deba@414: Graph::Node n4 = graph.addNode(); deba@414: deba@414: Graph::Edge e1 = graph.addEdge(n1, n2); deba@414: Graph::Edge e2 = graph.addEdge(n1, n3); deba@414: Graph::Edge e3 = graph.addEdge(n2, n3); deba@414: Graph::Edge e4 = graph.addEdge(n3, n4); deba@414: deba@414: node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; deba@414: edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true; deba@414: deba@414: checkGraphNodeList(adaptor, 4); deba@414: checkGraphArcList(adaptor, 8); deba@414: checkGraphEdgeList(adaptor, 4); deba@414: checkGraphConArcList(adaptor, 8); deba@414: checkGraphConEdgeList(adaptor, 4); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 2); deba@414: checkGraphOutArcList(adaptor, n2, 2); deba@414: checkGraphOutArcList(adaptor, n3, 3); deba@414: checkGraphOutArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 2); deba@414: checkGraphInArcList(adaptor, n2, 2); deba@414: checkGraphInArcList(adaptor, n3, 3); deba@414: checkGraphInArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphIncEdgeList(adaptor, n1, 2); deba@414: checkGraphIncEdgeList(adaptor, n2, 2); deba@414: checkGraphIncEdgeList(adaptor, n3, 3); deba@414: checkGraphIncEdgeList(adaptor, n4, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: checkEdgeIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: checkGraphEdgeMap(adaptor); deba@414: deba@416: edge_filter[e2] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 4); deba@414: checkGraphArcList(adaptor, 6); deba@414: checkGraphEdgeList(adaptor, 3); deba@414: checkGraphConArcList(adaptor, 6); deba@414: checkGraphConEdgeList(adaptor, 3); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 1); deba@414: checkGraphOutArcList(adaptor, n2, 2); deba@414: checkGraphOutArcList(adaptor, n3, 2); deba@414: checkGraphOutArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 1); deba@414: checkGraphInArcList(adaptor, n2, 2); deba@414: checkGraphInArcList(adaptor, n3, 2); deba@414: checkGraphInArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphIncEdgeList(adaptor, n1, 1); deba@414: checkGraphIncEdgeList(adaptor, n2, 2); deba@414: checkGraphIncEdgeList(adaptor, n3, 2); deba@414: checkGraphIncEdgeList(adaptor, n4, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: checkEdgeIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: checkGraphEdgeMap(adaptor); deba@414: deba@416: node_filter[n1] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 3); deba@414: checkGraphArcList(adaptor, 4); deba@414: checkGraphEdgeList(adaptor, 2); deba@414: checkGraphConArcList(adaptor, 4); deba@414: checkGraphConEdgeList(adaptor, 2); deba@414: deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 2); deba@414: checkGraphOutArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphInArcList(adaptor, n2, 1); deba@414: checkGraphInArcList(adaptor, n3, 2); deba@414: checkGraphInArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphIncEdgeList(adaptor, n2, 1); deba@414: checkGraphIncEdgeList(adaptor, n3, 2); deba@414: checkGraphIncEdgeList(adaptor, n4, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: checkEdgeIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: checkGraphEdgeMap(adaptor); deba@414: deba@414: node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false; deba@414: edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 0); deba@414: checkGraphArcList(adaptor, 0); deba@414: checkGraphEdgeList(adaptor, 0); deba@414: checkGraphConArcList(adaptor, 0); deba@414: checkGraphConEdgeList(adaptor, 0); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: checkEdgeIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: checkGraphEdgeMap(adaptor); deba@414: } deba@414: deba@416: void checkFilterNodes2() { deba@416: checkConcept > >(); deba@414: deba@414: typedef ListGraph Graph; deba@414: typedef Graph::NodeMap NodeFilter; deba@416: typedef FilterNodes Adaptor; deba@414: deba@414: Graph graph; deba@414: NodeFilter node_filter(graph); deba@414: Adaptor adaptor(graph, node_filter); deba@414: deba@414: Graph::Node n1 = graph.addNode(); deba@414: Graph::Node n2 = graph.addNode(); deba@414: Graph::Node n3 = graph.addNode(); deba@414: Graph::Node n4 = graph.addNode(); deba@414: deba@414: Graph::Edge e1 = graph.addEdge(n1, n2); deba@414: Graph::Edge e2 = graph.addEdge(n1, n3); deba@414: Graph::Edge e3 = graph.addEdge(n2, n3); deba@414: Graph::Edge e4 = graph.addEdge(n3, n4); deba@414: deba@414: node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; deba@414: deba@414: checkGraphNodeList(adaptor, 4); deba@414: checkGraphArcList(adaptor, 8); deba@414: checkGraphEdgeList(adaptor, 4); deba@414: checkGraphConArcList(adaptor, 8); deba@414: checkGraphConEdgeList(adaptor, 4); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 2); deba@414: checkGraphOutArcList(adaptor, n2, 2); deba@414: checkGraphOutArcList(adaptor, n3, 3); deba@414: checkGraphOutArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 2); deba@414: checkGraphInArcList(adaptor, n2, 2); deba@414: checkGraphInArcList(adaptor, n3, 3); deba@414: checkGraphInArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphIncEdgeList(adaptor, n1, 2); deba@414: checkGraphIncEdgeList(adaptor, n2, 2); deba@414: checkGraphIncEdgeList(adaptor, n3, 3); deba@414: checkGraphIncEdgeList(adaptor, n4, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: checkEdgeIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: checkGraphEdgeMap(adaptor); deba@414: deba@416: node_filter[n1] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 3); deba@414: checkGraphArcList(adaptor, 4); deba@414: checkGraphEdgeList(adaptor, 2); deba@414: checkGraphConArcList(adaptor, 4); deba@414: checkGraphConEdgeList(adaptor, 2); deba@414: deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 2); deba@414: checkGraphOutArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphInArcList(adaptor, n2, 1); deba@414: checkGraphInArcList(adaptor, n3, 2); deba@414: checkGraphInArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphIncEdgeList(adaptor, n2, 1); deba@414: checkGraphIncEdgeList(adaptor, n3, 2); deba@414: checkGraphIncEdgeList(adaptor, n4, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: checkEdgeIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: checkGraphEdgeMap(adaptor); deba@414: deba@414: node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 0); deba@414: checkGraphArcList(adaptor, 0); deba@414: checkGraphEdgeList(adaptor, 0); deba@414: checkGraphConArcList(adaptor, 0); deba@414: checkGraphConEdgeList(adaptor, 0); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: checkEdgeIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: checkGraphEdgeMap(adaptor); deba@414: } deba@414: deba@416: void checkFilterEdges() { deba@416: checkConcept > >(); deba@414: deba@414: typedef ListGraph Graph; deba@414: typedef Graph::EdgeMap EdgeFilter; deba@416: typedef FilterEdges Adaptor; deba@414: deba@414: Graph graph; deba@414: EdgeFilter edge_filter(graph); deba@414: Adaptor adaptor(graph, edge_filter); deba@414: deba@414: Graph::Node n1 = graph.addNode(); deba@414: Graph::Node n2 = graph.addNode(); deba@414: Graph::Node n3 = graph.addNode(); deba@414: Graph::Node n4 = graph.addNode(); deba@414: deba@414: Graph::Edge e1 = graph.addEdge(n1, n2); deba@414: Graph::Edge e2 = graph.addEdge(n1, n3); deba@414: Graph::Edge e3 = graph.addEdge(n2, n3); deba@414: Graph::Edge e4 = graph.addEdge(n3, n4); deba@414: deba@414: edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true; deba@414: deba@414: checkGraphNodeList(adaptor, 4); deba@414: checkGraphArcList(adaptor, 8); deba@414: checkGraphEdgeList(adaptor, 4); deba@414: checkGraphConArcList(adaptor, 8); deba@414: checkGraphConEdgeList(adaptor, 4); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 2); deba@414: checkGraphOutArcList(adaptor, n2, 2); deba@414: checkGraphOutArcList(adaptor, n3, 3); deba@414: checkGraphOutArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 2); deba@414: checkGraphInArcList(adaptor, n2, 2); deba@414: checkGraphInArcList(adaptor, n3, 3); deba@414: checkGraphInArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphIncEdgeList(adaptor, n1, 2); deba@414: checkGraphIncEdgeList(adaptor, n2, 2); deba@414: checkGraphIncEdgeList(adaptor, n3, 3); deba@414: checkGraphIncEdgeList(adaptor, n4, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: checkEdgeIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: checkGraphEdgeMap(adaptor); deba@414: deba@416: edge_filter[e2] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 4); deba@414: checkGraphArcList(adaptor, 6); deba@414: checkGraphEdgeList(adaptor, 3); deba@414: checkGraphConArcList(adaptor, 6); deba@414: checkGraphConEdgeList(adaptor, 3); deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 1); deba@414: checkGraphOutArcList(adaptor, n2, 2); deba@414: checkGraphOutArcList(adaptor, n3, 2); deba@414: checkGraphOutArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 1); deba@414: checkGraphInArcList(adaptor, n2, 2); deba@414: checkGraphInArcList(adaptor, n3, 2); deba@414: checkGraphInArcList(adaptor, n4, 1); deba@414: deba@414: checkGraphIncEdgeList(adaptor, n1, 1); deba@414: checkGraphIncEdgeList(adaptor, n2, 2); deba@414: checkGraphIncEdgeList(adaptor, n3, 2); deba@414: checkGraphIncEdgeList(adaptor, n4, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: checkEdgeIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: checkGraphEdgeMap(adaptor); deba@414: deba@414: edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false; deba@414: deba@414: checkGraphNodeList(adaptor, 4); deba@414: checkGraphArcList(adaptor, 0); deba@414: checkGraphEdgeList(adaptor, 0); deba@414: checkGraphConArcList(adaptor, 0); deba@414: checkGraphConEdgeList(adaptor, 0); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: checkEdgeIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: checkGraphEdgeMap(adaptor); deba@414: } deba@414: deba@416: void checkOrienter() { deba@416: checkConcept > >(); deba@414: deba@414: typedef ListGraph Graph; deba@414: typedef ListGraph::EdgeMap DirMap; deba@416: typedef Orienter Adaptor; deba@414: deba@414: Graph graph; deba@414: DirMap dir(graph, true); deba@414: Adaptor adaptor(graph, dir); deba@414: deba@414: Graph::Node n1 = graph.addNode(); deba@414: Graph::Node n2 = graph.addNode(); deba@414: Graph::Node n3 = graph.addNode(); deba@414: deba@414: Graph::Edge e1 = graph.addEdge(n1, n2); deba@414: Graph::Edge e2 = graph.addEdge(n1, n3); deba@414: Graph::Edge e3 = graph.addEdge(n2, n3); deba@416: deba@414: checkGraphNodeList(adaptor, 3); deba@414: checkGraphArcList(adaptor, 3); deba@414: checkGraphConArcList(adaptor, 3); deba@416: deba@414: { deba@414: dir[e1] = true; deba@414: Adaptor::Node u = adaptor.source(e1); deba@414: Adaptor::Node v = adaptor.target(e1); deba@416: deba@414: dir[e1] = false; deba@414: check (u == adaptor.target(e1), "Wrong dir"); deba@414: check (v == adaptor.source(e1), "Wrong dir"); deba@414: deba@414: check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir"); deba@414: dir[e1] = n1 == u; deba@414: } deba@414: deba@414: { deba@414: dir[e2] = true; deba@414: Adaptor::Node u = adaptor.source(e2); deba@414: Adaptor::Node v = adaptor.target(e2); deba@416: deba@414: dir[e2] = false; deba@414: check (u == adaptor.target(e2), "Wrong dir"); deba@414: check (v == adaptor.source(e2), "Wrong dir"); deba@414: deba@414: check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir"); deba@414: dir[e2] = n3 == u; deba@414: } deba@414: deba@414: { deba@414: dir[e3] = true; deba@414: Adaptor::Node u = adaptor.source(e3); deba@414: Adaptor::Node v = adaptor.target(e3); deba@416: deba@414: dir[e3] = false; deba@414: check (u == adaptor.target(e3), "Wrong dir"); deba@414: check (v == adaptor.source(e3), "Wrong dir"); deba@414: deba@414: check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir"); deba@414: dir[e3] = n2 == u; deba@414: } deba@414: deba@414: checkGraphOutArcList(adaptor, n1, 1); deba@414: checkGraphOutArcList(adaptor, n2, 1); deba@414: checkGraphOutArcList(adaptor, n3, 1); deba@414: deba@414: checkGraphInArcList(adaptor, n1, 1); deba@414: checkGraphInArcList(adaptor, n2, 1); deba@414: checkGraphInArcList(adaptor, n3, 1); deba@414: deba@414: checkNodeIds(adaptor); deba@414: checkArcIds(adaptor); deba@414: deba@414: checkGraphNodeMap(adaptor); deba@414: checkGraphArcMap(adaptor); deba@414: deba@414: } deba@414: deba@414: deba@414: int main(int, const char **) { deba@414: deba@416: checkReverseDigraph(); deba@416: checkSubDigraph(); deba@416: checkFilterNodes1(); deba@416: checkFilterArcs(); deba@416: checkUndirector(); deba@416: checkResidual(); deba@416: checkSplitNodes(); deba@414: deba@416: checkSubGraph(); deba@416: checkFilterNodes2(); deba@416: checkFilterEdges(); deba@416: checkOrienter(); deba@414: deba@414: return 0; deba@414: }