-
Notifications
You must be signed in to change notification settings - Fork 0
/
enumerate.go
69 lines (64 loc) · 2.11 KB
/
enumerate.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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package segment
import (
"github.com/scionproto/scion/go/lib/addr"
)
// SrcDstPaths enumerates all possible end-to-end segments between a source and
// destination ISD-AS pair from a given set of segments. For constant-bounded
// segment length, the runtime complexity is linear in the number of
// enumeratable segments starting at the source ISD-AS.
func SrcDstPaths(segments []Segment, srcIA, dstIA addr.IA) []Segment {
maxSegLen := 3 // SCION-specific
buckets := createSegmentBuckets(segments)
seglists := recursiveSrcDstSeglists(maxSegLen, srcIA, dstIA, buckets)
flattened := flattenSeglists(seglists)
return flattened
}
func createSegmentBuckets(segments []Segment) map[addr.IA][]Segment {
buckets := make(map[addr.IA][]Segment, len(segments))
for _, segment := range segments {
srcIA, dstIA := segment.SrcIA(), segment.DstIA()
if srcIA == dstIA { // cyclic
continue
}
buckets[srcIA] = append(buckets[srcIA], segment)
}
return buckets
}
func recursiveSrcDstSeglists(maxlen int, srcIA, dstIA addr.IA, buckets map[addr.IA][]Segment) [][]Segment {
if srcIA == dstIA {
return [][]Segment{{}} // outer list contains one empty segment list
} else if maxlen <= 0 {
return [][]Segment{} // outer list is empty
}
srcToDstSeglists := make([][]Segment, 0)
for _, srcToMidSegment := range buckets[srcIA] {
midIA := srcToMidSegment.DstIA()
midToDstSeglists := recursiveSrcDstSeglists(maxlen-1, midIA, dstIA, buckets)
for _, midToDstSeglist := range midToDstSeglists {
cyclic := false
for _, seg := range midToDstSeglist {
if srcIA == seg.DstIA() {
cyclic = true
}
}
if !cyclic {
srcToDstSeglist := append([]Segment{srcToMidSegment}, midToDstSeglist...)
srcToDstSeglists = append(srcToDstSeglists, srcToDstSeglist)
}
}
}
return srcToDstSeglists
}
func flattenSeglists(seglists [][]Segment) []Segment {
segments := make([]Segment, 0)
for _, seglist := range seglists {
switch len(seglist) {
case 0: // Skip if segment list is empty
case 1:
segments = append(segments, seglist[0])
default:
segments = append(segments, FromSegments(seglist...))
}
}
return segments
}