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.

Maximum Adjacency Search

Traverses vertices of an undirected graph, always visiting next the vertex with the most visited neighbors.

Complexity: O(E + V)
Defined in: <boost/graph/maximum_adjacency_search.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/maximum_adjacency_search.hpp>
#include <iostream>
#include <vector>

struct Edge { int weight; };

int main() {
    using namespace boost;
    using Graph = adjacency_list<vecS, vecS, undirectedS, no_property, Edge>;

    Graph g(5);
    add_edge(0, 1, Edge{2}, g);
    add_edge(0, 4, Edge{3}, g);
    add_edge(1, 2, Edge{3}, g);
    add_edge(1, 4, Edge{2}, g);
    add_edge(2, 3, Edge{4}, g);
    add_edge(3, 4, Edge{1}, g);

    // Bundled weight via member pointer — passed through the named parameter.
    maximum_adjacency_search(g,
        boost::weight_map(get(&Edge::weight, g)));

    std::cout << "Maximum adjacency search completed\n";
    std::cout << "Last vertex visited has highest connectivity\n";
}
Maximum adjacency search completed
Last vertex visited has highest connectivity

(1) Positional version

template <class Graph, class WeightMap, class MASVisitor>
void maximum_adjacency_search(
    const Graph& g, WeightMap weights, MASVisitor vis,
    const typename graph_traits<Graph>::vertex_descriptor start);
Direction Parameter Description

IN

const Graph& g

A connected, directed graph. The graph type must be a model of Incidence Graph and Vertex List Graph.

IN

WeightMap weights

The weight or length of each edge in the graph. The WeightMap type must be a model of Readable Property Map and its value type must be Less Than Comparable and summable. The key type of this map needs to be the graph’s edge descriptor type.

IN

MASVisitor vis

A visitor object that is invoked inside the algorithm at the event-points specified by the MAS Visitor concept. The visitor object is passed by value [1].

IN

vertex_descriptor start

This specifies the vertex that the search should originate from. The type is the type of a vertex descriptor for the given graph.

(2) Named parameter version

template <class Graph, class P, class T, class R>
void maximum_adjacency_search(
    const Graph& g,
    const bgl_named_params<P, T, R>& params);
Direction Parameter Description

IN

const Graph& g

A connected, directed graph. The graph type must be a model of Incidence Graph and Vertex List Graph.

IN

params

Named parameters passed via bgl_named_params. The following are accepted:
Direction Named Parameter Description / Default

IN

weight_map(WeightMap weights)

The weight or length of each edge in the graph. The WeightMap type must be a model of Readable Property Map and its value type must be Less Than Comparable and summable. The key type of this map needs to be the graph’s edge descriptor type.
Default: get(edge_weight, g)

IN

visitor(MASVisitor vis)

A visitor object that is invoked inside the algorithm at the event-points specified by the MAS Visitor concept. The visitor object is passed by value [1].
Default: mas_visitor<null_visitor>

IN

root_vertex(typename graph_traits<VertexListGraph>::vertex_descriptor start)

This specifies the vertex that the search should originate from. The type is the type of a vertex descriptor for the given graph.
Default: *vertices(g).first

IN

vertex_index_map(VertexIndexMap vertexIndices)

This maps each vertex to an integer in the range [0, num_vertices(g)). This is only necessary if the default is used for the assignment, index-in-heap, or distance maps. VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The key type must be the graph’s vertex descriptor type.
Default: get(boost::vertex_index, g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.

UTIL

vertex_assignment_map(AssignmentMap assignments)

AssignmentMap must be a model of Read/Write Property Map. The key and value types must be the graph’s vertex descriptor type.
Default: A boost::iterator_property_map using a std::vector of num_vertices(g) vertex descriptors and vertexIndices for the index map.

UTIL

max_priority_queue(MaxPriorityQueue& pq)

MaxPriorityQueue must be a model of Keyed Updatable Queue and a max-Updatable Priority Queue. The value type must be the graph’s vertex descriptor and the key type must be the weight type.
Default: A boost::d_ary_heap_indirect using a default index-in-heap and distance map.

UTIL

index_in_heap_map(IndexInHeapMap indicesInHeap)

This parameter only has an effect when the default max-priority queue is used.
IndexInHeapMap must be a model of Read/Write Property Map. The key type must be the graph’s vertex descriptor type. The value type must be a size type (typename std::vector<vertex_descriptor>::size_type).
Default: A boost::iterator_property_map using a std::vector of num_vertices(g) size type objects and vertexIndices for the index map.

UTIL

distance_map(DistanceMap wAs)

This parameter only has an effect when the default max-priority queue is used.
DistanceMap must be a model of Read/Write Property Map. The key type must be the graph’s vertex descriptor type. The value type must be the weight type (typename boost::property_traits<WeightMap>::value_type).
Default: A boost::iterator_property_map using a std::vector of num_vertices(g) weight type objects and vertexIndices for the index map.

Description

The maximum_adjacency_search() function performs a traversal of the vertices in an undirected graph. The next vertex visited is the vertex that has the most visited neighbors at any time. In the case of an unweighted, undirected graph, the number of visited neighbors of the very last vertex visited in the graph is also the number of edge-disjoint paths between that vertex and the next-to-last vertex visited. These can be retrieved from a visitor, an example of which is in the test harness mas_test.cpp.

The maximum_adjacency_search() function invokes user-defined actions at certain event-points within the algorithm. This provides a mechanism for adapting the generic MAS algorithm to the many situations in which it can be used. In the pseudo-code below, the event points for MAS are the labels on the right. The user-defined actions must be provided in the form of a visitor object, that is, an object whose type meets the requirements for a MAS Visitor.

Pseudo-Code

MAS(G)
  for each vertex u in V
    reach_count[u] := 0
  end for
  // for the starting vertex s
  reach_count[s] := 1
  for each unvisited vertex u in V
    call MAS-VISIT(G, u)
    remove u from the list on unvisited vertices
    for each out edge from u to t
       if t has not yet been visited
         increment reach_count[t]
       end if
    end for each out edge
    call MAS-VISIT(G, u)
  end for each unvisited vertex
 
.
.
initialize vertex u
.
.
.
.
examine vertex u
.
examine edge (u,t)
.
.
.
.
finish vertex u
.

Returns

void

Throws

bad_graph

If num_vertices(g) is less than 2.

std::invalid_argument

If a max-priority queue is given as an argument and it is not empty.

Visitor Event Points

  • vis.initialize_vertex(s, g) is invoked on every vertex of the graph before the start of the graph search.

  • vis.start_vertex(s, g) is invoked on the source vertex once before processing its out edges.

  • vis.examine_edge(e, g) is invoked on every out-edge of each vertex after it is started.

  • vis.finish_vertex(u, g) is invoked on a vertex after all of its out edges have been examined and the reach counts of the unvisited targets have been updated.

Notes

[1] Since the visitor parameter is passed by value, if your visitor contains state then any changes to the state during the algorithm will be made to a copy of the visitor object, not the visitor object passed in. Therefore you may want the visitor to hold this state by pointer or reference.

References

Edit this Page