1 // ==========================================================================
2 // SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2015, Knut Reinert, FU Berlin
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 // * Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 // * Redistributions in binary form must reproduce the above copyright
13 // notice, this list of conditions and the following disclaimer in the
14 // documentation and/or other materials provided with the distribution.
15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of
16 // its contributors may be used to endorse or promote products derived
17 // from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 // DAMAGE.
30 //
31 // ==========================================================================
32 // Author: Tobias Raussch <rausch@embl.de>
33 // ==========================================================================
34 // Implementation of the Floyd-Warshall algorithm.
35 // ==========================================================================
36
37 #ifndef INCLUDE_SEQAN_GRAPH_ALGORITHMS_FLOYD_WARSHALL_H_
38 #define INCLUDE_SEQAN_GRAPH_ALGORITHMS_FLOYD_WARSHALL_H_
39
40 namespace seqan {
41
42 // ============================================================================
43 // Forwards
44 // ============================================================================
45
46 // ============================================================================
47 // Tags, Classes, Enums
48 // ============================================================================
49
50 // ============================================================================
51 // Metafunctions
52 // ============================================================================
53
54 // ============================================================================
55 // Functions
56 // ============================================================================
57
58 // ----------------------------------------------------------------------------
59 // Function floydWarshallAlgorithm()
60 // ----------------------------------------------------------------------------
61
62 /*!
63 * @fn floydWarshallAlgorithm
64 * @headerfile <seqan/graph_algorithms.h>
65 * @brief Finds shortest paths between all pairs of vertices in a graph.
66 *
67 * @signature void floydWarshallAlgorithm(g, weight, distance, predecessor);
68 *
69 * @param[out] predecessor A matrix with predecessors. Entry (i,j) in this matrix indicates the predecessor of j on
70 * a shortest path from vertex i to vertex j. You can use <tt>_printAllPairsShortestPath(g,
71 * predecessor, i, j)</tt> to print the shortest path from i to j. Types: Matrix
72 * @param[out] distance A matrix with distances.Entry (i,j) in this matrix indicates the distance from vertex i
73 * to vertex j. Types: Matrix
74 * @param[in] weight A weight map. A property map with edge weights. Edge weights may be negative.
75 * @param[in] g A directed graph. Types: Directed Graph
76 *
77 * The graph must be free of negative-weight cycles.
78 *
79 * @section Example
80 *
81 * @include demos/graph_algorithms/floyd_warshall_algorithm.cpp
82 *
83 * @include demos/graph_algorithms/floyd_warshall_algorithm.cpp.stdout
84 *
85 * @see allPairsShortestPath
86 */
87 template <typename TSpec, typename TWeightMap, typename TMatrix, typename TPredecessor>
floydWarshallAlgorithm(TMatrix & distMatrix,TPredecessor & predecessor,Graph<TSpec> const & g,TWeightMap const & weight)88 void floydWarshallAlgorithm(TMatrix & distMatrix,
89 TPredecessor & predecessor,
90 Graph<TSpec> const & g,
91 TWeightMap const & weight)
92 {
93 typedef typename Size<TMatrix>::Type TSize;
94 typedef typename Value<TMatrix>::Type TMatrixVal;
95
96 // Initialize first distance matrix
97 _initializeAllPairs(g,weight,distMatrix,predecessor);
98
99 // Floyd-Warshall
100 TSize len = (TSize) std::sqrt((double) length(distMatrix));
101 TMatrix local = distMatrix;
102 for(TSize k=0;k<len;++k) {
103 for(TSize i=0;i<len;++i) {
104 for(TSize j=0;j<len;++j) {
105 TMatrixVal min1 = getValue(distMatrix, i*len+j);
106 TMatrixVal min2 = getValue(distMatrix, i*len+k) + getValue(distMatrix, k*len + j);
107 if (min2 < min1) {
108 assignValue(local, i*len+j,min2);
109 assignValue(predecessor, i*len+j,getValue(predecessor, k*len+j));
110 } else {
111 assignValue(local, i*len+j,min1);
112 assignValue(predecessor, i*len+j, getValue(predecessor, i*len+j));
113 }
114 }
115 }
116 distMatrix=local;
117 }
118 }
119
120 } // namespace seqan
121
122 #endif // #ifndef INCLUDE_SEQAN_GRAPH_ALGORITHMS_FLOYD_WARSHALL_H_
123