-
Notifications
You must be signed in to change notification settings - Fork 2
/
parentsearch.go
50 lines (38 loc) · 1.26 KB
/
parentsearch.go
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
package lib
import (
"github.com/cem-okulmus/BalancedGo/lib"
"github.com/cem-okulmus/disjoint"
)
// ParentCheck looks a separator that could function as the direct ancestor (or "parent")
// of some child node in the GHD, where the connecting vertices "Conn" are explicitly provided
type ParentCheck struct {
Conn []int
Child []int
}
// Check performs the needed computation to ensure whether sep is a good parent
func (p ParentCheck) Check(H *lib.Graph, sep *lib.Edges, balFactor int, Vertices map[int]*disjoint.Element) bool {
//balancedness condition
comps, _, _ := H.GetComponents(*sep, Vertices)
foundCompLow := false
var compLow lib.Graph
balancednessLimit := (((H.Len()) * (balFactor - 1)) / balFactor)
for i := range comps {
if comps[i].Len() > balancednessLimit {
foundCompLow = true
compLow = comps[i]
}
}
if !foundCompLow {
return false // a bad parent :(
}
vertCompLow := compLow.Vertices()
childχ := lib.Inter(p.Child, vertCompLow)
if !lib.Subset(lib.Inter(vertCompLow, p.Conn), sep.Vertices()) {
return false // also a bad parent :(
}
// Connectivity check
if !lib.Subset(lib.Inter(vertCompLow, sep.Vertices()), childχ) {
return false // again a bad parent :( Calling child services ...
}
return true // found a good parent :)
}