1/** \file
2 * \brief Tests for fileformat reading and writing using GraphIO,
3 * only graphs without attributes
4 *
5 * \author Stephan Beyer, Tilo Wiedera
6 *
7 * \par License:
8 * This file is part of the Open Graph Drawing Framework (OGDF).
9 *
10 * \par
11 * Copyright (C)<br>
12 * See README.md in the OGDF root directory for details.
13 *
14 * \par
15 * This program is free software; you can redistribute it and/or
16 * modify it under the terms of the GNU General Public License
17 * Version 2 or 3 as published by the Free Software Foundation;
18 * see the file LICENSE.txt included in the packaging of this file
19 * for details.
20 *
21 * \par
22 * This program is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 * GNU General Public License for more details.
26 *
27 * \par
28 * You should have received a copy of the GNU General Public
29 * License along with this program; if not, see
30 * http://www.gnu.org/copyleft/gpl.html
31 */
32
33#include <algorithm>
34#include <string>
35#include <regex>
36#include <unordered_map>
37#include <ogdf/basic/Graph.h>
38#include <ogdf/basic/EpsilonTest.h>
39#include <ogdf/basic/graph_generators.h>
40#include <ogdf/fileformats/GraphIO.h>
41#include <resources.h>
42#include <ogdf/basic/simple_graph_alg.h>
43
44using namespace ogdf;
45using namespace bandit;
46using namespace std;
47
48void assertSeemsEqual(const Graph &G1, const Graph &G2) {
49 AssertThat(G1.numberOfNodes(), Equals(G2.numberOfNodes()));
50 AssertThat(G1.numberOfEdges(), Equals(G2.numberOfEdges()));
51
52 Array<int> counter1, counter2;
53 degreeDistribution(G1, counter1);
54 degreeDistribution(G2, counter2);
55
56 AssertThat(counter1.size(), Equals(counter2.size()));
57 AssertThat(counter1.low(), Equals(counter2.low()));
58
59 for(int i = counter1.low(); i < counter1.high(); i++) {
60 AssertThat(counter1[i], Equals(counter2[i]));
61 }
62}
63void establishNodeMapping(NodeArray<node> &map1to2, const GraphAttributes &GA1,
64 const GraphAttributes &GA2)
65{
66 const Graph &G1 = GA1.constGraph();
67 const Graph &G2 = GA2.constGraph();
68 std::vector<node> mapIndexToNode;
69 mapIndexToNode.resize(G1.numberOfNodes());
70 for(node v1 : G1.nodes) {
71 int x1;
72 if(GA1.has(GraphAttributes::nodeGraphics)) {
73 x1 = GA1.x(v1) - 1;
74 } else {
75 AssertThat(GA1.has(GraphAttributes::nodeLabel), IsTrue());
76 x1 = atoi(GA1.label(v1).c_str());
77 }
78 AssertThat(mapIndexToNode[x1], Equals(nullptr));
79 mapIndexToNode[x1] = v1;
80 }
81 for(node v2 : G2.nodes) {
82 int x2;
83 if(GA1.has(GraphAttributes::nodeGraphics)) {
84 x2 = GA2.x(v2) - 1;
85 } else {
86 AssertThat(GA1.has(GraphAttributes::nodeLabel), IsTrue());
87 x2 = atoi(GA2.label(v2).c_str());
88 }
89 AssertThat(map1to2[mapIndexToNode[x2]], Equals(nullptr));
90 map1to2[mapIndexToNode[x2]] = v2;
91 }
92}
93
94void assertEqualGAs(const GraphAttributes &GA1, const GraphAttributes &GA2) {
95 const Graph &G1 = GA1.constGraph();
96 const Graph &G2 = GA2.constGraph();
97 NodeArray<node> map1to2(G1, nullptr);
98 AssertThat(GA1.attributes(), Equals(GA2.attributes()));
99 AssertThat(G1.numberOfNodes(), Equals(G2.numberOfNodes()));
100 AssertThat(G1.numberOfEdges(), Equals(G2.numberOfEdges()));
101
102 establishNodeMapping(map1to2, GA1, GA2);
103
104 constexpr double delta { 0.5 };
105
106 for(node v : G1.nodes) {
107 if(GA1.has(GraphAttributes::nodeGraphics)) {
108 AssertThat(GA2.x(map1to2[v]), Equals(GA1.x(v)));
109 AssertThat(GA2.y(map1to2[v]), EqualsWithDelta(GA1.y(v), delta));
110 if(GA1.has(GraphAttributes::threeD)) {
111 AssertThat(GA2.z(map1to2[v]), EqualsWithDelta(GA1.z(v), delta));
112 }
113 AssertThat(GA2.width(map1to2[v]), EqualsWithDelta(GA1.width(v), delta));
114 AssertThat(GA2.height(map1to2[v]), EqualsWithDelta(GA1.height(v), delta));
115 AssertThat(GA2.shape(map1to2[v]), Equals(GA1.shape(v)));
116 }
117 if(GA1.has(GraphAttributes::nodeId)) {
118 AssertThat(GA2.idNode(map1to2[v]), Equals(GA1.idNode(v)));
119 }
120 if(GA1.has(GraphAttributes::nodeLabel)) {
121 AssertThat(GA2.label(map1to2[v]), Equals(GA1.label(v)));
122 }
123 if(GA1.has(GraphAttributes::nodeLabelPosition)) {
124 AssertThat(GA2.xLabel(map1to2[v]), EqualsWithDelta(GA1.xLabel(v), delta));
125 AssertThat(GA2.yLabel(map1to2[v]), EqualsWithDelta(GA1.yLabel(v), delta));
126 if(GA1.has(GraphAttributes::threeD)) {
127 AssertThat(GA2.zLabel(map1to2[v]), Equals(GA1.zLabel(v)));
128 }
129 }
130 if(GA1.has(GraphAttributes::nodeStyle)) {
131 AssertThat(GA2.fillColor(map1to2[v]), Equals(GA1.fillColor(v)));
132 AssertThat(GA2.strokeColor(map1to2[v]), Equals(GA1.strokeColor(v)));
133 AssertThat(GA2.strokeType(map1to2[v]), Equals(GA1.strokeType(v)));
134 AssertThat(GA2.strokeWidth(map1to2[v]), Equals(GA1.strokeWidth(v)));
135 AssertThat(GA2.fillPattern(map1to2[v]), Equals(GA1.fillPattern(v)));
136 }
137 if(GA1.has(GraphAttributes::nodeTemplate)) {
138 AssertThat(GA2.templateNode(map1to2[v]), Equals(GA1.templateNode(v)));
139 }
140 if(GA1.has(GraphAttributes::nodeType)) {
141 AssertThat(int(GA2.type(map1to2[v])), Equals(int(GA1.type(v))));
142 }
143 if(GA1.has(GraphAttributes::nodeWeight)) {
144 AssertThat(GA2.weight(map1to2[v]), EqualsWithDelta(GA1.weight(v), delta));
145 }
146 }
147 for(edge e : G1.edges) {
148 edge e2 = G2.searchEdge(map1to2[e->source()], map1to2[e->target()]);
149 AssertThat(e2, !Equals(nullptr));
150
151 if(GA1.has(GraphAttributes::edgeArrow)) {
152 AssertThat(GA2.arrowType(e2), Equals(GA1.arrowType(e)));
153 }
154 if(GA1.has(GraphAttributes::edgeGraphics)) {
155 AssertThat(GA2.bends(e2), Equals(GA1.bends(e)));
156 }
157 if(GA1.has(GraphAttributes::edgeLabel)) {
158 AssertThat(GA2.label(e2), Equals(GA1.label(e)));
159 }
160 if(GA1.has(GraphAttributes::edgeType)) {
161 AssertThat(GA2.type(e2), Equals(GA1.type(e)));
162 }
163 if(GA1.has(GraphAttributes::edgeStyle)) {
164 AssertThat(GA2.strokeColor(e2), Equals(GA1.strokeColor(e)));
165 AssertThat(GA2.strokeType(e2), Equals(GA1.strokeType(e)));
166 AssertThat(GA2.strokeWidth(e2), EqualsWithDelta(GA1.strokeWidth(e), delta));
167 }
168 if(GA1.has(GraphAttributes::edgeDoubleWeight)) {
169 AssertThat(GA2.doubleWeight(e2), EqualsWithDelta(GA1.doubleWeight(e), delta));
170 } else if(GA1.has(GraphAttributes::edgeIntWeight)) {
171 AssertThat(GA2.intWeight(e2), Equals(GA1.intWeight(e)));
172 }
173 }
174}
175
176void describeSTPonlyGraph() {
177 describe("unweighted STP", [] {
178 for_each_file("fileformats/stp/valid", [&](const ResourceFile* file){
179 it("successfully parses " + file->fullPath(), [&] {
180 Graph graph;
181 stringstream is{file->data()};
182 AssertThat(GraphIO::readSTP(graph, is), IsTrue());
183 });
184 });
185
186 for_each_file("fileformats/stp/invalid", [&](const ResourceFile* file){
187 it("detects errors in " + file->fullPath(), [&] {
188 Graph graph;
189 stringstream is{file->data()};
190 AssertThat(GraphIO::readSTP(graph, is), IsFalse());
191 });
192 });
193 });
194}
195
196template<typename T>
197void describeSTP(const string &typeName) {
198 describe("STP for " + typeName, [] {
199 for(int i = 4; i < 1024; i *= 2) {
200 it("stores and loads an instance of size " + to_string(i), [&] {
201 std::ostringstream writeStream;
202
203 EdgeWeightedGraph<T> graph;
204 List<node> terminals;
205 NodeArray<bool> isTerminal(graph, false);
206
207 randomGraph(graph, i, (i*(i-1))/2);
208 for(node v : graph.nodes) {
209 if(randomDouble(0, 1) > .5) {
210 terminals.pushBack(v);
211 isTerminal(v) = true;
212 }
213 }
214 for (edge e : graph.edges) {
215 graph.setWeight(e, (T) randomDouble(0, 1000));
216 }
217
218 string myComment = "";
219 if (randomDouble(0, 1) > .5) {
220 myComment += "Name \"MyRandomInstance\"\n";
221 myComment += "Creator \"Tilo Wiedera\"\n";
222 }
223 GraphIO::writeSTP(graph, terminals, writeStream, myComment);
224
225 EdgeWeightedGraph<T> readGraph;
226 List<node> readTerminals;
227 NodeArray<bool> readIsTerminal;
228
229 std::istringstream readStream(writeStream.str());
230 AssertThat(GraphIO::readSTP(readGraph, readTerminals, readIsTerminal, readStream), Equals(true));
231
232 AssertThat(readGraph.numberOfNodes(), Equals(graph.numberOfNodes()));
233 AssertThat(readGraph.numberOfEdges(), Equals(graph.numberOfEdges()));
234 AssertThat(readTerminals.size(), Equals(terminals.size()));
235 for(node v : readGraph.nodes) {
236 AssertThat(readIsTerminal[v], Equals(readTerminals.search(v).valid()));
237 }
238 });
239 }
240
241 it("clears the graph", [&](){
242 EdgeWeightedGraph<T> writeGraph;
243 List<node> terminals;
244 std::ostringstream write;
245 AssertThat(GraphIO::writeSTP(writeGraph, terminals, write), Equals(true));
246
247 EdgeWeightedGraph<T> readGraph;
248 customGraph(readGraph, 2, {{0, 1}});
249 NodeArray<bool> isTerminal(readGraph, true);
250 terminals.pushBack(readGraph.firstNode());
251 std::istringstream read(write.str());
252 AssertThat(GraphIO::readSTP(readGraph, terminals, isTerminal, read), Equals(true));
253 AssertThat(readGraph.empty(), IsTrue());
254 AssertThat(terminals.empty(), IsTrue());
255 AssertThat(isTerminal.begin(), Equals(isTerminal.end()));
256 });
257
258 for_each_file("fileformats/stp/valid", [&](const ResourceFile* file){
259 it("successfully parses " + file->fullPath(), [&] {
260 EdgeWeightedGraph<T> graph;
261 List<node> terminals;
262 NodeArray<bool> isTerminal;
263 stringstream is{file->data()};
264 AssertThat(GraphIO::readSTP(graph, terminals, isTerminal, is), IsTrue());
265
266 AssertThat(graph.numberOfNodes(), IsGreaterThan(0));
267 AssertThat(graph.numberOfEdges(), IsGreaterThan(0));
268 AssertThat(terminals.size(), IsGreaterThan(0));
269
270 int terminalCounter = 0;
271 for(node v : graph.nodes) {
272 terminalCounter += isTerminal[v];
273 }
274
275 AssertThat(terminalCounter, Equals(terminals.size()));
276 });
277 });
278
279 for_each_file("fileformats/stp/invalid", [&](const ResourceFile* file){
280 it("detects errors in " + file->fullPath(), [&](){
281 EdgeWeightedGraph<T> graph;
282 List<node> terminals;
283 NodeArray<bool> isTerminal;
284 stringstream is{file->data()};
285 AssertThat(GraphIO::readSTP(graph, terminals, isTerminal, is), IsFalse());
286 });
287 });
288 });
289}
290
291template<typename T>
292void describeDMF(const string &typeName) {
293 describe("DMF for " + typeName, [] {
294 const void* nullPointer = nullptr;
295
296 for_each_file("fileformats/dmf/valid", [&](const ResourceFile* file) {
297 it("reads " + file->fullPath(), [&]() {
298 Graph graph;
299 EdgeArray<T> weights;
300 node source;
301 node sink;
302
303 stringstream is{file->data()};
304 AssertThat(GraphIO::readDMF(graph, weights, source, sink, is), IsTrue());
305 AssertThat(graph.numberOfNodes(), IsGreaterThan(1));
306 AssertThat(weights.valid(), IsTrue());
307 AssertThat(source, Is().Not().EqualTo(nullPointer));
308 AssertThat(sink, Is().Not().EqualTo(nullPointer));
309#ifdef OGDF_DEBUG
310 AssertThat(source->graphOf(), Equals(&graph));
311 AssertThat(sink->graphOf(), Equals(&graph));
312#endif
313 AssertThat(source, Is().Not().EqualTo(sink));
314
315 for(edge e : graph.edges) {
316 AssertThat(weights(e) > 0, IsTrue());
317 }
318 });
319 });
320
321 for_each_file("fileformats/dmf/invalid", [&](const ResourceFile* file) {
322 it("reads " + file->fullPath(), [&]() {
323 Graph graph;
324 EdgeArray<T> weights(graph, 0);
325 node source;
326 node sink;
327 stringstream is{file->data()};
328 AssertThat(GraphIO::readDMF(graph, weights, source, sink, is), IsFalse());
329 });
330 });
331
332 it("writes and reads a random graph", [&]() {
333 Graph graph;
334 EdgeArray<T> weights(graph, 0);
335 node source;
336 node sink;
337
338 randomGraph(graph, 42, 189);
339 source = graph.chooseNode();
340 sink = graph.chooseNode([&](node v) { return v != source; });
341
342 T sum = 0;
343 for(edge e : graph.edges) {
344 T cap = static_cast<T>(randomDoubleNormal(10, 5));
345 if(cap < 0) {
346 cap *= -1;
347 }
348 weights(e) = cap;
349 sum += cap;
350 }
351
352 std::ostringstream writeStream;
353
354 AssertThat(GraphIO::writeDMF(graph, weights, source, sink, writeStream), IsTrue());
355
356 Graph readGraph;
357 EdgeArray<T> readWeights(readGraph, 0);
358 node readSource = nullptr;
359 node readSink = nullptr;
360
361 std::istringstream readStream(writeStream.str());
362 AssertThat(GraphIO::readDMF(readGraph, readWeights, readSource, readSink, readStream), IsTrue());
363
364 AssertThat(readGraph.numberOfNodes(), Equals(graph.numberOfNodes()));
365 AssertThat(readGraph.numberOfEdges(), Equals(graph.numberOfEdges()));
366 AssertThat(readSource, Is().Not().EqualTo(nullPointer));
367 AssertThat(readSink, Is().Not().EqualTo(nullPointer));
368#ifdef OGDF_DEBUG
369 AssertThat(readSource->graphOf(), Equals(&readGraph));
370 AssertThat(readSink->graphOf(), Equals(&readGraph));
371#endif
372 AssertThat(readSource->degree(), Equals(source->degree()));
373 AssertThat(readSink->degree(), Equals(sink->degree()));
374
375 T readSum = 0;
376 for(edge e : readGraph.edges) {
377 readSum += readWeights(e);
378 }
379
380 EpsilonTest eps(1.0e-3);
381 AssertThat(eps.equal(sum, readSum), IsTrue());
382 });
383
384 it("clears the graph", [&]() {
385 Graph writeGraph;
386 EdgeArray<T> writeWeights(writeGraph, 42);
387 completeGraph(writeGraph, 3);
388 node source = writeGraph.firstNode();
389 node sink = writeGraph.lastNode();
390
391 std::ostringstream write;
392 AssertThat(GraphIO::writeDMF(writeGraph, writeWeights, source, sink, write), IsTrue());
393
394 Graph readGraph;
395 EdgeArray<T> readWeights(readGraph, 0);
396 customGraph(readGraph, 2, {{0, 1}});
397 source = nullptr;
398 sink = nullptr;
399
400 std::istringstream read(write.str());
401 AssertThat(GraphIO::readDMF(readGraph, readWeights, source, sink, read), IsTrue());
402 AssertThat(readGraph.numberOfNodes(), Equals(3));
403 AssertThat(readGraph.numberOfEdges(), Equals(3));
404 AssertThat(readWeights[readGraph.firstEdge()], Equals(42));
405 AssertThat(source, !Equals(sink));
406 AssertThat(source, !Equals(nullptr));
407 AssertThat(sink, !Equals(nullptr));
408 });
409 });
410}
411
412/**
413 * Used to describe a format parser and writer.
414 *
415 * \param name The name of the format.
416 * \param reader The parse function to be tested.
417 * \param writer The write function to be tested.
418 * \param isXml Whether the format is based on XML.
419 */
420void testFormat(const std::string name, function<bool(Graph &G, istream &is)> reader,
421 function<bool(Graph &G, ostream &os)> writer, bool isXml)
422{
423 std::string lowerCaseName = name;
424 std::transform(lowerCaseName.begin(), lowerCaseName.end(), lowerCaseName.begin(), ::tolower);
425
426 auto errorTest = [&](const ResourceFile* file) {
427 it("detects errors in " + file->fullPath(), [&]() {
428 Graph graph;
429 stringstream ss{file->data()};
430 AssertThat(reader(graph, ss), IsFalse());
431 });
432 };
433
434 auto resourceBasedTest = [&]() {
435 for_each_file("fileformats/" + lowerCaseName + "/valid", [&](const ResourceFile* file) {
436 it("successfully parses " + file->fullPath(), [&](){
437 Graph graph;
438 stringstream ss{file->data()};
439 AssertThat(reader(graph, ss), IsTrue());
440 AssertThat(graph.numberOfNodes(), IsGreaterThan(0));
441 AssertThat(graph.numberOfEdges(), IsGreaterThan(0));
442 });
443 });
444 for_each_file("fileformats/" + lowerCaseName + "/valid/skip", [&](const ResourceFile* file) {
445 it_skip("successfully parses " + file->fullPath(), [&]() {});
446 });
447
448 for_each_file("fileformats/" + lowerCaseName + "/invalid", errorTest);
449 for_each_file("fileformats/" + lowerCaseName + "/invalid/skip", [&](const ResourceFile* file) {
450 it_skip("detects errors in " + file->fullPath(), [&]() {});
451 });
452
453 it("returns false if the files does not exist", [&]() {
454 Graph graph;
455 ifstream input;
456 input.close();
457 AssertThat(reader(graph, input), IsFalse());
458 });
459 };
460
461 if(isXml) {
462 for_each_file("fileformats/xml/invalid", errorTest);
463 }
464
465 it("detects invalid input streams", [&]() {
466 Graph G;
467 std::istringstream badStream;
468 badStream.setstate(std::istringstream::badbit);
469 AssertThat(reader(G, badStream), IsFalse());
470 });
471
472 it("detects invalid output streams", [&]() {
473 Graph G;
474 randomGraph(G, 10, 20);
475 std::ostringstream badStream;
476 badStream.setstate(std::ostringstream::badbit);
477 AssertThat(writer(G, badStream), IsFalse());
478 });
479
480 resourceBasedTest();
481
482 it("writes and reads an empty graph", [&]() {
483 Graph G, Gtest;
484 std::ostringstream write;
485 AssertThat(writer(G, write), Equals(true));
486 std::istringstream read(write.str());
487 AssertThat(reader(Gtest, read), Equals(true));
488 assertSeemsEqual(G, Gtest);
489 });
490
491 it("clears the graph", [&]() {
492 Graph writeGraph;
493 std::ostringstream write;
494 AssertThat(writer(writeGraph, write), IsTrue());
495
496 Graph readGraph;
497 customGraph(readGraph, 2, {{0, 1}});
498 std::istringstream read(write.str());
499 AssertThat(reader(readGraph, read), IsTrue());
500 AssertThat(readGraph.empty(), IsTrue());
501 });
502
503 it("writes and reads a graph of isolated nodes", [&]() {
504 Graph G, Gtest;
505 G.newNode(); G.newNode();
506 std::ostringstream write;
507 AssertThat(writer(G, write), Equals(true));
508 std::istringstream read(write.str());
509 AssertThat(reader(Gtest, read), Equals(true));
510 assertSeemsEqual(G, Gtest);
511 });
512
513 it("writes and reads a Petersen graph", [&]() {
514 Graph G, Gtest;
515 petersenGraph(G, 5, 2);
516 std::ostringstream write;
517 AssertThat(writer(G, write), Equals(true));
518 std::istringstream read(write.str());
519 AssertThat(reader(Gtest, read), Equals(true));
520 assertSeemsEqual(G, Gtest);
521 });
522
523 it("writes and reads a big complete graph", [&]() {
524 Graph G, Gtest;
525 completeGraph(G, 243);
526 std::ostringstream write;
527 AssertThat(writer(G, write), Equals(true));
528 std::istringstream read(write.str());
529 AssertThat(reader(Gtest, read), Equals(true));
530 assertSeemsEqual(G, Gtest);
531 });
532}
533
534/**
535 * Used to describe a format parser and writer.
536 *
537 * \param name The name of the format.
538 * \param reader The parse function to be tested.
539 * \param writer The write function to be tested.
540 * \param isXml Whether the format is based on XML.
541 * \param alreadyDescribed Whether this function is called from inside a describe.
542 */
543void describeFormat(const std::string name, function<bool(Graph &G, istream &is)> reader, GraphIO::WriterFunc writer,
544 bool isXml, bool alreadyDescribed = false)
545{
546 if(alreadyDescribed) {
547 testFormat(name, reader, writer, isXml);
548 } else {
549 describe(name, [&]() {
550 testFormat(name, reader, writer, isXml);
551 });
552 }
553}
554
555/**
556 * Used to describe a format parser and writer that respects GraphAttributes.
557 *
558 * @copydetails describeFormat
559 *
560 * @param readerGA The parse function respecting GraphAttributes to be tested.
561 * @param writerGA The write function respecting GraphAttributes to be tested.
562 * @param attr The chosen GraphAttributes.
563 */
564void describeGAFormat(const std::string name, GraphIO::AttrReaderFunc readerGA, GraphIO::AttrWriterFunc writerGA,
565 GraphIO::ReaderFunc reader, GraphIO::WriterFunc writer, bool isXml, long attr, bool isGEXF = false)
566{
567 function<bool(Graph &G, istream &is)> graphOnlyReader = [&](Graph& G,istream& is) {
568 GraphAttributes GA(G, 0);
569 return readerGA(GA, G, is);
570 };
571
572 function<bool(Graph &G, ostream &is)> graphOnlyWriter = [&](Graph& G,ostream& os) {
573 GraphAttributes GA(G, 0);
574 return writerGA(GA, os);
575 };
576
577 describeFormat(name, reader, writer, isXml, true);
578
579 describe(name, [&](){
580 describe("with GraphAttributes", [&]() {
581 testFormat(name, graphOnlyReader, graphOnlyWriter, isXml);
582
583 it("writes and reads a big graph while maintaining GraphAttributes", [&](){
584 Graph graph;
585 randomSimpleGraph(graph, 20, 40);
586 GraphAttributes GA(graph, attr); // all attributes specified in the call activated
587 for(node v : graph.nodes) {
588 if(attr & GraphAttributes::nodeLabelPosition) {
589 GA.xLabel(v) = v->index();
590 GA.yLabel(v) = randomNumber(1, std::numeric_limits<int>::max());
591 if(attr & GraphAttributes::threeD) {
592 GA.zLabel(v) = randomNumber(1, std::numeric_limits<int>::max());
593 }
594 }
595 if(attr & GraphAttributes::nodeStyle) {
596 GA.strokeColor(v) = randomNumber(0,1) ? Color::Name::Peru : Color::Name::Whitesmoke;
597 GA.strokeType(v) = randomNumber(0,1) ? StrokeType::Dashdotdot : StrokeType::Solid;
598 GA.strokeWidth(v) = randomNumber(1, std::numeric_limits<int>::max());
599 GA.fillPattern(v) = randomNumber(0, 1) ? FillPattern::Cross : FillPattern::Dense1;
600 GA.fillColor(v) = randomNumber(0, 1) ? Color::Name::Blanchedalmond : Color::Name::Gainsboro;
601 GA.fillBgColor(v) = randomNumber(0, 1) ? Color::Name::Mistyrose : Color::Name::Mintcream;
602 }
603 if(attr & GraphAttributes::threeD) {
604 GA.z(v) = randomNumber(1, std::numeric_limits<int>::max());
605 }
606 if(attr & GraphAttributes::nodeWeight) {
607 GA.weight(v) = randomNumber(1, std::numeric_limits<int>::max());
608 }
609 if(attr & GraphAttributes::nodeTemplate) {
610 GA.templateNode(v) = to_string(randomNumber(1, std::numeric_limits<int>::max()));
611 }
612 if(attr & GraphAttributes::nodeType) {
613 GA.type(v) = (randomNumber(0, 1) ? Graph::NodeType::dummy : Graph::NodeType::associationClass);
614 }
615 if(attr & GraphAttributes::nodeLabel) {
616 GA.label(v) = to_string(v->index());
617 }
618 if(attr & GraphAttributes::nodeId) {
619 GA.idNode(v) = v->index();
620 }
621 if(attr & GraphAttributes::nodeGraphics) {
622 GA.x(v) = v->index() + 1;
623 GA.y(v) = randomNumber(1, std::numeric_limits<int>::max());
624 int size = randomNumber(1, 10);
625 GA.width(v) = size;
626 GA.height(v) = isGEXF ? size : randomNumber(1, 10);
627 GA.shape(v) = (randomNumber(0, 1) ? Shape::Ellipse : Shape::Image);
628 }
629 }
630 for(edge e : graph.edges) {
631 if(attr & GraphAttributes::edgeGraphics) {
632 DPolyline bends1;
633 bends1.emplaceFront(randomNumber(1, std::numeric_limits<int>::max()), randomNumber(1, std::numeric_limits<int>::max()));
634 GA.bends(e) = bends1;
635 }
636 if(attr & GraphAttributes::edgeIntWeight) {
637 GA.intWeight(e) = randomNumber(2, std::numeric_limits<int>::max());
638 }
639 if(attr & GraphAttributes::edgeDoubleWeight) {
640 GA.doubleWeight(e) = randomNumber(2, std::numeric_limits<int>::max());
641 }
642 if(attr & GraphAttributes::edgeLabel) {
643 GA.label(e) = to_string(randomNumber(1, std::numeric_limits<int>::max()));
644 }
645 if(attr & GraphAttributes::edgeType) {
646 GA.type(e) = randomNumber(0,1) ? Graph::EdgeType::generalization : Graph::EdgeType::association;
647 }
648 if(attr & GraphAttributes::edgeArrow) {
649 GA.arrowType(e) = randomNumber(0,1) ? EdgeArrow::Both : EdgeArrow::First;
650 }
651 if(attr & GraphAttributes::edgeStyle) {
652 GA.strokeColor(e) = randomNumber(0,1) ? Color::Name::Papayawhip : Color::Name::Cornsilk;
653 GA.strokeType(e) = randomNumber(0,1) ? StrokeType::Dashdotdot : StrokeType::Dashdot;
654 GA.strokeWidth(e) = randomNumber(1, std::numeric_limits<int>::max());
655 }
656 }
657
658 std::ostringstream write;
659 auto flagsBefore = write.flags();
660 AssertThat(writerGA(GA, write), Equals(true));
661 AssertThat(write.flags(), Equals(flagsBefore));
662 std::istringstream read(write.str());
663 Graph G2;
664 GraphAttributes GA2(G2, attr);
665 flagsBefore = read.flags();
666 AssertThat(readerGA(GA2, G2, read), Equals(true));
667 AssertThat(read.flags(), Equals(flagsBefore));
668 assertEqualGAs(GA, GA2);
669 });
670 });
671 });
672}
673
674void describeDOTSpecialCases()
675{
676 describe("DOT with subgraphs as clusters", []() {
677 // Tests reading a DOT clustergraph, using a simplified version of:
678 // https://graphviz.gitlab.io/_pages/Gallery/directed/cluster.html
679 it("reads a cluster graph", []() {
680 const ResourceFile* file = ResourceFile::get(
681 "fileformats/dot/valid/cluster");
682 std::stringstream is{file->data()};
683
684 Graph G;
685 ClusterGraph CG(G);
686
687 const bool readStatus = GraphIO::readDOT(CG, G, is);
688 AssertThat(readStatus, Equals(true));
689
690 // this graph has two clusters inside the root cluster, each of which
691 // has four nodes.
692 AssertThat(CG.numberOfClusters(), Equals(3));
693 AssertThat(CG.rootCluster()->children.size(), Equals(2));
694 for (const auto &cluster : CG.rootCluster()->children) {
695 AssertThat(cluster->nodes.size(), Equals(4));
696 }
697 });
698
699 it("reads assignment statements", []() {
700 std::stringstream is{ResourceFile::get("fileformats/dot/valid/assignments")->data()};
701
702 Graph G;
703 ClusterGraph CG(G);
704 ClusterGraphAttributes CGA(CG);
705
706 const bool readStatus = GraphIO::readDOT(CGA, CG, G, is);
707 AssertThat(readStatus, Equals(true));
708 AssertThat(CGA.label(CG.rootCluster()), Equals("wat"));
709 });
710
711 { // a scope for the variables to deal with arrow types
712 std::stringstream is{ResourceFile::get("fileformats/dot/valid/arrowtypes")->data()};
713 Graph G;
714 GraphAttributes GA(G, GraphAttributes::edgeArrow);
715 const bool readStatus = GraphIO::readDOT(GA, G, is);
716 AssertThat(readStatus, Equals(true));
717 auto checkDir = [&](EdgeArrow e, const edge& ed, const string &s) {
718 it("parses dir attribute set to " + s,
719 [&]() { AssertThat(GA.arrowType(ed), Equals(e)); });
720 };
721 auto ed = G.firstEdge();
722 checkDir(EdgeArrow::Both, ed, "both");
723 ed = ed->succ();
724 checkDir(EdgeArrow::Last, ed, "last");
725 ed = ed->succ();
726 checkDir(EdgeArrow::First, ed, "first");
727 ed = ed->succ();
728 checkDir(EdgeArrow::None, ed, "none");
729 ed = ed->succ();
730 checkDir(EdgeArrow::Undefined, ed, "undefined");
731 }
732 });
733}
734
735function<bool(Graph &G, istream &is)> toLambda(const GraphIO::ReaderFunc &reader) {
736 return [&](Graph &G, istream &is) { return reader(G, is); };
737}
738
739go_bandit([]() {
740describe("GraphIO", []() {
741 describeSTP<int>("int");
742 describeSTP<double>("double");
743 describeSTPonlyGraph();
744
745 describeDMF<int>("int");
746 describeDMF<double>("double");
747
748 describeGAFormat("GML", GraphIO::readGML, GraphIO::writeGML, GraphIO::readGML, GraphIO::writeGML, false,
749 GraphAttributes::nodeGraphics | GraphAttributes::edgeGraphics | GraphAttributes::edgeDoubleWeight
750 | GraphAttributes::edgeLabel | GraphAttributes::nodeLabel | GraphAttributes::edgeType
751 | GraphAttributes::nodeId | GraphAttributes::edgeArrow | GraphAttributes::edgeStyle
752 | GraphAttributes::nodeTemplate | GraphAttributes::nodeWeight | GraphAttributes::nodeStyle
753 | GraphAttributes::threeD);
754 describeFormat("Rome", toLambda(GraphIO::readRome), GraphIO::writeRome, false);
755 describeFormat("LEDA", toLambda(GraphIO::readLEDA), GraphIO::writeLEDA, false);
756 describeFormat("Chaco", toLambda(GraphIO::readChaco), GraphIO::writeChaco, false);
757 describeFormat("PMDiss", toLambda(GraphIO::readPMDissGraph), GraphIO::writePMDissGraph, false);
758 describeGAFormat("GraphML", GraphIO::readGraphML, GraphIO::writeGraphML, GraphIO::readGraphML, GraphIO::writeGraphML, true,
759 GraphAttributes::nodeGraphics | GraphAttributes::edgeIntWeight | GraphAttributes::edgeDoubleWeight
760 | GraphAttributes::edgeLabel | GraphAttributes::nodeLabel | GraphAttributes::nodeType
761 | GraphAttributes::edgeType | GraphAttributes::edgeArrow | GraphAttributes::nodeTemplate
762 | GraphAttributes::nodeWeight | GraphAttributes::threeD | GraphAttributes::nodeStyle);
763 describeGAFormat("DOT", GraphIO::readDOT, GraphIO::writeDOT, GraphIO::readDOT, GraphIO::writeDOT, false,
764 GraphAttributes::nodeGraphics | GraphAttributes::edgeGraphics | GraphAttributes::edgeIntWeight
765 | GraphAttributes::edgeLabel | GraphAttributes::nodeLabel | GraphAttributes::nodeType
766 | GraphAttributes::edgeDoubleWeight | GraphAttributes::edgeArrow | GraphAttributes::nodeTemplate
767 | GraphAttributes::nodeWeight | GraphAttributes::nodeStyle | GraphAttributes::threeD);
768 describeDOTSpecialCases();
769 describeGAFormat("GEXF", GraphIO::readGEXF, GraphIO::writeGEXF, GraphIO::readGEXF, GraphIO::writeGEXF, true,
770 GraphAttributes::nodeGraphics | GraphAttributes::edgeIntWeight
771 | GraphAttributes::edgeDoubleWeight | GraphAttributes::nodeType | GraphAttributes::edgeType
772 | GraphAttributes::edgeArrow | GraphAttributes::nodeTemplate | GraphAttributes::nodeWeight
773 | GraphAttributes::threeD | GraphAttributes::nodeStyle, true);
774 describeGAFormat("GDF", GraphIO::readGDF, GraphIO::writeGDF, GraphIO::readGDF, GraphIO::writeGDF, false,
775 GraphAttributes::nodeGraphics | GraphAttributes::edgeIntWeight | GraphAttributes::edgeGraphics
776 | GraphAttributes::edgeLabel | GraphAttributes::nodeLabel
777 | GraphAttributes::edgeDoubleWeight | GraphAttributes::nodeTemplate | GraphAttributes::nodeWeight
778 | GraphAttributes::threeD | GraphAttributes::nodeStyle);
779 describeGAFormat("DL", GraphIO::readDL, GraphIO::writeDL, GraphIO::readDL, GraphIO::writeDL, false,
780 GraphAttributes::edgeIntWeight | GraphAttributes::edgeDoubleWeight | GraphAttributes::nodeLabel);
781 describeGAFormat("TLP", GraphIO::readTLP, GraphIO::writeTLP, GraphIO::readTLP, GraphIO::writeTLP, false,
782 GraphAttributes::nodeGraphics | GraphAttributes::edgeLabel | GraphAttributes::nodeLabel
783 | GraphAttributes::threeD | GraphAttributes::nodeStyle);
784 describeFormat("Graph6", [&](Graph& G, istream &is) { return GraphIO::readGraph6(G, is, false); },
785 GraphIO::writeGraph6, false);
786
787 describe("generic reader", []() {
788 std::function<void(const ResourceFile*)> genericTestTrue = [](const ResourceFile* file) {
789 it("parses " + file->fullPath(), [&]() {
790 Graph graph;
791 stringstream ss{file->data()};
792 AssertThat(GraphIO::read(graph, ss), IsTrue());
793 });
794 };
795
796 std::function<void(const ResourceFile*)> genericTestFalse = [](const ResourceFile* file) {
797 it("does not recognize " + file->fullPath(), [&]() {
798 Graph graph;
799 stringstream ss{file->data()};
800 AssertThat(GraphIO::read(graph, ss), IsFalse());
801 });
802 };
803
804 for_each_file("fileformats/gml/valid", genericTestTrue);
805 for_each_file("fileformats/gml/invalid", genericTestFalse);
806
807 for_each_file("fileformats/chaco/valid", genericTestTrue);
808 for_each_file("fileformats/chaco/invalid", genericTestFalse);
809
810 for_each_file("fileformats/dl/valid", genericTestTrue);
811 for_each_file("fileformats/dl/invalid", genericTestFalse);
812
813 for_each_file("fileformats/dot/valid", genericTestTrue);
814 for_each_file("fileformats/dot/invalid", genericTestFalse);
815
816 for_each_file("fileformats/gdf/valid", genericTestTrue);
817
818 for_each_file("fileformats/gexf/valid", genericTestTrue);
819
820 for_each_file("fileformats/graphml/valid", genericTestTrue);
821
822 for_each_file("fileformats/leda/valid", genericTestTrue);
823 for_each_file("fileformats/leda/invalid", genericTestFalse);
824
825 for_each_file("fileformats/tlp/valid", genericTestTrue);
826 for_each_file("fileformats/tlp/invalid", genericTestFalse);
827
828 for_each_file("fileformats/stp/valid", genericTestTrue);
829
830 for_each_file("fileformats/graph6/valid", genericTestTrue);
831
832 for_each_file("fileformats/dmf/invalid", genericTestFalse);
833 });
834});
835});
836