グラフ関連のアルゴリズムの俺俺クラスを作ってみた

が、色々網羅する前に力尽き(ry。

• 深さ、幅優先探索
• 強連結成分分解
• ベルマンフォード法

くらいしか書いてない。

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <math.h>
#include <boost/assign.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/foreach.hpp>

template <typename NodeType, typename WeightType>
class Graph {
public:
  typedef std::set<NodeType> Nodes;
  typedef std::map<NodeType, Nodes> Edges;
  typedef std::map<std::pair<NodeType, NodeType>, WeightType> Weights;
  Nodes nodes;
  Edges edges;
  Weights weights;
  Graph<NodeType, WeightType>() {};
  void insert(NodeType src, NodeType dst, WeightType weight) {
	nodes.insert(src); nodes.insert(dst);
	edges[src].insert(dst);
	weights.insert(std::make_pair(std::make_pair(src, dst), weight));
  }
  std::vector<NodeType> bfs(NodeType src) {
	std::vector<NodeType> result;
	result.push_back(src);
	Nodes visited;
	std::queue<NodeType> queue;
	queue.push(src);
	while(!queue.empty()) {
	  int v = queue.front(); queue.pop();
	  visited.insert(v);
	  BOOST_FOREACH(NodeType n, edges[v]) {
		if(visited.find(n) == visited.end()) {
		  queue.push(n); result.push_back(n);
		}
	  }
	}
	return result;
  };

  std::vector<NodeType> dfs(NodeType src, 
							std::vector<NodeType> result = std::vector<NodeType>()) {
	if (find(result.begin(), result.end(), src) == result.end()) {
	  result.push_back(src);
	} else {
	  return result;
	}
	BOOST_FOREACH(NodeType n, edges[src]) { 
	  BOOST_FOREACH(NodeType m, dfs(n, result)) {
		if (find(result.begin(), result.end(), m) == result.end()) result.push_back(m);
	  }
	} 
	return result;
  };

  std::set<Nodes> strongly_connected_components() {
	std::set<Nodes> result;
	Nodes unvisited = nodes;
	std::stack<NodeType> stack;
	while(!unvisited.empty()) {
	  std::vector<NodeType> v = dfs(*(unvisited.begin()));
	  reverse(v.begin(), v.end());
	  BOOST_FOREACH(NodeType n, v) {
		if (unvisited.find(n) != unvisited.end()) stack.push(n);
		unvisited.erase(n);
	  }
	}

	Graph<NodeType, WeightType> reversed_graph;
	reversed_graph.nodes = nodes;
	std::pair<NodeType, Nodes> p;
	BOOST_FOREACH(p, edges) {
	  BOOST_FOREACH(NodeType n, p.second) {
		reversed_graph.edges[n].insert(p.first);
	  }
	}

	std::set<NodeType> tmp;
	while(!stack.empty()) {
	  NodeType n = stack.top(); stack.pop();
	  std::vector<NodeType> v = reversed_graph.dfs(n);
	  Nodes ns;
	  BOOST_FOREACH(NodeType m, v) {
		if (tmp.find(m) == tmp.end()) ns.insert(m); 
		tmp.insert(m);
	  }
	  result.insert(ns);
	  while(!stack.empty()) {
		n = stack.top(); 
		if (tmp.find(n) != tmp.end()) {
		  tmp.insert(n); stack.pop();
		} else {
		  break;
		}
	  }
	}
	return result;
  };

  // ref [http://d.hatena.ne.jp/syou6162/20090625/1245920954]
  std::vector<std::pair<std::vector<NodeType>, WeightType> > bellman_ford(NodeType s){
	std::vector<std::pair<std::vector<NodeType>, WeightType> > result;
	// initialization
	std::map<NodeType, WeightType> d;

	std::map<NodeType, NodeType> pi;
	BOOST_FOREACH(NodeType m, nodes) {
	  d[m] = HUGE_VAL;
	  pi[m] = "\0";
	}
	d[s] = 0.0;
	for (unsigned int i = 0; i < nodes.size() - 1; ++i) {
	  std::pair<std::pair<NodeType, NodeType>, WeightType> p;
	  BOOST_FOREACH(p, weights) {
		NodeType u = p.first.first;
		NodeType v = p.first.second;
		WeightType w = p.second;
		// relax
		if (d[v] > d[u] + w) {
		  d[v] = d[u] + w;
		  pi[v] = u;
		}
	  }
	}

	std::pair<std::pair<NodeType, NodeType>, WeightType> p;
	BOOST_FOREACH(p, weights) {
	  NodeType u = p.first.first;
	  NodeType v = p.first.second;
	  WeightType w = p.second;
	  if (d[v] > d[u] + w) return result;
	}

	BOOST_FOREACH(NodeType n, nodes) {
	  std::vector<NodeType> tmp;
	  std::string v = n;
	  while(v != s) {
		tmp.push_back(v);
		v = pi[v];
	  }
	  reverse(tmp.begin(), tmp.end());
	  tmp.insert(tmp.begin(), s);
	  result.push_back(std::make_pair(tmp, d[n]));
	}
	return result;
  };
};

int main(int argc, char *argv[]) {
  {
	Graph<int, int> g;
	g.insert(16, 13, 0);
	g.insert(16, 15, 0);
	g.insert(15, 13, 0);
	g.insert(15, 14, 0);
	g.insert(14, 16, 0);
	g.insert(13, 12, 0);
	g.insert(13, 11, 0);
	g.insert(12, 9, 0);
	g.insert(12, 11, 0);
	g.insert(11, 10, 0);
	g.insert(11, 9, 0);
	g.insert(11, 8, 0);
	g.insert(9, 6, 0);
	g.insert(9, 8, 0);
	g.insert(8, 9, 0);
	g.insert(8, 7, 0);
	g.insert(8, 5, 0);
	g.insert(6, 5, 0);
	g.insert(5, 4, 0);
	g.insert(5, 3, 0);
	g.insert(5, 1, 0);
	g.insert(4, 9, 0);
	g.insert(3, 2, 0);

	std::cout << "幅優先探索1..." << std::endl;
	BOOST_FOREACH(int v, g.bfs(1)) {
	  std::cout << v << std::endl;
	}

	std::cout << "幅優先探索2..." << std::endl;
	BOOST_FOREACH(int v, g.bfs(13)) {
	  std::cout << v << std::endl;
	}

	std::cout << "深さ優先探索1..." << std::endl;
	BOOST_FOREACH(int v, g.dfs(1)) {
	  std::cout << v << std::endl;
	}

	std::cout << "深さ優先探索2..." << std::endl;
	BOOST_FOREACH(int v, g.dfs(13)) {
	  std::cout << v << std::endl;
	}

	std::cout << "強連結成分分解..." << std::endl;
	Graph<int, int>::Nodes ns;
	std::cout << "[";
	BOOST_FOREACH(ns, g.strongly_connected_components()) {
	  std::cout << "[";
	  BOOST_FOREACH(int v, ns) {
		std::cout << v << ",";
	  }
	  std::cout << "], ";
	}
	std::cout << "]" << std::endl;  
  }

  {
	Graph<std::string, double> g;
	g.insert("a", "b", 6.0);
	g.insert("a", "c", 7.0);
	g.insert("b", "d", 5);
	g.insert("b", "e", -4.0);
	g.insert("b", "c", 8.0);
	g.insert("c", "d", -3.0);
	g.insert("c", "e", 9.0);
	g.insert("d", "b", -2);
	g.insert("e", "d", 7.0);
	g.insert("e", "a", 2.0);
	std::cout << "ベルマンフォード法..." << std::endl;
	std::pair<std::vector<std::string>, double> p;
	BOOST_FOREACH(p, g.bellman_ford("a")) {
	  unsigned int i = 0;
	  BOOST_FOREACH(std::string m, p.first) {
		if (i < p.first.size() - 1) {
		  std::cout << m << " -> ";
		} else {
		  std::cout << m;
		}
		i++;
	  }
	  std::cout << " (" << p.second << ")" << std::endl;
	}
  }
  
};