[/
 / Copyright (c) 2007 Andrew Sutton
 /
 / Distributed under the Boost Software License, Version 1.0. (See accompanying
 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 /]

[section Predecessor Recorder]

    template <class PredecessorMap, class EventTag>
    class predecessor_recorder;

This is an [EventVisitor] that records the predecessor (or parent) of a vertex in
a predecessor property map. This is particularly useful in graph search algorithms where
recording the predecessors is an efficient way to encode the search tree that was traversed
during the search. The predecessor recorder is typically used with the `on_tree_edge` or
`on_relax_edge events`, and cannot be used with vertex events.

[predecessor_recorder] can be used with graph algorithms by wrapping it with the
algorithm specific adaptor, such as [bfs_visitor] and [dfs_visitor]. Also, this
event visitor can be combined with other event visitors using `std::pair` to form an [EventVisitorList].

Algorithms such as Dijkstra's and breadth-first search will not assign a predecessor
to the source vertex (which is the root of the search tree). Often times it is useful to
initialize the source vertex's predecessor to itself, thereby identifying the root vertex
as the only vertex which is its own parent. When using an algorithm like depth-first search
that creates a forest (multiple search trees), it is useful to intialize the predecessor
of every vertex to itself, so that all the root nodes can be distinguished.

[h4 Model Of]
[EventVisitor]

[h4 Where Defined]
`boost/graph/visitors.hpp`

[h4 Template Parameters]
[table
    [[Parameter] [Description] [Default]]
    [
        [`PredecessorMap`]
        [
            A [WritablePropertyMap] where the key type and value type are  of type
            `vertex_descriptor`.
        ]
    ]
    [
        [`EventTag`]
        [
            A tag used to specify when the recorder should be applied during the graph
            algorithm. `EventTag` must be an edge event.
        ]
    ]
]

[h4 Associated Types]
[table
    [[Type] [Description]]
    [
        [`predecessor_recorder::event_filter`]
        [
            This type will be the same as the template parameter `EventTag`.
        ]
    ]
]

[h4 Member Functions]
[table
    [[Function] [Description]]
    [
        [`predecessor_recorder(PredecessorMap pa)`]
        [Construct a predecessor recorder object with a predecessor property map `pa`.]
    ]
    [
        [
``
template <class Edge, class Graph>
void operator()(Edge e, const Graph& g)
``
        ]
        [
            Given edge `e` as /(u,v)/, this records `u` as the predecessor (parent) of `v`.
        ]
    ]
]

[h4 Non-Member Functions]
[table
    [[Function] [Description]]
    [
        [
``
template <class PredecessorMap, class EventTag>
predecessor_recorder<PredecessorMap, EventTag>
record_predecessors(PredecessorMap pa, EventTag)
``
        ]
        [
            A convenience function for creating [predecessor_recorder] instances.
        ]
    ]
]

[endsect]
