1 /* Copyright (C) 2007-2013 Arjen G Lentz & Antony T Curtis for Open Query
2 
3    This program is free software; you can redistribute it and/or modify
4    it under the terms of the GNU General Public License as published by
5    the Free Software Foundation; version 2 of the License, or
6    (at your option) any later version.
7 
8    This program is distributed in the hope that it will be useful,
9    but WITHOUT ANY WARRANTY; without even the implied warranty of
10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11    GNU General Public License for more details.
12 
13    You should have received a copy of the GNU General Public License
14    along with this program; if not, write to the Free Software
15    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
16 
17 /* ======================================================================
18    Open Query Graph Computation Engine, based on a concept by Arjen Lentz
19    v3 implementation by Antony Curtis, Arjen Lentz, Andrew McDonnell
20    For more information, documentation, support, enhancement engineering,
21    see http://openquery.com/graph or contact graph@openquery.com
22    ======================================================================
23 */
24 
25 #pragma once
26 
27 #include "oqgraph_judy.h"
28 #include "oqgraph_thunk.h"
29 
30 #include <boost/graph/directed_graph.hpp>
31 #include <boost/graph/adjacency_iterator.hpp>
32 
33 namespace open_query
34 {
35   struct OQGraphTraversalCategory
36     : public boost::bidirectional_graph_tag
37     , public boost::adjacency_graph_tag
38     , public boost::edge_list_graph_tag
39   { };
40 
41 }
42 
43 namespace oqgraph3
44 {
45   struct traversal_category
46     : public boost::adjacency_graph_tag
47     , public boost::bidirectional_graph_tag
48     , public boost::edge_list_graph_tag
49   { };
50 
51   struct edge_iterator
52   {
53     typedef edge_iterator self;
54     typedef edge_info value_type;
55     typedef edge_info& reference;
56     typedef edge_info pointer;
57     typedef std::ptrdiff_t difference_type;
58     typedef std::input_iterator_tag iterator_category;
edge_iteratoredge_iterator59     edge_iterator() { }
60     edge_iterator(const graph_ptr& graph, size_t offset=0)
_graphedge_iterator61       : _graph(graph)
62       , _offset(offset) { }
edge_iteratoredge_iterator63     edge_iterator(const edge_iterator& pos)
64       : _graph(pos._graph)
65       , _offset(pos._offset) { }
66     value_type operator*();
67     self& operator+=(size_t n) { _offset+= n; return *this; }
68     self& operator++() { ++_offset; return *this; }
69     self operator++(int)
70     { size_t temp= _offset++; return edge_iterator(_graph, temp); }
71     bool seek();
72     bool operator==(const self& x);
73     bool operator!=(const self& x);
74     graph_ptr _graph;
75     size_t _offset;
76   };
77 
78   struct vertex_iterator
79   {
80     typedef vertex_iterator self;
81     typedef vertex_id value_type;
82     typedef vertex_id& reference;
83     typedef vertex_id pointer;
84     typedef std::ptrdiff_t difference_type;
85     typedef std::input_iterator_tag iterator_category;
vertex_iteratorvertex_iterator86     vertex_iterator() { }
vertex_iteratorvertex_iterator87     vertex_iterator(const cursor_ptr& pos) : _cursor(pos.operator->()) { }
88     vertex_id operator*() const
89     {
90       edge_info edge(*_cursor);
91       if (!_seen.test(edge.origid()))
92         return edge.origid();
93       else
94         return edge.destid();
95     }
96 
97     self& operator++()
98     {
99       edge_info edge(*_cursor);
100       if (!_seen.test(edge.origid()))
101       {
102         _seen.set(edge.origid());
103       }
104       else
105       {
106         _seen.set(edge.destid());
107       }
108 
109       while (_seen.test(edge.origid()) && _seen.test(edge.destid()))
110       {
111         if (_cursor->seek_next())
112           break;
113         edge= _cursor;
114       }
115       return *this;
116     }
117     self operator++(int) { cursor* t(new cursor(*_cursor)); ++(*this); return vertex_iterator(t); }
118     bool operator==(const self& x) { return *_cursor == *x._cursor; }
119     bool operator!=(const self& x) { return *_cursor != *x._cursor; }
120     cursor_ptr _cursor;
121     open_query::judy_bitset _seen;
122   };
123 
124 
125   struct out_edge_iterator
126   {
127     typedef out_edge_iterator self;
128     typedef edge_info value_type;
129     typedef edge_info& reference;
130     typedef edge_info pointer;
131     typedef std::ptrdiff_t difference_type;
132     typedef std::input_iterator_tag iterator_category;
out_edge_iteratorout_edge_iterator133     out_edge_iterator() { }
out_edge_iteratorout_edge_iterator134     out_edge_iterator(const cursor_ptr& cursor) : _cursor(cursor) { }
135     value_type operator*() { return value_type(_cursor); }
136     self& operator++() { _cursor->seek_next(); return *this; }
137     self operator++(int)
138     { cursor_ptr t(new cursor(*_cursor)); ++(*this); return out_edge_iterator(t); }
139     bool operator==(const self& x) { return _cursor == x._cursor; }
140     bool operator!=(const self& x) { return _cursor != x._cursor; }
141     cursor_ptr _cursor;
142   };
143 
144   struct in_edge_iterator
145   {
146     typedef in_edge_iterator self;
147     typedef edge_info value_type;
148     typedef edge_info& reference;
149     typedef edge_info pointer;
150     typedef std::ptrdiff_t difference_type;
151     typedef std::input_iterator_tag iterator_category;
in_edge_iteratorin_edge_iterator152     in_edge_iterator() { }
in_edge_iteratorin_edge_iterator153     in_edge_iterator(const cursor_ptr& cursor) : _cursor(cursor) { }
154     value_type operator*() const { return value_type(_cursor); }
155     self& operator++() { _cursor->seek_next(); return *this; }
156     self operator++(int)
157     { cursor_ptr t(new cursor(*_cursor)); ++(*this); return in_edge_iterator(t); }
158     bool operator==(const self& x) const { return _cursor == x._cursor; }
159     bool operator!=(const self& x) const { return _cursor != x._cursor; }
160     cursor_ptr _cursor;
161   };
162 
163   struct vertex_index_property_map
164   {
165     typedef vertex_id value_type;
166     typedef value_type reference;
167     typedef vertex_id key_type;
168     typedef boost::readable_property_map_tag category;
vertex_index_property_mapvertex_index_property_map169     vertex_index_property_map(const graph& g) : _g(g) { }
170     const graph& _g;
171 
172     friend inline reference
getvertex_index_property_map173     get(const vertex_index_property_map&, key_type key)
174     { return key; }
175   };
176 
177   struct edge_weight_property_map
178   {
179     typedef weight_t value_type;
180     typedef value_type reference;
181     typedef edge_info key_type;
182     typedef boost::readable_property_map_tag category;
edge_weight_property_mapedge_weight_property_map183     edge_weight_property_map(const graph& g) : _g(g) { }
184     friend inline reference
getedge_weight_property_map185     get(const edge_weight_property_map& p, const key_type& key)
186     { return key.weight(); }
187 
188     const graph& _g;
189   };
190 
191   struct edge_index_property_map
192   {
193     typedef cursor_ptr value_type;
194     typedef cursor_ptr reference;
195     typedef edge_info key_type;
196     typedef boost::readable_property_map_tag category;
edge_index_property_mapedge_index_property_map197     edge_index_property_map(const graph& g) : _g(g) { }
198     const graph& _g;
199   };
200 }
201 
202 namespace boost
203 {
204 
205   template<>
206   struct graph_traits<oqgraph3::graph>
207   {
208     typedef oqgraph3::vertex_id vertex_descriptor;
209     typedef oqgraph3::edge_info edge_descriptor;
210     typedef boost::adjacency_iterator_generator<
211         oqgraph3::graph,
212         oqgraph3::vertex_id,
213         oqgraph3::out_edge_iterator>::type adjacency_iterator;
214     typedef oqgraph3::out_edge_iterator out_edge_iterator;
215     typedef oqgraph3::in_edge_iterator in_edge_iterator;
216     typedef oqgraph3::vertex_iterator vertex_iterator;
217     typedef oqgraph3::edge_iterator edge_iterator;
218 
219     typedef boost::directed_tag directed_category;
220     typedef boost::allow_parallel_edge_tag edge_parallel_category;
221     typedef oqgraph3::traversal_category traversal_category;
222 
223     typedef oqgraph3::vertices_size_type vertices_size_type;
224     typedef oqgraph3::edges_size_type edges_size_type;
225     typedef oqgraph3::degree_size_type degree_size_type;
226 
227     static inline oqgraph3::vertex_id null_vertex()
228     { return oqgraph3::vertex_id(-1); }
229   };
230 
231   template<>
232   struct graph_traits<const oqgraph3::graph>
233     : public graph_traits<oqgraph3::graph>
234   { };
235 
236   template <>
237   struct graph_property_type<oqgraph3::graph>
238   {
239     typedef no_property type;
240   };
241 
242   template <>
243   struct vertex_property_type<oqgraph3::graph>
244   {
245     typedef no_property type;
246   };
247 
248   template <>
249   struct edge_property_type<oqgraph3::graph>
250   {
251     typedef no_property type;
252   };
253 
254 #if BOOST_VERSION < 106000 && BOOST_VERSION >= 104601
255   template <>
256   struct graph_bundle_type<oqgraph3::graph>
257   {
258     typedef no_graph_bundle type;
259   };
260 
261   template <>
262   struct vertex_bundle_type<oqgraph3::graph>
263   {
264     typedef no_vertex_bundle type;
265   };
266 
267   template <>
268   struct edge_bundle_type<oqgraph3::graph>
269   {
270     typedef no_edge_bundle type;
271   };
272 #endif
273 
274   template<>
275   struct property_map<oqgraph3::graph, edge_weight_t>
276   {
277     typedef void type;
278     typedef oqgraph3::edge_weight_property_map const_type;
279   };
280 
281   template<>
282   struct property_map<oqgraph3::graph, vertex_index_t>
283   {
284     typedef void type;
285     typedef oqgraph3::vertex_index_property_map const_type;
286   };
287 
288   template<>
289   struct property_map<oqgraph3::graph, edge_index_t>
290   {
291     typedef void type;
292     typedef oqgraph3::edge_index_property_map const_type;
293   };
294 
295 }
296 
297 namespace oqgraph3
298 {
299   using namespace boost;
300 
301   inline graph_traits<oqgraph3::graph>::vertex_descriptor
302   source(
303       const graph_traits<oqgraph3::graph>::edge_descriptor& e,
304       const oqgraph3::graph&)
305   { return e.origid(); }
306 
307   inline graph_traits<oqgraph3::graph>::vertex_descriptor
308   target(
309       const graph_traits<oqgraph3::graph>::edge_descriptor& e,
310       const oqgraph3::graph&)
311   { return e.destid(); }
312 
313   inline std::pair<
314       graph_traits<oqgraph3::graph>::out_edge_iterator,
315       graph_traits<oqgraph3::graph>::out_edge_iterator>
316   out_edges(
317       graph_traits<oqgraph3::graph>::vertex_descriptor v,
318       const oqgraph3::graph& g)
319   {
320     oqgraph3::cursor*
321         end= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
322     oqgraph3::cursor*
323         start= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
324     start->seek_to(v, boost::none);
325     return std::make_pair(
326         graph_traits<oqgraph3::graph>::out_edge_iterator(start),
327         graph_traits<oqgraph3::graph>::out_edge_iterator(end));
328   }
329 
330   inline graph_traits<oqgraph3::graph>::degree_size_type
331   out_degree(
332       graph_traits<oqgraph3::graph>::vertex_descriptor v,
333       const oqgraph3::graph& g)
334   {
335     std::size_t count = 0;
336     for (std::pair<
337             graph_traits<oqgraph3::graph>::out_edge_iterator,
338             graph_traits<oqgraph3::graph>::out_edge_iterator> i= out_edges(v, g);
339         i.first != i.second; ++i.first)
340     {
341       ++count;
342     }
343     return count;
344   }
345 
346 
347   inline std::pair<
348       graph_traits<oqgraph3::graph>::in_edge_iterator,
349       graph_traits<oqgraph3::graph>::in_edge_iterator>
350   in_edges(
351       graph_traits<oqgraph3::graph>::vertex_descriptor v,
352       const oqgraph3::graph& g)
353   {
354     oqgraph3::cursor*
355         end= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
356     oqgraph3::cursor*
357         start= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
358     start->seek_to(boost::none, v);
359     return std::make_pair(
360         graph_traits<oqgraph3::graph>::in_edge_iterator(start),
361         graph_traits<oqgraph3::graph>::in_edge_iterator(end));
362   }
363 
364   inline graph_traits<oqgraph3::graph>::degree_size_type
365   in_degree(
366       graph_traits<oqgraph3::graph>::vertex_descriptor v,
367       const oqgraph3::graph& g)
368   {
369     std::size_t count = 0;
370     for (std::pair<
371             graph_traits<oqgraph3::graph>::in_edge_iterator,
372             graph_traits<oqgraph3::graph>::in_edge_iterator> it= in_edges(v, g);
373         it.first != it.second; ++it.first)
374     {
375       ++count;
376     }
377     return count;
378   }
379 
380 
381   // EdgeListGraph concepts
382   inline std::pair<
383       graph_traits<oqgraph3::graph>::edge_iterator,
384       graph_traits<oqgraph3::graph>::edge_iterator>
385   edges(const oqgraph3::graph& g)
386   {
387     std::size_t end= std::size_t(-1);
388     std::size_t start= end;
389 
390     if (g.num_edges())
391       start= 0;
392 
393     return std::make_pair(
394         graph_traits<oqgraph3::graph>::edge_iterator(
395             const_cast<oqgraph3::graph*>(&g), start),
396         graph_traits<oqgraph3::graph>::edge_iterator(
397             const_cast<oqgraph3::graph*>(&g), end));
398   }
399 
400   inline std::pair<
401       graph_traits<oqgraph3::graph>::vertex_iterator,
402       graph_traits<oqgraph3::graph>::vertex_iterator>
403   vertices(const oqgraph3::graph& g)
404   {
405     oqgraph3::cursor*
406         start= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
407     start->seek_to(boost::none, boost::none);
408     return std::make_pair(
409         graph_traits<oqgraph3::graph>::vertex_iterator(start),
410         graph_traits<oqgraph3::graph>::vertex_iterator(
411             new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g))));
412   }
413 
414   inline graph_traits<oqgraph3::graph>::vertices_size_type
415   num_vertices(const oqgraph3::graph& g)
416   {
417     std::size_t count = 0;
418     for (std::pair<
419             graph_traits<oqgraph3::graph>::vertex_iterator,
420             graph_traits<oqgraph3::graph>::vertex_iterator> i= vertices(g);
421         i.first != i.second; ++i.first)
422     {
423       ++count;
424     }
425     return count;
426   }
427 
428   inline property_map<
429       oqgraph3::graph,
430       edge_weight_t>::const_type::reference
431   get(
432       edge_weight_t,
433       const oqgraph3::graph& g,
434       const property_map<
435           oqgraph3::graph,
436           edge_weight_t>::const_type::key_type& key)
437   { return key.weight(); }
438 
439   inline property_map<
440       oqgraph3::graph,
441       edge_weight_t>::const_type
442   get(edge_weight_t,
443       const oqgraph3::graph& g)
444   { return property_map<oqgraph3::graph, edge_weight_t>::const_type(g); }
445 
446   inline property_map<
447       oqgraph3::graph,
448       edge_index_t>::const_type::reference
449   get(edge_index_t,
450       const oqgraph3::graph&,
451       const property_map<
452           oqgraph3::graph,
453           edge_index_t>::const_type::key_type& key)
454   { return key._cursor; }
455 
456   inline property_map<oqgraph3::graph, edge_index_t>::const_type
457   get(edge_index_t, const oqgraph3::graph& g)
458   { return property_map<oqgraph3::graph, edge_index_t>::const_type(g); }
459 
460   inline property_map<oqgraph3::graph, edge_index_t>::const_type::reference
461   get(const property_map<oqgraph3::graph, edge_index_t>::const_type&,
462       const property_map<oqgraph3::graph,
463       edge_index_t>::const_type::key_type& key)
464   { return key._cursor; }
465 
466   inline property_map<oqgraph3::graph, vertex_index_t>::const_type::reference
467   get(vertex_index_t, const oqgraph3::graph&,
468       const property_map<oqgraph3::graph,
469       vertex_index_t>::const_type::key_type& key)
470   { return key; }
471 
472   inline property_map<oqgraph3::graph, vertex_index_t>::const_type
473   get(vertex_index_t, const oqgraph3::graph& g)
474   { return property_map<oqgraph3::graph, vertex_index_t>::const_type(g); }
475 
476   inline optional<graph_traits<oqgraph3::graph>::vertex_descriptor>
477   find_vertex(oqgraph3::vertex_id id, const oqgraph3::graph& g)
478   {
479     // Fix for https://bugs.launchpad.net/oqgraph/+bug/1196020 returning vertex even when not in graph
480     // Psuedocode for fix:
481     // if count(*) from g->TABLE where source=id or target=id > 0 then return id else return null
482     oqgraph3::cursor* found_cursor = new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
483     bool found = (found_cursor->seek_to(id, boost::none) && found_cursor->seek_to(boost::none, id));
484     delete found_cursor;
485     if (found) {
486       // id is neither a from or a to in a link
487       return optional<graph_traits<oqgraph3::graph>::vertex_descriptor>();
488     }
489     return id;
490   }
491 
492 }
493 
494