Graphs#

Refer to Developer Guide: Graphs.

Programming interface#

All types and functions in this section are declared in the oneapi::dal::preview namespace and are available via inclusion of the oneapi/dal/graph/common.hpp header file.

Graph#

The graph concept is represented by the types with the _graph suffix and all of them are reference-counted:

  1. The instance stores pointers to the graph topology and attributes of vertices and edges.

  2. The reference count indicates how many graph objects refer to the same implementation.

  3. The graph increments the reference count for it to be equal to the number of graph objects sharing the same implementation.

  4. The graph decrements the reference count when the graph goes out of the scope. If the reference count is zero, the graph frees its implementation.

The graph types are defined as templated classes:

template <typename VertexValue,
          typename EdgeValue,
          typename GraphValue,
          typename IndexType,
          typename Allocator>
class [graph_name]_graph;

Type name

Description

Supported types

VertexValue

The type of the vertex attribute values

Empty value

EdgeValue

The type of the edge attribute values

std::int32, double, Empty value

GraphValue

The type of the graph attribute value

Empty value

IndexType

The type of the vertex indices

std::int32

Allocator

The type of a graph allocator

C++17 (ISO/IEC 14882:2017) compliant allocator

Empty value tag structure is used to define the absence of a specified attribute of a graph.

struct empty_value#

Graph class contains the default and the move constructor as well as the move assignment operator. The graph is accessed using the service functions.

graph_type method

Description

Default constructor

Constructs an empty graph object

Move constructor

Creates a new graph instance and moves the implementation from another instance into this one

Move assignment

Swaps the implementation of this object and another one

Graph traits#

Graph traits is a data type that defines the data model and a set of types associated with the graph. Graph traits are used by processing and service functionality.

Type graph_traits is specialized for each graph by following the pattern below.

template <typename G>
struct graph_traits {
   using graph_type = ...;
   using allocator_type = ...;
   ...
};

The full list of types defined in graph_traits<G> is in the table below:

Type, graph_traits<G>::

Description

Undirected Adjacency Vector Graph

Directed Adjacency Vector Graph

graph_type

The type of the graph G

undirected_adjacency_vector_graph<VertexValue, EdgeValue, GraphValue, IndexType, Allocator>

directed_adjacency_vector_graph<VertexValue, EdgeValue, GraphValue, IndexType, Allocator>

allocator_type

The type of the allocator of the graph G

Allocator [1]

Allocator [1]

graph_user_value_type

The type of the attribute of the graph G

GraphValue [1]

GraphValue [1]

const_graph_user_value_type

The constant type of the attribute of the graph G

const GraphValue [1]

const GraphValue [1]

vertex_type

The type of the vertices in the graph G

IndexType [1]

IndexType [1]

vertex_iterator

The type of the vertex iterator in the graph G

vertex_type*

vertex_type*

const_vertex_iterator

The constant type of the vertex iterator in the graph G

const vertex_type*

const vertex_type*

vertex_size_type

The type of the vertex indices in the graph G

std::int64_t

std::int64_t

vertex_user_value_type

The type of the vertex attribute of the graph G

VertexValue [1]

VertexValue [1]

edge_type

The type of edges in the graph G

std::int64_t

std::int64_t

edge_iterator

The type of the edge iterator in the graph G

Not available

Not available

const_edge_iterator

The constant type of the edge iterator in the graph G

Not available

Not available

edge_size_type

The type of the edge indices in the graph G

std::int64_t

std::int64_t

edge_user_value_type

The type of edge attribute

EdgeValue [1]

EdgeValue [1]

vertex_edge_size_type

The type of the vertex neighbors indices

std::int64_t

Not available

vertex_outward_edge_size_type

The type of the vertex outward neighbors indices

Not available

std::int64_t

vertex_edge_iterator_type

The type of the vertex neighbors iterator

IndexType* [1]

Not available

const_vertex_edge_iterator_type

The type of the vertex neighbors constant iterator

const IndexType* [1]

Not available

vertex_outward_edge_iterator_type

The type of the vertex outward neighbors iterator

Not available

IndexType* [1]

const_vertex_outward_edge_iterator_type

The type of the vertex outward neighbors constant iterator

Not available

const IndexType* [1]

vertex_edge_range

The type of the range of vertex neighbors

std::pair<IndexType*, IndexType*> [1]

Not available

const_vertex_edge_range

The type of the constant range of vertex neighbors

std::pair<IndexType*, IndexType*> [1]

Not available

vertex_outward_edge_range

The type of the range of vertex outward neighbors

Not available

std::pair<IndexType*, IndexType*> [1]

const_vertex_outward_edge_range

The type of the constant range of vertex outward neighbors

Not available

std::pair<IndexType*, IndexType*> [1]

[1] VertexValue, EdgeValue, GraphValue, IndexType, Allocatortemplate parameters of graph G.

This section describes API of the specified graph types.