1 package simple
2
3 import (
4 "k8s.io/kubernetes/third_party/forked/gonum/graph"
5 )
6
7
8
9 type DirectedAcyclicGraph struct {
10 *UndirectedGraph
11 }
12
13 func NewDirectedAcyclicGraph(self, absent float64) *DirectedAcyclicGraph {
14 return &DirectedAcyclicGraph{
15 UndirectedGraph: NewUndirectedGraph(self, absent),
16 }
17 }
18
19 func (g *DirectedAcyclicGraph) HasEdgeFromTo(u, v graph.Node) bool {
20 edge := g.UndirectedGraph.EdgeBetween(u, v)
21 if edge == nil {
22 return false
23 }
24 return (edge.From().ID() == u.ID())
25 }
26
27 func (g *DirectedAcyclicGraph) From(n graph.Node) []graph.Node {
28 if !g.Has(n) {
29 return nil
30 }
31
32 fid := n.ID()
33 nodes := make([]graph.Node, 0, g.UndirectedGraph.edges[n.ID()].Len())
34 g.UndirectedGraph.edges[n.ID()].Visit(func(neighbor int, edge graph.Edge) {
35 if edge.From().ID() == fid {
36 nodes = append(nodes, g.UndirectedGraph.nodes[edge.To().ID()])
37 }
38 })
39 return nodes
40 }
41
42 func (g *DirectedAcyclicGraph) VisitFrom(n graph.Node, visitor func(neighbor graph.Node) (shouldContinue bool)) {
43 if !g.Has(n) {
44 return
45 }
46 fid := n.ID()
47 g.UndirectedGraph.edges[n.ID()].Visit(func(neighbor int, edge graph.Edge) {
48 if edge.From().ID() == fid {
49 if !visitor(g.UndirectedGraph.nodes[edge.To().ID()]) {
50 return
51 }
52 }
53 })
54 }
55
56 func (g *DirectedAcyclicGraph) To(n graph.Node) []graph.Node {
57 if !g.Has(n) {
58 return nil
59 }
60
61 tid := n.ID()
62 nodes := make([]graph.Node, 0, g.UndirectedGraph.edges[n.ID()].Len())
63 g.UndirectedGraph.edges[n.ID()].Visit(func(neighbor int, edge graph.Edge) {
64 if edge.To().ID() == tid {
65 nodes = append(nodes, g.UndirectedGraph.nodes[edge.From().ID()])
66 }
67 })
68 return nodes
69 }
70
71 func (g *DirectedAcyclicGraph) VisitTo(n graph.Node, visitor func(neighbor graph.Node) (shouldContinue bool)) {
72 if !g.Has(n) {
73 return
74 }
75 tid := n.ID()
76 g.UndirectedGraph.edges[n.ID()].Visit(func(neighbor int, edge graph.Edge) {
77 if edge.To().ID() == tid {
78 if !visitor(g.UndirectedGraph.nodes[edge.From().ID()]) {
79 return
80 }
81 }
82 })
83 }
84
View as plain text