mirror of
https://github.com/MariaDB/server.git
synced 2025-10-31 19:06:14 +01:00
490 lines
15 KiB
C++
490 lines
15 KiB
C++
/* Copyright (C) 2007-2013 Arjen G Lentz & Antony T Curtis for Open Query
|
|
|
|
This program is free software; you can redistribute it and/or modify
|
|
it under the terms of the GNU General Public License as published by
|
|
the Free Software Foundation; version 2 of the License, or
|
|
(at your option) any later version.
|
|
|
|
This program 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
|
|
|
|
/* ======================================================================
|
|
Open Query Graph Computation Engine, based on a concept by Arjen Lentz
|
|
v3 implementation by Antony Curtis, Arjen Lentz, Andrew McDonnell
|
|
For more information, documentation, support, enhancement engineering,
|
|
see http://openquery.com/graph or contact graph@openquery.com
|
|
======================================================================
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
#include "oqgraph_judy.h"
|
|
#include "oqgraph_thunk.h"
|
|
|
|
#include <boost/graph/directed_graph.hpp>
|
|
#include <boost/graph/adjacency_iterator.hpp>
|
|
|
|
namespace open_query
|
|
{
|
|
struct OQGraphTraversalCategory
|
|
: public boost::bidirectional_graph_tag
|
|
, public boost::adjacency_graph_tag
|
|
, public boost::edge_list_graph_tag
|
|
{ };
|
|
|
|
}
|
|
|
|
namespace oqgraph3
|
|
{
|
|
struct traversal_category
|
|
: public boost::adjacency_graph_tag
|
|
, public boost::bidirectional_graph_tag
|
|
, public boost::edge_list_graph_tag
|
|
{ };
|
|
|
|
struct edge_iterator
|
|
{
|
|
typedef edge_iterator self;
|
|
typedef edge_info value_type;
|
|
typedef edge_info& reference;
|
|
typedef edge_info pointer;
|
|
typedef std::ptrdiff_t difference_type;
|
|
typedef std::input_iterator_tag iterator_category;
|
|
edge_iterator() { }
|
|
edge_iterator(const graph_ptr& graph, size_t offset=0)
|
|
: _graph(graph)
|
|
, _offset(offset) { }
|
|
value_type operator*();
|
|
self& operator+=(size_t n) { _offset+= n; return *this; }
|
|
self& operator++() { ++_offset; return *this; }
|
|
self operator++(int)
|
|
{ size_t temp= _offset++; return edge_iterator(_graph, temp); }
|
|
bool seek();
|
|
bool operator==(const self& x);
|
|
bool operator!=(const self& x);
|
|
graph_ptr _graph;
|
|
size_t _offset;
|
|
};
|
|
|
|
struct vertex_iterator
|
|
{
|
|
typedef vertex_iterator self;
|
|
typedef vertex_id value_type;
|
|
typedef vertex_id& reference;
|
|
typedef vertex_id pointer;
|
|
typedef std::ptrdiff_t difference_type;
|
|
typedef std::input_iterator_tag iterator_category;
|
|
vertex_iterator() { }
|
|
vertex_iterator(const cursor_ptr& pos) : _cursor(pos.operator->()) { }
|
|
vertex_id operator*() const
|
|
{
|
|
edge_info edge(*_cursor);
|
|
if (!_seen.test(edge.origid()))
|
|
return edge.origid();
|
|
else
|
|
return edge.destid();
|
|
}
|
|
|
|
self& operator++()
|
|
{
|
|
edge_info edge(*_cursor);
|
|
if (!_seen.test(edge.origid()))
|
|
{
|
|
_seen.set(edge.origid());
|
|
}
|
|
else
|
|
{
|
|
_seen.set(edge.destid());
|
|
}
|
|
|
|
while (_seen.test(edge.origid()) && _seen.test(edge.destid()))
|
|
{
|
|
if (_cursor->seek_next())
|
|
break;
|
|
edge= _cursor;
|
|
}
|
|
return *this;
|
|
}
|
|
self operator++(int) { cursor* t(new cursor(*_cursor)); ++(*this); return vertex_iterator(t); }
|
|
bool operator==(const self& x) { return *_cursor == *x._cursor; }
|
|
bool operator!=(const self& x) { return *_cursor != *x._cursor; }
|
|
cursor_ptr _cursor;
|
|
open_query::judy_bitset _seen;
|
|
};
|
|
|
|
|
|
struct out_edge_iterator
|
|
{
|
|
typedef out_edge_iterator self;
|
|
typedef edge_info value_type;
|
|
typedef edge_info& reference;
|
|
typedef edge_info pointer;
|
|
typedef std::ptrdiff_t difference_type;
|
|
typedef std::input_iterator_tag iterator_category;
|
|
out_edge_iterator() { }
|
|
out_edge_iterator(const cursor_ptr& cursor) : _cursor(cursor) { }
|
|
value_type operator*() { return value_type(_cursor); }
|
|
self& operator++() { _cursor->seek_next(); return *this; }
|
|
self operator++(int)
|
|
{ cursor_ptr t(new cursor(*_cursor)); ++(*this); return out_edge_iterator(t); }
|
|
bool operator==(const self& x) { return _cursor == x._cursor; }
|
|
bool operator!=(const self& x) { return _cursor != x._cursor; }
|
|
cursor_ptr _cursor;
|
|
};
|
|
|
|
struct in_edge_iterator
|
|
{
|
|
typedef in_edge_iterator self;
|
|
typedef edge_info value_type;
|
|
typedef edge_info& reference;
|
|
typedef edge_info pointer;
|
|
typedef std::ptrdiff_t difference_type;
|
|
typedef std::input_iterator_tag iterator_category;
|
|
in_edge_iterator() { }
|
|
in_edge_iterator(const cursor_ptr& cursor) : _cursor(cursor) { }
|
|
value_type operator*() const { return value_type(_cursor); }
|
|
self& operator++() { _cursor->seek_next(); return *this; }
|
|
self operator++(int)
|
|
{ cursor_ptr t(new cursor(*_cursor)); ++(*this); return in_edge_iterator(t); }
|
|
bool operator==(const self& x) const { return _cursor == x._cursor; }
|
|
bool operator!=(const self& x) const { return _cursor != x._cursor; }
|
|
cursor_ptr _cursor;
|
|
};
|
|
|
|
struct vertex_index_property_map
|
|
{
|
|
typedef vertex_id value_type;
|
|
typedef value_type reference;
|
|
typedef vertex_id key_type;
|
|
typedef boost::readable_property_map_tag category;
|
|
vertex_index_property_map(const graph& g) : _g(g) { }
|
|
const graph& _g;
|
|
|
|
friend inline reference
|
|
get(const vertex_index_property_map&, key_type key)
|
|
{ return key; }
|
|
};
|
|
|
|
struct edge_weight_property_map
|
|
{
|
|
typedef weight_t value_type;
|
|
typedef value_type reference;
|
|
typedef edge_info key_type;
|
|
typedef boost::readable_property_map_tag category;
|
|
edge_weight_property_map(const graph& g) : _g(g) { }
|
|
friend inline reference
|
|
get(const edge_weight_property_map& p, const key_type& key)
|
|
{ return key.weight(); }
|
|
|
|
const graph& _g;
|
|
};
|
|
|
|
struct edge_index_property_map
|
|
{
|
|
typedef cursor_ptr value_type;
|
|
typedef cursor_ptr reference;
|
|
typedef edge_info key_type;
|
|
typedef boost::readable_property_map_tag category;
|
|
edge_index_property_map(const graph& g) : _g(g) { }
|
|
const graph& _g;
|
|
};
|
|
}
|
|
|
|
namespace boost
|
|
{
|
|
|
|
template<>
|
|
struct graph_traits<oqgraph3::graph>
|
|
{
|
|
typedef oqgraph3::vertex_id vertex_descriptor;
|
|
typedef oqgraph3::edge_info edge_descriptor;
|
|
typedef boost::adjacency_iterator_generator<
|
|
oqgraph3::graph,
|
|
oqgraph3::vertex_id,
|
|
oqgraph3::out_edge_iterator>::type adjacency_iterator;
|
|
typedef oqgraph3::out_edge_iterator out_edge_iterator;
|
|
typedef oqgraph3::in_edge_iterator in_edge_iterator;
|
|
typedef oqgraph3::vertex_iterator vertex_iterator;
|
|
typedef oqgraph3::edge_iterator edge_iterator;
|
|
|
|
typedef boost::directed_tag directed_category;
|
|
typedef boost::allow_parallel_edge_tag edge_parallel_category;
|
|
typedef oqgraph3::traversal_category traversal_category;
|
|
|
|
typedef oqgraph3::vertices_size_type vertices_size_type;
|
|
typedef oqgraph3::edges_size_type edges_size_type;
|
|
typedef oqgraph3::degree_size_type degree_size_type;
|
|
|
|
static inline oqgraph3::vertex_id null_vertex()
|
|
{ return oqgraph3::vertex_id(-1); }
|
|
};
|
|
|
|
template<>
|
|
struct graph_traits<const oqgraph3::graph>
|
|
: public graph_traits<oqgraph3::graph>
|
|
{ };
|
|
|
|
template <>
|
|
struct graph_property_type<oqgraph3::graph>
|
|
{
|
|
typedef no_property type;
|
|
};
|
|
|
|
template <>
|
|
struct vertex_property_type<oqgraph3::graph>
|
|
{
|
|
typedef no_property type;
|
|
};
|
|
|
|
template <>
|
|
struct edge_property_type<oqgraph3::graph>
|
|
{
|
|
typedef no_property type;
|
|
};
|
|
|
|
#if BOOST_VERSION < 106000 && BOOST_VERSION >= 104601
|
|
template <>
|
|
struct graph_bundle_type<oqgraph3::graph>
|
|
{
|
|
typedef no_graph_bundle type;
|
|
};
|
|
|
|
template <>
|
|
struct vertex_bundle_type<oqgraph3::graph>
|
|
{
|
|
typedef no_vertex_bundle type;
|
|
};
|
|
|
|
template <>
|
|
struct edge_bundle_type<oqgraph3::graph>
|
|
{
|
|
typedef no_edge_bundle type;
|
|
};
|
|
#endif
|
|
|
|
template<>
|
|
struct property_map<oqgraph3::graph, edge_weight_t>
|
|
{
|
|
typedef void type;
|
|
typedef oqgraph3::edge_weight_property_map const_type;
|
|
};
|
|
|
|
template<>
|
|
struct property_map<oqgraph3::graph, vertex_index_t>
|
|
{
|
|
typedef void type;
|
|
typedef oqgraph3::vertex_index_property_map const_type;
|
|
};
|
|
|
|
template<>
|
|
struct property_map<oqgraph3::graph, edge_index_t>
|
|
{
|
|
typedef void type;
|
|
typedef oqgraph3::edge_index_property_map const_type;
|
|
};
|
|
|
|
}
|
|
|
|
namespace oqgraph3
|
|
{
|
|
using namespace boost;
|
|
|
|
inline graph_traits<oqgraph3::graph>::vertex_descriptor
|
|
source(
|
|
const graph_traits<oqgraph3::graph>::edge_descriptor& e,
|
|
const oqgraph3::graph&)
|
|
{ return e.origid(); }
|
|
|
|
inline graph_traits<oqgraph3::graph>::vertex_descriptor
|
|
target(
|
|
const graph_traits<oqgraph3::graph>::edge_descriptor& e,
|
|
const oqgraph3::graph&)
|
|
{ return e.destid(); }
|
|
|
|
inline std::pair<
|
|
graph_traits<oqgraph3::graph>::out_edge_iterator,
|
|
graph_traits<oqgraph3::graph>::out_edge_iterator>
|
|
out_edges(
|
|
graph_traits<oqgraph3::graph>::vertex_descriptor v,
|
|
const oqgraph3::graph& g)
|
|
{
|
|
oqgraph3::cursor*
|
|
end= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
|
|
oqgraph3::cursor*
|
|
start= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
|
|
start->seek_to(v, boost::none);
|
|
return std::make_pair(
|
|
graph_traits<oqgraph3::graph>::out_edge_iterator(start),
|
|
graph_traits<oqgraph3::graph>::out_edge_iterator(end));
|
|
}
|
|
|
|
inline graph_traits<oqgraph3::graph>::degree_size_type
|
|
out_degree(
|
|
graph_traits<oqgraph3::graph>::vertex_descriptor v,
|
|
const oqgraph3::graph& g)
|
|
{
|
|
std::size_t count = 0;
|
|
for (std::pair<
|
|
graph_traits<oqgraph3::graph>::out_edge_iterator,
|
|
graph_traits<oqgraph3::graph>::out_edge_iterator> i= out_edges(v, g);
|
|
i.first != i.second; ++i.first)
|
|
{
|
|
++count;
|
|
}
|
|
return count;
|
|
}
|
|
|
|
|
|
inline std::pair<
|
|
graph_traits<oqgraph3::graph>::in_edge_iterator,
|
|
graph_traits<oqgraph3::graph>::in_edge_iterator>
|
|
in_edges(
|
|
graph_traits<oqgraph3::graph>::vertex_descriptor v,
|
|
const oqgraph3::graph& g)
|
|
{
|
|
oqgraph3::cursor*
|
|
end= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
|
|
oqgraph3::cursor*
|
|
start= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
|
|
start->seek_to(boost::none, v);
|
|
return std::make_pair(
|
|
graph_traits<oqgraph3::graph>::in_edge_iterator(start),
|
|
graph_traits<oqgraph3::graph>::in_edge_iterator(end));
|
|
}
|
|
|
|
inline graph_traits<oqgraph3::graph>::degree_size_type
|
|
in_degree(
|
|
graph_traits<oqgraph3::graph>::vertex_descriptor v,
|
|
const oqgraph3::graph& g)
|
|
{
|
|
std::size_t count = 0;
|
|
for (std::pair<
|
|
graph_traits<oqgraph3::graph>::in_edge_iterator,
|
|
graph_traits<oqgraph3::graph>::in_edge_iterator> it= in_edges(v, g);
|
|
it.first != it.second; ++it.first)
|
|
{
|
|
++count;
|
|
}
|
|
return count;
|
|
}
|
|
|
|
|
|
// EdgeListGraph concepts
|
|
inline std::pair<
|
|
graph_traits<oqgraph3::graph>::edge_iterator,
|
|
graph_traits<oqgraph3::graph>::edge_iterator>
|
|
edges(const oqgraph3::graph& g)
|
|
{
|
|
std::size_t end= std::size_t(-1);
|
|
std::size_t start= end;
|
|
|
|
if (g.num_edges())
|
|
start= 0;
|
|
|
|
return std::make_pair(
|
|
graph_traits<oqgraph3::graph>::edge_iterator(
|
|
const_cast<oqgraph3::graph*>(&g), start),
|
|
graph_traits<oqgraph3::graph>::edge_iterator(
|
|
const_cast<oqgraph3::graph*>(&g), end));
|
|
}
|
|
|
|
inline std::pair<
|
|
graph_traits<oqgraph3::graph>::vertex_iterator,
|
|
graph_traits<oqgraph3::graph>::vertex_iterator>
|
|
vertices(const oqgraph3::graph& g)
|
|
{
|
|
oqgraph3::cursor*
|
|
start= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
|
|
start->seek_to(boost::none, boost::none);
|
|
return std::make_pair(
|
|
graph_traits<oqgraph3::graph>::vertex_iterator(start),
|
|
graph_traits<oqgraph3::graph>::vertex_iterator(
|
|
new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g))));
|
|
}
|
|
|
|
inline graph_traits<oqgraph3::graph>::vertices_size_type
|
|
num_vertices(const oqgraph3::graph& g)
|
|
{
|
|
std::size_t count = 0;
|
|
for (std::pair<
|
|
graph_traits<oqgraph3::graph>::vertex_iterator,
|
|
graph_traits<oqgraph3::graph>::vertex_iterator> i= vertices(g);
|
|
i.first != i.second; ++i.first)
|
|
{
|
|
++count;
|
|
}
|
|
return count;
|
|
}
|
|
|
|
inline property_map<
|
|
oqgraph3::graph,
|
|
edge_weight_t>::const_type::reference
|
|
get(
|
|
edge_weight_t,
|
|
const oqgraph3::graph& g,
|
|
const property_map<
|
|
oqgraph3::graph,
|
|
edge_weight_t>::const_type::key_type& key)
|
|
{ return key.weight(); }
|
|
|
|
inline property_map<
|
|
oqgraph3::graph,
|
|
edge_weight_t>::const_type
|
|
get(edge_weight_t,
|
|
const oqgraph3::graph& g)
|
|
{ return property_map<oqgraph3::graph, edge_weight_t>::const_type(g); }
|
|
|
|
inline property_map<
|
|
oqgraph3::graph,
|
|
edge_index_t>::const_type::reference
|
|
get(edge_index_t,
|
|
const oqgraph3::graph&,
|
|
const property_map<
|
|
oqgraph3::graph,
|
|
edge_index_t>::const_type::key_type& key)
|
|
{ return key._cursor; }
|
|
|
|
inline property_map<oqgraph3::graph, edge_index_t>::const_type
|
|
get(edge_index_t, const oqgraph3::graph& g)
|
|
{ return property_map<oqgraph3::graph, edge_index_t>::const_type(g); }
|
|
|
|
inline property_map<oqgraph3::graph, edge_index_t>::const_type::reference
|
|
get(const property_map<oqgraph3::graph, edge_index_t>::const_type&,
|
|
const property_map<oqgraph3::graph,
|
|
edge_index_t>::const_type::key_type& key)
|
|
{ return key._cursor; }
|
|
|
|
inline property_map<oqgraph3::graph, vertex_index_t>::const_type::reference
|
|
get(vertex_index_t, const oqgraph3::graph&,
|
|
const property_map<oqgraph3::graph,
|
|
vertex_index_t>::const_type::key_type& key)
|
|
{ return key; }
|
|
|
|
inline property_map<oqgraph3::graph, vertex_index_t>::const_type
|
|
get(vertex_index_t, const oqgraph3::graph& g)
|
|
{ return property_map<oqgraph3::graph, vertex_index_t>::const_type(g); }
|
|
|
|
inline optional<graph_traits<oqgraph3::graph>::vertex_descriptor>
|
|
find_vertex(oqgraph3::vertex_id id, const oqgraph3::graph& g)
|
|
{
|
|
// Fix for https://bugs.launchpad.net/oqgraph/+bug/1196020 returning vertex even when not in graph
|
|
// Pseudocode for fix:
|
|
// if count(*) from g->TABLE where source=id or target=id > 0 then return id else return null
|
|
oqgraph3::cursor* found_cursor = new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
|
|
bool found = (found_cursor->seek_to(id, boost::none) && found_cursor->seek_to(boost::none, id));
|
|
delete found_cursor;
|
|
if (found) {
|
|
// id is neither a from or a to in a link
|
|
return optional<graph_traits<oqgraph3::graph>::vertex_descriptor>();
|
|
}
|
|
return id;
|
|
}
|
|
|
|
}
|
|
|