aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2007-04-15 20:57:27 +0000
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2007-04-15 20:57:27 +0000
commit0abd2e2f37f8edf61a4a03ae8a403dc3fcb8b502 (patch)
treee0e78871fb28910ac73c4bee48e1ee51727f204c
parent93d1769e99e77c61d8b20b28dd741ebf83559519 (diff)
downloadpaludis-0abd2e2f37f8edf61a4a03ae8a403dc3fcb8b502.tar.gz
paludis-0abd2e2f37f8edf61a4a03ae8a403dc3fcb8b502.tar.xz
More graph work
-rw-r--r--paludis/util/graph-impl.hh39
-rw-r--r--paludis/util/graph.cc19
-rw-r--r--paludis/util/graph.hh11
-rw-r--r--paludis/util/graph_TEST.cc10
4 files changed, 72 insertions, 7 deletions
diff --git a/paludis/util/graph-impl.hh b/paludis/util/graph-impl.hh
index 37a1fbf..62919cf 100644
--- a/paludis/util/graph-impl.hh
+++ b/paludis/util/graph-impl.hh
@@ -21,10 +21,36 @@
#define PALUDIS_GUARD_PALUDIS_UTIL_GRAPH_IMPL_HH 1
#include <paludis/util/graph.hh>
+#include <libwrapiter/libwrapiter_forward_iterator.hh>
#include <map>
+#include <list>
namespace paludis
{
+ class NoGraphTopologicalOrderExistsError::RemainingNodes
+ {
+ private:
+ std::list<std::string> _n;
+
+ public:
+ void add(const std::string & s)
+ {
+ _n.push_back(s);
+ }
+
+ typedef libwrapiter::ForwardIterator<RemainingNodes, const std::string> Iterator;
+
+ Iterator begin() const
+ {
+ return Iterator(_n.begin());
+ }
+
+ Iterator end() const
+ {
+ return Iterator(_n.end());
+ }
+ };
+
template<>
template <typename Node_, typename Edge_>
struct Implementation<DirectedGraph<Node_, Edge_> >
@@ -231,7 +257,7 @@ namespace paludis
template <typename Node_, typename Edge_>
template <typename OutputIterator_>
void
- DirectedGraph<Node_, Edge_>::topological_sort(OutputIterator_ i) const
+ DirectedGraph<Node_, Edge_>::topological_sort(OutputIterator_ x) const
{
struct Sorter
{
@@ -267,12 +293,19 @@ namespace paludis
do_one(i, *n++);
if (g.begin_nodes() != g.end_nodes())
- throw NoGraphTopologicalOrderExistsError();
+ {
+ std::tr1::shared_ptr<NoGraphTopologicalOrderExistsError::RemainingNodes> r(
+ new NoGraphTopologicalOrderExistsError::RemainingNodes);
+ for (typename DirectedGraph::NodeIterator n(g.begin_nodes()), n_end(g.end_nodes()) ; n != n_end ; ++n)
+ r->add(stringify(*n));
+
+ throw NoGraphTopologicalOrderExistsError(r);
+ }
}
};
Sorter s(*this);
- s.sort(i);
+ s.sort(x);
}
}
diff --git a/paludis/util/graph.cc b/paludis/util/graph.cc
index 8d3017f..8051b2b 100644
--- a/paludis/util/graph.cc
+++ b/paludis/util/graph.cc
@@ -17,7 +17,8 @@
* Place, Suite 330, Boston, MA 02111-1307 USA
*/
-#include "graph.hh"
+#include <paludis/util/graph.hh>
+#include <paludis/util/graph-impl.hh>
using namespace paludis;
@@ -26,8 +27,20 @@ GraphError::GraphError(const std::string & msg) throw () :
{
}
-NoGraphTopologicalOrderExistsError::NoGraphTopologicalOrderExistsError() throw () :
- GraphError("No topological order exists")
+NoGraphTopologicalOrderExistsError::NoGraphTopologicalOrderExistsError(
+ std::tr1::shared_ptr<const RemainingNodes> r) throw () :
+ GraphError("No topological order exists"),
+ _remaining_nodes(r)
+{
+}
+
+std::tr1::shared_ptr<const NoGraphTopologicalOrderExistsError::RemainingNodes>
+NoGraphTopologicalOrderExistsError::remaining_nodes() const
+{
+ return _remaining_nodes;
+}
+
+NoGraphTopologicalOrderExistsError::~NoGraphTopologicalOrderExistsError() throw ()
{
}
diff --git a/paludis/util/graph.hh b/paludis/util/graph.hh
index a6bfd3a..f1ecd2f 100644
--- a/paludis/util/graph.hh
+++ b/paludis/util/graph.hh
@@ -58,8 +58,17 @@ namespace paludis
class NoGraphTopologicalOrderExistsError :
public GraphError
{
+ private:
+ class RemainingNodes;
+
+ private:
+ std::tr1::shared_ptr<const RemainingNodes> _remaining_nodes;
+
public:
- NoGraphTopologicalOrderExistsError() throw ();
+ NoGraphTopologicalOrderExistsError(std::tr1::shared_ptr<const RemainingNodes>) throw ();
+ ~NoGraphTopologicalOrderExistsError() throw ();
+
+ std::tr1::shared_ptr<const RemainingNodes> remaining_nodes() const;
};
template <typename Node_, typename Edge_>
diff --git a/paludis/util/graph_TEST.cc b/paludis/util/graph_TEST.cc
index ff3f6bb..b5ec2dd 100644
--- a/paludis/util/graph_TEST.cc
+++ b/paludis/util/graph_TEST.cc
@@ -98,6 +98,16 @@ namespace test_cases
g.add_edge("e", "b", 7);
TEST_CHECK_THROWS(g.topological_sort(std::back_inserter(t)), NoGraphTopologicalOrderExistsError);
+
+ try
+ {
+ g.topological_sort(std::back_inserter(t));
+ TEST_CHECK(false);
+ }
+ catch (const NoGraphTopologicalOrderExistsError & e)
+ {
+ TEST_CHECK_EQUAL(join(e.remaining_nodes()->begin(), e.remaining_nodes()->end(), " "), "a b c d e");
+ }
}
} test_directed_graph;
}