Xuanyi Fu Blog
0%

Graph Algorithms Code Templates

Posted on Edited on
Symbols count in article: 234

Code Template for Graph Algorithms.

Graph

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

struct Edge{
  int from_;
  int to_;
  int weight_;
};

struct Graph{

  Graph(int nc, int ec)
  :nodeCount_{nc}
  ,edgeCount_{ec}
  {}
  
  int AddEdge(int from, int to, int weight = 0) {
    const auto id = id_++;
    next_[id] = head_[from];
    head_[from] = id;
    edges_[id] = Edge{from, to, weight};
    return id;
  }
  
  int AddUndirectedEdge(int from, int to, int weight = 0) {
    const auto id1 = AddEdge(from, to, weight);
    const auto id2 = AddEdge(to, from, weight);
    return id1;
  }
  
  template<typename Func>
  void ForEachEdgeOfNode(int node, Func func) {
    for(int id = head_[node]; id >= 0; id = next_[id]) {
      func(id, edges_[id]);
    }
  }
  
  void Print() const {
    for(int eid = 0; eid < id_; ++eid) {
      const auto& edge = edges_[eid];
      std::printf("(%d,%d,%d)\n", edge.from_, edge.to_, edge.weight_);
    }
  }
  
  int id_ = 0;
  const int nodeCount_;
  const int edgeCount_;
  std::vector<int> head_ = std::vector<int>(nodeCount_, -1);
  std::vector<int> next_ = std::vector<int>(edgeCount_, -1);
  std::vector<Edge> edges_ = std::vector<Edge>(edgeCount_);
};

DFS

BFS

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
struct BFS{
  
  BFS(Graph& g, int start)
  :g_{g}
  {
    Run(start);
  }
  
  void Run(int start) {
    auto q = std::deque<int>{start};
    visited_[start] = 1;
    while(!q.empty()) {
      auto n = q.front();
      q.pop_front();
      
      g_.ForEachEdgeOfNode(n, [&q, n, this](int eid, Edge e){
        const auto to = e.to_;
        if(!visited_[to]) {
          visited_[to] = 1;
          dist_[to] = dist_[n] + 1;
          q.push_back(to);
        }
      });
    }
  } 
  
  Graph& g_;
  std::vector<int> visited_ = std::vector<int>(g_.head_.size(), 0);
  std::vector<int> dist_ = std::vector<int>(g_.head_.size(), 0);
};

Topological Sort

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
struct TopoSort{
  
  explicit TopoSort(Graph& g)
  :g_{g}
  {
    Run();
  }
  
  void Run() {
    for(int n = 0; n < indegree_.size(); ++n) {
      g_.ForEachEdgeOfNode(n, [this](int eid, Edge e){
        const auto to = e.to_;
        ++indegree_[to];
      });
    }
    
    auto q = std::deque<int>{};
    for(int n = 0; n < indegree_.size(); ++n) {
      if(indegree_[n] == 0) {
        q.push_back(n);
      }
    }
    
    while(!q.empty()) {
      auto n = q.front();
      q.pop_front();
      res_.push_back(n);
      
      g_.ForEachEdgeOfNode(n, [&q, this](int eid, Edge e){
        const auto to = e.to_;
        --indegree_[to];
        if(indegree_[to] == 0) {
          q.push_back(to);
        }
      });
    }
    
    
    failed_ = false;
    for(int n = 0; n < indegree_.size(); ++n) {
      if(indegree_[n] != 0) {
        failed_ = true;
        break;
      }
    }
  }
  
  Graph& g_;
  std::vector<int> indegree_ = std::vector<int>(g_.head_.size(), 0);
  bool failed_ = true;
  std::vector<int> res_{};
};

Single Souce Shortest Path

0-1 BFS

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
struct BFS01{
  
  BFS01(Graph& g, int start)
  :g_{g}
  {
    Run(start);
  }
  
  void Run(int start) {
    auto q = std::deque<int>{start};
    dist_[start] = 0;
    while(!q.empty()) {
      auto n = q.front();
      q.pop_front();      
      visited_[n] = 1;
      
      g_.ForEachEdgeOfNode(n, [&q, n, this](int eid, Edge e){
        const auto to = e.to_;
        if(visited_[to]) {
          return;
        }
        if(const auto newDist = dist_[n] + e.weight_;
          dist_[to] > newDist) {
          dist_[to] = newDist;
          if(e.weight_ != 0) {
            q.push_back(to);
          } else {
            q.push_front(to);
          }
        }
      });
    }
  } 
  
  Graph& g_;
  std::vector<int> visited_ = std::vector<int>(g_.head_.size(), 0);
  std::vector<int> dist_ = std::vector<int>(g_.head_.size(), INT_MAX);
};

SPFA

Dijkstra

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
struct Dijkstra{
  
  struct NodeDist{
    int node_;
    int dist_;
    
    friend bool operator<(NodeDist l, NodeDist r) {
      return r.dist_ < l.dist_;
    }
  };
  
  Dijkstra(Graph& g, int start)
  :g_{g}
  {
    Run(start);
  }
  
  void Run(int start) {
    dist_[start] = 0;
    auto pq = std::priority_queue<NodeDist>{};
    auto visited = std::vector<int>(dist_.size(), 0);
    pq.push(NodeDist{start, 0});
    while(!pq.empty()) {
      auto nd = pq.top();
      pq.pop();

      const auto n = nd.node_;
      const auto d = nd.dist_;
      if(visited[n]) {
        continue;
      }
      visited[n] = 1;
      
      g_.ForEachEdgeOfNode(n, [&pq, n, d, this](int eid, Edge e){
        const auto adj = e.to_;
        if(const auto newDist = d + e.weight_;
           dist_[adj] > newDist) {
          dist_[adj] = newDist;
          pq.push(NodeDist{adj, newDist});
        }
      });
    }
  }
  
  Graph& g_; 
  std::vector<int> dist_ = std::vector<int>(g_.head_.size(), INT_MAX);
};

A*

Minimum Spanning Tree

Bipartite Graph

Test if Bipartite

Unweighted Maximum Matching

Weighted Maximum Matching

Flow Network

Graph with Flow

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
struct FlowNetwork{
  
  struct Edge{
    int from_;
    int to_;
    int cap_;
    int cost_;
  };
  
  explicit FlowNetwork(int nc)
  :nodeCount_(nc + 2)
  {}
  
  void AddDirected(int from, int to, int cap, int cost) {
    const auto id = ++id_;
    next_[id] = head_[from];
    head_[from] = id;
    edge_[id] = Edge{from, to, cap, cost};
  }
  
  void AddFlowEdge(int from, int to, int cap, int cost) {
    AddDirected(from, to, cap, cost);
    AddDirected(to, from, 0, -cost);
  }
        
  int id_ = BEGIN - 1;
  const int source_ = SOURCE;
  const int sink_ = SINK;
  const int nodeCount_;
  const int edgeCount_ = nodeCount_ * nodeCount_;
  std::vector<int> head_ = std::vector<int>(nodeCount_, -1);
  std::vector<int> next_ = std::vector<int>(edgeCount_, -1);
  std::vector<Edge> edge_ = std::vector<Edge>(edgeCount_); 
};

SSP

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
struct SSP{
  
  struct SSPInfo{
    int visited_ = 0;
    int prev_ = -1;
    int dist_ = INT_MIN;
    int incf_ = INT_MAX;
  };
  
  SSP(FlowNetwork& g, int start)
  :g_{g}
  {
    Run(start);
  }
  
  void Clear() {
    info_.assign(g_.head_.size(), SSPInfo{});
  }
  
  void Run(int start) {
    auto q = std::deque<int>{start};
    info_[start] = SSPInfo{.visited_ = 1, .dist_ = 0};
    while(!q.empty()) {
      auto node = q.front();
      q.pop_front();
      info_[node].visited_ = 0;
      const auto nodeInfo = info_[node];
      for(int i = g_.head_[node]; i > 0; i = g_.next_[i]) {
        const auto edge = g_.edge_[i];
        const auto adjNode = edge.to_;
        auto& adjInfo = info_[adjNode];
        if(g_.edge_[i].cap_ == 0
          || adjInfo.dist_ >= nodeInfo.dist_ + edge.cost_) {
          continue;
        }
        
        adjInfo.dist_ = nodeInfo.dist_ + edge.cost_;
        adjInfo.prev_ = i;
        adjInfo.incf_ = std::min(nodeInfo.incf_, edge.cap_);
        
        if(!adjInfo.visited_) {
          adjInfo.visited_ = 1;
          q.push_back(adjNode);
        }
      }
    }
  }
  
  FlowNetwork& g_;
  std::vector<SSPInfo> info_ = std::vector<SSPInfo>(g_.head_.size(), SSPInfo{});
};

EdmondsKarp

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
struct EdmondsKarp{
  
  explicit EdmondsKarp(FlowNetwork& g)
  :g_{g}
  {
    Run();
  }
  
  void Update(SSP& ssp) {
    int node = g_.sink_;
    const auto incf = ssp.info_[node].incf_;
    while(node > 0) {
      const auto prev = ssp.info_[node].prev_;
      g_.edge_[prev].cap_ -= incf;
      g_.edge_[prev ^ 1].cap_ += incf;
      node = g_.edge_[prev ^ 1].to_;
    }
    cost_ += ssp.info_[g_.sink_].dist_ * incf;
  }
  
  void Run() {
    auto ssp = SSP{g_, g_.source_};
    while(ssp.info_[g_.sink_].prev_ != -1) {
      Update(ssp);
      ssp.Clear();
      ssp.Run(g_.source_);
    }
  }
  
  FlowNetwork& g_;
  int cost_ = 0;
};