This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

wavefront

Functions for computing the wavefront and related metrics of a graph.

Defined in: <boost/graph/wavefront.hpp>

Example

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/wavefront.hpp>

int main() {
    using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
    Graph g{5};
    boost::add_edge(0, 1, g);
    boost::add_edge(1, 2, g);
    boost::add_edge(0, 4, g);
    boost::add_edge(3, 4, g);

    auto mw = boost::max_wavefront(g);
    auto aw = boost::aver_wavefront(g);
    std::cout << "Max wavefront: " << mw << "\n";
    std::cout << "Avg wavefront: " << aw << "\n";
}
Max wavefront: 3
Avg wavefront: 2.2

ith_wavefront

Calculates the wavefront of the i-th vertex.

Complexity: O(|V| * max_out_degree)
Defined in: <boost/graph/wavefront.hpp>

(1) Default vertex index overload

template <typename Graph>
typename graph_traits<Graph>::vertices_size_type
ith_wavefront(
    typename graph_traits<Graph>::vertex_descriptor i,
    const Graph& g)
Direction Parameter Description

IN

vertex_descriptor i

The vertex for which to compute the wavefront.

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph. The default vertex_index property map is used.

(2) Explicit vertex index map overload

template <typename Graph, typename VertexIndexMap>
typename graph_traits<Graph>::vertices_size_type
ith_wavefront(
    typename graph_traits<Graph>::vertex_descriptor i,
    const Graph& g,
    VertexIndexMap index)
Direction Parameter Description

IN

vertex_descriptor i

The vertex for which to compute the wavefront.

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph.

IN

VertexIndexMap index

This maps each vertex to an integer in the range [0, num_vertices(g)). The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Description

The i-th wavefront of a graph counts the number of distinct rows active at vertex i, including vertex i itself. A row v is active at i if index[v] <= index[i] and v has a neighbor w with index[w] >= index[i].

Returns

The wavefront of the i-th vertex as a vertices_size_type value.

max_wavefront

Calculates the maximum wavefront of a graph.

Complexity: O(|V|2 * max_out_degree)
Defined in: <boost/graph/wavefront.hpp>

(1) Default vertex index overload

template <typename Graph>
typename graph_traits<Graph>::vertices_size_type
max_wavefront(const Graph& g)
Direction Parameter Description

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph. The default vertex_index property map is used.

(2) Explicit vertex index map overload

template <typename Graph, typename VertexIndexMap>
typename graph_traits<Graph>::vertices_size_type
max_wavefront(const Graph& g, VertexIndexMap index)
Direction Parameter Description

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph.

IN

VertexIndexMap index

This maps each vertex to an integer in the range [0, num_vertices(g)). The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Description

Computes the maximum wavefront of a graph, which is the maximum over all vertices of the individual wavefront values.

Wmax(G) = max { Wi(G)   | i=0…​|V|-1 }

Returns

The maximum wavefront of the graph as a vertices_size_type value.

aver_wavefront

Calculates the average wavefront of a graph (sum of all wavefronts divided by the number of vertices).

Complexity: O(|V|2 * max_out_degree)
Defined in: <boost/graph/wavefront.hpp>

(1) Default vertex index overload

template <typename Graph>
double aver_wavefront(const Graph& g)
Direction Parameter Description

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph. The default vertex_index property map is used.

(2) Explicit vertex index map overload

template <typename Graph, typename VertexIndexMap>
double aver_wavefront(const Graph& g, VertexIndexMap index)
Direction Parameter Description

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph.

IN

VertexIndexMap index

This maps each vertex to an integer in the range [0, num_vertices(g)). The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Description

Computes the average wavefront of a graph, which is the sum of all individual vertex wavefronts divided by the number of vertices.

Wavg(G) = (sum { Wi(G)   | i=0…​|V|-1 }) / |V|

Returns

The average wavefront as a double value.

rms_wavefront

Calculates the root mean square of all wavefronts.

Complexity: O(|V|2 * max_out_degree)
Defined in: <boost/graph/wavefront.hpp>

(1) Default vertex index overload

template <typename Graph>
double rms_wavefront(const Graph& g)
Direction Parameter Description

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph. The default vertex_index property map is used.

(2) Explicit vertex index map overload

template <typename Graph, typename VertexIndexMap>
double rms_wavefront(const Graph& g, VertexIndexMap index)
Direction Parameter Description

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Vertex List Graph and Incidence Graph.

IN

VertexIndexMap index

This maps each vertex to an integer in the range [0, num_vertices(g)). The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Description

Computes the root mean square wavefront of a graph, which is the square root of the mean of the squared wavefront values across all vertices.

Wrms(G) = sqrt( (sum { Wi(G)2   | i=0…​|V|-1 }) / |V| )

Returns

The root mean square wavefront as a double value.

Edit this Page