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>

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 the MAS Visitor concept.

Overloads

(1) Fully Positional

namespace boost::graph {
template <class Graph, class WeightMap, class MASVisitor, class KeyedUpdatablePriorityQueue>
void maximum_adjacency_search(
    const Graph& g,
    WeightMap weights,
    MASVisitor vis,
    typename graph_traits<Graph>::vertex_descriptor start,
    KeyedUpdatablePriorityQueue pq);
}
Direction Parameter Description

IN

const Graph& g

A connected, undirected 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.

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.

IN

KeyedUpdatablePriorityQueue pq

A max priority queue keyed on the reach counts. It 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. It must be empty when passed in.

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/maximum_adjacency_search.hpp>
#include <boost/graph/detail/d_ary_heap.hpp>
#include <boost/property_map/shared_array_property_map.hpp>
#include <functional>
#include <iostream>
#include <vector>

struct Edge { int weight; };

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, Edge>;
using vertex_descriptor = boost::graph_traits<Graph>::vertex_descriptor;
using weight_type = int;

// records the vertices in the order the search visits them
struct order_recorder : boost::graph::default_mas_visitor {
    std::vector<vertex_descriptor> order;
    void finish_vertex(vertex_descriptor u, const Graph&) { order.push_back(u); }
};

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

    auto weight_map = boost::get(&Edge::weight, g);

    // keyed max priority queue the search runs on: reach counts plus heap positions
    using index_map_type = boost::property_map<Graph, boost::vertex_index_t>::const_type;
    using distances_map_type = boost::shared_array_property_map<weight_type, index_map_type>;
    using index_in_heap_type = std::vector<vertex_descriptor>::size_type;
    using indices_map_type = boost::shared_array_property_map<index_in_heap_type, index_map_type>;
    using max_priority_queue_type = boost::d_ary_heap_indirect<vertex_descriptor, 4, indices_map_type, distances_map_type, std::greater<weight_type>>;

    auto distances_map = boost::make_shared_array_property_map(boost::num_vertices(g), weight_type(0), boost::get(boost::vertex_index, g));
    auto indices_map = boost::make_shared_array_property_map(boost::num_vertices(g), index_in_heap_type(-1), boost::get(boost::vertex_index, g));
    max_priority_queue_type pq(distances_map, indices_map);

    order_recorder visitor;
    vertex_descriptor start = *boost::vertices(g).first;

    // std::ref lets the visitor keep its state across the copy the algorithm makes
    boost::graph::maximum_adjacency_search(g, weight_map, std::ref(visitor), start, pq);

    std::cout << "Visit order:";
    for (vertex_descriptor v : visitor.order) std::cout << ' ' << v;
    std::cout << "\nLast visited vertex (highest connectivity): " << visitor.order.back() << '\n';
}
Visit order: 0 4 1 2 3
Last visited vertex (highest connectivity): 3

(2) Four arguments overload

Building the priority queue is the cumbersome part, so this form defaults it to a max d_ary_heap_indirect keyed on the reach counts.

namespace boost::graph {
template <class Graph, class WeightMap, class MASVisitor>
void maximum_adjacency_search(
  const Graph& g,
  WeightMap weights,
  MASVisitor vis,
  typename graph_traits<Graph>::vertex_descriptor start);
}

Example

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

struct Edge { int weight; };

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, Edge>;
using vertex_descriptor = boost::graph_traits<Graph>::vertex_descriptor;

// records the vertices in the order the search visits them
struct order_recorder : boost::graph::default_mas_visitor {
    std::vector<vertex_descriptor> order;
    void finish_vertex(vertex_descriptor u, const Graph&) { order.push_back(u); }
};

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

    auto weight_map = boost::get(&Edge::weight, g);

    order_recorder visitor;

    // std::ref lets the visitor keep its state across the copy the algorithm makes
    boost::graph::maximum_adjacency_search(g, weight_map, std::ref(visitor), *vertices(g).first);

    std::cout << "Visit order:";
    for (vertex_descriptor v : visitor.order) std::cout << ' ' << v;
    std::cout << "\nLast visited vertex (highest connectivity): " << visitor.order.back() << '\n';
}
Visit order: 0 4 1 2 3
Last visited vertex (highest connectivity): 3

(3) Three arguments overload

The start vertex rarely matters, this form defaults it to *vertices(g).first.

namespace boost::graph {
template <class Graph, class WeightMap, class MASVisitor>
void maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis);
}

(4) Six arguments overload (deprecated)

Deprecated: the assignments map is unused. Use the fully positional or convenience boost::graph::maximum_adjacency_search overloads instead. Removal planned for Boost 1.95.

 
namespace boost {
template <class Graph, class WeightMap, class MASVisitor,
          class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
void maximum_adjacency_search(
    const Graph& g, WeightMap weights, MASVisitor vis,
    typename graph_traits<Graph>::vertex_descriptor start,
    VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq);
}

Identical to the fully positional overload except for the extra VertexAssignmentMap assignments parameter, which is accepted for backward compatibility but never read.

(5) Named parameter version (deprecated)

Deprecated: the named parameter interface is deprecated. Use the fully positional or convenience boost::graph::maximum_adjacency_search overloads instead. Removal planned for Boost 1.95.

 
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, undirected 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.
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.

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

The maximum_adjacency_search() function invokes user-defined actions at four event points during the traversal. You supply these actions through a visitor object whose type models the MAS Visitor concept.

The visitor is taken by value, so the algorithm works on a copy. To keep state, give the visitor ordinary data members and pass it with std::ref. The algorithm then operates on the referenced object and its state survives the call.

These symbols moved to namespace boost::graph. The boost:: aliases are kept for backward compatibility but are deprecated. Removal planned for Boost 1.95.

  • boost::mas_visitor → boost::graph::mas_visitor

  • boost::make_mas_visitor → boost::graph::make_mas_visitor

  • boost::default_mas_visitor → boost::graph::default_mas_visitor

  • boost::MASVisitorConcept → boost::graph::MASVisitorConcept

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 unvisited
    for each out edge from u to t
       if t has not yet been visited
         reach_count[t] += weight(u, t)
       end if
    end for each out edge
    call MAS-VISIT(G, u)
  end for each unvisited vertex
 
.
.
initialize vertex u
.
.
.
.
start vertex u
.
examine edge (u,t)
.
.
.
.
finish vertex u
.

Visitor Concept

The MASVisitor template parameter must be a model of the MAS Visitor concept, which defines the event points at which the algorithm invokes user-defined actions.

Refinement of

Copy Constructible (copying a visitor should be a lightweight operation).

Notation

V

A type that is a model of MAS Visitor.

vis

An object of type V.

G

A type that is a model of Graph.

g

An object of type G.

e

An object of type boost::graph_traits<G>::edge_descriptor.

s,u

An object of type boost::graph_traits<G>::vertex_descriptor.

Valid Expressions

Name Expression Return Type Description

Initialize Vertex

vis.initialize_vertex(s, g)

void

Invoked on every vertex of the graph before the start of the search.

Start Vertex

vis.start_vertex(s, g)

void

Invoked on the source vertex once before processing its out-edges.

Examine Edge

vis.examine_edge(e, g)

void

Invoked on every out-edge of each vertex after it is started.

Finish Vertex

vis.finish_vertex(u, g)

void

Invoked on a vertex after all of its out-edges have been examined and the reach counts of the unvisited targets have been updated.

Minimal Implementation

Two ways to write a visitor.

Inherit from default_mas_visitor and shadow only the relevant handlers. The base supplies a no-op for every other event.

struct my_mas_visitor : boost::graph::default_mas_visitor
{
    template <class Edge, class Graph>
    void examine_edge(Edge e, const Graph& g)
    {
        // logic here
    }
};

Or copy the full struct and fill in each handler. All four must be declared.

struct my_mas_visitor
{
    template <class Vertex, class Graph>
    void initialize_vertex(Vertex u, const Graph& g) {}

    template <class Vertex, class Graph>
    void start_vertex(Vertex u, const Graph& g) {}

    template <class Edge, class Graph>
    void examine_edge(Edge e, const Graph& g) {}

    template <class Vertex, class Graph>
    void finish_vertex(Vertex u, const Graph& g) {}
};

References