ShortestPathAlgorithms.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/GraphAttributes.h>
#include <ogdf/basic/Graph_d.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/SList.h>
#include <ogdf/graphalg/Dijkstra.h>
 
namespace ogdf {
 
 
template<typename TCost>
void bfs_SPAP(const Graph& G, NodeArray<NodeArray<TCost>>& distance, TCost edgeCosts) {
    for (node v : G.nodes) {
        bfs_SPSS(v, G, distance[v], edgeCosts);
    }
}
 
 
template<typename TCost>
void bfs_SPSS(node s, const Graph& G, NodeArray<TCost>& distanceArray, TCost edgeCosts) {
    NodeArray<bool> mark(G, false);
    SListPure<node> bfs;
    bfs.pushBack(s);
    // mark s and set distance to itself 0
    mark[s] = true;
    distanceArray[s] = TCost(0);
    while (!bfs.empty()) {
        node w = bfs.popFrontRet();
        TCost d = distanceArray[w] + edgeCosts;
        for (adjEntry adj : w->adjEntries) {
            node v = adj->twinNode();
            if (!mark[v]) {
                mark[v] = true;
                bfs.pushBack(v);
                distanceArray[v] = d;
            }
        }
    }
}
 
 
template<typename TCost>
double dijkstra_SPAP(const GraphAttributes& GA, NodeArray<NodeArray<TCost>>& shortestPathMatrix) {
    const Graph& G = GA.constGraph();
    EdgeArray<TCost> edgeCosts(G);
    double avgCosts = 0;
    for (edge e : G.edges) {
        edgeCosts[e] = GA.doubleWeight(e);
        avgCosts += edgeCosts[e];
    }
    dijkstra_SPAP(G, shortestPathMatrix, edgeCosts);
    return avgCosts / G.numberOfEdges();
}
 
 
template<typename TCost>
void dijkstra_SPAP(const Graph& G, NodeArray<NodeArray<TCost>>& shortestPathMatrix,
        const EdgeArray<TCost>& edgeCosts) {
    for (node v : G.nodes) {
        dijkstra_SPSS(v, G, shortestPathMatrix[v], edgeCosts);
    }
}
 
 
template<typename TCost>
void dijkstra_SPSS(node s, const Graph& G, NodeArray<TCost>& shortestPathMatrix,
        const EdgeArray<TCost>& edgeCosts) {
    NodeArray<edge> predecessor;
    Dijkstra<TCost> sssp;
    sssp.call(G, edgeCosts, s, predecessor, shortestPathMatrix);
}
 
 
template<typename TCost>
void floydWarshall_SPAP(NodeArray<NodeArray<TCost>>& shortestPathMatrix, const Graph& G) {
    for (node u : G.nodes) {
        for (node v : G.nodes) {
            for (node w : G.nodes) {
                Math::updateMin(shortestPathMatrix[v][w],
                        shortestPathMatrix[u][v] + shortestPathMatrix[u][w]);
            }
        }
    }
}
 
}