Month: July 2013

Chu-Liu/Edmonds’ algorithm in C++ / POJ3164

Directed graph에서 MST를 구하는 알고리즘인 Chu-Liu / Edmonds’ algorithm입니다. POJ 3164(http://poj.org/problem?id=3164)를 푸는데 필요한 핵심 알고리즘이기도 합니다.

http://en.wikipedia.org/wiki/Edmonds’_algorithm 의 설명을 참조하여 만들었습니다.

알고리즘의 procedure은 간단히 설명하자면 다음과 같습니다.

(1) 주어진 graph G(V, E)에서, 어떤 노드 v로 들어오는 edge 중 가장 cost가 작은 edge를 (\pi(v), v)로 하고, 이 edge들로 이루어진 새로운 그래프를 G'(V, E’)라 합니다.

(2) 만약 E’에 cycle이 없다면 만들어진 graph는 SRT(shortest route tree)를 나타내며 이는 G의 MST가 됩니다.

(3) 만약 cycle이 존재한다면, 이 cycle을 하나의 node로 한 새로운 graph G”에 대해서 (1)을 다시 수행합니다. 단, 이 과정에서 edge들의 cost가 바뀌어야 되는 경우가 존재하는데, 이곳에 적기엔 상당히 복잡하고 위키피디아 문서에 자세히 설명이 되어 있습니다.

// Time complexity O(N^2)
// Assumes node 0 is the root node.
// i_map[N][N] : input map,
// SRT_pi[v] : output. (MST에서, 노드 v의 parent.)
// node 0이 MST의 root라고 가정함.
// Accepted : POJ 3164
#define MAX_NODE 100
#define NO_EDGE numeric_limits<double>::infinity()

double edmonds_map[MAX_NODE * 3][MAX_NODE * 3]; // input.
int org_N; // input에서 주어진 노드 수

bool node_isused[MAX_NODE * 3];
int cur_N; // node 수가 늘어나면서 된 노드 수
int SRT_pi[MAX_NODE * 3]; // SRT_pi[v] : pi[v] ; v의 parent. 답이 저장되는 곳.

bool dfs_visited[MAX_NODE * 3];
bool dfs_total_visited[MAX_NODE * 3];
int dfs_history[MAX_NODE * 3];
int dfs_history_size;

bool dfs_pi_findCycle(int node){
	int i;

	if(SRT_pi[node] != -1){
		i = SRT_pi[node];
		assert(edmonds_map[SRT_pi[node]][node] != NO_EDGE);
		assert(node_isused[SRT_pi[node]]);

		if(dfs_visited[i]){
			dfs_history[dfs_history_size++] = i;
			// cycle found!!
			return true;
		}
		else if(!dfs_total_visited[i]){
			dfs_total_visited[i] = true;
			dfs_visited[i] = true;
			dfs_history[dfs_history_size++] = i;
			if(dfs_pi_findCycle(i))
				return true;
			dfs_visited[i] = false;
			dfs_history_size--;
		}
	}
	return false;
}

void calc_SRT_pi()
{
	int i;
	SRT_pi[0] = -1;
	for(i = 1; i < cur_N; i++){
		if(!node_isused[i])
			continue;
		SRT_pi[i] = -1;

		int j;
		for(j = 0; j < cur_N; j++){
			if(!node_isused[j])
				continue;
			if(edmonds_map[j][i] == NO_EDGE)
				continue;
			if(SRT_pi[i] == -1)
				SRT_pi[i] = j;
			else if(edmonds_map[SRT_pi[i]][i] > edmonds_map[j][i])
				SRT_pi[i] = j;
		}
	}
}

void edmonds_algorithm(){
	int i;
	assert(cur_N >= org_N);
	assert(cur_N < org_N * 3);

	calc_SRT_pi();

	bool cycle_found = false;
	for(i = 0; i < cur_N; i++)
		dfs_total_visited[i] = dfs_visited[i] = false;

	for(i = 0; i < cur_N; i++){
		if(!node_isused[i])
			continue;
		else if(dfs_total_visited[i])
			continue;

		dfs_total_visited[i] = dfs_visited[i] = true;
		dfs_history[0] = i;
		dfs_history_size = 1;
		if(dfs_pi_findCycle(i)){
			cycle_found = true;
			break;
		}
		dfs_visited[i] = false;
	}

	if(cycle_found){
		int cycle_start = -1;
		for(i = 0; i < dfs_history_size - 1; i++){
			if(dfs_history[i] == dfs_history[dfs_history_size - 1]){
				cycle_start = i;
				break;
			}
		}
		assert(cycle_start != -1);

		for(i = cycle_start; i < dfs_history_size - 1; i++){
			assert(node_isused[dfs_history[i]]);
			assert(dfs_history[i] != 0);// not root.
			node_isused[dfs_history[i]] = false;
		}
		int new_node = cur_N;

		int j;
		for(j = 0; j < cur_N; j++){
			if(!node_isused[j])
				continue;

			int k;
			for(k = cycle_start; k < dfs_history_size - 1; k++){
				// j -> dfs_history[k] :
				int v = dfs_history[k];
				if(edmonds_map[j][v] != NO_EDGE){
					double cost= edmonds_map[j][v] - edmonds_map[SRT_pi[v]][v];
					if(edmonds_map[j][new_node] == NO_EDGE)
						edmonds_map[j][new_node] = cost;
					else if(edmonds_map[j][new_node] > cost)
						edmonds_map[j][new_node] = cost;
				}
				if(edmonds_map[v][j] != NO_EDGE){
					if(edmonds_map[new_node][j] == NO_EDGE)
						edmonds_map[new_node][j] = edmonds_map[v][j];
					else if(edmonds_map[new_node][j] > edmonds_map[v][j])
						edmonds_map[new_node][j] = edmonds_map[v][j];
				}
			}
		}

		int cycle_nodes[MAX_NODE * 3];
		int SRT_pi_copied[MAX_NODE * 3];
		int cycle_nodes_size =0 ;
		for(j = cycle_start; j < dfs_history_size - 1; j++)
			cycle_nodes[cycle_nodes_size++] = dfs_history[j];
		for(j = 0; j < cur_N; j++)
			SRT_pi_copied[j] = SRT_pi[j];

		node_isused[new_node] = true;
		cur_N++;

		edmonds_algorithm();
		// 이제 SRT_pi[new_node], SRT_pi[v] = new_node인 v에 대해서 처리.

		cur_N--;
		node_isused[new_node] = false;

		// SRT_pi[new_node] -> new_node.
		// SRT_pi[new_node]는 cycle 밖에 있음.
		assert(node_isused[SRT_pi[new_node]]);
		for(j = 0; j < cycle_nodes_size; j++){
			if(edmonds_map[SRT_pi[new_node]][cycle_nodes[j]] - edmonds_map[SRT_pi_copied[cycle_nodes[j]]][cycle_nodes[j]]
					== edmonds_map[SRT_pi[new_node]][new_node]){
				SRT_pi[cycle_nodes[j]] = SRT_pi[new_node];
				break;
			}
		}
		int vv = -1 ;// SRT_pi[vv] == new_node인 vv ; new_node -> vv를 cycle에 있는 node -> vv로 바꾸어야 함.
		for(i = 0; i < cur_N; i++){
			if(!node_isused[i])
				continue;
			if(SRT_pi[i] == new_node){
				vv = i;
				for(j = 0; j < cycle_nodes_size; j++){
					if(edmonds_map[new_node][vv] == edmonds_map[cycle_nodes[j]][vv]){
						SRT_pi[vv] = cycle_nodes[j];
						break;
					}
				}
				assert(SRT_pi[vv] != new_node);
			}
		}
		for(j = 0; j < cycle_nodes_size; j++){
			assert(node_isused[cycle_nodes[j]] == false);
			node_isused[cycle_nodes[j]] = true;
		}
		node_isused[cur_N] = false;
	}
}

void init_edmonds_algorithm(){
	cur_N = org_N = N;
	int i, j;
	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++)
			edmonds_map[i][j] = i_map[i][j];
	for(i = 0; i < 3 * N; i++)
		for(j = 0; j< 3 * N; j++)
			if(!(i < N && j < N))
				edmonds_map[i][j] = NO_EDGE;
	for(i = 0; i < N; i++)
		node_isused[i] = true;
	for(i = N; i < N * 3; i++)
		node_isused[i] = false;
}

http://poj.org/problem?id=3164

그래프 visualization 프로그램 Graphviz

http://www.graphviz.org/

그래프 visualization 프로그램 Graphviz입니다.

데이터를 보기 쉽도록 가시화하는 것을 다루는 정보가시화가 최근 이슈가 되고 있습니다.

Graphviz는 이미 연구된 정보가시화 알고리즘을 이용해서 관계 데이터를 그래프 형태로 보여주는 프로그램이라 하네요.

자세한 정보는 위 홈페이지에서 알아볼 수 있습니다.