1/** \file
2 * \brief Tests for LCA (lowest common ancestor) class
3 *
4 * \author Stephan Beyer
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#include <sstream>
33#include <ogdf/basic/Graph.h>
34#include <ogdf/tree/LCA.h>
35#include <ogdf/basic/graph_generators.h>
36#include <testing.h>
37
38static void trivial() {
39 it("constructs LCA data structure on an empty graph", [] {
40 Graph G;
41 LCA lca(G);
42 });
43
44 it("answers level query on an arborescence with one node", [] {
45 Graph G;
46 node root = G.newNode();
47 LCA lca(G);
48 AssertThat(lca.level(root), Equals(0));
49 });
50
51 it("answers LCA query on an arborescence with one node", [] {
52 Graph G;
53 node root = G.newNode();
54 LCA lca(G);
55 node commonAncestor = lca.call(root, root);
56 AssertThat(commonAncestor, Equals(root));
57 });
58
59 it("answers LCA queries on an arborescence with two nodes", [] {
60 Graph G;
61 customGraph(G, 2, {{0, 1}});
62 LCA lca(G);
63 AssertThat(lca.call(G.firstNode(), G.firstNode()), Equals(G.firstNode()));
64 AssertThat(lca.call(G.lastNode(), G.firstNode()), Equals(G.firstNode()));
65 AssertThat(lca.call(G.firstNode(), G.lastNode()), Equals(G.firstNode()));
66 AssertThat(lca.call(G.lastNode(), G.lastNode()), Equals(G.lastNode()));
67 });
68
69 it("answers LCA queries on an arborescence with three nodes", [] {
70 Graph G;
71 Array<node> nodes;
72 customGraph(G, 3, {{0, 1}, {0, 2}}, nodes);
73 LCA lca(G);
74 AssertThat(lca.call(nodes[0], nodes[0]), Equals(nodes[0]));
75 AssertThat(lca.call(nodes[0], nodes[1]), Equals(nodes[0]));
76 AssertThat(lca.call(nodes[0], nodes[2]), Equals(nodes[0]));
77 AssertThat(lca.call(nodes[1], nodes[0]), Equals(nodes[0]));
78 AssertThat(lca.call(nodes[1], nodes[1]), Equals(nodes[1]));
79 AssertThat(lca.call(nodes[1], nodes[2]), Equals(nodes[0]));
80 AssertThat(lca.call(nodes[2], nodes[0]), Equals(nodes[0]));
81 AssertThat(lca.call(nodes[2], nodes[1]), Equals(nodes[0]));
82 AssertThat(lca.call(nodes[2], nodes[2]), Equals(nodes[2]));
83 });
84}
85
86static void interesting() {
87 const List<std::pair<int,int>> arborescence({
88 {4, 0},
89 {5, 1}, {5, 2}, {5, 3}, {5, 4},
90 {7, 6}, {7, 5},
91 {13, 9}, {13, 11}, {13, 12},
92 {11, 10},
93 {9, 8}, {9, 7}
94 });
95 Graph G;
96 Array<node> nodes;
97 customGraph(G, 14, arborescence, nodes);
98
99 it("answers level queries on a more interesting arborescence", [&] {
100 LCA lca(G);
101 AssertThat(lca.level(nodes[0]), Equals(5));
102 AssertThat(lca.level(nodes[1]), Equals(4));
103 AssertThat(lca.level(nodes[5]), Equals(3));
104 AssertThat(lca.level(nodes[7]), Equals(2));
105 AssertThat(lca.level(nodes[10]), Equals(2));
106 AssertThat(lca.level(nodes[11]), Equals(1));
107 AssertThat(lca.level(nodes[13]), Equals(0));
108 });
109
110 it("answers LCA queries on a more interesting arborescence", [&] {
111 LCA lca(G);
112 AssertThat(lca.call(nodes[0], nodes[0]), Equals(nodes[0]));
113 AssertThat(lca.call(nodes[0], nodes[1]), Equals(nodes[5]));
114 AssertThat(lca.call(nodes[0], nodes[4]), Equals(nodes[4]));
115 AssertThat(lca.call(nodes[4], nodes[1]), Equals(nodes[5]));
116 AssertThat(lca.call(nodes[6], nodes[0]), Equals(nodes[7]));
117 AssertThat(lca.call(nodes[6], nodes[0]), Equals(nodes[7]));
118 AssertThat(lca.call(nodes[8], nodes[5]), Equals(nodes[9]));
119 AssertThat(lca.call(nodes[10], nodes[1]), Equals(nodes[13]));
120 });
121
122 it("answers LCA queries when initialization is on sub-arborescence", [&] {
123 LCA lca(G, nodes[5]);
124 AssertThat(lca.call(nodes[0], nodes[0]), Equals(nodes[0]));
125 AssertThat(lca.call(nodes[0], nodes[1]), Equals(nodes[5]));
126 AssertThat(lca.call(nodes[0], nodes[4]), Equals(nodes[4]));
127 AssertThat(lca.call(nodes[4], nodes[1]), Equals(nodes[5]));
128 AssertThat(lca.call(nodes[2], nodes[3]), Equals(nodes[5]));
129 AssertThat(lca.call(nodes[5], nodes[5]), Equals(nodes[5]));
130 });
131}
132
133go_bandit([] {
134 describe("Lowest Common Ancestor algorithm", [] {
135 describe("on trivial arborescences", [] {
136 trivial();
137 });
138
139 describe("on more interesting arborescence", [] {
140 interesting();
141 });
142 });
143});
144