ceph/src/boost/libs/graph/doc/floyd_warshall_shortest.html

   1 <HTML>
   2 <!--
   3      Copyright (c) 2002 Rensselaer Polytechnic Institute
   4
   5      Distributed under the Boost Software License, Version 1.0.
   6      (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8   -->
   9 <Head>
  10 <Title>Floyd-Warshall All Pairs Shortest Paths</Title>
  11 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  12         ALINK="#ff0000">
  13 <IMG SRC="../../../boost.png"
  14      ALT="C++ Boost" width="277" height="86">
  15
  16 <BR Clear>
  17
  18 <H1><A NAME="sec:floyd-warshall">
  19 <TT>floyd_warshall_all_pairs_shortest_paths</TT>
  20 </H1>
  21
  22 <PRE><em>// Named parameters version</em>
  23 template &lt;class VertexListGraph, class DistanceMatrix,
  24     class P, class T, class R&gt;
  25 bool floyd_warshall_initialized_all_pairs_shortest_paths(
  26     const VertexListGraph&amp; g, DistanceMatrix&amp; d,
  27     const bgl_named_params&lt;P, T, R&gt;&amp; params)
  28
  29 template &lt;class VertexAndEdgeListGraph, class DistanceMatrix,
  30     class P, class T, class R&gt;
  31 bool floyd_warshall_all_pairs_shortest_paths(
  32     const VertexAndEdgeListGraph&amp; g, DistanceMatrix&amp; d,
  33     const bgl_named_params&lt;P, T, R&gt;&amp; params)
  34
  35 <em>// Positional parameter versions</em>
  36 \begin{verbatim}
  37 template &lt;typename VertexListGraph, typename DistanceMatrix,
  38     typename BinaryPredicate, typename BinaryFunction,
  39     typename Infinity, typename Zero&gt;
  40 bool floyd_warshall_initialized_all_pairs_shortest_paths(
  41     const VertexListGraph&amp; g, DistanceMatrix&amp; d,
  42     const BinaryPredicate&amp; compare, const BinaryFunction&amp; combine,
  43     const Infinity&amp; inf, const Zero&amp; zero)
  44
  45 template &lt;typename VertexAndEdgeListGraph, typename DistanceMatrix,
  46     typename WeightMap, typename BinaryPredicate,
  47     typename BinaryFunction, typename Infinity, typename Zero&gt;
  48 bool floyd_warshall_all_pairs_shortest_paths(
  49     const VertexAndEdgeListGraph&amp; g, DistanceMatrix&amp; d,
  50     const WeightMap&amp; w, const BinaryPredicate&amp; compare,
  51     const BinaryFunction&amp; combine,
  52     const Infinity&amp; inf, const Zero&amp; zero)</PRE>
  53
  54 <P>
  55 These algorithms find the shortest distance between every pair of
  56 vertices in the graph.  The algorithms return false if there is a
  57 negative weight cycle in the graph, true otherwise.  The shortest
  58 distance between each pair of vertices is stored in the distance
  59 matrix <code>d</code>.  The difference between the two algorithms is in
  60 whether the distance matrix is assumed to be initialized or not, as
  61 discussed below under the OUT parameter description.
  62
  63 <P>This algorithm should be used to compute shortest paths between
  64 every pair of vertices for dense graphs. For sparse graphs, use <a
  65 href="johnson_all_pairs_shortest.html"><code>johnson_all_pairs_shortest_paths</code></a>.
  66
  67 <H3>Where Defined</H3>
  68
  69 <P>
  70 <a href="../../../boost/graph/floyd_warshall_shortest.hpp"><TT>boost/graph/floyd_warshall_shortest.hpp</TT></a>
  71
  72 <h3>Parameters</h3>
  73 IN: <code>Graph&amp; g</code>
  74 <blockquote>
  75 A directed or undirected graph.  The graph must be a model of <a href="VertexListGraph.html">Vertex List Graph</a> for calls to
  76 <code>floyd_warshall_initialized_all_pairs_shortest_paths</code>, and
  77 <a href="VertexAndEdgeListGraph.html">Vertex And Edge List Graph</a> for calls to
  78 <code>floyd_warshall_all_pairs_shortest_paths</code>.<br>
  79 </blockquote>
  80
  81 OUT: <code>DistanceMatrix&amp; d</code>
  82 <blockquote>
  83 The length of the shortest path between each pair of vertices
  84 <code>u</code>,<code>v</code> are
  85 stored in the matrix at location <code>D[u][v]</code>.  The
  86 DistanceMatrix must be
  87 of type <code>{M, I, V}</code> where <code>I</code> is of type
  88 <code>vertex_descriptor</code> and <code>V</code> is the
  89 type of the <code>weight_map</code>.  The set of types must be a model of
  90 <a href="BasicMatrix.html">BasicMatrix</a>, with the exceptions that
  91 it isn't required to
  92 run in constant time, and it must be mutable.  The matrix must be
  93 properly initialized when it is passed to the function
  94 <code>floyd_warshall_initialized_all_pairs_shortest_paths</code>.  If the
  95 function <code>floyd_warshall_all_pairs_shortest_paths</code> is used then the
  96 matrix will be initialized for the user.
  97 </blockquote>
  98
  99 <h3>Named Parameters</h3>
 100
 101 IN: <code>weight_map(WeightMap w)</code>
 102 <blockquote>
 103 The weight of length of each edge in the graph.  The <code>WeightMap</code>
 104 must be a model of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 105 Map</a>.  The edge descriptor
 106 type of the graph needs to be usable as the key type for the weight
 107 map.  The <code>value_type</code> of the weight map must be the type of the
 108 <code>DistanceMatrix</code>, and must always either be part of the
 109 graph passed to the function, or passed in as a parameter.<br>
 110 <b>Default:</b> <code>get(edge_weight, g)</code>
 111 </blockquote>
 112
 113 IN: <code>distance_compare(CompareFunction cmp)</code>
 114 <blockquote>
 115 The function used to compare distances to determine which target
 116 vertex is closer to the source vertex.  The CompareFunction must be a
 117 model of <code>BinaryPredicate</code>.  The argument types must match the
 118 value type of the <code>WeightMap</code>.<br>
 119
 120 <b>Default:</b> <code>std::less&lt;WM&gt;</code>with <code>WM = typename property_traits&lt;WeightMap&gt;::value_type</code>
 121 </blockquote>
 122
 123 IN: <code>distance_combine(CombineFunction cmb)</code>
 124 <blockquote>
 125 The function used to combine distance to compute the distance of a
 126 path.  The CombineFunction must be a model of <code>BinaryFunction</code>.
 127 The argument types must match the value type of the <code>WeightMap</code>.
 128 The result type must be the same as the distance value type.<br>
 129
 130 <b>Default:</b> <code>boost::closed_plus&lt;WM&gt;</code> with <code>WM = typename property_traits&lt;WeightMap&gt;::value_type</code>
 131 </blockquote>
 132
 133 IN: <code>distance_inf(WM inf)</code>
 134 <blockquote>
 135 The value used to initialize the distance for each vertex before
 136 starting the algorithm, and to represent the distance between vertices
 137 for which there is no path.  Should be larger than any possible valid
 138 path length.  The argument type must match the value type of the <code>
 139 WeightMap</code>.<br>
 140
 141 <b>Default:</b> <code>std::numeric_limits&lt;WM&gt;::max()</code> with <code>WM = typename property_traits&lt;WeightMap&gt;::value_type</code>
 142 </blockquote>
 143
 144 IN: <code>distance_zero(WM zero)</code>
 145 <blockquote>
 146 The value used to represent the distance from a vertex to itself, and
 147 to determine if a value is negative.  The argument type must match the
 148 value type of the <code>WeightMap</code>.<br>
 149 <b>Default:</b> <code>0</code>
 150 </blockquote>
 151
 152 <h3>Complexity</h3>
 153
 154 The time complexity is <i>O(V<sup>3</sup>)</i>.
 155
 156 <br>
 157 <HR>
 158 <TABLE>
 159 <TR valign=top>
 160 <TD nowrap>Copyright &copy; 2002-2004</TD><TD>
 161   Lauren Foutz, Rensselaer Polytechnic Institute</td>
 162   </tr><tr valign="top"><td></td>
 163   <td>Scott Hill, Rensselaer Polytechnic Institute
 164 </TD></TR></TABLE>
 165
 166 </BODY>
 167 </HTML>