Location: LEMON/LEMON-main/test/graph_utils_test.cc - annotation
Load file history
Reorganize header files (Ticket #97)
In addition on some places the DefaultMap<G, K, V> is replaced with
ItemSetTraits<G, K>::template Map<V>::Type, to decrease the dependencies
of different tools. It is obviously better solution.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 | r209:765619b7cbb2 r139:701c529ba737 r209:765619b7cbb2 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r139:701c529ba737 r171:02f4d5d9bfd7 r139:701c529ba737 r139:701c529ba737 r220:a5d8c039f218 r139:701c529ba737 r171:02f4d5d9bfd7 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r210:81cfc04531e8 r210:81cfc04531e8 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r210:81cfc04531e8 r210:81cfc04531e8 r210:81cfc04531e8 r210:81cfc04531e8 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r210:81cfc04531e8 r210:81cfc04531e8 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r139:701c529ba737 r171:02f4d5d9bfd7 r209:765619b7cbb2 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r209:765619b7cbb2 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r209:765619b7cbb2 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r209:765619b7cbb2 r171:02f4d5d9bfd7 r209:765619b7cbb2 r139:701c529ba737 r209:765619b7cbb2 r171:02f4d5d9bfd7 r209:765619b7cbb2 r171:02f4d5d9bfd7 r209:765619b7cbb2 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r171:02f4d5d9bfd7 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r139:701c529ba737 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r171:02f4d5d9bfd7 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 r139:701c529ba737 | /* -*- mode: C++; indent-tabs-mode: nil; -*-
*
* This file is a part of LEMON, a generic C++ optimization library.
*
* Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
*
* Permission to use, modify and distribute this software is granted
* provided that this copyright notice appears in all copies. For
* precise terms see the accompanying LICENSE file.
*
* This software is provided "AS IS" with no warranty of any kind,
* express or implied, and with no claim as to its suitability for any
* purpose.
*
*/
#include <cstdlib>
#include <ctime>
#include <lemon/random.h>
#include <lemon/list_graph.h>
#include <lemon/smart_graph.h>
#include <lemon/maps.h>
#include "graph_test.h"
#include "test_tools.h"
using namespace lemon;
template <typename Digraph>
void checkFindArcs() {
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
{
Digraph digraph;
for (int i = 0; i < 10; ++i) {
digraph.addNode();
}
DescriptorMap<Digraph, Node> nodes(digraph);
typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
for (int i = 0; i < 100; ++i) {
int src = rnd[invNodes.size()];
int trg = rnd[invNodes.size()];
digraph.addArc(invNodes[src], invNodes[trg]);
}
typename Digraph::template ArcMap<bool> found(digraph, false);
DescriptorMap<Digraph, Arc> arcs(digraph);
for (NodeIt src(digraph); src != INVALID; ++src) {
for (NodeIt trg(digraph); trg != INVALID; ++trg) {
for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
check(digraph.source(con) == src, "Wrong source.");
check(digraph.target(con) == trg, "Wrong target.");
check(found[con] == false, "The arc found already.");
found[con] = true;
}
}
}
for (ArcIt it(digraph); it != INVALID; ++it) {
check(found[it] == true, "The arc is not found.");
}
}
{
int num = 5;
Digraph fg;
std::vector<Node> nodes;
for (int i = 0; i < num; ++i) {
nodes.push_back(fg.addNode());
}
for (int i = 0; i < num * num; ++i) {
fg.addArc(nodes[i / num], nodes[i % num]);
}
check(countNodes(fg) == num, "Wrong node number.");
check(countArcs(fg) == num*num, "Wrong arc number.");
for (NodeIt src(fg); src != INVALID; ++src) {
for (NodeIt trg(fg); trg != INVALID; ++trg) {
ConArcIt<Digraph> con(fg, src, trg);
check(con != INVALID, "There is no connecting arc.");
check(fg.source(con) == src, "Wrong source.");
check(fg.target(con) == trg, "Wrong target.");
check(++con == INVALID, "There is more connecting arc.");
}
}
ArcLookUp<Digraph> al1(fg);
DynArcLookUp<Digraph> al2(fg);
AllArcLookUp<Digraph> al3(fg);
for (NodeIt src(fg); src != INVALID; ++src) {
for (NodeIt trg(fg); trg != INVALID; ++trg) {
Arc con1 = al1(src, trg);
Arc con2 = al2(src, trg);
Arc con3 = al3(src, trg);
Arc con4 = findArc(fg, src, trg);
check(con1 == con2 && con2 == con3 && con3 == con4,
"Different results.")
check(con1 != INVALID, "There is no connecting arc.");
check(fg.source(con1) == src, "Wrong source.");
check(fg.target(con1) == trg, "Wrong target.");
check(al3(src, trg, con3) == INVALID,
"There is more connecting arc.");
check(findArc(fg, src, trg, con4) == INVALID,
"There is more connecting arc.");
}
}
}
}
template <typename Graph>
void checkFindEdges() {
TEMPLATE_GRAPH_TYPEDEFS(Graph);
Graph graph;
for (int i = 0; i < 10; ++i) {
graph.addNode();
}
DescriptorMap<Graph, Node> nodes(graph);
typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
for (int i = 0; i < 100; ++i) {
int src = rnd[invNodes.size()];
int trg = rnd[invNodes.size()];
graph.addEdge(invNodes[src], invNodes[trg]);
}
typename Graph::template EdgeMap<int> found(graph, 0);
DescriptorMap<Graph, Edge> edges(graph);
for (NodeIt src(graph); src != INVALID; ++src) {
for (NodeIt trg(graph); trg != INVALID; ++trg) {
for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
check( (graph.u(con) == src && graph.v(con) == trg) ||
(graph.v(con) == src && graph.u(con) == trg),
"Wrong end nodes.");
++found[con];
check(found[con] <= 2, "The edge found more than twice.");
}
}
}
for (EdgeIt it(graph); it != INVALID; ++it) {
check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
(graph.u(it) == graph.v(it) && found[it] == 1),
"The edge is not found correctly.");
}
}
template <class Digraph>
void checkDeg()
{
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
const int nodeNum = 10;
const int arcNum = 100;
Digraph digraph;
InDegMap<Digraph> inDeg(digraph);
OutDegMap<Digraph> outDeg(digraph);
std::vector<Node> nodes(nodeNum);
for (int i = 0; i < nodeNum; ++i) {
nodes[i] = digraph.addNode();
}
std::vector<Arc> arcs(arcNum);
for (int i = 0; i < arcNum; ++i) {
arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
}
for (int i = 0; i < nodeNum; ++i) {
check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
"Wrong in degree map");
}
for (int i = 0; i < nodeNum; ++i) {
check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
"Wrong out degree map");
}
}
template <class Digraph>
void checkSnapDeg()
{
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
Digraph g;
Node n1=g.addNode();
Node n2=g.addNode();
InDegMap<Digraph> ind(g);
g.addArc(n1,n2);
typename Digraph::Snapshot snap(g);
OutDegMap<Digraph> outd(g);
check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
g.addArc(n1,n2);
g.addArc(n2,n1);
check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
snap.restore();
check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
}
int main() {
// Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
checkFindArcs<ListDigraph>();
checkFindArcs<SmartDigraph>();
checkFindEdges<ListGraph>();
checkFindEdges<SmartGraph>();
// Checking In/OutDegMap (and Snapshot feature)
checkDeg<ListDigraph>();
checkDeg<SmartDigraph>();
checkSnapDeg<ListDigraph>();
checkSnapDeg<SmartDigraph>();
return 0;
}
|