// libsemigroups - C++ library for semigroups and monoids // Copyright (C) 2020 James D. Mitchell, Maria Tsalakou // // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see <http://www.gnu.org/licenses/>. //
#include <algorithm> // for all_of #include <cstddef> // for size_t #include <cstdint> // for uint8_t #include <iterator> // for reverse_iterator, operat... #include <stdexcept> // for runtime_error #include <string> // for basic_string, operator== #include <utility> // for pair #include <vector> // for vector, operator==
#include"catch.hpp"// for REQUIRE, REQUIRE_NOTHROW, REQUIRE_THROWS_AS #include"test-main.hpp"// for LIBSEMIGROUPS_TEST_CASE
#include"libsemigroups/digraph-helper.hpp"// for is_acyclic, topological_... #include"libsemigroups/digraph.hpp"// for ActionDigraph, operator<< #include"libsemigroups/string.hpp"// for to_string #include"libsemigroups/types.hpp"// for word_type
namespace libsemigroups { namespace { void add_path(ActionDigraph<size_t>& digraph, size_t n) {
size_t old_nodes = digraph.number_of_nodes();
digraph.add_nodes(n); for (size_t i = old_nodes; i < digraph.number_of_nodes() - 1; ++i) {
digraph.add_edge(i, i + 1, 0);
}
}
LIBSEMIGROUPS_TEST_CASE("is_acyclic", "003", "complete digraph 100", "[quick]") {
ActionDigraph<size_t> ad;
size_t const n = 100;
ad.add_nodes(n);
ad.add_to_out_degree(n); for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { if (i != j) {
ad.add_edge(i, j, j);
}
}
}
REQUIRE(!action_digraph_helper::is_acyclic(ad));
REQUIRE(action_digraph_helper::topological_sort(ad).empty());
}
LIBSEMIGROUPS_TEST_CASE("is_acyclic", "004", "acyclic digraph with 20000 nodes", "[quick]") {
ActionDigraph<size_t> ad;
size_t const n = 20000;
ad.add_nodes(n);
ad.add_to_out_degree(2); for (size_t i = 0; i < (n / 2 - 1); ++i) {
ad.add_edge(i, i + 1, 0);
}
ad.add_edge(n / 2 - 1, n - 1, 1);
ad.add_edge(n / 2 + 1, (3 * n) / 4 - 1, 1);
ad.add_edge(n / 2, 0, 1); for (size_t i = n / 2; i < n - 1; ++i) {
ad.add_edge(i, i + 1, 0);
}
REQUIRE(action_digraph_helper::is_acyclic(ad));
REQUIRE(action_digraph_helper::topological_sort(ad).size()
== ad.number_of_nodes());
}
LIBSEMIGROUPS_TEST_CASE("is_acyclic", "005", "acyclic digraph with 10 million nodes", "[standard]") {
ActionDigraph<size_t> ad;
size_t const n = 10000000;
ad.add_nodes(n);
ad.add_to_out_degree(2); for (size_t i = 0; i < (n / 2 - 1); ++i) {
ad.add_edge(i, i + 1, 0);
}
ad.add_edge(n / 2 - 1, n - 1, 1);
ad.add_edge(n / 2 + 1, (3 * n) / 4 - 1, 1);
ad.add_edge(n / 2, 0, 1); for (size_t i = n / 2; i < n - 1; ++i) {
ad.add_edge(i, i + 1, 0);
}
REQUIRE(action_digraph_helper::is_acyclic(ad));
REQUIRE(action_digraph_helper::topological_sort(ad).size() == n);
}
LIBSEMIGROUPS_TEST_CASE("is_acyclic", "006", "for a node", "[quick]") { using node_type = ActionDigraph<size_t>::node_type;
ActionDigraph<size_t> ad;
size_t const n = 100;
ad.add_nodes(n);
ad.add_to_out_degree(2); for (size_t i = 0; i < n - 1; ++i) {
ad.add_edge(i, i + 1, i % 2);
}
action_digraph_helper::add_cycle(ad, 100);
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
