#ifndef RUBY_BGL_GRAPH_HH #define RUBY_BGL_GRAPH_HH #include <ruby.h> #include <boost/graph/adjacency_list.hpp> #include <set> #include <boost/tuple/tuple.hpp> extern VALUE bglModule; extern VALUE bglGraph; extern VALUE bglReverseGraph; extern VALUE bglUndirectedGraph; extern VALUE bglVertex; /********************************************************************** * Definition of base C++ types */ struct EdgeProperty { VALUE info; boost::default_color_type color; // needed by some algorithms EdgeProperty(VALUE info) : info(info) { } }; typedef boost::adjacency_list< boost::setS, boost::setS , boost::bidirectionalS, VALUE, EdgeProperty> RubyGraph; typedef std::map<VALUE, RubyGraph::vertex_descriptor> graph_map; inline RubyGraph& graph_wrapped(VALUE self) { RubyGraph* object = 0; Data_Get_Struct(self, RubyGraph, object); return *object; } extern graph_map& vertex_descriptor_map(VALUE self); /* Return the vertex_descriptor of +self+ in +graph+. The boolean is true if * +self+ is in graph, and false otherwise. */ inline std::pair<RubyGraph::vertex_descriptor, bool> rb_to_vertex(VALUE vertex, VALUE graph) { graph_map& descriptors = vertex_descriptor_map(vertex); graph_map::iterator it = descriptors.find(graph); if(it == descriptors.end()) return std::make_pair(static_cast<void*>(0), false); else return std::make_pair(it->second, true); } /* Returns a range for all descriptors of +self+ */ inline std::pair<graph_map::iterator, graph_map::iterator> vertex_descriptors(VALUE self) { graph_map& descriptors = vertex_descriptor_map(self); return make_pair(descriptors.begin(), descriptors.end()); } namespace details { template<typename Graph, bool direct> struct vertex_range; template<typename Graph> struct vertex_range<Graph, true> { typedef typename Graph::adjacency_iterator iterator; typedef std::pair<iterator, iterator> range; static range get(RubyGraph::vertex_descriptor v, Graph& graph) { return adjacent_vertices(v, graph); } static range get(RubyGraph::vertex_descriptor v, Graph const& graph) { return adjacent_vertices(v, graph); } }; template<typename Graph> struct vertex_range<Graph, false> { typedef typename Graph::inv_adjacency_iterator iterator; typedef std::pair<iterator, iterator> range; static range get(RubyGraph::vertex_descriptor v, Graph& graph) { return inv_adjacent_vertices(v, graph); } static range get(RubyGraph::vertex_descriptor v, Graph const& graph) { return inv_adjacent_vertices(v, graph); } }; } /** Iterates on all vertices in the range */ template <typename Range, typename F> static bool for_each_value(Range range, RubyGraph& graph, F f) { typedef typename Range::first_type Iterator; Iterator it, end; for (boost::tie(it, end) = range; it != end; ) { VALUE value = graph[*it]; ++it; if (!f(value)) return false; } return true; } /** Iterates on each adjacent vertex of +v+ in +graph+ which are not yet in +already_seen+ */ template <typename Graph, bool direct> static bool for_each_adjacent_uniq(RubyGraph::vertex_descriptor v, Graph const& graph, std::set<VALUE>& already_seen) { typedef details::vertex_range<Graph, direct> getter; typedef typename getter::iterator Iterator; Iterator it, end; for (boost::tie(it, end) = details::vertex_range<Graph, direct>::get(v, graph); it != end; ) { VALUE related_object = graph[*it]; bool inserted; boost::tie(boost::tuples::ignore, inserted) = already_seen.insert(related_object); ++it; if (inserted) rb_yield_values(1, related_object); } return true; } /* Iterates on all graphs +vertex+ is part of, calling f(RubyGraph&, vertex_descriptor). If the calling * function returns false, stop iteration here */ template<typename F> static bool for_each_graph(VALUE vertex, F f) { graph_map::iterator graph, graph_end; for (boost::tie(graph, graph_end) = vertex_descriptors(vertex); graph != graph_end;) { RubyGraph& g = graph_wrapped(graph->first); RubyGraph::vertex_descriptor v = graph->second; ++graph; if (!f(v, g)) return false; } return true; } // Returns true if +v+ has either no child (if +direct+ is true) or no parents (if +direct+ is false) template<typename Graph, bool direct> bool vertex_has_adjacent_i(RubyGraph::vertex_descriptor v, Graph const& g) { typedef typename details::vertex_range<Graph, direct> getter; typename getter::iterator begin, end; boost::tie(begin, end) = getter::get(v, g); return begin == end; } template<bool direct> VALUE vertex_has_adjacent(int argc, VALUE* argv, VALUE self) { VALUE graph = Qnil; rb_scan_args(argc, argv, "01", &graph); bool result; if (NIL_P(graph)) result = for_each_graph(self, vertex_has_adjacent_i<RubyGraph, direct>); else { RubyGraph::vertex_descriptor v; bool exists; boost::tie(v, exists) = rb_to_vertex(self, graph); if (! exists) return Qtrue; RubyGraph& g = graph_wrapped(graph); result = vertex_has_adjacent_i<RubyGraph, direct>(v, g); } return result ? Qtrue : Qfalse; } #endif