blob: 34d57a9e46e0af4d5bf35358af1296b51165216b (
plain)
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
use crate::graph::Graph;
pub async fn dominating_numbers(
g: Graph,
) -> (String, Option<u32>, Option<u32>) {
let line = g.to_g6();
let mut independent_dominating = None;
let mut geodesic_sets = Vec::new();
let mut min_size = g.size as u32;
for cs in g.cutsets() {
let dom = cs.is_dominating_in(&g);
let idp = cs.graph.is_independent();
if independent_dominating.is_none() && dom && idp {
independent_dominating = Some(cs.cardinality as u32);
}
let mut visited = vec![0; g.size];
for a in 0..cs.graph.size {
if cs.vertices[a] == 0 {
continue;
}
for b in a..cs.graph.size {
if cs.vertices[b] == 0 {
continue;
}
if a != b {
for geod in g.get_geodesics(a, b) {
for i in geod {
visited[i] = 1;
}
}
}
}
}
if visited.iter().sum::<usize>() == g.size {
geodesic_sets.push(cs.vertices.clone());
let tmp = cs.vertices.into_iter().sum::<u32>();
if tmp < min_size {
min_size = tmp;
}
}
}
let geodesic_sets: Vec<_> = geodesic_sets
.into_iter()
.filter(|s| s.iter().sum::<u32>() == min_size)
.collect();
let mut fg = None;
if geodesic_sets.len() == 1 {
fg = Some(0)
} else {
for i in 0..geodesic_sets.len() {
let check = &geodesic_sets[i];
let mut verts = check.clone();
for j in 0..geodesic_sets.len() {
if i == j {
continue;
}
let set = &geodesic_sets[j];
for v in 0..g.size {
if check[v] == set[v] {
verts[v] = 0;
}
}
}
let new_fg = verts.iter().sum::<u32>();
if new_fg > 0 {
if new_fg < fg.unwrap_or(g.size as u32) {
fg = Some(new_fg);
}
}
}
}
println!("{line} {independent_dominating:?} {fg:?}");
(line, independent_dominating, fg)
}
|
