...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

// named parameter versionstemplate <class Graph, class class P, class T, class R> void maximum_adjacency_search(const Graph& g, const bgl_named_params<P, T, R>& params);// non-named parameter versionstemplate <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);

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.

MAS( |
- - initialize vertex |

`boost/graph/maximum_adjacency_search.hpp`

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. TheIN:WeightMaptype 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)

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:

Default:mas_visitor<null_visitor>

This specifies the vertex that the depth-first 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.VertexIndexMapmust 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 internalvertex_indexproperty. For example,adjacency_listwithVertexList=listSdoes not have an internalvertex_indexproperty.

UTIL: `vertex_assignment_map(AssignmentMap assignments)`

AssignmentMapmust be a model of Read/Write Property Map. The key and value types must be the graph's vertex descriptor type.

Default:Aboost::iterator_property_mapusing astd::vectorofnum_vertices(g)vertex descriptors andvertexIndicesfor the index map.

UTIL: `max_priority_queue(MaxPriorityQueue& pq)`

MaxPriorityQueuemust 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:Aboost::d_ary_heap_indirectusing 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.

IndexInHeapMapmust 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:Aboost::iterator_property_mapusing astd::vectorofnum_vertices(g)size type objects andvertexIndicesfor the index map.

UTIL: `distance_map(DistanceMap wAs)`

This parameter only has an effect when the default max-priority queue is used.

DistanceMapmust 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:Aboost::iterator_property_mapusing astd::vectorofnum_vertices(g)weight type objects andvertexIndicesfor the index map.

void

`bad_graph`

Ifnum_vertices(g)is less than 2

`std::invalid_argument`

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

The time complexity is *O(E + V)*.

- David Matula (1993).
A linear time 2 + epsilon approximation algorightm for edge connectivity

- Cai, Weiqing and Matula, David W. Partitioning by maximum adjacency search of graphs. Partitioning Data Sets: Dimacs Workshop, April 19-21, 1993. Vol 19. Page 55. 1995. Amer Mathematical Society }

is invoked on every vertex of the graph before the start of the graph search.`vis.initialize_vertex(s, g)`is invoked on the source vertex once before processing its out edges.`vis.start_vertex(s, g)`is invoked on every out-edge of each vertex after it is started.`vis.examine_edge(e, 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.`vis.finish_vertex(u, g)`

[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.

Copyright © 2012 | Fernando Vilas |