CLRS-Cpp-Implementations-Chapter-22

 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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include "chapter-22/edge_graph/edge_graph.h"
#include "chapter-22/vertex_graph/vertex_graph.h"
#include "chapter-22/linked_list_graph/linked_list_graph.h"
namespace CLRS
{
  enum class BFSVertexColor {white, gray, black};
  class BFSVertexGraph: public VertexGraph
  {
  private:
    BFSVertexColor color = BFSVertexColor::white;
    std::size_t p_index = 0;
    bool p_set = false;
    std::size_t d = 0;
    bool d_set = false;
  public:
    BFSVertexGraph(std::size_t i): VertexGraph(i) {}
    BFSVertexColor get_color() const {return color;}
    void set_color(BFSVertexColor c) {color = c;}
    std::size_t get_p() const {return p_index;}
    bool is_p_set() const {return p_set;}
    void set_p_b() {p_set = true;}
    void clear_p_b() {p_set = false;}
    void set_p(std::size_t i) {p_index = i;}
    std::size_t get_d() const {return d;}
    bool is_d_set() const {return d_set;}
    void set_d_b() {d_set = true;}
    void clear_d_b() {d_set = false;}
    void set_d(std::size_t D) {d = D;}
  };
  void bfs_graph
  (LinkedListGraph<BFSVertexGraph,
   EdgeGraph<BFSVertexGraph>> &g,
   std::size_t i)
  {
    // initialize
    for(std::size_t i = 0; i != g.get_vertexes_size(); ++i)
      {
	g.vertex(i).set_color(BFSVertexColor::white);
	g.vertex(i).set_p(0);
	g.vertex(i).clear_p_b();
	g.vertex(i).set_d(0);
	g.vertex(i).clear_d_b();
      }
    g.vertex(i).set_color(BFSVertexColor::gray);
    g.vertex(i).set_d_b();
    std::queue<std::size_t> q;
    q.push(i);
    while(!q.empty())
      {
	std::size_t u = q.front();
	q.pop();
	for(const auto &ev : g.get_adj_vertexes(u))
	  {
	    std::size_t v = g.edgesr()[ev].get_second_vertex();
	    if(g.vertex(v).get_color() ==
	       BFSVertexColor::white)
	      {
		g.vertex(v).set_color
		  (BFSVertexColor::gray);
		g.vertex(v).set_d(g.vertex(u).get_d() + 1);
		g.vertex(v).set_d_b();
		g.vertex(v).set_p(u);
		g.vertex(v).set_p_b();
		q.push(v);
	      }
	  }
	g.vertex(u).set_color(BFSVertexColor::black);
      }
  }

  void BFS_print_path(LinkedListGraph<BFSVertexGraph,
		      EdgeGraph<BFSVertexGraph>> &g,
		      std::size_t s, std::size_t v)
  {
    if(s == v)
      std::cout << s << std::endl;
    else if(!g.vertex(v).is_p_set())
      std::cout << "no path from " << s << " to " << v << std::endl;
    else
      {
	BFS_print_path(g, s, g.vertex(v).get_p());
	std::cout << v << std::endl;
      }
  }
}

 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
61
62
63
64

#include "chapter-22/base_graph/base_graph.h"
namespace CLRS
{
  template <typename T1, typename T2>
  class LinkedListGraph: public BaseGraph<T1, T2>
  {
  protected:
    std::vector<std::vector<std::size_t>> adj;
  public:
    LinkedListGraph(const std::vector<T1> &vs,
		    const std::vector<T2> &es);
    bool edge_or_not(const T2 &e) const override;
    bool edge_or_not(std::size_t i1,
		     std::size_t i2) const override;
    std::vector<std::size_t> get_adj_vertexes(std::size_t i) const
    {return adj[i];}
  };

  template <typename T1, typename T2>
  bool LinkedListGraph<T1, T2>::
  edge_or_not(const T2 &e) const
  {
    std::size_t i =
      e.get_first_vertex();
    std::size_t j =
      e.get_second_vertex();
    for(const auto &ev : adj[i])
      {
	if(BaseGraph<T1, T2>::edges[ev].
	   get_second_vertex() == j)
	  return true;
      }
    return false;
  }

  template <typename T1, typename T2>
  bool LinkedListGraph<T1, T2>::edge_or_not(std::size_t i,
					    std::size_t j) const
  {
    for(const auto &ev : adj[i])
      {
	if(BaseGraph<T1, T2>::edges[ev].
	   get_second_vertex() == j)
	  return true;
      }
    return false;
  }

  template <typename T1, typename T2>
  LinkedListGraph<T1, T2>::LinkedListGraph
  (const std::vector<T1> &vs,
   const std::vector<T2> &es):
    BaseGraph<T1, T2>(vs, es), adj(vs.size())
  {
    for(std::size_t i = 0;
	i != BaseGraph<T1, T2>::edges.size();
	++i)
      {
	adj[BaseGraph<T1, T2>::edges[i]
	    .get_first_vertex()].push_back(i);
      }
  }
}

 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

namespace CLRS
{
  /*
   * T1 should be class VertexGraph or its derivation
   * T2 should be class EdgeGraph or its derivation
   */
  template <typename T1, typename T2>
  class BaseGraph
  {
  protected:
    std::vector<T1> vertexes;
    std::vector<T2> edges;
  public:
    /*
     * when construct,
     * make sure passed-in vs has every
     * graph node stored in an order of index;
     * and es only stores existing graph edges.
     */
    BaseGraph(const std::vector<T1> &vs,
	      const std::vector<T2> &es):
      vertexes(vs), edges(es) {}

    // indexes of the passed in object are inside the range
    virtual bool edge_or_not (const T2 &) const = 0;
    virtual bool edge_or_not(std::size_t i1, std::size_t i2) const = 0;
    // exception if nothing match
    T1 &vertex(std::size_t i)
    {return vertexes[i];}
    T2 &edge(std::size_t i, std::size_t j);
    T2 &edge(std::size_t i) {return edges[i];}
    // return amount of vertexes
    std::size_t get_vertexes_size() const
    {return vertexes.size();}
    std::vector<T2> get_edges() const {return edges;}
    std::vector<T1> get_vertexes() const {return vertexes;}
    std::vector<T2> &edgesr() {return edges;}
  };

  template <typename T1, typename T2>
  T2 & BaseGraph<T1, T2>::edge(std::size_t i, std::size_t j)
  {
    for(auto &e : edges)
      {
	if(e.get_first_vertex() == i &&
	   e.get_second_vertex() == j)
	  return e;
      }
    // exception if nothing match
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

namespace CLRS
{
  // vertex index must start from 0
  class VertexGraph
  {
    // In every occasion a vertex should have a index
    std::size_t index = 0;
  public:
    VertexGraph(std::size_t i): index(i) {}
    std::size_t get_index() const {return index;}
  };
}

 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

#include "chapter-22/base_graph/base_graph.h"
namespace CLRS
{
  template <typename T1, typename T2>
  class MatrixGraph: public BaseGraph<T1, T2>
  {
  protected:
    // square matrix
    std::vector<std::vector<bool>> a;
  public:
    MatrixGraph(const std::vector<T1> &vs,
		const std::vector<T2> &es);
    bool edge_or_not(const T2 &e) const override
    {
      std::size_t i1 = e.get_first_vertex();
      std::size_t i2 = e.get_second_vertex();
      return a[i1][i2];
    }
    bool edge_or_not(std::size_t i1,
		     std::size_t i2) const override
    {return a[i1][i2];}
  };

  template <typename T1, typename T2>
  MatrixGraph<T1, T2>::MatrixGraph
  (const std::vector<T1> &vs,
   const std::vector<T2> &es):
    BaseGraph<T1, T2>(vs, es),
    a(vs.size(), std::vector<bool>(vs.size()))
  {
    auto it = es.cbegin();
    while(it != es.cend())
      {
	std::size_t i1 =
	  (*it).get_first_vertex();
	std::size_t i2 =
	  (*it).get_second_vertex();
	a[i1][i2] = true;
	++it;
      }
  }
}

 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

namespace CLRS
{
  // T should be class VertexGraph or its derivation
  template <typename T>
  struct EdgeGraph
  {
    std::pair<std::size_t, std::size_t> edge;
  public:
    EdgeGraph(const T &v1,
	      const T &v2):
      edge(std::make_pair(v1.get_index(),
			  v2.get_index())) {}
    EdgeGraph(std::size_t i1,
	      std::size_t i2):
      edge(std::make_pair(i1, i2)) {}
    std::size_t get_first_vertex() const
    {return edge.first;}
    std::size_t get_second_vertex() const
    {return edge.second;}
    void set_first_vertex(std::size_t i)
    {edge.first = i;}
    void set_second_vertex(std::size_t i)
    {edge.second = i;}
  };
}

  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
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

#include "chapter-22/edge_graph/edge_graph.h"
#include "chapter-22/vertex_graph/vertex_graph.h"
#include "chapter-22/linked_list_graph/linked_list_graph.h"
namespace CLRS
{
  enum class DFSVertexColor {white, gray, black};
  class DFSVertexGraph: public VertexGraph
  {
  private:
    DFSVertexColor color = DFSVertexColor::white;
    std::size_t p = 0;
    bool p_set = false;
    // visit time
    std::size_t d = 0;
    bool d_set = false;
    // visit completed time
    std::size_t f = 0;
    bool f_set = false;
  public:
    DFSVertexGraph(std::size_t i): VertexGraph(i) {}
    DFSVertexColor get_color() const {return color;}
    void set_color(DFSVertexColor c) {color = c;}
    std::size_t get_p() const {return p;}
    bool is_p_set() const {return p_set;}
    void set_p_flag() {p_set = true;}
    void set_p(std::size_t i) {p = i;}
    std::size_t get_d() const {return d;}
    bool is_d_set() const {return d_set;}
    void set_d_flag() {d_set = true;}
    void set_d(std::size_t D) {d = D;}
    std::size_t get_f() const {return f;}
    bool is_f_set() const {return f_set;}
    void set_f_flag() {f_set = true;}
    void set_f(std::size_t F) {f = F;}
  };

  template <typename T1, typename T2>
  void dfs_visit_graph
  (LinkedListGraph<T1, T2> &g,
   std::size_t u, std::size_t *t)
  {
    *t = *t + 1;
    g.vertex(u).set_d(*t);
    g.vertex(u).set_d_flag();
    g.vertex(u).set_color(DFSVertexColor::gray);
    for(const auto &ev : g.get_adj_vertexes(u))
      {
	std::size_t v = g.edgesr()[ev].get_second_vertex();
	if(g.vertex(v).get_color() ==
	   DFSVertexColor::white)
	  {
	    g.vertex(v).set_p(u);
	    g.vertex(v).set_p_flag();
	    dfs_visit_graph(g, v, t);
	  }
      }
    g.vertex(u).set_color(DFSVertexColor::black);
    *t = *t + 1;
    g.vertex(u).set_f(*t);
    g.vertex(u).set_f_flag();
  }

  template <typename T1, typename T2>
  void dfs_graph
  (LinkedListGraph<T1, T2> &g)
  {
    std::size_t time = 0;
    std::size_t amount = g.get_vertexes_size();
    for(std::size_t index = 0;
	index < amount;
	++index)
      {
	if(g.vertex(index).get_color() ==
	   DFSVertexColor::white)
	  dfs_visit_graph(g, index, &time);
      }
  }

  // TODO: any better way to implement dfs topo sort?
  template <typename T1, typename T2>
  void topo_dfs_visit_graph
  (LinkedListGraph<T1, T2> &g,
   std::size_t u, std::size_t *t,
   std::list<std::size_t> &l)
  {
    *t = *t + 1;
    g.vertex(u).set_d(*t);
    g.vertex(u).set_d_flag();
    g.vertex(u).set_color(DFSVertexColor::gray);
    for(const auto &ev: g.get_adj_vertexes(u))
      {
	std::size_t v = g.edgesr()[ev].get_second_vertex();
	if(g.vertex(v).get_color() ==
	   DFSVertexColor::white)
	  {
	    g.vertex(v).set_p(u);
	    g.vertex(v).set_p_flag();
	    topo_dfs_visit_graph(g, v, t, l);
	  }
      }
    g.vertex(u).set_color(DFSVertexColor::black);
    l.push_front(u);
    *t = *t + 1;
    g.vertex(u).set_f(*t);
    g.vertex(u).set_f_flag();
  }

  template <typename T1, typename T2>
  void topo_dfs_graph
  (LinkedListGraph<T1, T2> &g,
   std::list<std::size_t> &l)
  {
    std::size_t time = 0;
    std::size_t amount = g.get_vertexes_size();
    for(std::size_t index = 0;
	index < amount;
	++index)
      {
	if(g.vertex(index).get_color() ==
	   DFSVertexColor::white)
	  topo_dfs_visit_graph
	    (g, index, &time, l);
      }
  }

  template <typename T1, typename T2>
  std::list<std::size_t> topological_sort_graph
  (LinkedListGraph<T1, T2> &g)
  {
    std::list<std::size_t> l;
    topo_dfs_graph(g, l);
    return l;
  }

  // implement strongly connected components
  template <typename T1, typename T2>
  class SCCLinkedListGraph: public LinkedListGraph<T1, T2>
  {
  public:
    SCCLinkedListGraph(const std::vector<T1> &vs,
		       const std::vector<T2> &es):
      LinkedListGraph<T1, T2>(vs, es) {}
    void tranpose();
  };
  template <typename T1, typename T2>
  void SCCLinkedListGraph<T1, T2>::tranpose()
  {
    for(auto &l: LinkedListGraph<T1, T2>::adj)
      l.clear();
    std::size_t i = 0;
    for(auto &e : BaseGraph<T1, T2>::edges)
      {
	std::size_t i1 = e.get_first_vertex();
	std::size_t i2 = e.get_second_vertex();
	e.set_first_vertex(i2);
	e.set_second_vertex(i1);
	LinkedListGraph<T1, T2>::adj[i2].push_back(i);
	++i;
      }
  }

  template <typename T1, typename T2>
  void scc_dfs_graph
  (SCCLinkedListGraph<T1, T2> &g,
   const std::list<std::size_t> &decr_f)
  {
    std::size_t time = 0;
    for(std::size_t index : decr_f)
      {
	if(g.vertex(index).get_color() ==
	   DFSVertexColor::white)
	  dfs_visit_graph(g, index, &time);
      }
  }

  // return a graph proves scc
  template <typename T1, typename T2>
  SCCLinkedListGraph<T1, T2>
  scc_graph
  (SCCLinkedListGraph<T1, T2> &g)
  {
    auto gt = g;
    gt.tranpose();
    std::list<std::size_t> l;
    topo_dfs_graph(g, l);
    scc_dfs_graph(gt, l);
    return gt;
  }
}