lgraph_traversal

namespace lgraph_api
namespace traversal

Functions

ParallelVector<size_t> FindVertices(GraphDB &db, Transaction &txn, std::function<bool(VertexIterator&)> filter, bool parallel = false)

Retrieve all vertices passing the specified filter. Note that if the transaction is not read-only, parallel will be ignored (i.e. parallelism will not be available).

参数

  • db – [inout] The GraphDB instance.

  • txn – [inout] The transaction.

  • filter – [inout] The user-defined filter function.

  • parallel – (Optional) Enable parallelism or not.

返回

The corresponding list of vertices.

template<typename VertexData>
static ParallelVector<VertexData> ExtractVertexData(GraphDB &db, Transaction &txn, ParallelVector<size_t> &frontier, std::function<void(VertexIterator&, VertexData&)> extract, bool parallel = false)

Extract data from specified vertices. Note that if the transaction is not read-only, parallel will be ignored (i.e. parallelism will not be available).

抛出

std::runtime_error – Raised when a runtime error condition occurs.

模板参数

VertexData – Type of the vertex data.

参数

  • db – [inout] The database.

  • txn – [inout] The transaction.

  • frontier – [inout] The vertices to extract data from.

  • extract – [inout] The user-defined extract function.

  • parallel – (Optional) Enable parallelism or not.

返回

The corresponding extracted data.

template<class IT>
bool DefaultFilter(IT &it)

The default filter you may use.

模板参数

IT – Type of the iterator.

参数

it – [inout] An iterator class.

返回

Always true.

template<class IT>
std::function<bool(IT&)> LabelEquals(const std::string &label)

Function closure filtering by label.

模板参数

IT – Type of the iterator.

参数

label – An iterator class.

返回

The filter function.

template<class IT>
std::function<bool(IT&)> LabelEquals(size_t label_id)

Function closure filtering by label id.

模板参数

IT – Type of the iterator.

参数

label_id – An iterator class.

返回

The filter function.

bool operator==(const Vertex &lhs, const Vertex &rhs)
bool operator!=(const Vertex &lhs, const Vertex &rhs)
bool operator==(const Edge &lhs, const Edge &rhs)
bool operator!=(const Edge &lhs, const Edge &rhs)

Variables

static constexpr size_t MAX_RESULT_SIZE = 1ul << 36
static constexpr size_t TRAVERSAL_PARALLEL = 1ul << 0
static constexpr size_t TRAVERSAL_ALLOW_REVISITS = 1ul << 1
class Edge
#include <lgraph_traversal.h>

Represent an edge.

Public Functions

Edge(size_t start, uint16_t lid, uint64_t tid, size_t end, size_t eid, bool forward)

Constructor

参数

  • start – The start.

  • lid – The lid.

  • tid – The tid.

  • end – The end.

  • eid – The eid.

  • forward – True to forward.

Edge(const Edge &rhs) = default

Copy constructor

参数

rhs – The right hand side.

Vertex GetStartVertex() const

Get the start vertex of this edge.

返回

The start vertex.

Vertex GetEndVertex() const

Get the end vertex of this edge.

返回

The end vertex.

uint16_t GetLabelId() const

Get the label ID.

返回

The label ID.

uint64_t GetTemporalId() const

Get the Temporal ID.

返回

The temporal ID.

size_t GetEdgeId() const

Get the edge ID.

返回

The edge ID.

bool IsForward() const

Get the direction of this edge.

返回

true : forward; false: backward.

Vertex GetSrcVertex() const

Get the source vertex of this edge.

返回

The source vertex.

Vertex GetDstVertex() const

Get the destination vertex of this edge.

返回

The destination vertex.

Private Members

size_t start_
size_t end_
size_t eid_
uint16_t lid_
int64_t tid_
bool forward_

Friends

friend class Path
friend class IteratorHelper
friend class PathTraversal
class FrontierTraversal
#include <lgraph_traversal.h>

FrontierTraversal provides the most common way to traverse graphs. You can start from a single vertex or a set of vertices (known as the initial frontier), and expand them frontier by frontier, each time visiting neighboring vertices of the current frontier and make those matching specified conditions the new frontier. One powerful feature of FrontierTraversal is that the traversal can be performed in parallel, accelerating those deep queries significantly.

Public Functions

FrontierTraversal(GraphDB &db, Transaction &txn, size_t flags = 0)

Construct the FrontierTraversal object. Note that the transaction must be read- only if you want to perform the traversals in parallel (i.e. TRAVERSAL_PARALLEL is specified in flags). Be careful when TRAVERSAL_ALLOW_REVISITS is used, as each vertex may be visited more than once, making the result set huge.

参数

  • db – [inout] The GraphDB instance.

  • txn – [inout] The transaction.

  • flags – (Optional) The options used during traversals.

ParallelVector<size_t> &GetFrontier()

Retrieve the current (i.e. latest) frontier.

返回

The frontier.

void SetFrontier(size_t root_vid)

Set the (initial) frontier to contain a single vertex.

参数

root_vid – The identifer for the starting vertex.

void SetFrontier(ParallelVector<size_t> &root_vids)

Set the (initial) frontier to contain a set of vertices.

参数

root_vids – [inout] The starting vertex identifiers.

void SetFrontier(std::function<bool(VertexIterator&)> root_vertex_filter)

Set the (initial) frontier by using a filter function. Each vertex will be checked against the specified filter.

参数

root_vertex_filter – [inout] The filter function.

void ExpandOutEdges(std::function<bool(OutEdgeIterator&)> out_edge_filter = nullptr, std::function<bool(VertexIterator&)> out_neighbour_filter = nullptr)

Expand the current frontier through outgoing edges using filters. Note that the default value for the two filters (nullptr) means all the expansions of this level should succeed and enables some optimizations.

参数

  • out_edge_filter – [inout] (Optional) The filter for an outgoing edge.

  • out_neighbour_filter – [inout] (Optional) The filter for an destination vertex.

void ExpandInEdges(std::function<bool(InEdgeIterator&)> in_edge_filter = nullptr, std::function<bool(VertexIterator&)> in_neighbour_filter = nullptr)

Expand the current frontier through incoming edges using filters. Note that the default value for the two filters (nullptr) means all the expansions of this level should succeed and enables some optimizations.

参数

  • in_edge_filter – [inout] (Optional) The filter for an incoming edge.

  • in_neighbour_filter – [inout] (Optional) The filter for an source vertex.

void ExpandEdges(std::function<bool(OutEdgeIterator&)> out_edge_filter = nullptr, std::function<bool(InEdgeIterator&)> in_edge_filter = nullptr, std::function<bool(VertexIterator&)> out_neighbour_filter = nullptr, std::function<bool(VertexIterator&)> in_neighbour_filter = nullptr)

Expand the current frontier through both directions using filters. Note that the default value for the two filters (nullptr) means all the expansions of this level should succeed and enables some optimizations.

参数

  • out_edge_filter – [inout] (Optional) The filter for an outgoing edge.

  • in_edge_filter – [inout] (Optional) The filter for an incoming edge.

  • out_neighbour_filter – [inout] (Optional) The filter for an destination vertex.

  • in_neighbour_filter – [inout] (Optional) The filter for an source vertex.

void Reset()

Reset the traversal.

void ResetVisited()

Reset only the visited flags.

Private Members

GraphDB &db_
Transaction &txn_
size_t flags_
size_t num_vertices_
ParallelVector<size_t> curr_frontier_
ParallelVector<size_t> next_frontier_
ParallelBitset visited_
class IteratorHelper
#include <lgraph_traversal.h>

IteratorHelper provides some useful methods, such as casting Vertex/Edge objects to their iterator forms.

Public Functions

explicit IteratorHelper(Transaction &txn)

Constructor

参数

txn – [inout] The transaction.

VertexIterator Cast(const Vertex &vertex)

Casting a Vertex to a VertexIterator.

参数

vertex – A Vertex object.

返回

A VertexIterator corresponding to vertex.

OutEdgeIterator Cast(const Edge &edge)

Casting an Edge to an OutEdgeIterator.

参数

edge – An edge object.

返回

An OutEdgeIterator corresponding to edge.

Private Members

Transaction &txn_
class Path
#include <lgraph_traversal.h>

Represent a path.

Public Functions

explicit Path(const Vertex &start)

Constructor

参数

start – The start.

Path(const Path &rhs)

Copy constructor

参数

rhs – The right hand side.

Path(Path &&rhs) = delete

Move constructor

参数

rhs – [inout] The right hand side.

Path &operator=(const Path &rhs)

Assignment operator

参数

rhs – The right hand side.

返回

A shallow copy of this object.

Path &operator=(Path &&rhs) = delete

Move assignment operator

参数

rhs – [inout] The right hand side.

返回

A shallow copy of this object.

size_t Length() const

Get the length of this path.

返回

The path length.

void Append(const Edge &edge)

Append an edge to the path. Note that the edge’s start vertex should match the current path’s end vertex.

参数

edge – edge to append.

Vertex GetStartVertex() const

Get the start vertex of this path.

Vertex GetEndVertex() const

Get the end vertex of this path.

Edge GetLastEdge() const

Get the last edge of this path.

Edge GetNthEdge(size_t n) const

Get the Nth edge of this path. The available range of N is [0, Length).

Vertex GetNthVertex(size_t n) const

Get the Nth vertex of this path. The available range of N is [0, Length].

Private Members

std::vector<bool> dirs_
std::vector<uint16_t> lids_
std::vector<size_t> ids_
class PathTraversal
#include <lgraph_traversal.h>

PathTraversal behaves similar to FrontierTraversal, except that 1) Each vertex could be revisited multiple times. 2) Each traversed path would be stored, and the filter function has access to the path.

Public Functions

PathTraversal(GraphDB &db, Transaction &txn, size_t flags)

Construct the PathTraversal object. Note that the transaction must be read-only if you want to perform the traversals in parallel (i.e. TRAVERSAL_PARALLEL is specified in flags). Since TRAVERSAL_ALLOW_REVISITS is implied in PathTraversal and storing the Paths also takes a lot of space, the memory consumption could be very large if the filters are not very selective.

参数

  • db – [inout] The GraphDB instance.

  • txn – [inout] The transaction.

  • flags – The options used during traversals.

ParallelVector<Path> &GetFrontier()

Retrieve the current (i.e. latest) frontier.

返回

The frontier.

void SetFrontier(size_t root_vid)

Set the (initial) frontier to contain a single vertex.

参数

root_vid – The identifer for the starting vertex.

void SetFrontier(ParallelVector<size_t> &root_vids)

Set the (initial) frontier to contain a set of vertices.

参数

root_vids – [inout] The starting vertex identifiers.

void SetFrontier(std::function<bool(VertexIterator&)> root_vertex_filter)

Set the (initial) frontier by using a filter function. Each vertex will be checked against the specified filter.

参数

root_vertex_filter – [inout] The filter function.

void ExpandOutEdges(std::function<bool(OutEdgeIterator&, Path&, IteratorHelper&)> out_edge_filter = nullptr, std::function<bool(VertexIterator&, Path&, IteratorHelper&)> out_neighbour_filter = nullptr)

Expand the current frontier through outgoing edges using filters.

参数

  • out_edge_filter – [inout] (Optional) The filter for an outgoing edge.

  • out_neighbour_filter – [inout] (Optional) The filter for an destination vertex.

void ExpandInEdges(std::function<bool(InEdgeIterator&, Path&, IteratorHelper&)> in_edge_filter = nullptr, std::function<bool(VertexIterator&, Path&, IteratorHelper&)> in_neighbour_filter = nullptr)

Expand the current frontier through incoming edges using filters.

参数

  • in_edge_filter – [inout] (Optional) The filter for an incoming edge.

  • in_neighbour_filter – [inout] (Optional) The filter for an source vertex.

void ExpandEdges(std::function<bool(OutEdgeIterator&, Path&, IteratorHelper&)> out_edge_filter = nullptr, std::function<bool(InEdgeIterator&, Path&, IteratorHelper&)> in_edge_filter = nullptr, std::function<bool(VertexIterator&, Path&, IteratorHelper&)> out_neighbour_filter = nullptr, std::function<bool(VertexIterator&, Path&, IteratorHelper&)> in_neighbour_filter = nullptr)

Expand the current frontier through both directions using filters.

参数

  • out_edge_filter – [inout] (Optional) The filter for an outgoing edge.

  • in_edge_filter – [inout] (Optional) The filter for an incoming edge.

  • out_neighbour_filter – [inout] (Optional) The filter for an destination vertex.

  • in_neighbour_filter – [inout] (Optional) The filter for an source vertex.

void Reset()

Reset the traversal.

Private Members

GraphDB &db_
Transaction &txn_
size_t flags_
size_t num_vertices_
ParallelVector<Path> curr_frontier_
ParallelVector<Path> next_frontier_
class Vertex
#include <lgraph_traversal.h>

Represent a vertex.

Public Functions

explicit Vertex(size_t vid)

Constructor

参数

vid – The vid.

Vertex(const Vertex &rhs) = default

Copy constructor

参数

rhs – The right hand side.

size_t GetId() const

Get the Id of this vertex.

返回

The Id.

Private Members

size_t vid_

Friends

friend class Path
friend class IteratorHelper
friend class PathTraversal