Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/extern/quadriflow/3rd/lemon-1.3.1/test/path_test.cc
diff options
context:
space:
mode:
Diffstat (limited to 'extern/quadriflow/3rd/lemon-1.3.1/test/path_test.cc')
-rw-r--r--extern/quadriflow/3rd/lemon-1.3.1/test/path_test.cc339
1 files changed, 339 insertions, 0 deletions
diff --git a/extern/quadriflow/3rd/lemon-1.3.1/test/path_test.cc b/extern/quadriflow/3rd/lemon-1.3.1/test/path_test.cc
new file mode 100644
index 00000000000..f2d96038135
--- /dev/null
+++ b/extern/quadriflow/3rd/lemon-1.3.1/test/path_test.cc
@@ -0,0 +1,339 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2013
+ * 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 <string>
+#include <iostream>
+
+#include <lemon/concepts/path.h>
+#include <lemon/concepts/digraph.h>
+#include <lemon/concept_check.h>
+
+#include <lemon/path.h>
+#include <lemon/list_graph.h>
+
+#include "test_tools.h"
+
+using namespace std;
+using namespace lemon;
+
+template <typename GR>
+void checkConcepts() {
+ checkConcept<concepts::Path<GR>, concepts::Path<GR> >();
+ checkConcept<concepts::Path<GR>, Path<GR> >();
+ checkConcept<concepts::Path<GR>, SimplePath<GR> >();
+ checkConcept<concepts::Path<GR>, StaticPath<GR> >();
+ checkConcept<concepts::Path<GR>, ListPath<GR> >();
+}
+
+// Conecpt checking for path structures
+void checkPathConcepts() {
+ checkConcepts<concepts::Digraph>();
+ checkConcepts<ListDigraph>();
+}
+
+// Check if proper copy consructor is called (use valgrind for testing)
+template <typename GR, typename P1, typename P2>
+void checkCopy(typename GR::Arc a) {
+ P1 p;
+ p.addBack(a);
+ P1 q;
+ q = p;
+ P1 r(p);
+ P2 q2;
+ q2 = p;
+ P2 r2(p);
+}
+
+// Tests for copy constructors and assignment operators of paths
+void checkPathCopy() {
+ ListDigraph g;
+ ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode());
+
+ typedef Path<ListDigraph> Path1;
+ typedef SimplePath<ListDigraph> Path2;
+ typedef ListPath<ListDigraph> Path3;
+ typedef StaticPath<ListDigraph> Path4;
+ checkCopy<ListDigraph, Path1, Path2>(a);
+ checkCopy<ListDigraph, Path1, Path3>(a);
+ checkCopy<ListDigraph, Path1, Path4>(a);
+ checkCopy<ListDigraph, Path2, Path1>(a);
+ checkCopy<ListDigraph, Path2, Path3>(a);
+ checkCopy<ListDigraph, Path2, Path4>(a);
+ checkCopy<ListDigraph, Path3, Path1>(a);
+ checkCopy<ListDigraph, Path3, Path2>(a);
+ checkCopy<ListDigraph, Path3, Path4>(a);
+}
+
+// Class for testing path functions
+class CheckPathFunctions {
+ typedef ListDigraph GR;
+ DIGRAPH_TYPEDEFS(GR);
+ GR gr;
+ const GR& cgr;
+ Node n1, n2, n3, n4;
+ Node tmp_n;
+ Arc a1, a2, a3, a4;
+ Arc tmp_a;
+
+public:
+
+ CheckPathFunctions() : cgr(gr) {
+ n1 = gr.addNode();
+ n2 = gr.addNode();
+ n3 = gr.addNode();
+ n4 = gr.addNode();
+ a1 = gr.addArc(n1, n2);
+ a2 = gr.addArc(n2, n3);
+ a3 = gr.addArc(n3, n4);
+ a4 = gr.addArc(n4, n1);
+ }
+
+ void run() {
+ checkBackAndFrontInsertablePath<Path<GR> >();
+ checkBackAndFrontInsertablePath<ListPath<GR> >();
+ checkBackInsertablePath<SimplePath<GR> >();
+
+ checkListPathSplitAndSplice();
+ }
+
+private:
+
+ template <typename P>
+ void checkBackInsertablePath() {
+
+ // Create and check empty path
+ P p;
+ const P& cp = p;
+ check(cp.empty(), "The path is not empty");
+ check(cp.length() == 0, "The path is not empty");
+// check(cp.front() == INVALID, "Wrong front()");
+// check(cp.back() == INVALID, "Wrong back()");
+ typename P::ArcIt ai(cp);
+ check(ai == INVALID, "Wrong ArcIt");
+ check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()");
+ check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()");
+ check(checkPath(cgr, cp), "Wrong checkPath()");
+ PathNodeIt<P> ni(cgr, cp);
+ check(ni == INVALID, "Wrong PathNodeIt");
+
+ // Check single-arc path
+ p.addBack(a1);
+ check(!cp.empty(), "Wrong empty()");
+ check(cp.length() == 1, "Wrong length");
+ check(cp.front() == a1, "Wrong front()");
+ check(cp.back() == a1, "Wrong back()");
+ check(cp.nth(0) == a1, "Wrong nth()");
+ ai = cp.nthIt(0);
+ check((tmp_a = ai) == a1, "Wrong nthIt()");
+ check(++ai == INVALID, "Wrong nthIt()");
+ typename P::ArcIt ai2(cp);
+ check((tmp_a = ai2) == a1, "Wrong ArcIt");
+ check(++ai2 == INVALID, "Wrong ArcIt");
+ check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
+ check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
+ check(checkPath(cgr, cp), "Wrong checkPath()");
+ PathNodeIt<P> ni2(cgr, cp);
+ check((tmp_n = ni2) == n1, "Wrong PathNodeIt");
+ check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt");
+ check(++ni2 == INVALID, "Wrong PathNodeIt");
+
+ // Check adding more arcs
+ p.addBack(a2);
+ p.addBack(a3);
+ check(!cp.empty(), "Wrong empty()");
+ check(cp.length() == 3, "Wrong length");
+ check(cp.front() == a1, "Wrong front()");
+ check(cp.back() == a3, "Wrong back()");
+ check(cp.nth(0) == a1, "Wrong nth()");
+ check(cp.nth(1) == a2, "Wrong nth()");
+ check(cp.nth(2) == a3, "Wrong nth()");
+ typename P::ArcIt ai3(cp);
+ check((tmp_a = ai3) == a1, "Wrong ArcIt");
+ check((tmp_a = ++ai3) == a2, "Wrong nthIt()");
+ check((tmp_a = ++ai3) == a3, "Wrong nthIt()");
+ check(++ai3 == INVALID, "Wrong nthIt()");
+ ai = cp.nthIt(0);
+ check((tmp_a = ai) == a1, "Wrong nthIt()");
+ check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+ ai = cp.nthIt(2);
+ check((tmp_a = ai) == a3, "Wrong nthIt()");
+ check(++ai == INVALID, "Wrong nthIt()");
+ check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
+ check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()");
+ check(checkPath(cgr, cp), "Wrong checkPath()");
+ PathNodeIt<P> ni3(cgr, cp);
+ check((tmp_n = ni3) == n1, "Wrong PathNodeIt");
+ check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt");
+ check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt");
+ check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt");
+ check(++ni3 == INVALID, "Wrong PathNodeIt");
+
+ // Check arc removal and addition
+ p.eraseBack();
+ p.eraseBack();
+ p.addBack(a2);
+ check(!cp.empty(), "Wrong empty()");
+ check(cp.length() == 2, "Wrong length");
+ check(cp.front() == a1, "Wrong front()");
+ check(cp.back() == a2, "Wrong back()");
+ check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
+ check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
+ check(checkPath(cgr, cp), "Wrong checkPath()");
+
+ // Check clear()
+ p.clear();
+ check(cp.empty(), "The path is not empty");
+ check(cp.length() == 0, "The path is not empty");
+
+ // Check inconsistent path
+ p.addBack(a4);
+ p.addBack(a2);
+ p.addBack(a1);
+ check(!cp.empty(), "Wrong empty()");
+ check(cp.length() == 3, "Wrong length");
+ check(cp.front() == a4, "Wrong front()");
+ check(cp.back() == a1, "Wrong back()");
+ check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
+ check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
+ check(!checkPath(cgr, cp), "Wrong checkPath()");
+ }
+
+ template <typename P>
+ void checkBackAndFrontInsertablePath() {
+
+ // Include back insertable test cases
+ checkBackInsertablePath<P>();
+
+ // Check front and back insertion
+ P p;
+ const P& cp = p;
+ p.addFront(a4);
+ p.addBack(a1);
+ p.addFront(a3);
+ check(!cp.empty(), "Wrong empty()");
+ check(cp.length() == 3, "Wrong length");
+ check(cp.front() == a3, "Wrong front()");
+ check(cp.back() == a1, "Wrong back()");
+ check(cp.nth(0) == a3, "Wrong nth()");
+ check(cp.nth(1) == a4, "Wrong nth()");
+ check(cp.nth(2) == a1, "Wrong nth()");
+ typename P::ArcIt ai(cp);
+ check((tmp_a = ai) == a3, "Wrong ArcIt");
+ check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+ check((tmp_a = ++ai) == a1, "Wrong nthIt()");
+ check(++ai == INVALID, "Wrong nthIt()");
+ ai = cp.nthIt(0);
+ check((tmp_a = ai) == a3, "Wrong nthIt()");
+ check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+ ai = cp.nthIt(2);
+ check((tmp_a = ai) == a1, "Wrong nthIt()");
+ check(++ai == INVALID, "Wrong nthIt()");
+ check(pathSource(cgr, cp) == n3, "Wrong pathSource()");
+ check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
+ check(checkPath(cgr, cp), "Wrong checkPath()");
+
+ // Check eraseFront()
+ p.eraseFront();
+ p.addBack(a2);
+ check(!cp.empty(), "Wrong empty()");
+ check(cp.length() == 3, "Wrong length");
+ check(cp.front() == a4, "Wrong front()");
+ check(cp.back() == a2, "Wrong back()");
+ check(cp.nth(0) == a4, "Wrong nth()");
+ check(cp.nth(1) == a1, "Wrong nth()");
+ check(cp.nth(2) == a2, "Wrong nth()");
+ typename P::ArcIt ai2(cp);
+ check((tmp_a = ai2) == a4, "Wrong ArcIt");
+ check((tmp_a = ++ai2) == a1, "Wrong nthIt()");
+ check((tmp_a = ++ai2) == a2, "Wrong nthIt()");
+ check(++ai2 == INVALID, "Wrong nthIt()");
+ ai = cp.nthIt(0);
+ check((tmp_a = ai) == a4, "Wrong nthIt()");
+ check((tmp_a = ++ai) == a1, "Wrong nthIt()");
+ ai = cp.nthIt(2);
+ check((tmp_a = ai) == a2, "Wrong nthIt()");
+ check(++ai == INVALID, "Wrong nthIt()");
+ check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
+ check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
+ check(checkPath(cgr, cp), "Wrong checkPath()");
+ }
+
+ void checkListPathSplitAndSplice() {
+
+ // Build a path with spliceFront() and spliceBack()
+ ListPath<GR> p1, p2, p3, p4;
+ p1.addBack(a3);
+ p1.addFront(a2);
+ p2.addBack(a1);
+ p1.spliceFront(p2);
+ p3.addFront(a4);
+ p1.spliceBack(p3);
+ check(p1.length() == 4, "Wrong length");
+ check(p1.front() == a1, "Wrong front()");
+ check(p1.back() == a4, "Wrong back()");
+ ListPath<GR>::ArcIt ai(p1);
+ check((tmp_a = ai) == a1, "Wrong ArcIt");
+ check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+ check((tmp_a = ++ai) == a3, "Wrong nthIt()");
+ check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+ check(++ai == INVALID, "Wrong nthIt()");
+ check(checkPath(cgr, p1), "Wrong checkPath()");
+
+ // Check split()
+ p1.split(p1.nthIt(2), p2);
+ check(p1.length() == 2, "Wrong length");
+ ai = p1.nthIt(0);
+ check((tmp_a = ai) == a1, "Wrong ArcIt");
+ check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+ check(++ai == INVALID, "Wrong nthIt()");
+ check(checkPath(cgr, p1), "Wrong checkPath()");
+ check(p2.length() == 2, "Wrong length");
+ ai = p2.nthIt(0);
+ check((tmp_a = ai) == a3, "Wrong ArcIt");
+ check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+ check(++ai == INVALID, "Wrong nthIt()");
+ check(checkPath(cgr, p2), "Wrong checkPath()");
+
+ // Check split() and splice()
+ p1.spliceFront(p2);
+ p1.split(p1.nthIt(2), p2);
+ p2.split(p2.nthIt(1), p3);
+ p2.spliceBack(p1);
+ p2.splice(p2.nthIt(1), p3);
+ check(p2.length() == 4, "Wrong length");
+ check(p2.front() == a1, "Wrong front()");
+ check(p2.back() == a4, "Wrong back()");
+ ai = p2.nthIt(0);
+ check((tmp_a = ai) == a1, "Wrong ArcIt");
+ check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+ check((tmp_a = ++ai) == a3, "Wrong nthIt()");
+ check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+ check(++ai == INVALID, "Wrong nthIt()");
+ check(checkPath(cgr, p2), "Wrong checkPath()");
+ }
+
+};
+
+int main() {
+ checkPathConcepts();
+ checkPathCopy();
+ CheckPathFunctions cpf;
+ cpf.run();
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-26 14:34:21 +0300