aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2007-04-05 15:01:47 +0000
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2007-04-05 15:01:47 +0000
commitcccae142fc1b1312c1fbe25718ff7ff1a69e252d (patch)
tree77256e933a5ea42e1af4d685f5e35db2e3e3fce1
parent4ca7a0a5b93d06198c580168fa45eb07a29e9f58 (diff)
downloadpaludis-cccae142fc1b1312c1fbe25718ff7ff1a69e252d.tar.gz
paludis-cccae142fc1b1312c1fbe25718ff7ff1a69e252d.tar.xz
Add simple graph utilities for future use.
-rw-r--r--paludis/util/files.m41
-rw-r--r--paludis/util/graph.cc205
-rw-r--r--paludis/util/graph.hh151
-rw-r--r--paludis/util/graph_TEST.cc175
4 files changed, 532 insertions, 0 deletions
diff --git a/paludis/util/files.m4 b/paludis/util/files.m4
index 942aa75..bcdf510 100644
--- a/paludis/util/files.m4
+++ b/paludis/util/files.m4
@@ -20,6 +20,7 @@ add(`fast_unique_copy', `hh', `test')
add(`fd_output_stream', `hh')
add(`fs_entry', `hh', `cc', `test', `testscript')
add(`fd_holder', `hh')
+add(`graph', `hh', `cc', `test')
add(`iterator', `hh', `test')
add(`instantiation_policy', `hh', `test')
add(`is_file_with_extension', `hh', `cc', `test', `testscript')
diff --git a/paludis/util/graph.cc b/paludis/util/graph.cc
new file mode 100644
index 0000000..cf05314
--- /dev/null
+++ b/paludis/util/graph.cc
@@ -0,0 +1,205 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2007 Ciaran McCreesh <ciaranm@ciaranm.org>
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis 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, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include "graph.hh"
+#include <paludis/util/save.hh>
+#include <stdint.h>
+#include <vector>
+
+using namespace paludis;
+
+namespace
+{
+ unsigned size_needed_for(const unsigned s)
+ {
+ return 1 + ((s - 1) / 8);
+ }
+}
+
+namespace paludis
+{
+ template<>
+ struct Implementation<SimpleGraph>
+ {
+ std::vector<uint8_t> pool;
+ const unsigned size;
+
+ Implementation(unsigned sz) :
+ pool(size_needed_for(sz * sz), 0),
+ size(sz)
+ {
+ }
+ };
+}
+
+SimpleGraph::SimpleGraph(const unsigned sz) :
+ PrivateImplementationPattern<SimpleGraph>(new Implementation<SimpleGraph>(sz))
+{
+}
+
+SimpleGraph::~SimpleGraph()
+{
+}
+
+unsigned
+SimpleGraph::size() const
+{
+ return _imp->size;
+}
+
+void
+SimpleGraph::connect(const unsigned s, const unsigned d)
+{
+ const unsigned offset(s * _imp->size + d);
+ _imp->pool[offset / 8] |= (1 << (offset % 8));
+}
+
+void
+SimpleGraph::unconnect(const unsigned s, const unsigned d)
+{
+ const unsigned offset(s * _imp->size + d);
+ _imp->pool[offset / 8] &= ~(1 << (offset % 8));
+}
+
+bool
+SimpleGraph::is_connected(const unsigned s, const unsigned d) const
+{
+ const unsigned offset(s * _imp->size + d);
+ return _imp->pool[offset / 8] & (1 << (offset % 8));
+}
+
+bool
+SimpleGraph::has_outgoing(const unsigned s) const
+{
+ for (unsigned d(0) ; d < _imp->size ; ++d)
+ if (is_connected(s, d))
+ return true;
+
+ return false;
+}
+
+bool
+SimpleGraph::has_incoming(const unsigned s) const
+{
+ for (unsigned d(0) ; d < _imp->size ; ++d)
+ if (is_connected(d, s))
+ return true;
+
+ return false;
+}
+
+void
+SimpleGraph::reverse()
+{
+ for (unsigned s(0), s_end(_imp->pool.size()) ; s < s_end ; ++s)
+ _imp->pool[s] = ~_imp->pool[s];
+
+ for (unsigned s(0), s_end(_imp->size) ; s < s_end ; ++s)
+ if (is_connected(s, s))
+ unconnect(s, s);
+ else
+ connect(s, s);
+}
+
+void
+SimpleGraph::clear_incoming(const unsigned s)
+{
+ for (unsigned d(0) ; d < _imp->size ; ++d)
+ unconnect(d, s);
+}
+
+void
+SimpleGraph::clear_outgoing(const unsigned s)
+{
+ for (unsigned d(0) ; d < _imp->size ; ++d)
+ unconnect(s, d);
+}
+
+NoSimpleTopologicalOrderingExists::NoSimpleTopologicalOrderingExists(const unsigned & c) throw () :
+ Exception("No topological ordering exists because of cycle on '" + stringify(c) + "'"),
+ _cycle(c)
+{
+}
+
+unsigned
+NoSimpleTopologicalOrderingExists::cycle() const
+{
+ return _cycle;
+}
+
+namespace paludis
+{
+ template<>
+ struct Implementation<SimpleTopologicalOrdering>
+ {
+ std::vector<unsigned> order;
+ std::vector<uint8_t> pending;
+ std::vector<uint8_t> done;
+
+ Implementation(const unsigned s) :
+ pending(s, 0),
+ done(s, 0)
+ {
+ order.reserve(s);
+ }
+ };
+}
+
+SimpleTopologicalOrdering::SimpleTopologicalOrdering(const SimpleGraph & g) :
+ PrivateImplementationPattern<SimpleTopologicalOrdering>(new Implementation<SimpleTopologicalOrdering>(g.size()))
+{
+ for (unsigned x(0), x_end(g.size()) ; x != x_end ; ++x)
+ _dfs(g, x);
+}
+
+void
+SimpleTopologicalOrdering::_dfs(const SimpleGraph & g, const unsigned node)
+{
+ if (_imp->pending[node])
+ throw NoSimpleTopologicalOrderingExists(node);
+
+ if (_imp->done[node])
+ return;
+
+ Save<uint8_t> save_pending(&_imp->pending[node], 1);
+
+ for (unsigned x(0), x_end(g.size()) ; x != x_end ; ++x)
+ if (g.is_connected(node, x))
+ _dfs(g, x);
+
+ _imp->order.push_back(node);
+ _imp->done[node] = 1;
+}
+
+SimpleTopologicalOrdering::~SimpleTopologicalOrdering()
+{
+}
+
+SimpleTopologicalOrdering::Iterator
+SimpleTopologicalOrdering::begin() const
+{
+ return Iterator(_imp->order.begin());
+}
+
+SimpleTopologicalOrdering::Iterator
+SimpleTopologicalOrdering::end() const
+{
+ return Iterator(_imp->order.end());
+}
+
diff --git a/paludis/util/graph.hh b/paludis/util/graph.hh
new file mode 100644
index 0000000..0f118ed
--- /dev/null
+++ b/paludis/util/graph.hh
@@ -0,0 +1,151 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2007 Ciaran McCreesh <ciaranm@ciaranm.org>
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis 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, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_UTIL_GRAPH_HH
+#define PALUDIS_GUARD_PALUDIS_UTIL_GRAPH_HH 1
+
+#include <paludis/util/private_implementation_pattern.hh>
+#include <paludis/util/instantiation_policy.hh>
+
+namespace paludis
+{
+ class SimpleGraph :
+ private PrivateImplementationPattern<SimpleGraph>,
+ private InstantiationPolicy<SimpleGraph, instantiation_method::NonCopyableTag>
+ {
+ public:
+ SimpleGraph(const unsigned nodes);
+ ~SimpleGraph();
+
+ unsigned size() const;
+
+ void connect(const unsigned, const unsigned);
+ void unconnect(const unsigned, const unsigned);
+ void reverse();
+
+ bool is_connected(const unsigned, const unsigned) const
+ PALUDIS_ATTRIBUTE((warn_unused_result));
+ bool has_outgoing(const unsigned) const
+ PALUDIS_ATTRIBUTE((warn_unused_result));
+ bool has_incoming(const unsigned) const
+ PALUDIS_ATTRIBUTE((warn_unused_result));
+
+ void clear_incoming(const unsigned);
+ void clear_outgoing(const unsigned);
+ };
+
+ class NoSimpleTopologicalOrderingExists :
+ public Exception
+ {
+ private:
+ const unsigned _cycle;
+
+ public:
+ NoSimpleTopologicalOrderingExists(const unsigned &) throw ();
+
+ unsigned cycle() const
+ PALUDIS_ATTRIBUTE((warn_unused_result));
+ };
+
+ class SimpleTopologicalOrdering :
+ private PrivateImplementationPattern<SimpleTopologicalOrdering>
+ {
+ private:
+ void _dfs(const SimpleGraph &, const unsigned);
+
+ public:
+ SimpleTopologicalOrdering(const SimpleGraph &);
+ ~SimpleTopologicalOrdering();
+
+ typedef libwrapiter::ForwardIterator<SimpleTopologicalOrdering, const unsigned> Iterator;
+ Iterator begin() const PALUDIS_ATTRIBUTE((warn_unused_result));
+ Iterator end() const PALUDIS_ATTRIBUTE((warn_unused_result));
+ };
+
+ template <typename T_>
+ class Graph :
+ protected SimpleGraph
+ {
+ protected:
+ virtual unsigned node_to_index(const T_ &) const = 0;
+
+ Graph(const unsigned nodes) :
+ SimpleGraph(nodes)
+ {
+ }
+
+ public:
+ virtual ~Graph()
+ {
+ }
+
+ using SimpleGraph::size;
+
+ void connect(const T_ & a, const T_ & b)
+ {
+ SimpleGraph::connect(node_to_index(a), node_to_index(b));
+ }
+
+ void unconnect(const T_ a, const T_ & b)
+ {
+ SimpleGraph::unconnect(node_to_index(a), node_to_index(b));
+ }
+
+ using SimpleGraph::reverse;
+
+ bool is_connected(const T_ &, const T_ &) const
+ PALUDIS_ATTRIBUTE((warn_unused_result));
+
+ bool has_outgoing(const T_ &) const
+ PALUDIS_ATTRIBUTE((warn_unused_result));
+
+ bool has_incoming(const T_ &) const
+ PALUDIS_ATTRIBUTE((warn_unused_result));
+
+ void clear_incoming(const T_ & a)
+ {
+ SimpleGraph::clear_incoming(a);
+ }
+
+ void clear_outgoing(const T_ & a)
+ {
+ SimpleGraph::clear_outgoing(a);
+ }
+ };
+
+ template <typename T_>
+ bool Graph<T_>::is_connected(const T_ & a, const T_ & b) const
+ {
+ return SimpleGraph::is_connected(node_to_index(a), node_to_index(b));
+ }
+
+ template <typename T_>
+ bool Graph<T_>::has_outgoing(const T_ & a) const
+ {
+ return SimpleGraph::has_outgoing(node_to_index(a));
+ }
+
+ template <typename T_>
+ bool Graph<T_>::has_incoming(const T_ & a) const
+ {
+ return SimpleGraph::has_incoming(node_to_index(a));
+ }
+}
+
+#endif
diff --git a/paludis/util/graph_TEST.cc b/paludis/util/graph_TEST.cc
new file mode 100644
index 0000000..005fba9
--- /dev/null
+++ b/paludis/util/graph_TEST.cc
@@ -0,0 +1,175 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2007 Ciaran McCreesh <ciaranm@ciaranm.org>
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis 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, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include "graph.hh"
+#include <test/test_framework.hh>
+#include <test/test_runner.hh>
+#include <paludis/util/join.hh>
+#include <paludis/util/destringify.hh>
+
+using namespace test;
+using namespace paludis;
+
+namespace
+{
+ class StringGraph :
+ public Graph<std::string>
+ {
+ protected:
+ virtual unsigned node_to_index(const std::string & s) const
+ {
+ return destringify<unsigned>(s);
+ }
+
+ public:
+ StringGraph(unsigned size) :
+ Graph<std::string>(size)
+ {
+ }
+ };
+}
+
+namespace test_cases
+{
+ struct SimpleGraphTest : TestCase
+ {
+ SimpleGraphTest() : TestCase("simple graph") { }
+
+ void run()
+ {
+ SimpleGraph g(20);
+ for (unsigned x(0) ; x < 20 ; ++x)
+ for (unsigned y(0) ; y < 20 ; ++y)
+ {
+ TEST_CHECK(! g.is_connected(x, y));
+ if (x > y)
+ {
+ g.connect(x, y);
+ TEST_CHECK(g.is_connected(x, y));
+ }
+ }
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ for (unsigned y(0) ; y < 20 ; ++y)
+ TEST_CHECK_EQUAL(g.is_connected(x, y), bool(x > y));
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ TEST_CHECK_EQUAL(g.has_outgoing(x), bool(x > 0));
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ TEST_CHECK_EQUAL(g.has_incoming(x), bool(x < 19));
+
+ g.reverse();
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ for (unsigned y(0) ; y < 20 ; ++y)
+ TEST_CHECK_EQUAL(g.is_connected(x, y), bool(x < y));
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ TEST_CHECK_EQUAL(g.has_incoming(x), bool(x > 0));
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ TEST_CHECK_EQUAL(g.has_outgoing(x), bool(x < 19));
+ }
+ } test_simple_graph;
+
+ struct SimpleTopologicalOrderingTest : TestCase
+ {
+ SimpleTopologicalOrderingTest() : TestCase("simple topological ordering") { }
+
+ void run()
+ {
+ SimpleGraph g(8);
+ g.connect(0, 1);
+ g.connect(1, 2);
+ g.connect(2, 3);
+ g.connect(1, 4);
+ g.connect(4, 3);
+ g.connect(4, 5);
+ g.connect(7, 6);
+
+ SimpleTopologicalOrdering t(g);
+ TEST_CHECK_EQUAL(join(t.begin(), t.end(), " "), "3 2 5 4 1 0 6 7");
+ }
+ } test_topological_ordering;
+
+ struct SimpleTopologicalOrderingCycleTest : TestCase
+ {
+ SimpleTopologicalOrderingCycleTest() : TestCase("simple topological ordering cycles") { }
+
+ void run()
+ {
+ SimpleGraph g(3);
+ g.connect(0, 1);
+ g.connect(1, 2);
+ g.connect(2, 0);
+
+ TEST_CHECK_THROWS((SimpleTopologicalOrdering(g)), NoSimpleTopologicalOrderingExists);
+
+ SimpleGraph h(3);
+ h.connect(0, 1);
+ h.connect(2, 2);
+
+ TEST_CHECK_THROWS((SimpleTopologicalOrdering(h)), NoSimpleTopologicalOrderingExists);
+ }
+ } test_topological_ordering_cycles;
+
+ struct GraphTest : TestCase
+ {
+ GraphTest() : TestCase("graph") { }
+
+ void run()
+ {
+ StringGraph g(20);
+ for (unsigned x(0) ; x < 20 ; ++x)
+ for (unsigned y(0) ; y < 20 ; ++y)
+ {
+ TEST_CHECK(! g.is_connected(stringify(x), stringify(y)));
+ if (x > y)
+ {
+ g.connect(stringify(x), stringify(y));
+ TEST_CHECK(g.is_connected(stringify(x), stringify(y)));
+ }
+ }
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ for (unsigned y(0) ; y < 20 ; ++y)
+ TEST_CHECK_EQUAL(g.is_connected(stringify(x), stringify(y)), bool(x > y));
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ TEST_CHECK_EQUAL(g.has_outgoing(stringify(x)), bool(x > 0));
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ TEST_CHECK_EQUAL(g.has_incoming(stringify(x)), bool(x < 19));
+
+ g.reverse();
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ for (unsigned y(0) ; y < 20 ; ++y)
+ TEST_CHECK_EQUAL(g.is_connected(stringify(x), stringify(y)), bool(x < y));
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ TEST_CHECK_EQUAL(g.has_incoming(stringify(x)), bool(x > 0));
+
+ for (unsigned x(0) ; x < 20 ; ++x)
+ TEST_CHECK_EQUAL(g.has_outgoing(stringify(x)), bool(x < 19));
+ }
+ } test_graph;
+}
+