aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2007-04-15 19:08:55 +0000
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2007-04-15 19:08:55 +0000
commit93d1769e99e77c61d8b20b28dd741ebf83559519 (patch)
treef36e06cc13c648352fece782f93dffa7a1f5441a
parentea20886b9bf8f29fa841e56b4c262ae3e341b497 (diff)
downloadpaludis-93d1769e99e77c61d8b20b28dd741ebf83559519.tar.gz
paludis-93d1769e99e77c61d8b20b28dd741ebf83559519.tar.xz
Easier to use graph code
-rw-r--r--paludis/util/files.m42
-rw-r--r--paludis/util/graph-impl.hh279
-rw-r--r--paludis/util/graph.cc180
-rw-r--r--paludis/util/graph.hh219
-rw-r--r--paludis/util/graph_TEST.cc191
5 files changed, 460 insertions, 411 deletions
diff --git a/paludis/util/files.m4 b/paludis/util/files.m4
index 9cc9ac5..9320133 100644
--- a/paludis/util/files.m4
+++ b/paludis/util/files.m4
@@ -20,7 +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(`graph', `hh', `cc', `impl', `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-impl.hh b/paludis/util/graph-impl.hh
new file mode 100644
index 0000000..37a1fbf
--- /dev/null
+++ b/paludis/util/graph-impl.hh
@@ -0,0 +1,279 @@
+/* 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_IMPL_HH
+#define PALUDIS_GUARD_PALUDIS_UTIL_GRAPH_IMPL_HH 1
+
+#include <paludis/util/graph.hh>
+#include <map>
+
+namespace paludis
+{
+ template<>
+ template <typename Node_, typename Edge_>
+ struct Implementation<DirectedGraph<Node_, Edge_> >
+ {
+ std::map<Node_, std::map<Node_, Edge_> > store;
+
+ Implementation()
+ {
+ }
+
+ Implementation(const std::map<Node_, std::map<Node_, Edge_> > s) :
+ store(s)
+ {
+ }
+ };
+
+ template <typename Node_, typename Edge_>
+ DirectedGraph<Node_, Edge_>::DirectedGraph() :
+ PrivateImplementationPattern<DirectedGraph<Node_, Edge_> >(new Implementation<DirectedGraph<Node_, Edge_> >)
+ {
+ }
+
+ template <typename Node_, typename Edge_>
+ DirectedGraph<Node_, Edge_>::DirectedGraph(const DirectedGraph & g) :
+ PrivateImplementationPattern<DirectedGraph<Node_, Edge_> >(new Implementation<DirectedGraph<Node_, Edge_> >(g._imp->store))
+ {
+ }
+
+ template <typename Node_, typename Edge_>
+ DirectedGraph<Node_, Edge_>::~DirectedGraph()
+ {
+ }
+
+ template <typename Node_, typename Edge_>
+ void
+ DirectedGraph<Node_, Edge_>::add_node(const Node_ & n)
+ {
+ _imp->store.insert(std::make_pair(n, std::map<Node_, Edge_>()));
+ }
+
+ template <typename Node_, typename Edge_>
+ void
+ DirectedGraph<Node_, Edge_>::delete_node(const Node_ & n)
+ {
+ delete_incoming_edges(n);
+ _imp->store.erase(n);
+ }
+
+ template <typename Node_, typename Edge_>
+ bool
+ DirectedGraph<Node_, Edge_>::has_node(const Node_ & n) const
+ {
+ return _imp->store.end() != _imp->store.find(n);
+ }
+
+ template <typename Node_, typename Edge_>
+ class DirectedGraph<Node_, Edge_>::NodeIterator
+ {
+ friend class DirectedGraph<Node_, Edge_>;
+
+ private:
+ typename std::map<Node_, std::map<Node_, Edge_> >::const_iterator _i;
+
+ NodeIterator(const typename std::map<Node_, std::map<Node_, Edge_> >::const_iterator & i) :
+ _i(i)
+ {
+ }
+
+ public:
+ NodeIterator(const NodeIterator & other) :
+ _i(other._i)
+ {
+ }
+
+ ~NodeIterator()
+ {
+ }
+
+ bool operator== (const NodeIterator & other) const
+ {
+ return _i == other._i;
+ }
+
+ bool operator!= (const NodeIterator & other) const
+ {
+ return ! operator== (other);
+ }
+
+ NodeIterator & operator++ ()
+ {
+ ++_i;
+ return *this;
+ }
+
+ NodeIterator operator++ (int)
+ {
+ NodeIterator tmp(*this);
+ ++_i;
+ return tmp;
+ }
+
+ const Node_ & operator*() const
+ {
+ return _i->first;
+ }
+
+ const Node_ * operator->() const
+ {
+ return &_i->first;
+ }
+ };
+
+ template <typename Node_, typename Edge_>
+ typename DirectedGraph<Node_, Edge_>::NodeIterator
+ DirectedGraph<Node_, Edge_>::begin_nodes() const
+ {
+ return NodeIterator(_imp->store.begin());
+ }
+
+ template <typename Node_, typename Edge_>
+ typename DirectedGraph<Node_, Edge_>::NodeIterator
+ DirectedGraph<Node_, Edge_>::end_nodes() const
+ {
+ return NodeIterator(_imp->store.end());
+ }
+
+ template <typename Node_, typename Edge_>
+ void
+ DirectedGraph<Node_, Edge_>::add_edge(const Node_ & n1, const Node_ & n2, const Edge_ & e)
+ {
+ typename std::map<Node_, std::map<Node_, Edge_> >::iterator i(_imp->store.find(n1));
+ if (i == _imp->store.end())
+ throw NoSuchGraphNodeError(n1);
+
+ if (! has_node(n2))
+ throw NoSuchGraphNodeError(n2);
+
+ i->second.insert(std::make_pair(n2, e));
+ }
+
+ template <typename Node_, typename Edge_>
+ void
+ DirectedGraph<Node_, Edge_>::delete_edge(const Node_ & n1, const Node_ & n2)
+ {
+ typename std::map<Node_, std::map<Node_, Edge_> >::iterator i(_imp->store.find(n1));
+ if (i != _imp->store.end())
+ i->second.erase(n2);
+ }
+
+ template <typename Node_, typename Edge_>
+ void
+ DirectedGraph<Node_, Edge_>::delete_outgoing_edges(const Node_ & n)
+ {
+ typename std::map<Node_, std::map<Node_, Edge_> >::iterator i(_imp->store.find(n.first));
+ if (i != _imp->store.end())
+ i->second.clear();
+ }
+
+ template <typename Node_, typename Edge_>
+ void
+ DirectedGraph<Node_, Edge_>::delete_incoming_edges(const Node_ & n)
+ {
+ for (typename std::map<Node_, std::map<Node_, Edge_> >::iterator i(_imp->store.begin()),
+ i_end(_imp->store.end()) ; i != i_end ; ++i)
+ i->second.erase(n);
+ }
+
+ template <typename Node_, typename Edge_>
+ bool
+ DirectedGraph<Node_, Edge_>::has_edge(const Node_ & n1, const Node_ & n2) const
+ {
+ typename std::map<Node_, std::map<Node_, Edge_> >::const_iterator i(_imp->store.find(n1));
+ if (i != _imp->store.end())
+ return i->second.end() != i->second.find(n2);
+ return false;
+ }
+
+ template <typename Node_, typename Edge_>
+ const Edge_
+ DirectedGraph<Node_, Edge_>::fetch_edge(const Node_ & n1, const Node_ & n2) const
+ {
+ typename std::map<Node_, std::map<Node_, Edge_> >::const_iterator i(_imp->store.find(n1));
+ if (i != _imp->store.end())
+ {
+ typename std::map<Node_, Edge_>::const_iterator j(i->second.find(n2));
+ if (j != i->second.end())
+ return j->second;
+ }
+
+ throw NoSuchGraphEdgeError(n1, n2);
+ }
+
+ template <typename Node_, typename Edge_>
+ bool
+ DirectedGraph<Node_, Edge_>::has_outgoing_edges(const Node_ & n) const
+ {
+ typename std::map<Node_, std::map<Node_, Edge_> >::const_iterator i(_imp->store.find(n));
+ if (i == _imp->store.end())
+ throw NoSuchGraphNodeError(n);
+
+ return ! i->second.empty();
+ }
+
+ template <typename Node_, typename Edge_>
+ template <typename OutputIterator_>
+ void
+ DirectedGraph<Node_, Edge_>::topological_sort(OutputIterator_ i) const
+ {
+ struct Sorter
+ {
+ DirectedGraph g;
+
+ Sorter(const DirectedGraph & gg) :
+ g(gg)
+ {
+ }
+
+ void do_one(OutputIterator_ i, const Node_ & n)
+ {
+ if (g.has_outgoing_edges(n))
+ return;
+
+ *i++ = n;
+
+ for (typename DirectedGraph::NodeIterator m(g.begin_nodes()), m_end(g.end_nodes()) ; m != m_end ; )
+ if ((*m != n) && g.has_edge(*m, n))
+ {
+ g.delete_edge(*m, n);
+ do_one(i, *m++);
+ }
+ else
+ ++m;
+
+ g.delete_node(n);
+ }
+
+ void sort(OutputIterator_ i)
+ {
+ for (typename DirectedGraph::NodeIterator n(g.begin_nodes()), n_end(g.end_nodes()) ; n != n_end ; )
+ do_one(i, *n++);
+
+ if (g.begin_nodes() != g.end_nodes())
+ throw NoGraphTopologicalOrderExistsError();
+ }
+ };
+
+ Sorter s(*this);
+ s.sort(i);
+ }
+}
+
+#endif
diff --git a/paludis/util/graph.cc b/paludis/util/graph.cc
index cf05314..8d3017f 100644
--- a/paludis/util/graph.cc
+++ b/paludis/util/graph.cc
@@ -18,188 +18,16 @@
*/
#include "graph.hh"
-#include <paludis/util/save.hh>
-#include <stdint.h>
-#include <vector>
using namespace paludis;
-namespace
+GraphError::GraphError(const std::string & msg) throw () :
+ Exception(msg)
{
- unsigned size_needed_for(const unsigned s)
- {
- return 1 + ((s - 1) / 8);
- }
}
-namespace paludis
+NoGraphTopologicalOrderExistsError::NoGraphTopologicalOrderExistsError() throw () :
+ GraphError("No topological order exists")
{
- 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
index 0f118ed..a6bfd3a 100644
--- a/paludis/util/graph.hh
+++ b/paludis/util/graph.hh
@@ -22,130 +22,143 @@
#include <paludis/util/private_implementation_pattern.hh>
#include <paludis/util/instantiation_policy.hh>
+#include <paludis/util/exception.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 :
+ class GraphError :
public Exception
{
- private:
- const unsigned _cycle;
-
- public:
- NoSimpleTopologicalOrderingExists(const unsigned &) throw ();
-
- unsigned cycle() const
- PALUDIS_ATTRIBUTE((warn_unused_result));
+ protected:
+ GraphError(const std::string & msg) throw ();
};
- class SimpleTopologicalOrdering :
- private PrivateImplementationPattern<SimpleTopologicalOrdering>
+ class NoSuchGraphNodeError :
+ public GraphError
{
- 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)
+ template <typename Node_>
+ NoSuchGraphNodeError(const Node_ & node) throw () :
+ GraphError("Node '" + stringify(node) + "' does not exist")
{
}
+ };
+ class NoSuchGraphEdgeError :
+ public GraphError
+ {
public:
- virtual ~Graph()
+ template <typename Node_>
+ NoSuchGraphEdgeError(const Node_ & e1, const Node_ & e2) throw () :
+ GraphError("Edge '" + stringify(e1) + "' -> '" + stringify(e2) + "' does not exist")
{
}
-
- 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
+ class NoGraphTopologicalOrderExistsError :
+ public GraphError
{
- return SimpleGraph::is_connected(node_to_index(a), node_to_index(b));
- }
+ public:
+ NoGraphTopologicalOrderExistsError() throw ();
+ };
- template <typename T_>
- bool Graph<T_>::has_outgoing(const T_ & a) const
+ template <typename Node_, typename Edge_>
+ class DirectedGraph :
+ private PrivateImplementationPattern<DirectedGraph<Node_, Edge_> >
{
- return SimpleGraph::has_outgoing(node_to_index(a));
- }
+ private:
+ using PrivateImplementationPattern<DirectedGraph<Node_, Edge_> >::_imp;
- template <typename T_>
- bool Graph<T_>::has_incoming(const T_ & a) const
- {
- return SimpleGraph::has_incoming(node_to_index(a));
- }
+ void operator= (const DirectedGraph &);
+
+ public:
+ DirectedGraph();
+ DirectedGraph(const DirectedGraph &);
+ ~DirectedGraph();
+
+ ///\name Node related functions
+ ///\{
+
+ /**
+ * Add a node, if it does not already exist.
+ */
+ void add_node(const Node_ &);
+
+ /**
+ * Delete a node, if it exists.
+ */
+ void delete_node(const Node_ &);
+
+ /**
+ * Return whether a node exists.
+ */
+ bool has_node(const Node_ &) const;
+
+ class NodeIterator;
+ NodeIterator begin_nodes() const;
+ NodeIterator end_nodes() const;
+
+ ///\}
+
+ ///\name Edge related functions
+ ///\{
+
+ /**
+ * Add an edge, if it does not already exist.
+ *
+ * \throw NoSuchGraphNodeError if either node is not in the graph.
+ */
+ void add_edge(const Node_ &, const Node_ &, const Edge_ &);
+
+ /**
+ * Delete an edge, if it exists.
+ */
+ void delete_edge(const Node_ &, const Node_ &);
+
+ /**
+ * Delete all edges leaving a node.
+ */
+ void delete_outgoing_edges(const Node_ &);
+
+ /**
+ * Delete all edges entering a node.
+ */
+ void delete_incoming_edges(const Node_ &);
+
+ /**
+ * Return whether an edge exists.
+ */
+ bool has_edge(const Node_ &, const Node_ &) const;
+
+ /**
+ * Fetch an edge.
+ *
+ * \throw NoSuchGraphEdgeError if the edge does not exist.
+ */
+ const Edge_ fetch_edge(const Node_ &, const Node_ &) const;
+
+ /**
+ * Return whether a node has outgoing edges.
+ *
+ * \throw NoSuchGraphNodeError if the node does not exist.
+ */
+ bool has_outgoing_edges(const Node_ &) const;
+
+ ///\}
+
+ ///\name Ordering functions
+ ///\{
+
+ /**
+ * Place our nodes, topological sorted, into OutputIterator_.
+ *
+ * \throw NoGraphTopologicalOrderExistsError if no such order exists.
+ */
+ template <typename OutputIterator_>
+ void topological_sort(OutputIterator_ i) const;
+
+ ///\}
+ };
}
#endif
diff --git a/paludis/util/graph_TEST.cc b/paludis/util/graph_TEST.cc
index 005fba9..ff3f6bb 100644
--- a/paludis/util/graph_TEST.cc
+++ b/paludis/util/graph_TEST.cc
@@ -17,159 +17,88 @@
* Place, Suite 330, Boston, MA 02111-1307 USA
*/
-#include "graph.hh"
#include <test/test_framework.hh>
#include <test/test_runner.hh>
+
+#include <paludis/util/graph.hh>
+#include <paludis/util/graph-impl.hh>
#include <paludis/util/join.hh>
#include <paludis/util/destringify.hh>
+#include <list>
+
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
+ struct TestDirectedGraph : TestCase
{
- SimpleGraphTest() : TestCase("simple graph") { }
+ TestDirectedGraph() : TestCase("directed graph") { }
void run()
{
- SimpleGraph g(20);
- for (unsigned x(0) ; x < 20 ; ++x)
- for (unsigned y(0) ; y < 20 ; ++y)
+ DirectedGraph<std::string, int> g;
+
+ TEST_CHECK(! g.has_node("a"));
+ TEST_CHECK(! g.has_node("b"));
+ TEST_CHECK(! g.has_node("c"));
+ TEST_CHECK(! g.has_node("d"));
+ TEST_CHECK(! g.has_node("e"));
+ TEST_CHECK(! g.has_node("f"));
+ TEST_CHECK(! g.has_node("x"));
+
+ g.add_node("a");
+ g.add_node("b");
+ g.add_node("c");
+ g.add_node("d");
+ g.add_node("e");
+ g.add_node("f");
+
+ TEST_CHECK(g.has_node("a"));
+ TEST_CHECK(g.has_node("b"));
+ TEST_CHECK(g.has_node("c"));
+ TEST_CHECK(g.has_node("d"));
+ TEST_CHECK(g.has_node("e"));
+ TEST_CHECK(g.has_node("f"));
+ TEST_CHECK(! g.has_node("x"));
+
+ g.add_node("y");
+ TEST_CHECK(g.has_node("y"));
+ g.delete_node("y");
+ TEST_CHECK(! g.has_node("y"));
+
+ g.add_edge("a", "b", 1);
+ g.add_edge("b", "c", 2);
+ g.add_edge("c", "e", 3);
+ g.add_edge("b", "d", 4);
+ g.add_edge("d", "e", 5);
+ g.add_edge("d", "f", 6);
+
+ int x(0);
+ for (char mc('a') ; mc < 'g' ; ++mc)
+ for (char nc('a') ; nc < 'g' ; ++nc)
{
- 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));
+ std::string m(stringify(mc)), n(stringify(nc));
- 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)
+ if (g.has_edge(m, n))
{
- g.connect(stringify(x), stringify(y));
- TEST_CHECK(g.is_connected(stringify(x), stringify(y)));
+ TEST_CHECK(! g.has_edge(n, m));
+ TEST_CHECK(g.has_outgoing_edges(m));
+ TEST_CHECK(0 != g.fetch_edge(m, n));
}
+ else
+ TEST_CHECK_THROWS(g.fetch_edge(m, n), NoSuchGraphEdgeError);
}
- 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));
+ std::list<std::string> t;
+ g.topological_sort(std::back_inserter(t));
- for (unsigned x(0) ; x < 20 ; ++x)
- TEST_CHECK_EQUAL(g.has_incoming(stringify(x)), bool(x > 0));
+ TEST_CHECK_EQUAL(join(t.begin(), t.end(), " "), "e c f d b a");
- for (unsigned x(0) ; x < 20 ; ++x)
- TEST_CHECK_EQUAL(g.has_outgoing(stringify(x)), bool(x < 19));
+ g.add_edge("e", "b", 7);
+ TEST_CHECK_THROWS(g.topological_sort(std::back_inserter(t)), NoGraphTopologicalOrderExistsError);
}
- } test_graph;
+ } test_directed_graph;
}