|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r63530 - in trunk: boost/graph libs/graph/doc
From: jewillco_at_[hidden]
Date: 2010-07-02 15:30:54
Author: jewillco
Date: 2010-07-02 15:30:52 EDT (Fri, 02 Jul 2010)
New Revision: 63530
URL: http://svn.boost.org/trac/boost/changeset/63530
Log:
Changed to using const reference for input graphs; added Incidence Graph requirements to documentation; fixes #4386
Text files modified:
trunk/boost/graph/astar_search.hpp | 36 ++++++++++++++++++------------------
trunk/libs/graph/doc/astar_search.html | 26 +++++++++++++++++++-------
2 files changed, 37 insertions(+), 25 deletions(-)
Modified: trunk/boost/graph/astar_search.hpp
==============================================================================
--- trunk/boost/graph/astar_search.hpp (original)
+++ trunk/boost/graph/astar_search.hpp 2010-07-02 15:30:52 EDT (Fri, 02 Jul 2010)
@@ -83,18 +83,18 @@
: bfs_visitor<Visitors>(vis) {}
template <class Edge, class Graph>
- void edge_relaxed(Edge e, Graph& g) {
+ void edge_relaxed(Edge e, const Graph& g) {
invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
}
template <class Edge, class Graph>
- void edge_not_relaxed(Edge e, Graph& g) {
+ void edge_not_relaxed(Edge e, const Graph& g) {
invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
}
private:
template <class Edge, class Graph>
- void tree_edge(Edge e, Graph& g) {}
+ void tree_edge(Edge e, const Graph& g) {}
template <class Edge, class Graph>
- void non_tree_edge(Edge e, Graph& g) {}
+ void non_tree_edge(Edge e, const Graph& g) {}
};
template <class Visitors>
astar_visitor<Visitors>
@@ -130,34 +130,34 @@
template <class Vertex, class Graph>
- void initialize_vertex(Vertex u, Graph& g) {
+ void initialize_vertex(Vertex u, const Graph& g) {
m_vis.initialize_vertex(u, g);
}
template <class Vertex, class Graph>
- void discover_vertex(Vertex u, Graph& g) {
+ void discover_vertex(Vertex u, const Graph& g) {
m_vis.discover_vertex(u, g);
}
template <class Vertex, class Graph>
- void examine_vertex(Vertex u, Graph& g) {
+ void examine_vertex(Vertex u, const Graph& g) {
m_vis.examine_vertex(u, g);
}
template <class Vertex, class Graph>
- void finish_vertex(Vertex u, Graph& g) {
+ void finish_vertex(Vertex u, const Graph& g) {
m_vis.finish_vertex(u, g);
}
template <class Edge, class Graph>
- void examine_edge(Edge e, Graph& g) {
+ void examine_edge(Edge e, const Graph& g) {
if (m_compare(get(m_weight, e), m_zero))
BOOST_THROW_EXCEPTION(negative_edge());
m_vis.examine_edge(e, g);
}
template <class Edge, class Graph>
- void non_tree_edge(Edge, Graph&) {}
+ void non_tree_edge(Edge, const Graph&) {}
template <class Edge, class Graph>
- void tree_edge(Edge e, Graph& g) {
+ void tree_edge(Edge e, const Graph& g) {
m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
m_combine, m_compare);
@@ -172,7 +172,7 @@
template <class Edge, class Graph>
- void gray_target(Edge e, Graph& g) {
+ void gray_target(Edge e, const Graph& g) {
m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
m_combine, m_compare);
@@ -188,7 +188,7 @@
template <class Edge, class Graph>
- void black_target(Edge e, Graph& g) {
+ void black_target(Edge e, const Graph& g) {
m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
m_combine, m_compare);
@@ -234,7 +234,7 @@
typename CostInf, typename CostZero>
inline void
astar_search_no_init
- (VertexListGraph &g,
+ (const VertexListGraph &g,
typename graph_traits<VertexListGraph>::vertex_descriptor s,
AStarHeuristic h, AStarVisitor vis,
PredecessorMap predecessor, CostMap cost,
@@ -271,7 +271,7 @@
typename CostInf, typename CostZero>
inline void
astar_search
- (VertexListGraph &g,
+ (const VertexListGraph &g,
typename graph_traits<VertexListGraph>::vertex_descriptor s,
AStarHeuristic h, AStarVisitor vis,
PredecessorMap predecessor, CostMap cost,
@@ -308,7 +308,7 @@
class IndexMap, class ColorMap, class Params>
inline void
astar_dispatch2
- (VertexListGraph& g,
+ (const VertexListGraph& g,
typename graph_traits<VertexListGraph>::vertex_descriptor s,
AStarHeuristic h, CostMap cost, DistanceMap distance,
WeightMap weight, IndexMap index_map, ColorMap color,
@@ -337,7 +337,7 @@
class IndexMap, class ColorMap, class Params>
inline void
astar_dispatch1
- (VertexListGraph& g,
+ (const VertexListGraph& g,
typename graph_traits<VertexListGraph>::vertex_descriptor s,
AStarHeuristic h, CostMap cost, DistanceMap distance,
WeightMap weight, IndexMap index_map, ColorMap color,
@@ -362,7 +362,7 @@
typename P, typename T, typename R>
void
astar_search
- (VertexListGraph &g,
+ (const VertexListGraph &g,
typename graph_traits<VertexListGraph>::vertex_descriptor s,
AStarHeuristic h, const bgl_named_params<P, T, R>& params)
{
Modified: trunk/libs/graph/doc/astar_search.html
==============================================================================
--- trunk/libs/graph/doc/astar_search.html (original)
+++ trunk/libs/graph/doc/astar_search.html 2010-07-02 15:30:52 EDT (Fri, 02 Jul 2010)
@@ -28,7 +28,7 @@
typename P, typename T, typename R>
void
astar_search
- (VertexListGraph &g,
+ (const VertexListGraph &g,
typename graph_traits<VertexListGraph>::vertex_descriptor s,
<a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params<P, T, R>& params);
@@ -42,7 +42,7 @@
typename CostInf, typename CostZero>
inline void
astar_search
- (VertexListGraph &g,
+ (const VertexListGraph &g,
typename graph_traits<VertexListGraph>::vertex_descriptor s,
AStarHeuristic h, AStarVisitor vis,
PredecessorMap predecessor, CostMap cost,
@@ -61,7 +61,7 @@
typename CostInf, typename CostZero>
inline void
astar_search_no_init
- (IncidenceGraph &g,
+ (const IncidenceGraph &g,
typename graph_traits<IncidenceGraph>::vertex_descriptor s,
AStarHeuristic h, AStarVisitor vis,
PredecessorMap predecessor, CostMap cost,
@@ -117,7 +117,10 @@
neighbors of newly-expanded vertices. Please note that
<tt>astar_search_no_init()</tt> must be used for implicit graphs; the basic
<tt>astar_search()</tt> function requires a graph that models
-VertexListGraph.
+the Vertex List Graph concept. Both
+versions
+also require the graph type to model the <a
+href="IncidenceGraph.html">Incidence Graph</a> concept.
</P>
<P>
@@ -228,12 +231,21 @@
<h3>Parameters</h3>
-IN: <tt>VertexListGraph& g</tt>
+IN: <tt>const VertexListGraph& g</tt>
<blockquote>
- The graph object on which the algorithm will be applied. The type
+ The graph object on which the algorithm will be applied for <tt>astar_search()</tt>. The type
<tt>VertexListGraph</tt> must be a model of the <a
href="VertexListGraph.html">
- Vertex List Graph</a> concept.
+ Vertex List Graph</a> and Incidence Graph
+ concepts.
+</blockquote>
+
+IN: <tt>const IncidenceGraph& g</tt>
+<blockquote>
+ The graph object on which the algorithm will be applied for <tt>astar_search_no_init()</tt>. The type
+ <tt>IncidenceGraph</tt> must be a model of the
+ Incidence Graph
+ concept.
</blockquote>
IN: <tt>vertex_descriptor s</tt>
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk