// /// Kernighan–Lin 알고리즘을 이용하여 그래프를 두 그룹으로 분할한다.
// ///
// /// # 인수
// /// - `graph`: 노드에 ()를, 엣지에 i32 가중치를 가지는 무방향 그래프.
// ///
// /// # 반환값
// /// 두 개의 HashSet<NodeIndex>로, 각각 그룹 A와 그룹 B의 노드들을 나타낸다.
// pub fn kernighan_lin(graph: &UnGraph<(), i32>) -> (HashSet<NodeIndex>, HashSet<NodeIndex>) {
// let n = graph.node_count();
// if n == 0 {
// return (HashSet::new(), HashSet::new());
// }
// // 초기 분할: 노드들을 정렬한 후 앞쪽 절반은 그룹 A, 나머지는 그룹 B로 배정.
// let mut partition = vec![false; n]; // true: 그룹 A, false: 그룹 B
// let mut nodes: Vec<NodeIndex> = graph.node_indices().collect();
// nodes.sort_by_key(|n| n.index());
// let half = nodes.len() / 2;
// for (i, &node) in nodes.iter().enumerate() {
// if i < half {
// partition[node.index()] = true; // 그룹 A
// } else {
// partition[node.index()] = false; // 그룹 B
// }
// }
// let mut improvement = true;
// // 반복: swap을 통해 절단 비용을 줄일 수 있으면 계속 진행
// while improvement {
// improvement = false;
// // 각 노드의 D값 계산: D(v) = (v와 다른 그룹 노드와의 연결 가중치 합) - (v와 같은 그룹 노드와의 연결 가중치 합)
// let mut d = vec![0; n];
// for node in graph.node_indices() {
// let idx = node.index();
// let mut internal = 0;
// let mut external = 0;
// for edge in graph.edges(node) {
// let neighbor = edge.target();
// let weight = *edge.weight();
// if partition[neighbor.index()] == partition[idx] {
// internal += weight;
// } else {
// external += weight;
// }
// }
// d[idx] = external - internal;
// }
// // swap 과정에서 이미 선택한 노드를 기록하기 위한 locked 배열
// let mut locked = vec![false; n];
// // 선택한 swap 쌍과 각 쌍의 gain 값을 저장하는 벡터
// let mut swap_pairs: Vec<(NodeIndex, NodeIndex, i32)> = Vec::new();
// let mut gains: Vec<i32> = Vec::new();
// // 한 번의 패스에서 교환 가능한 최대 쌍의 수는 min(그룹 A의 노드 수, 그룹 B의 노드 수)
// let count_a = partition.iter().filter(|&&p| p).count();
// let count_b = n - count_a;
// let max_possible_swaps = std::cmp::min(count_a, count_b);
// // 아직 locked되지 않은 그룹 A와 그룹 B의 노드 쌍에 대해 최대 gain을 주는 swap 쌍을 반복적으로 선택
// for _ in 0..max_possible_swaps {
// let mut best_gain = std::i32::MIN;
// let mut best_pair: Option<(NodeIndex, NodeIndex)> = None;
// // 그룹 A의 unlocked 노드 i와 그룹 B의 unlocked 노드 j에 대해 gain을 계산
// for &i in &nodes {
// if locked[i.index()] || !partition[i.index()] {
// continue; // i는 그룹 A에 있어야 함.
// }
// for &j in &nodes {
// if locked[j.index()] || partition[j.index()] {
// continue; // j는 그룹 B에 있어야 함.
// }
// // i와 j 사이에 edge가 있으면 그 가중치를, 없으면 0으로 취급
// let weight = if let Some(edge) = graph.find_edge(i, j) {
// *graph.edge_weight(edge).unwrap()
// } else {
// 0
// };
// let gain = d[i.index()] + d[j.index()] - 2 * weight;
// if gain > best_gain {
// best_gain = gain;
// best_pair = Some((i, j));
// }
// }
// }
// // 더 이상 선택할 쌍이 없으면 break
// if best_pair.is_none() {
// break;
// }
// let (a, b) = best_pair.unwrap();
// swap_pairs.push((a, b, best_gain));
// if gains.is_empty() {
// gains.push(best_gain);
// } else {
// gains.push(gains.last().unwrap() + best_gain);
// }
// // 선택된 a, b는 locked 처리
// locked[a.index()] = true;
// locked[b.index()] = true;
// // 아직 locked되지 않은 각 노드 k에 대해 D값 업데이트:
// // - k가 그룹 A에 있으면: D(k) = D(k) + 2*(w(k, a) - w(k, b))
// // - k가 그룹 B에 있으면: D(k) = D(k) + 2*(w(k, b) - w(k, a))
// for &k in &nodes {
// if locked[k.index()] {
// continue;
// }
// let w_ka = if let Some(edge) = graph.find_edge(k, a) {
// *graph.edge_weight(edge).unwrap()
// } else {
// 0
// };
// let w_kb = if let Some(edge) = graph.find_edge(k, b) {
// *graph.edge_weight(edge).unwrap()
// } else {
// 0
// };
// if partition[k.index()] {
// // k는 그룹 A에 있음
// d[k.index()] += 2 * (w_ka - w_kb);
// } else {
// // k는 그룹 B에 있음
// d[k.index()] += 2 * (w_kb - w_ka);
// }
// }
// }
// // 각 swap 쌍을 순서대로 적용했을 때의 누적 gain의 최대값과 그때의 쌍 개수를 찾음.
// let mut max_gain = std::i32::MIN;
// let mut k_max = None;
// for (k, &gain_sum) in gains.iter().enumerate() {
// if gain_sum > max_gain {
// max_gain = gain_sum;
// k_max = Some(k);
// }
// }
// // 누적 gain이 양수이면, 실제로 swap 쌍들을 적용.
// if max_gain > 0 {
// improvement = true;
// let num_swaps = k_max.unwrap() + 1;
// for i in 0..num_swaps {
// let (a, b, _) = swap_pairs[i];
// // swap: a는 그룹 A에서 그룹 B로, b는 그룹 B에서 그룹 A로 이동
// partition[a.index()] = false;
// partition[b.index()] = true;
// }
// }
// }
// // 최종 분할 결과를 HashSet으로 생성하여 반환.
// let set_a: HashSet<NodeIndex> = nodes
// .iter()
// .filter(|&&node| partition[node.index()])
// .copied()
// .collect();
// let set_b: HashSet<NodeIndex> = nodes
// .iter()
// .filter(|&&node| !partition[node.index()])
// .copied()
// .collect();
// (set_a, set_b)
// }
// #[cfg(test)]
// mod tests {
// use std::collections::HashSet;
// use petgraph::graph::{NodeIndex, UnGraph};
// use super::*;
// #[test]
// fn test_simple_partition() {
// // 예제: 간단한 무방향 가중치 그래프 생성
// let mut graph = UnGraph::<(), i32>::new_undirected();
// // 노드 추가
// let a = graph.add_node(()); // Node 0
// let b = graph.add_node(()); // Node 1
// let c = graph.add_node(()); // Node 2
// let d = graph.add_node(()); // Node 3
// // 엣지 추가 (가중치 지정)
// graph.add_edge(a, b, 3);
// graph.add_edge(a, c, 1);
// graph.add_edge(b, c, 3);
// graph.add_edge(b, d, 1);
// graph.add_edge(c, d, 2);
// let (set_a, set_b) = kernighan_lin(&graph);
// println!("Group A: {:?}", set_a);
// println!("Group B: {:?}", set_b);
// }
// #[test]
// fn test_empty_graph() {
// let graph: UnGraph<(), i32> = UnGraph::new_undirected();
// let (set_a, set_b) = kernighan_lin(&graph);
// assert!(
// set_a.is_empty(),
// "Group A should be empty for an empty graph."
// );
// assert!(
// set_b.is_empty(),
// "Group B should be empty for an empty graph."
// );
// }
// #[test]
// fn test_two_nodes_graph() {
// let mut graph = UnGraph::<(), i32>::new_undirected();
// let a = graph.add_node(());
// let b = graph.add_node(());
// graph.add_edge(a, b, 5);
// let (set_a, set_b) = kernighan_lin(&graph);
// // 두 노드가 서로 다른 그룹에 속하는지 확인
// assert_eq!(set_a.len() + set_b.len(), 2, "총 노드 수는 2여야 합니다.");
// // 한 노드는 그룹 A, 다른 노드는 그룹 B에 있어야 함
// assert!(
// set_a.contains(&a) ^ set_b.contains(&a),
// "노드 a는 한 그룹에만 속해야 합니다."
// );
// assert!(
// set_a.contains(&b) ^ set_b.contains(&b),
// "노드 b는 한 그룹에만 속해야 합니다."
// );
// }
// #[test]
// fn test_six_nodes_graph() {
// let mut graph = UnGraph::<(), i32>::new_undirected();
// // 노드 추가 (노드가 추가되는 순서대로 인덱스가 0,1,... 할당됨)
// let a = graph.add_node(()); // index 0
// let b = graph.add_node(()); // index 1
// let c = graph.add_node(()); // index 2
// let d = graph.add_node(()); // index 3
// let e = graph.add_node(()); // index 4
// let f = graph.add_node(()); // index 5
// // 그룹 A 내부 (노드 0,1,2): 강한 연결
// graph.add_edge(a, b, 10);
// graph.add_edge(b, c, 10);
// graph.add_edge(a, c, 10);
// // 그룹 B 내부 (노드 3,4,5): 강한 연결
// graph.add_edge(d, e, 10);
// graph.add_edge(e, f, 10);
// graph.add_edge(d, f, 10);
// // 두 그룹 사이의 연결: 약한 연결
// graph.add_edge(c, d, 1);
// graph.add_edge(b, e, 1);
// graph.add_edge(a, d, 1);
// let (set_a, set_b) = kernighan_lin(&graph);
// // 초기 분할에 따라 노드 0,1,2는 그룹 A, 노드 3,4,5는 그룹 B가 되어야 함.
// let expected_a: HashSet<NodeIndex> =
// [NodeIndex::new(0), NodeIndex::new(1), NodeIndex::new(2)]
// .iter()
// .copied()
// .collect();
// let expected_b: HashSet<NodeIndex> =
// [NodeIndex::new(3), NodeIndex::new(4), NodeIndex::new(5)]
// .iter()
// .copied()
// .collect();
// // 분할 결과는 그룹 이름(label)이 뒤바뀔 수 있으므로 두 경우 모두 허용.
// if set_a == expected_a && set_b == expected_b {
// // 올바른 분할
// } else if set_a == expected_b && set_b == expected_a {
// // 올바른 분할 (그룹 레이블이 반대)
// } else {
// panic!(
// "분할 결과가 예상과 다릅니다.\nGroup A: {:?}\nGroup B: {:?}",
// set_a, set_b
// );
// }
// }
// }
// / 단순 노드 구조체
// #[derive(Debug)]
// struct Node;
// /// --- 1. 초기 분할을 인자로 받는 Kernighan–Lin 알고리즘 ---
// ///
// /// 인자로 받은 초기 partition(벡터의 i번째 요소가 true이면 노드 i는 그룹 A)에서 시작하여,
// /// gain이 개선되는 동안 swap을 반복한 후 최종 파티션을 반환한다.
// ///
// /// **주의:** 이 알고리즘은 입력 directed graph의 모든 간선(Outgoing, Incoming)을
// /// 합산하여 undirected하게 처리합니다.
// fn kernighan_lin_with_initial(
// graph: &Graph<Node, usize, Directed>,
// init_partition: &Vec<bool>,
// ) -> Vec<bool> {
// let n = graph.node_count();
// let mut partition = init_partition.clone();
// // 노드들을 인덱스 순서대로 정렬 (안정적인 순서를 위해)
// let mut nodes: Vec<NodeIndex> = graph.node_indices().collect();
// nodes.sort_by_key(|n| n.index());
// let mut improvement = true;
// while improvement {
// improvement = false;
// // 각 노드 v에 대해 D(v) = (외부 연결 가중치 합) - (내부 연결 가중치 합)
// let mut d = vec![0i64; n];
// for (i, &node) in nodes.iter().enumerate() {
// let mut internal = 0i64;
// let mut external = 0i64;
// // Outgoing edge 처리
// for edge in graph.edges_directed(node, petgraph::Direction::Outgoing) {
// let neighbor = edge.target();
// let w = *edge.weight() as i64;
// if partition[neighbor.index()] == partition[node.index()] {
// internal += w;
// } else {
// external += w;
// }
// }
// // Incoming edge 처리
// for edge in graph.edges_directed(node, petgraph::Direction::Incoming) {
// let neighbor = edge.source();
// let w = *edge.weight() as i64;
// if partition[neighbor.index()] == partition[node.index()] {
// internal += w;
// } else {
// external += w;
// }
// }
// d[i] = external - internal;
// }
// // 한 번의 swap 패스에서 이미 사용한 노드를 기록
// let mut locked = vec![false; n];
// // 선택한 swap 쌍과 각 쌍의 gain을 저장 (인덱스는 nodes 벡터 상의 위치)
// let mut swap_pairs: Vec<(usize, usize, i64)> = Vec::new();
// let mut gains: Vec<i64> = Vec::new();
// let count_a = partition.iter().filter(|&&b| b).count();
// let count_b = n - count_a;
// let max_possible_swaps = std::cmp::min(count_a, count_b);
// for _ in 0..max_possible_swaps {
// let mut best_gain = std::i64::MIN;
// let mut best_pair: Option<(usize, usize)> = None;
// // 그룹 A와 그룹 B에서 각각 하나씩 선택
// for i in 0..n {
// if locked[i] || !partition[i] {
// continue;
// }
// for j in 0..n {
// if locked[j] || partition[j] {
// continue;
// }
// // 두 노드 사이의 연결 가중치는
// // (nodes[i] → nodes[j])와 (nodes[j] → nodes[i])의 가중치 합으로 계산
// let mut weight = 0i64;
// if let Some(edge) = graph.find_edge(nodes[i], nodes[j]) {
// weight += *graph.edge_weight(edge).unwrap() as i64;
// }
// if let Some(edge) = graph.find_edge(nodes[j], nodes[i]) {
// weight += *graph.edge_weight(edge).unwrap() as i64;
// }
// let gain = d[i] + d[j] - 2 * weight;
// if gain > best_gain {
// best_gain = gain;
// best_pair = Some((i, j));
// }
// }
// }
// if best_pair.is_none() {
// break;
// }
// let (a, b) = best_pair.unwrap();
// swap_pairs.push((a, b, best_gain));
// if gains.is_empty() {
// gains.push(best_gain);
// } else {
// gains.push(gains.last().unwrap() + best_gain);
// }
// locked[a] = true;
// locked[b] = true;
// // 아직 locked되지 않은 노드에 대해 D값 업데이트
// for k in 0..n {
// if locked[k] {
// continue;
// }
// let mut w_ka = 0i64;
// if let Some(edge) = graph.find_edge(nodes[k], nodes[a]) {
// w_ka += *graph.edge_weight(edge).unwrap() as i64;
// }
// if let Some(edge) = graph.find_edge(nodes[a], nodes[k]) {
// w_ka += *graph.edge_weight(edge).unwrap() as i64;
// }
// let mut w_kb = 0i64;
// if let Some(edge) = graph.find_edge(nodes[k], nodes[b]) {
// w_kb += *graph.edge_weight(edge).unwrap() as i64;
// }
// if let Some(edge) = graph.find_edge(nodes[b], nodes[k]) {
// w_kb += *graph.edge_weight(edge).unwrap() as i64;
// }
// if partition[k] {
// d[k] += 2 * (w_ka - w_kb);
// } else {
// d[k] += 2 * (w_kb - w_ka);
// }
// }
// }
// // 최적의 swap prefix (누적 gain 최대 구간)을 찾음
// let mut max_gain_total = std::i64::MIN;
// let mut k_max = None;
// for (k, &g) in gains.iter().enumerate() {
// if g > max_gain_total {
// max_gain_total = g;
// k_max = Some(k);
// }
// }
// // 누적 gain이 양수이면 swap 적용
// if max_gain_total > 0 {
// improvement = true;
// let num_swaps = k_max.unwrap() + 1;
// for i in 0..num_swaps {
// let (a, b, _) = swap_pairs[i];
// partition[a] = false;
// partition[b] = true;
// }
// }
// }
// partition
// }
// /// --- 2. 이진 탐색을 이용해 target_size에 가까운 bipartition을 구하는 함수 ---
// ///
// /// induced subgraph에서 초기 partition을 만들 때 그룹 A의 비율을 나타내는 파라미터 p를 이진 탐색하여,
// /// 최종 Kernighan–Lin 결과에서 그룹 A의 노드 수가 target_size에 최대한 가깝도록 한다.
// fn binary_partition(graph: &Graph<Node, usize, Directed>, target_size: usize) -> (Vec<bool>, f64) {
// let n = graph.node_count();
// let mut low = 0.0;
// let mut high = 1.0;
// let mut best_partition = vec![false; n];
// let mut best_diff = usize::MAX;
// let mut best_p = 0.5;
// // 20회 반복 (정밀도 조절 가능)
// for _ in 0..20 {
// let mid = (low + high) / 2.0;
// let mut init_partition = vec![false; n];
// let cutoff = ((mid * n as f64).floor() as usize).min(n);
// for i in 0..n {
// init_partition[i] = i < cutoff;
// }
// let partition = kernighan_lin_with_initial(graph, &init_partition);
// let size_a = partition.iter().filter(|&&b| b).count();
// let diff = if size_a > target_size {
// size_a - target_size
// } else {
// target_size - size_a
// };
// // 그룹 A의 크기가 target_size 이하인 경우 최적 갱신
// if size_a <= target_size && diff < best_diff {
// best_diff = diff;
// best_partition = partition.clone();
// best_p = mid;
// }
// if size_a > target_size {
// high = mid;
// } else {
// low = mid;
// }
// }
// (best_partition, best_p)
// }
// /// --- 3. 원 그래프에서 induced subgraph를 만드는 함수 ---
// ///
// /// 주어진 노드 집합에 대해 induced subgraph를 구성하며,
// /// 새 그래프의 노드 순서와 원래 노드 인덱스 사이의 매핑(mapping)도 함께 반환한다.
// fn induced_subgraph(
// graph: &Graph<Node, usize, Directed>,
// nodes: &HashSet<NodeIndex>,
// ) -> (Graph<Node, usize, Directed>, Vec<NodeIndex>) {
// let mut subgraph = Graph::<Node, usize, Directed>::new();
// let mut mapping = Vec::new(); // subgraph의 각 노드에 대응하는 원래 NodeIndex
// let mut node_map = HashMap::new(); // 원래 NodeIndex -> subgraph의 노드 인덱스
// // 노드 추가
// for &n in nodes.iter() {
// let new_idx = subgraph.add_node(Node);
// node_map.insert(n, new_idx);
// mapping.push(n);
// }
// // 간선 추가: 원래 그래프에서 n의 Outgoing 간선 중 target도 nodes 집합에 포함되면 추가
// for &n in nodes.iter() {
// let source_new = node_map[&n];
// for edge in graph.edges_directed(n, petgraph::Direction::Outgoing) {
// let target = edge.target();
// if nodes.contains(&target) {
// let target_new = node_map[&target];
// subgraph.add_edge(source_new, target_new, *edge.weight());
// }
// }
// }
// (subgraph, mapping)
// }
// /// --- 4. 재귀적(그리디한) 분할 ---
// ///
// /// 주어진 원 그래프의 노드 집합 `nodes`에 대해, 만약 노드 수가 `max_size` 이하이면 그대로 반환하고,
// /// 그렇지 않으면 induced subgraph를 구성한 후 binary_partition을 통해 bipartition한 다음,
// /// 각 부분에 대해 재귀적으로 분할하여 최종적으로 “각 그룹의 크기가 max_size 이하”인 그룹들을 구한다.
// fn greedy_partition(
// graph: &Graph<Node, usize, Directed>,
// nodes: &HashSet<NodeIndex>,
// max_size: usize,
// ) -> Vec<HashSet<NodeIndex>> {
// if nodes.len() <= max_size {
// return vec![nodes.clone()];
// }
// let (subgraph, mapping) = induced_subgraph(graph, nodes);
// let (partition, _p_used) = binary_partition(&subgraph, max_size);
// let mut group_a = HashSet::new();
// let mut group_b = HashSet::new();
// // induced subgraph의 노드 순서는 mapping을 통해 원래 노드 인덱스로 변환
// for (i, &in_a) in partition.iter().enumerate() {
// if in_a {
// group_a.insert(mapping[i]);
// } else {
// group_b.insert(mapping[i]);
// }
// }
// let mut result = Vec::new();
// if group_a.len() > max_size {
// result.extend(greedy_partition(graph, &group_a, max_size));
// } else {
// result.push(group_a);
// }
// if group_b.len() > max_size {
// result.extend(greedy_partition(graph, &group_b, max_size));
// } else {
// result.push(group_b);
// }
// result
// }
// #[test]
// fn test_main() {
// // 예제: 간단한 Directed 그래프 생성 (노드 타입: Node, 가중치: usize)
// let mut graph = Graph::<Node, usize, Directed>::new();
// // 노드 추가
// let a = graph.add_node(Node);
// let b = graph.add_node(Node);
// let c = graph.add_node(Node);
// let d = graph.add_node(Node);
// let e = graph.add_node(Node);
// let f = graph.add_node(Node);
// let g = graph.add_node(Node);
// let h = graph.add_node(Node);
// // 엣지 추가 (방향 그래프)
// graph.add_edge(a, b, 5);
// graph.add_edge(a, c, 3);
// graph.add_edge(b, d, 4);
// graph.add_edge(c, d, 2);
// graph.add_edge(c, e, 6);
// graph.add_edge(d, f, 3);
// graph.add_edge(e, f, 1);
// graph.add_edge(e, g, 2);
// graph.add_edge(f, h, 4);
// graph.add_edge(g, h, 3);
// // 전체 노드 집합
// let all_nodes: HashSet<NodeIndex> = graph.node_indices().collect();
// // 예: 각 그룹의 최대 노드 수를 3개로 제한
// let max_size = 3;
// let groups = greedy_partition(&graph, &all_nodes, max_size);
// println!("총 {}개의 그룹:", groups.len());
// for (i, group) in groups.iter().enumerate() {
// println!("그룹 {} ({}개 노드): {:?}", i + 1, group.len(), group);
// }
// }
// #[cfg(test)]
// mod tests {
// use std::collections::HashSet;
// use petgraph::graph::Graph;
// use petgraph::Directed;
// use super::*;
// // 1. 빈 그래프: 노드가 하나도 없으면 그룹은 [∅]로 반환되어야 함.
// #[test]
// fn test_empty_graph() {
// let graph: Graph<Node, usize, Directed> = Graph::new();
// let nodes: HashSet<NodeIndex> = graph.node_indices().collect();
// let groups = greedy_partition(&graph, &nodes, 3);
// // 빈 그래프의 경우 하나의 그룹(빈 집합)이 반환됨
// assert_eq!(groups.len(), 1);
// assert!(groups[0].is_empty());
// }
// // 2. 단일 노드: 하나의 노드만 있으면 해당 노드가 포함된 그룹이 반환되어야 함.
// #[test]
// fn test_single_node() {
// let mut graph = Graph::<Node, usize, Directed>::new();
// let a = graph.add_node(Node);
// let nodes: HashSet<NodeIndex> = graph.node_indices().collect();
// let groups = greedy_partition(&graph, &nodes, 1);
// assert_eq!(groups.len(), 1);
// assert_eq!(groups[0].len(), 1);
// assert!(groups[0].contains(&a));
// }
// // 3. 두 노드, 간선 없음: 두 노드가 각각 분리되어 반환되어야 함.
// #[test]
// fn test_two_nodes_no_edge() {
// let mut graph = Graph::<Node, usize, Directed>::new();
// let a = graph.add_node(Node);
// let b = graph.add_node(Node);
// let nodes: HashSet<NodeIndex> = graph.node_indices().collect();
// // max_size = 1이면 두 노드는 서로 다른 그룹에 분리되어야 함.
// let groups = greedy_partition(&graph, &nodes, 1);
// assert_eq!(groups.len(), 2);
// for group in groups {
// assert_eq!(group.len(), 1);
// }
// }
// // 4. 두 노드, 간선 있음: 양방향 간선을 추가하여 두 노드가 분리되어야 함.
// #[test]
// fn test_two_nodes_one_edge() {
// let mut graph = Graph::<Node, usize, Directed>::new();
// let a = graph.add_node(Node);
// let b = graph.add_node(Node);
// graph.add_edge(a, b, 5);
// graph.add_edge(b, a, 5);
// let nodes: HashSet<NodeIndex> = graph.node_indices().collect();
// let groups = greedy_partition(&graph, &nodes, 1);
// assert_eq!(groups.len(), 2);
// for group in groups {
// assert_eq!(group.len(), 1);
// }
// }
// // 5. 체인 형태의 그래프: 4개의 노드가 일렬로 연결되어 있을 때, max_size = 2면 두 그룹으로 분할됨.
// #[test]
// fn test_chain_graph() {
// let mut graph = Graph::<Node, usize, Directed>::new();
// let a = graph.add_node(Node);
// let b = graph.add_node(Node);
// let c = graph.add_node(Node);
// let d = graph.add_node(Node);
// graph.add_edge(a, b, 1);
// graph.add_edge(b, a, 1);
// graph.add_edge(b, c, 1);
// graph.add_edge(c, b, 1);
// graph.add_edge(c, d, 1);
// graph.add_edge(d, c, 1);
// let nodes: HashSet<NodeIndex> = graph.node_indices().collect();
// let groups = greedy_partition(&graph, &nodes, 2);
// for group in groups.iter() {
// assert!(group.len() <= 2);
// }
// let total: usize = groups.iter().map(|g| g.len()).sum();
// assert_eq!(total, 4);
// }
// // 6. 양분된(바이파티트) 그래프: 6개의 노드 (3+3)로 구성되어, max_size = 3이면 2개의 그룹이 되어야 함.
// #[test]
// fn test_bipartite_graph() {
// let mut graph = Graph::<Node, usize, Directed>::new();
// let a = graph.add_node(Node);
// let b = graph.add_node(Node);
// let c = graph.add_node(Node);
// let d = graph.add_node(Node);
// let e = graph.add_node(Node);
// let f = graph.add_node(Node);
// // 강한 intra-group 간선 (양방향, 가중치 10)
// graph.add_edge(a, b, 10);
// graph.add_edge(b, a, 10);
// graph.add_edge(a, c, 10);
// graph.add_edge(c, a, 10);
// graph.add_edge(b, c, 10);
// graph.add_edge(c, b, 10);
// graph.add_edge(d, e, 10);
// graph.add_edge(e, d, 10);
// graph.add_edge(d, f, 10);
// graph.add_edge(f, d, 10);
// graph.add_edge(e, f, 10);
// graph.add_edge(f, e, 10);
// // 약한 inter-group 간선 (가중치 1)
// graph.add_edge(a, d, 1);
// graph.add_edge(d, a, 1);
// graph.add_edge(b, e, 1);
// graph.add_edge(e, b, 1);
// graph.add_edge(c, f, 1);
// graph.add_edge(f, c, 1);
// let nodes: HashSet<NodeIndex> = graph.node_indices().collect();
// let groups = greedy_partition(&graph, &nodes, 3);
// for group in groups.iter() {
// assert!(group.len() <= 3);
// }
// let total: usize = groups.iter().map(|g| g.len()).sum();
// assert_eq!(total, 6);
// }
// // 7. 사이클 그래프: 4개의 노드가 사이클을 이루며, max_size = 2이면 두 그룹으로 분할됨.
// #[test]
// fn test_cycle_graph() {
// let mut graph = Graph::<Node, usize, Directed>::new();
// let a = graph.add_node(Node);
// let b = graph.add_node(Node);
// let c = graph.add_node(Node);
// let d = graph.add_node(Node);
// graph.add_edge(a, b, 2);
// graph.add_edge(b, a, 2);
// graph.add_edge(b, c, 2);
// graph.add_edge(c, b, 2);
// graph.add_edge(c, d, 2);
// graph.add_edge(d, c, 2);
// graph.add_edge(d, a, 2);
// graph.add_edge(a, d, 2);
// let nodes: HashSet<NodeIndex> = graph.node_indices().collect();
// let groups = greedy_partition(&graph, &nodes, 2);
// for group in groups.iter() {
// assert!(group.len() <= 2);
// }
// let total: usize = groups.iter().map(|g| g.len()).sum();
// assert_eq!(total, 4);
// }
// // 8. 완전 그래프: 4개의 노드가 모두 연결되어 있고, max_size = 2이면 각 그룹의 크기는 2 이하.
// #[test]
// fn test_complete_graph() {
// let mut graph = Graph::<Node, usize, Directed>::new();
// let a = graph.add_node(Node);
// let b = graph.add_node(Node);
// let c = graph.add_node(Node);
// let d = graph.add_node(Node);
// let nodes: Vec<NodeIndex> = graph.node_indices().collect();
// for i in 0..nodes.len() {
// for j in 0..nodes.len() {
// if i != j {
// graph.add_edge(nodes[i], nodes[j], 1);
// }
// }
// }
// let all_nodes: HashSet<NodeIndex> = graph.node_indices().collect();
// let groups = greedy_partition(&graph, &all_nodes, 2);
// for group in groups.iter() {
// assert!(group.len() <= 2);
// }
// let total: usize = groups.iter().map(|g| g.len()).sum();
// assert_eq!(total, 4);
// }
// // 9. binary_partition 함수 테스트: 4개 노드 그래프에서 target_size = 2이면 그룹 A의 크기는 2 이하.
// #[test]
// fn test_binary_partition_function() {
// let mut graph = Graph::<Node, usize, Directed>::new();
// let a = graph.add_node(Node);
// let b = graph.add_node(Node);
// let c = graph.add_node(Node);
// let d = graph.add_node(Node);
// graph.add_edge(a, b, 3);
// graph.add_edge(b, a, 3);
// graph.add_edge(c, d, 2);
// graph.add_edge(d, c, 2);
// let (partition, p_used) = binary_partition(&graph, 2);
// let size_a = partition.iter().filter(|&&b| b).count();
// assert!(size_a <= 2);
// assert!(p_used >= 0.0 && p_used <= 1.0);
// }
// // 10. induced_subgraph 함수 테스트: 원래 그래프에서 일부 노드를 선택하여 induced subgraph가 올바르게 구성되어야 함.
// #[test]
// fn test_induced_subgraph_function() {
// let mut graph = Graph::<Node, usize, Directed>::new();
// let a = graph.add_node(Node);
// let b = graph.add_node(Node);
// let c = graph.add_node(Node);
// let d = graph.add_node(Node);
// let e = graph.add_node(Node);
// graph.add_edge(a, b, 4);
// graph.add_edge(b, a, 4);
// graph.add_edge(b, c, 5);
// graph.add_edge(c, b, 5);
// graph.add_edge(c, d, 6);
// graph.add_edge(d, c, 6);
// graph.add_edge(d, e, 7);
// graph.add_edge(e, d, 7);
// let subset: HashSet<NodeIndex> = [a, c, e].iter().cloned().collect();
// let (subgraph, mapping) = induced_subgraph(&graph, &subset);
// assert_eq!(subgraph.node_count(), 3);
// assert_eq!(mapping.len(), 3);
// for edge in subgraph.edge_references() {
// let source = mapping[edge.source().index()];
// let target = mapping[edge.target().index()];
// assert!(graph.find_edge(source, target).is_some());
// }
// }
// }
