CLRS-Cpp-Implementations-Chapter-25

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include "chapter-22/vertex_graph/vertex_graph.h"
#include "chapter-25/all_pairs_shortest_paths/all_pairs_shortest_paths_utilities.h"
namespace CLRS
{
  std::vector<std::vector<APSPMatrixElement>>
  floyd_warshall
  (const std::vector<std::vector<APSPMatrixElement>> &w)
  {
    std::size_t n = w.size();
    auto D = w;
    auto d = D;
    APSPMatrixElement temp;
    for(std::size_t k = 0; k != n; ++k)
      {
	d = D;
	for(std::size_t i = 0; i != n; ++i)
	  for(std::size_t j = 0; j != n; ++j)
	    {
	      temp = d[i][k] + d[k][j];
	      if(temp < d[i][j])
		D[i][j] = temp;
	      else if(d[i][j] < temp)
		D[i][j] = d[i][j];
	    }
      }
    return D;
  }
  std::vector<std::vector<bool>>
  transitive_closure
  (const APSPMatrixGraph &g)
  {
    std::size_t n = g.get_vertexes_size();
    std::vector<std::vector<bool>>
      T(n, std::vector<bool>(n));
    for(std::size_t i = 0; i != n; ++i)
      for(std::size_t j = 0; j != n; ++j)
	{
	  if(i == j || g.edge_or_not(i, j))
	    T[i][j] = true;
	  else
	    T[i][j] = false;
	}
    auto t = T;
    for(std::size_t k = 0; k != n; ++k)
      {
	t = T;
	for(std::size_t i = 0; i != n; ++i)
	  for(std::size_t j = 0; j != n; ++j)
	    T[i][j] = t[i][j] || (t[i][k] && t[k][j]);
      }
    return T;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include "chapter-22/vertex_graph/vertex_graph.h"
#include "chapter-25/all_pairs_shortest_paths/all_pairs_shortest_paths_utilities.h"
namespace CLRS
{
  std::vector<std::vector<APSPMatrixElement>>
  extend_shortest_paths
  (const std::vector<std::vector<APSPMatrixElement>> &l,
   const std::vector<std::vector<APSPMatrixElement>> &w)
  {
    std::size_t n = l.size();
    auto lr = l;
    APSPMatrixElement temp;
    for(std::size_t i = 0; i != n; ++i)
      for(std::size_t j = 0; j != n; ++j)
	for(std::size_t k = 0; k != n; ++k)
	  {
	    temp = l[i][k] + w[k][j];
	    if(temp < lr[i][j])
	      lr[i][j] = temp;
	  }
    return lr;
  }
  std::vector<std::vector<APSPMatrixElement>>
  faster_all_pairs_shortest_paths
  (const std::vector<std::vector<APSPMatrixElement>> &w)
  {
    std::size_t n = w.size();
    auto l = w;
    std::size_t m = 1;
    while(m < n - 1)
      {
	l = extend_shortest_paths(l, l);
	m *= 2;
      }
    return l;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include "chapter-22/linked_list_graph/linked_list_graph.h"
#include "chapter-23/minimum_spanning_tree/mst_utilities.h"
#include "chapter-24/single_source_shortest_paths/bellman_ford/bellman_ford.h"
#include "chapter-24/single_source_shortest_paths/dijkstra/dijkstra.h"
namespace CLRS
{
  /*
   * TODO: too many initialization work greatly lower efficience.
   * Needs improvement.
   */
  std::vector<std::vector<int>>
  johnson(const LinkedListGraph<SSSPVertexGraph,
	  SSSPWeightEdgeGraph<SSSPVertexGraph>> &g)
  {
    std::size_t n = g.get_vertexes_size();
    auto vn = SSSPVertexGraph(n);
    auto vs = g.get_vertexes();
    vs.push_back(vn);
    auto es = g.get_edges();
    for(std::size_t i = 0; i != n; ++i)
      {
	es.push_back
	  (SSSPWeightEdgeGraph<
	   SSSPVertexGraph>(n, i, 0));
      }
    auto g1 = LinkedListGraph<
      SSSPVertexGraph,
      SSSPWeightEdgeGraph<SSSPVertexGraph>>(vs, es);
    if(bellman_ford(g1, n) == false)
      std::logic_error
	("the input graph contains negative-weight cycle");
    std::vector<int> vh;
    for(std::size_t i = 0; i != n; ++i)
      vh.push_back(g1.vertex(i).get_dw());
    // create a graph suitable for dijkstra algorithm
    std::vector<DijkstraVertexGraph> dvs;
    std::vector<WeightEdgeGraph<DijkstraVertexGraph>> des;
    for(std::size_t i = 0; i != n; ++i)
      dvs.push_back(DijkstraVertexGraph(i));
    for(const auto &e : g.get_edges())
      des.push_back
	(WeightEdgeGraph<DijkstraVertexGraph>
	 (e.get_first_vertex(),
	  e.get_second_vertex(),
	  e.get_weight() +
	  vh[e.get_first_vertex()] -
	  vh[e.get_second_vertex()]));
    LinkedListGraph<DijkstraVertexGraph,
		    WeightEdgeGraph<DijkstraVertexGraph>> g2(dvs, des);
    std::vector<std::vector<int>> D(n, std::vector<int>(n));
    for(std::size_t i = 0; i != n; ++i)
      {
	dijkstra(g2, i);
	for(std::size_t j = 0; j != n; ++j)
	  D[i][j] = g2.vertex(j).get_dw() + vh[j] - vh[i];
      }
    return D;
  }
}