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
82
83
84
85
86
87
88
89
90
91
92
93
94
|
use crate::graph::Graph;
pub async fn dominating_numbers(
g: Graph,
) -> (String, usize, 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;
for cs in g.cutsets() {
if independent_dominating.is_none_or(|cur| cur > 1) {
let dom = cs.is_dominating_in(&g);
let idp = cs.graph.is_independent();
if dom && idp {
independent_dominating = Some(
independent_dominating
.map_or(cs.cardinality as u32, |cur| {
std::cmp::min(cur, cs.cardinality as u32)
}),
);
}
}
if cs.cardinality > min_size {
continue;
}
let mut visited = vec![0; g.size];
'outer: 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 {
break 'outer;
}
}
}
if visited.iter().sum::<usize>() == g.size {
geodesic_sets.push(cs.vertices.clone());
if cs.cardinality < min_size {
min_size = cs.cardinality;
}
}
}
let geodesic_sets: Vec<_> = geodesic_sets
.into_iter()
.filter(|s| s.iter().sum::<u32>() == min_size as u32)
.collect();
let mut fg = None;
if geodesic_sets.len() == 1 {
fg = Some(0)
} else {
for (i, check) in geodesic_sets.iter().enumerate() {
let mut verts = check.clone();
for (j, set) in geodesic_sets.iter().enumerate() {
if i == j {
continue;
}
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 && new_fg < fg.unwrap_or(g.size as u32) {
fg = Some(new_fg);
}
if let Some(fg) = fg {
if fg == 1 {
break;
}
}
}
}
(line, g.size, independent_dominating, fg)
}
|
