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