1 /** \file
2 * \brief Declaration of several shortest path algorithms.
3 *
4 * \author Mark Ortmann, University of Konstanz
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32 #pragma once
33
34 #include <ogdf/basic/SList.h>
35 #include <ogdf/basic/Graph_d.h>
36 #include <ogdf/basic/GraphAttributes.h>
37 #include <ogdf/basic/NodeArray.h>
38 #include <ogdf/basic/Array.h>
39 #include <ogdf/graphalg/Dijkstra.h>
40
41
42 namespace ogdf {
43
44 //! Computes all-pairs shortest paths in \p G using breadth-first serach (BFS).
45 /**
46 * @ingroup ga-sp
47 *
48 * The cost of each edge are \p edgeCost and the result is stored in \p distance.
49 */
50 template<typename TCost>
bfs_SPAP(const Graph & G,NodeArray<NodeArray<TCost>> & distance,TCost edgeCosts)51 void bfs_SPAP(const Graph& G, NodeArray<NodeArray<TCost>>& distance, TCost edgeCosts) {
52 for (node v : G.nodes) {
53 bfs_SPSS(v, G, distance[v], edgeCosts);
54 }
55 }
56
57
58 //! Computes single-source shortest paths from \p s in \p G using breadth-first search (BFS).
59 /**
60 * @ingroup ga-sp
61 *
62 * The cost of each edge are \p edgeCost and the result is stored in \p distanceArray.
63 */
64 template<typename TCost>
bfs_SPSS(node s,const Graph & G,NodeArray<TCost> & distanceArray,TCost edgeCosts)65 void bfs_SPSS(node s, const Graph& G, NodeArray<TCost> & distanceArray, TCost edgeCosts) {
66 NodeArray<bool> mark(G, false);
67 SListPure<node> bfs;
68 bfs.pushBack(s);
69 // mark s and set distance to itself 0
70 mark[s] = true;
71 distanceArray[s] = TCost(0);
72 while (!bfs.empty()) {
73 node w = bfs.popFrontRet();
74 TCost d = distanceArray[w] + edgeCosts;
75 for(adjEntry adj : w->adjEntries) {
76 node v = adj->twinNode();
77 if (!mark[v]) {
78 mark[v] = true;
79 bfs.pushBack(v);
80 distanceArray[v] = d;
81 }
82 }
83 }
84 }
85
86
87 //! Computes all-pairs shortest paths in \p GA using %Dijkstra's algorithm.
88 /**
89 * @ingroup ga-sp
90 *
91 * The cost of an edge \a e are given by GA.doubleWeight(\a e) and the result is stored in \p shortestPathMatrix.
92 *
93 * @return returns the average edge cost
94 */
95 template<typename TCost>
dijkstra_SPAP(const GraphAttributes & GA,NodeArray<NodeArray<TCost>> & shortestPathMatrix)96 double dijkstra_SPAP(const GraphAttributes& GA, NodeArray<NodeArray<TCost>>& shortestPathMatrix) {
97 const Graph& G = GA.constGraph();
98 EdgeArray<TCost> edgeCosts(G);
99 double avgCosts = 0;
100 for (edge e : G.edges) {
101 edgeCosts[e] = GA.doubleWeight(e);
102 avgCosts += edgeCosts[e];
103 }
104 dijkstra_SPAP(G, shortestPathMatrix, edgeCosts);
105 return avgCosts / G.numberOfEdges();
106 }
107
108
109 //! Computes all-pairs shortest paths in graph \p G using %Dijkstra's algorithm.
110 /**
111 * @ingroup ga-sp
112 *
113 * The cost of an edge are given by \p edgeCosts and the result is stored in \p shortestPathMatrix.
114 */
115 template<typename TCost>
dijkstra_SPAP(const Graph & G,NodeArray<NodeArray<TCost>> & shortestPathMatrix,const EdgeArray<TCost> & edgeCosts)116 void dijkstra_SPAP(
117 const Graph& G,
118 NodeArray<NodeArray<TCost>>& shortestPathMatrix,
119 const EdgeArray<TCost>& edgeCosts)
120 {
121 for (node v : G.nodes) {
122 dijkstra_SPSS(v, G, shortestPathMatrix[v], edgeCosts);
123 }
124 }
125
126
127 //! Computes single-source shortest paths from node \p s in \p G using Disjkstra's algorithm.
128 /**
129 * @ingroup ga-sp
130 *
131 * The cost of an edge are given by \p edgeCosts and the result is stored in \p shortestPathMatrix.
132 * Note this algorithm equals Dijkstra<T>::call, though it does not
133 * compute the predecessors on the path and is not inlined.
134 */
135 template<typename TCost>
dijkstra_SPSS(node s,const Graph & G,NodeArray<TCost> & shortestPathMatrix,const EdgeArray<TCost> & edgeCosts)136 void dijkstra_SPSS(
137 node s,
138 const Graph& G,
139 NodeArray<TCost>& shortestPathMatrix,
140 const EdgeArray<TCost>& edgeCosts)
141 {
142 NodeArray<edge> predecessor;
143 Dijkstra<TCost> sssp;
144 sssp.call(G, edgeCosts, s, predecessor, shortestPathMatrix);
145 }
146
147
148 //! Computes all-pairs shortest paths in graph \p G using Floyd-Warshall's algorithm.
149 /**
150 * @ingroup ga-sp
151 *
152 * Note that the \p shortestPathMatrix has to be initialized and all entries must be positive.
153 * The costs of non-adjacent nodes should be set to std::numeric_limits<TCost>::infinity().
154 */
155 template<typename TCost>
floydWarshall_SPAP(NodeArray<NodeArray<TCost>> & shortestPathMatrix,const Graph & G)156 void floydWarshall_SPAP(NodeArray<NodeArray<TCost>>& shortestPathMatrix, const Graph& G) {
157 for (node u : G.nodes) {
158 for (node v : G.nodes) {
159 for (node w : G.nodes) {
160 Math::updateMin(shortestPathMatrix[v][w], shortestPathMatrix[u][v] + shortestPathMatrix[u][w]);
161 }
162 }
163 }
164 }
165
166 }
167