profile

Computes the profile of a graph, which is the sum of all vertex bandwidths plus one for each vertex.

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

Example

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/profile.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 p = boost::profile(g);
    std::cout << "Profile: " << p << "\n";
}

Profile: 16

(1) Default vertex index overload

template <typename Graph>
typename graph_traits<Graph>::vertices_size_type
profile(const Graph& g)

Direction Parameter Description

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.

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
profile(const Graph& g, VertexIndexMap index_map)

Direction Parameter Description

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_map`	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.

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.

VertexIndexMap index_map

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 profile of a graph is the sum of all the maximum distances between the i-th vertex and any of its neighbors with an index j>i, plus one for each vertex. More precisely, the profile is the sum of all individual vertex bandwidths plus one:

P(G) = sum { B_i(G) + 1 | i=0…|V|-1 }

where B_i(G) is the i-th bandwidth.

Returns

The profile of the graph as a vertices_size_type value.

Edit this Page