dagro/parent_dummy_chains.go at main · d2lang/dagro · GitHub

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package dagro

type postorderRange struct{ low, lim int }

func parentDummyChains(g *Graph) {
	postorderNums := compoundPostorder(g)
	chains, _ := asAttrs(g.Graph())["dummyChains"].([]string)
	for _, start := range chains {
		v := start
		node := asAttrs(g.Node(v))
		edgeObj := node["edgeObj"].(Edge)
		path, lca := findCompoundPath(g, postorderNums, edgeObj.V, edgeObj.W)
		pathIdx := 0
		pathV := path[pathIdx]
		ascending := true
		for v != edgeObj.W {
			node = asAttrs(g.Node(v))
			if ascending {
				for {
					pathV = path[pathIdx]
					if pathV == lca || num(asAttrs(g.Node(pathV)), "maxRank") >= num(node, "rank") {
						break
					}
					pathIdx++
				}
				if pathV == lca {
					ascending = false
				}
			}
			if !ascending {
				for pathIdx < len(path)-1 {
					next := path[pathIdx+1]
					if num(asAttrs(g.Node(next)), "minRank") > num(node, "rank") {
						break
					}
					pathIdx++
					pathV = next
				}
				pathV = path[pathIdx]
			}
			if pathV == "" {
				_ = g.setParentKnownAcyclic(v)
			} else {
				_ = g.setParentKnownAcyclic(v, pathV)
			}
			v = g.Successors(v)[0]
		}
	}
}

func findCompoundPath(g *Graph, nums map[string]postorderRange, v, w string) ([]string, string) {
	var vPath, wPath []string
	low := nums[v].low
	if nums[w].low < low {
		low = nums[w].low
	}
	lim := nums[v].lim
	if nums[w].lim > lim {
		lim = nums[w].lim
	}
	parent := v
	for {
		p, ok := g.Parent(parent)
		if ok {
			parent = p
		} else {
			parent = ""
		}
		vPath = append(vPath, parent)
		if parent == "" || !(nums[parent].low > low || lim > nums[parent].lim) {
			break
		}
	}
	lca := parent
	parent = w
	for {
		p, ok := g.Parent(parent)
		if ok {
			parent = p
		} else {
			parent = ""
		}
		if parent == lca {
			break
		}
		wPath = append(wPath, parent)
	}
	for i, j := 0, len(wPath)-1; i < j; i, j = i+1, j-1 {
		wPath[i], wPath[j] = wPath[j], wPath[i]
	}
	return append(vPath, wPath...), lca
}

func compoundPostorder(g *Graph) map[string]postorderRange {
	result := map[string]postorderRange{}
	lim := 0
	var dfs func(string)
	dfs = func(v string) {
		low := lim
		for _, child := range g.Children(v) {
			dfs(child)
		}
		result[v] = postorderRange{low: low, lim: lim}
		lim++
	}
	for _, v := range g.Children() {
		dfs(v)
	}
	return result
}