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).

Parameters

db – [inout] The GraphDB instance.
txn – [inout] The transaction.
filter – [inout] The user-defined filter function.
parallel – (Optional) Enable parallelism or not.

Returns

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).

Throws

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

Template Parameters

VertexData – Type of the vertex data.

Parameters

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.

Returns

The corresponding extracted data.

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

The default filter you may use.

Template Parameters: IT – Type of the iterator.
Parameters: it – [inout] An iterator class.
Returns: Always true.

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

Function closure filtering by label.

Template Parameters: IT – Type of the iterator.
Parameters: label – An iterator class.
Returns: The filter function.

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

Function closure filtering by label id.

Template Parameters: IT – Type of the iterator.
Parameters: label_id – An iterator class.
Returns: 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.

Parameters

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.

Parameters: rhs – The right hand side.

Vertex GetStartVertex() const

Get the start vertex of this edge.

Returns: The start vertex.

Vertex GetEndVertex() const

Get the end vertex of this edge.

Returns: The end vertex.

uint16_t GetLabelId() const

Get the label ID.

Returns: The label ID.

uint64_t GetTemporalId() const

Get the Temporal ID.

Returns: The temporal ID.

size_t GetEdgeId() const

Get the edge ID.

Returns: The edge ID.

bool IsForward() const

Get the direction of this edge.

Returns: true : forward; false: backward.

Vertex GetSrcVertex() const

Get the source vertex of this edge.

Returns: The source vertex.

Vertex GetDstVertex() const

Get the destination vertex of this edge.

Returns: 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, size_t capacity = MAX_RESULT_SIZE)

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.

Parameters

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.

Returns: The frontier.

void SetFrontier(size_t root_vid)

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

Parameters: 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.

Parameters: 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.

Parameters: 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.

Parameters

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.

Parameters

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.

Parameters

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.

Parameters: txn – [inout] The transaction.

VertexIterator Cast(const Vertex &vertex)

Casting a Vertex to a VertexIterator.

Parameters: vertex – A Vertex object.
Returns: A VertexIterator corresponding to vertex.

OutEdgeIterator Cast(const Edge &edge)

Casting an Edge to an OutEdgeIterator.

Parameters: edge – An edge object.
Returns: 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.

Parameters: start – The start.

Path(const Path &rhs)

Copy constructor.

Parameters: rhs – The right hand side.

Path(Path &&rhs) = delete

Move constructor.

Parameters: rhs – [inout] The right hand side.

Path &operator=(const Path &rhs)

Assignment operator.

Parameters: rhs – The right hand side.
Returns: A shallow copy of this object.

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

Move assignment operator.

Parameters: rhs – [inout] The right hand side.
Returns: A shallow copy of this object.

size_t Length() const

Get the length of this path.

Returns: 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.

Parameters: 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, size_t capacity = MAX_RESULT_SIZE)

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.

Parameters

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.

Returns: The frontier.

void SetFrontier(size_t root_vid)

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

Parameters: 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.

Parameters: 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.

Parameters: 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.

Parameters

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.

Parameters

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.

Parameters

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.

Parameters: vid – The vid.

Vertex(const Vertex &rhs) = default

Copy constructor.

Parameters: rhs – The right hand side.

size_t GetId() const

Get the Id of this vertex.

Returns: The Id.

Private Members

size_t vid_

Friends

friend class Path

friend class IteratorHelper

friend class PathTraversal