[ceph.git] / ceph / src / boost / libs / graph / doc / floyd_warshall_shortest.html

<HTML>
<!--
     Copyright (c) 2002 Rensselaer Polytechnic Institute
    
     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)
  -->
<Head>
<Title>Floyd-Warshall All Pairs Shortest Paths</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
        ALINK="#ff0000"> 
<IMG SRC="../../../boost.png" 
     ALT="C++ Boost" width="277" height="86"> 

<BR Clear>

<H1><A NAME="sec:floyd-warshall">
<TT>floyd_warshall_all_pairs_shortest_paths</TT>
</H1>

<PRE><em>// Named parameters version</em>
template &lt;class VertexListGraph, class DistanceMatrix,
    class P, class T, class R&gt;
bool floyd_warshall_initialized_all_pairs_shortest_paths(
    const VertexListGraph&amp; g, DistanceMatrix&amp; d,
    const bgl_named_params&lt;P, T, R&gt;&amp; params)

template &lt;class VertexAndEdgeListGraph, class DistanceMatrix,
    class P, class T, class R&gt;
bool floyd_warshall_all_pairs_shortest_paths(
    const VertexAndEdgeListGraph&amp; g, DistanceMatrix&amp; d,
    const bgl_named_params&lt;P, T, R&gt;&amp; params)

<em>// Positional parameter versions</em>
\begin{verbatim}
template &lt;typename VertexListGraph, typename DistanceMatrix,
    typename BinaryPredicate, typename BinaryFunction,
    typename Infinity, typename Zero&gt;
bool floyd_warshall_initialized_all_pairs_shortest_paths(
    const VertexListGraph&amp; g, DistanceMatrix&amp; d,
    const BinaryPredicate&amp; compare, const BinaryFunction&amp; combine,
    const Infinity&amp; inf, const Zero&amp; zero)

template &lt;typename VertexAndEdgeListGraph, typename DistanceMatrix,
    typename WeightMap, typename BinaryPredicate,
    typename BinaryFunction, typename Infinity, typename Zero&gt;
bool floyd_warshall_all_pairs_shortest_paths(
    const VertexAndEdgeListGraph&amp; g, DistanceMatrix&amp; d,
    const WeightMap&amp; w, const BinaryPredicate&amp; compare,
    const BinaryFunction&amp; combine,
    const Infinity&amp; inf, const Zero&amp; zero)</PRE>

<P>
These algorithms find the shortest distance between every pair of
vertices in the graph.  The algorithms return false if there is a
negative weight cycle in the graph, true otherwise.  The shortest
distance between each pair of vertices is stored in the distance
matrix <code>d</code>.  The difference between the two algorithms is in
whether the distance matrix is assumed to be initialized or not, as
discussed below under the OUT parameter description.

<P>This algorithm should be used to compute shortest paths between
every pair of vertices for dense graphs. For sparse graphs, use <a
href="johnson_all_pairs_shortest.html"><code>johnson_all_pairs_shortest_paths</code></a>. 

<H3>Where Defined</H3>

<P>
<a href="../../../boost/graph/floyd_warshall_shortest.hpp"><TT>boost/graph/floyd_warshall_shortest.hpp</TT></a>

<h3>Parameters</h3>
IN: <code>Graph&amp; g</code>
<blockquote>
A directed or undirected graph.  The graph must be a model of <a href="VertexListGraph.html">Vertex List Graph</a> for calls to
<code>floyd_warshall_initialized_all_pairs_shortest_paths</code>, and
<a href="VertexAndEdgeListGraph.html">Vertex And Edge List Graph</a> for calls to
<code>floyd_warshall_all_pairs_shortest_paths</code>.<br>
</blockquote>

OUT: <code>DistanceMatrix&amp; d</code>
<blockquote>
The length of the shortest path between each pair of vertices
<code>u</code>,<code>v</code> are  
stored in the matrix at location <code>D[u][v]</code>.  The
DistanceMatrix must be 
of type <code>{M, I, V}</code> where <code>I</code> is of type
<code>vertex_descriptor</code> and <code>V</code> is the
type of the <code>weight_map</code>.  The set of types must be a model of
<a href="BasicMatrix.html">BasicMatrix</a>, with the exceptions that
it isn't required to 
run in constant time, and it must be mutable.  The matrix must be
properly initialized when it is passed to the function
<code>floyd_warshall_initialized_all_pairs_shortest_paths</code>.  If the
function <code>floyd_warshall_all_pairs_shortest_paths</code> is used then the
matrix will be initialized for the user.
</blockquote>

<h3>Named Parameters</h3>

IN: <code>weight_map(WeightMap w)</code>
<blockquote>
The weight of length of each edge in the graph.  The <code>WeightMap</code>
must be a model of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
Map</a>.  The edge descriptor 
type of the graph needs to be usable as the key type for the weight
map.  The <code>value_type</code> of the weight map must be the type of the
<code>DistanceMatrix</code>, and must always either be part of the
graph passed to the function, or passed in as a parameter.<br>
<b>Default:</b> <code>get(edge_weight, g)</code>
</blockquote>

IN: <code>distance_compare(CompareFunction cmp)</code>
<blockquote>
The function used to compare distances to determine which target
vertex is closer to the source vertex.  The CompareFunction must be a
model of <code>BinaryPredicate</code>.  The argument types must match the
value type of the <code>WeightMap</code>.<br>

<b>Default:</b> <code>std::less&lt;WM&gt;</code>with <code>WM = typename property_traits&lt;WeightMap&gt;::value_type</code>
</blockquote>

IN: <code>distance_combine(CombineFunction cmb)</code>
<blockquote>
The function used to combine distance to compute the distance of a
path.  The CombineFunction must be a model of <code>BinaryFunction</code>.
The argument types must match the value type of the <code>WeightMap</code>.
The result type must be the same as the distance value type.<br>

<b>Default:</b> <code>boost::closed_plus&lt;WM&gt;</code> with <code>WM = typename property_traits&lt;WeightMap&gt;::value_type</code>
</blockquote>

IN: <code>distance_inf(WM inf)</code>
<blockquote>
The value used to initialize the distance for each vertex before
starting the algorithm, and to represent the distance between vertices
for which there is no path.  Should be larger than any possible valid
path length.  The argument type must match the value type of the <code>
WeightMap</code>.<br>

<b>Default:</b> <code>std::numeric_limits&lt;WM&gt;::max()</code> with <code>WM = typename property_traits&lt;WeightMap&gt;::value_type</code>
</blockquote>

IN: <code>distance_zero(WM zero)</code>
<blockquote>
The value used to represent the distance from a vertex to itself, and
to determine if a value is negative.  The argument type must match the
value type of the <code>WeightMap</code>.<br>
<b>Default:</b> <code>0</code>
</blockquote>

<h3>Complexity</h3>

The time complexity is <i>O(V<sup>3</sup>)</i>.

<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 2002-2004</TD><TD>
  Lauren Foutz, Rensselaer Polytechnic Institute</td>
  </tr><tr valign="top"><td></td>
  <td>Scott Hill, Rensselaer Polytechnic Institute
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	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 <class VertexListGraph, class DistanceMatrix,
	24	class P, class T, class R>
	25	bool floyd_warshall_initialized_all_pairs_shortest_paths(
	26	const VertexListGraph& g, DistanceMatrix& d,
	27	const bgl_named_params<P, T, R>& params)
	28
	29	template <class VertexAndEdgeListGraph, class DistanceMatrix,
	30	class P, class T, class R>
	31	bool floyd_warshall_all_pairs_shortest_paths(
	32	const VertexAndEdgeListGraph& g, DistanceMatrix& d,
	33	const bgl_named_params<P, T, R>& params)
	34
	35	<em>// Positional parameter versions</em>
	36	\begin{verbatim}
	37	template <typename VertexListGraph, typename DistanceMatrix,
	38	typename BinaryPredicate, typename BinaryFunction,
	39	typename Infinity, typename Zero>
	40	bool floyd_warshall_initialized_all_pairs_shortest_paths(
	41	const VertexListGraph& g, DistanceMatrix& d,
	42	const BinaryPredicate& compare, const BinaryFunction& combine,
	43	const Infinity& inf, const Zero& zero)
	44
	45	template <typename VertexAndEdgeListGraph, typename DistanceMatrix,
	46	typename WeightMap, typename BinaryPredicate,
	47	typename BinaryFunction, typename Infinity, typename Zero>
	48	bool floyd_warshall_all_pairs_shortest_paths(
	49	const VertexAndEdgeListGraph& g, DistanceMatrix& d,
	50	const WeightMap& w, const BinaryPredicate& compare,
	51	const BinaryFunction& combine,
	52	const Infinity& inf, const Zero& 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& 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& 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<WM></code>with <code>WM = typename property_traits<WeightMap>::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<WM></code> with <code>WM = typename property_traits<WeightMap>::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<WM>::max()</code> with <code>WM = typename property_traits<WeightMap>::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 © 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>