자바에서 JGraphT 를 써서 Christofides의 알고리즘 구현하기 (2)

2018/05/26 - [노트정리/그래프 이론 graph theory] - 자바에서 JGraphT 를 써서 Christofides의 알고리즘 구현하기 (1)

앞서 글에서 크리스토피드 알고리즘이 동작하는 순서를 살펴보았습니다.

지금 당장 최단 순회 경로를 찾는 알고리즘을 자바로 만들어야겠는데, 구현 시간을 줄이기 위해서 어떻게 해야할까 하다 아래처럼 자바 그래프 라이브러리를 써서 구현해보았습니다.

다시 앞서 글의 내용을 돌아보면서 모든 도시로 만든 완전 그래프 G가 주어졌을 때, 알고리즘 동작을 순서대로 다시 써보면,

1. G의 최소 신장 트리 (minimum spanning tree) T를 구한다.

2-1. T에서 차수(degree)가 홀수인 노드 O를 구한다.

2-2. G로부터 O만을 이용해 부분그래프(subgraph)를 구한다.

3. 부분그래프에서 최소 가중치 완전 부합(minimum-weight perfect matching) M을 구한다.

4. T와 M의 합집합으로 된 다중 그래프(multi graph)를 구한다.

5. 다중 그래프의 한붓 그리기(Euler tour)를 구한다.

6. 한붓 그리기의 해밀턴 경로(Hamiltonian path)를 지름길을 써가며 구한다.

입니다.

1. 1에서 최소 신장 트리를 구할 때, 완벽한 답을 내는 알고리즘이 Kruskal의 알고리즘과 Prim의 알고리즘이 있는데요. 계산량이 조금이라도 작은 Kruskal 알고리즘이 JGraphT에 구현되어 있습니다(전체 노드 개수 N과 엣지 개수 E에 대해 E log N). 그래서 이를 이용해 구현해보면,

	private static SimpleWeightedGraph<Integer,DefaultWeightedEdge> getMinimumSpanningTree(SimpleWeightedGraph<Integer, DefaultWeightedEdge> G) {
		SimpleWeightedGraph<Integer, DefaultWeightedEdge> minimum_spanning_tree = new SimpleWeightedGraph<Integer, DefaultWeightedEdge>(DefaultWeightedEdge.class);
		
		for (Iterator<Integer> i = G.vertexSet().iterator(); i.hasNext(); )
			minimum_spanning_tree.addVertex(i.next());
		
		KruskalMinimumSpanningTree<Integer, DefaultWeightedEdge> kruskal = new KruskalMinimumSpanningTree<Integer, DefaultWeightedEdge>(G);
		for (Iterator<DefaultWeightedEdge> i = kruskal.getSpanningTree().iterator(); i.hasNext(); ) {
			DefaultWeightedEdge e = i.next();
			int v1 = G.getEdgeSource(e);
			int v2 = G.getEdgeTarget(e);
			double w = G.getEdgeWeight(e);
			
			minimum_spanning_tree.addEdge(v1, v2);
			DefaultWeightedEdge temp_e = minimum_spanning_tree.getEdge(v1, v2);
			minimum_spanning_tree.setEdgeWeight(temp_e, w);
		}
		
		return minimum_spanning_tree;
	}

2-1. 다음으로 2에서 차수가 홀수인 노드는 모든 노드를 순서대로 돌며 구합니다.

	private static HashSet<Integer> getOddDegreeVertices(
			SimpleWeightedGraph<Integer, DefaultWeightedEdge> minimum_spanning_tree) {

		HashSet<Integer> odd_degree_set = new HashSet<Integer>();
		
		for (Iterator<Integer> i = minimum_spanning_tree.vertexSet().iterator(); i.hasNext(); ) {
			int v = i.next();
			if (minimum_spanning_tree.degreeOf(v)%2 != 0)
				odd_degree_set.add(v);
		}
		
		return odd_degree_set;
	}

2-2. 2-1에서 구한 홀수 차수 노드 집합으로부터 부분그래프를 구합니다.

AsSubgraph<Integer,DefaultWeightedEdge> subgraph_G = new AsSubgraph(G, odd_degree_set, G.edgeSet());

3. 부분그래프에서 최소 가중치 완전 부합(minimum-weight perfect matching) M을 구할 때 엣지 가중치 오름차순으로 먼저 정렬합니다. TreeMap에 짚어넣기 때문에 시간 복잡도는 전체 노드 개수 N에 대해 N log N 입니다. 그리고 정렬된 엣지를 살펴가며 완전 부합을 구합니다. 이 때 앞서 부분그래프는 노드가 항상 짝수개이므로 항상 완전 부합이 찾아집니다.

	private static SimpleWeightedGraph<Integer,DefaultWeightedEdge> getMinimumWeightedPerfectMatching(AsSubgraph<Integer, DefaultWeightedEdge> subgraph_G) {
		SimpleWeightedGraph<Integer,DefaultWeightedEdge> min_weight_perfect_matching = new SimpleWeightedGraph<Integer,DefaultWeightedEdge>(DefaultWeightedEdge.class);
		TreeMap<Double, ArrayList<DefaultWeightedEdge>> edge_map = new TreeMap<Double,ArrayList<DefaultWeightedEdge>>();
		
		// Sort Edges by Weight
		for (Iterator<DefaultWeightedEdge> i = subgraph_G.edgeSet().iterator(); i.hasNext(); ) {
			DefaultWeightedEdge e = i.next();
			double w = subgraph_G.getEdgeWeight(e);
			ArrayList<DefaultWeightedEdge> temp_e_list = null;
			
			if (edge_map.containsKey(w)) 
				temp_e_list = edge_map.get(w);
			else
				temp_e_list = new ArrayList<DefaultWeightedEdge>();
			temp_e_list.add(e);
			
			edge_map.put(w, temp_e_list);
		}
		
		// Get Minimum Weight Perfect Matching
		for (Iterator<Double> i = edge_map.keySet().iterator(); i.hasNext(); ) {
			double w = i.next();
			ArrayList<DefaultWeightedEdge> e_list = edge_map.get(w);
			
			for (DefaultWeightedEdge e : e_list) {
				int v1 = subgraph_G.getEdgeSource(e);
				int v2 = subgraph_G.getEdgeTarget(e);
				
				if (min_weight_perfect_matching.containsVertex(v1) || 
						min_weight_perfect_matching.containsVertex(v2))
					continue;
				else {
					min_weight_perfect_matching.addVertex(v1);
					min_weight_perfect_matching.addVertex(v2);
					min_weight_perfect_matching.addEdge(v1, v2);
					DefaultWeightedEdge temp_e = min_weight_perfect_matching.getEdge(v1, v2);
					min_weight_perfect_matching.setEdgeWeight(temp_e, w);
				}
			}
			
			if (min_weight_perfect_matching.vertexSet().size() == 
					subgraph_G.vertexSet().size()) break;
		}
		
		return min_weight_perfect_matching;
	}

4. 최소신장트리와 완전부합의 합집합으로 다중 그래프를 구합니다. 구현은 단순하게 트리와 완전부합을 입력 받아 모든 노드와 엣지를 새롭게 생성한 다중 그래프에 삽입하면 됩니다.

	private static WeightedMultigraph<Integer,DefaultWeightedEdge> getMultiGraph(
			SimpleWeightedGraph<Integer,DefaultWeightedEdge> minimum_spanning_tree, 
			SimpleWeightedGraph<Integer,DefaultWeightedEdge> min_weight_perfect_matching) {
		
		WeightedMultigraph<Integer,DefaultWeightedEdge> multi_graph =
				new WeightedMultigraph<Integer,DefaultWeightedEdge>(DefaultWeightedEdge.class);
		
		// Add Vertex
		for (Iterator<Integer> i = minimum_spanning_tree.vertexSet().iterator(); i.hasNext(); )
			multi_graph.addVertex(i.next());
		for (Iterator<Integer> i = min_weight_perfect_matching.vertexSet().iterator(); i.hasNext(); ) {
			int v = i.next();
			if (!multi_graph.containsVertex(v))
				multi_graph.addVertex(v);
		}
		
		// Add Edge
		for (Iterator<DefaultWeightedEdge> i = minimum_spanning_tree.edgeSet().iterator(); i.hasNext(); ) {
			DefaultWeightedEdge e = i.next();
			int v1 = minimum_spanning_tree.getEdgeSource(e);
			int v2 = minimum_spanning_tree.getEdgeTarget(e);
			double w = minimum_spanning_tree.getEdgeWeight(e);
			
			multi_graph.addEdge(v1, v2);
			DefaultWeightedEdge temp_e = multi_graph.getEdge(v1, v2);
			multi_graph.setEdgeWeight(temp_e, w);
		}
		for (Iterator<DefaultWeightedEdge> i = min_weight_perfect_matching.edgeSet().iterator(); i.hasNext(); ) {
			DefaultWeightedEdge e = i.next();
			int v1 = min_weight_perfect_matching.getEdgeSource(e);
			int v2 = min_weight_perfect_matching.getEdgeTarget(e);
			double w = min_weight_perfect_matching.getEdgeWeight(e);
			
			multi_graph.addEdge(v1, v2);
			DefaultWeightedEdge temp_e = multi_graph.getEdge(v1, v2);
			multi_graph.setEdgeWeight(temp_e, w);
		}

		return multi_graph;
	}

5. 위 결과에 대해 한붓 그리기를 구합니다. 한붓 그리기는 엣지 개수에 대해 선형 시간 복잡도를 가졌다고 알려진 Hierholzer 알고리즘을 씁니다. JGraphT에 구현되어 있기 때문에 아래와 같이 쓰면 됩니다.

	private static ArrayList<Integer>
		getEulerTour(WeightedMultigraph<Integer,DefaultWeightedEdge> multi_graph) {
		
		HierholzerEulerianCycle<Integer,DefaultWeightedEdge> h = new HierholzerEulerianCycle<Integer,DefaultWeightedEdge>();
		
		ArrayList<Integer> euler_tour = new ArrayList<Integer>();
		
		int v = h.getEulerianCycle(multi_graph).getStartVertex();
		
		for (DefaultWeightedEdge e : h.getEulerianCycle(multi_graph).getEdgeList()) {
			int s = multi_graph.getEdgeSource(e);
			int t = multi_graph.getEdgeTarget(e);
			if (v == s) {
				euler_tour.add(s);
				v = t;
			} else {
				euler_tour.add(t);
				v = s;
			}
		}
		euler_tour.add(v);
		
		return euler_tour;
	}

6. 한붓 그리기 결과에 대해 해밀턴 경로를 구합니다. 이 때, 지름길로 가기 위해 앞서 구한 한붓 그리기 경로를 돌면서 이미 지났던 노드는 건너뛰면 됩니다.

	private static ArrayList<Integer> getHamiltonianPath(ArrayList<Integer> euler_tour) {
		// This method fits only in the Christofides class.
		ArrayList<Integer> hamiltonian = new ArrayList<Integer>();
		HashSet<Integer> temp_set = new HashSet<Integer>();
		
		for (int t : euler_tour) {
			if (!temp_set.contains(t)) {
				temp_set.add(t);
				hamiltonian.add(t);
			}
		}
		hamiltonian.add(euler_tour.get(0));
		
		return hamiltonian;
	}

JGraphT 라이브러리를 써서 자바로 크리스토피드 알고리즘을 구현해보았습니다.

전체 소스코드는 제 깃헙 저장소 에 있습니다.