139 lines
3.4 KiB
Go
139 lines
3.4 KiB
Go
package diagram
|
|
|
|
import (
|
|
"sync"
|
|
|
|
"modelRT/orm"
|
|
|
|
"github.com/gofrs/uuid"
|
|
)
|
|
|
|
// TopologyGraph represents directed topologic links with adjacency lists.
|
|
// It preserves multiple parents for one node.
|
|
type TopologyGraph struct {
|
|
Nodes map[uuid.UUID]struct{}
|
|
OutEdges map[uuid.UUID][]uuid.UUID
|
|
InEdges map[uuid.UUID][]uuid.UUID
|
|
StartNodes []uuid.UUID
|
|
EndNodes []uuid.UUID
|
|
}
|
|
|
|
var (
|
|
globalTopologyGraphMu sync.RWMutex
|
|
GlobalTopologyGraph *TopologyGraph
|
|
)
|
|
|
|
// NewTopologyGraph builds a directed graph cache from topologic edges.
|
|
func NewTopologyGraph(edges []orm.Topologic) *TopologyGraph {
|
|
graph := &TopologyGraph{
|
|
Nodes: make(map[uuid.UUID]struct{}, len(edges)*2),
|
|
OutEdges: make(map[uuid.UUID][]uuid.UUID, len(edges)),
|
|
InEdges: make(map[uuid.UUID][]uuid.UUID, len(edges)),
|
|
}
|
|
|
|
for _, edge := range edges {
|
|
from := edge.UUIDFrom
|
|
to := edge.UUIDTo
|
|
|
|
graph.Nodes[from] = struct{}{}
|
|
graph.Nodes[to] = struct{}{}
|
|
graph.OutEdges[from] = append(graph.OutEdges[from], to)
|
|
graph.InEdges[to] = append(graph.InEdges[to], from)
|
|
}
|
|
|
|
graph.StartNodes = graph.findStartNodes()
|
|
graph.EndNodes = graph.findEndNodes()
|
|
return graph
|
|
}
|
|
|
|
// SetGlobalTopologyGraph replaces the process-wide topology graph cache.
|
|
func SetGlobalTopologyGraph(graph *TopologyGraph) {
|
|
globalTopologyGraphMu.Lock()
|
|
defer globalTopologyGraphMu.Unlock()
|
|
GlobalTopologyGraph = graph
|
|
}
|
|
|
|
// GetGlobalTopologyGraph returns the process-wide topology graph cache.
|
|
func GetGlobalTopologyGraph() *TopologyGraph {
|
|
globalTopologyGraphMu.RLock()
|
|
defer globalTopologyGraphMu.RUnlock()
|
|
return GlobalTopologyGraph
|
|
}
|
|
|
|
func (g *TopologyGraph) findStartNodes() []uuid.UUID {
|
|
startNodes := make([]uuid.UUID, 0)
|
|
for id := range g.Nodes {
|
|
if len(g.InEdges[id]) == 0 && len(g.OutEdges[id]) > 0 {
|
|
startNodes = append(startNodes, id)
|
|
}
|
|
}
|
|
return startNodes
|
|
}
|
|
|
|
func (g *TopologyGraph) findEndNodes() []uuid.UUID {
|
|
endNodes := make([]uuid.UUID, 0)
|
|
for id := range g.Nodes {
|
|
if len(g.InEdges[id]) > 0 && len(g.OutEdges[id]) == 0 {
|
|
endNodes = append(endNodes, id)
|
|
}
|
|
}
|
|
return endNodes
|
|
}
|
|
|
|
// IsReachable reports whether end can be reached from start following directed
|
|
// uuid_from -> uuid_to edges.
|
|
func (g *TopologyGraph) IsReachable(start, end uuid.UUID) bool {
|
|
return len(g.FindPath(start, end)) > 0
|
|
}
|
|
|
|
// FindPath returns one shortest directed path from start to end, or nil when
|
|
// no directed path exists.
|
|
func (g *TopologyGraph) FindPath(start, end uuid.UUID) []uuid.UUID {
|
|
if g == nil {
|
|
return nil
|
|
}
|
|
if start == end {
|
|
if _, exists := g.Nodes[start]; exists {
|
|
return []uuid.UUID{start}
|
|
}
|
|
return nil
|
|
}
|
|
|
|
visited := map[uuid.UUID]struct{}{start: {}}
|
|
parent := make(map[uuid.UUID]uuid.UUID)
|
|
queue := []uuid.UUID{start}
|
|
|
|
for len(queue) > 0 {
|
|
cur := queue[0]
|
|
queue = queue[1:]
|
|
|
|
for _, next := range g.OutEdges[cur] {
|
|
if _, seen := visited[next]; seen {
|
|
continue
|
|
}
|
|
visited[next] = struct{}{}
|
|
parent[next] = cur
|
|
|
|
if next == end {
|
|
return reconstructTopologyGraphPath(parent, start, end)
|
|
}
|
|
|
|
queue = append(queue, next)
|
|
}
|
|
}
|
|
|
|
return nil
|
|
}
|
|
|
|
func reconstructTopologyGraphPath(parent map[uuid.UUID]uuid.UUID, start, end uuid.UUID) []uuid.UUID {
|
|
path := make([]uuid.UUID, 0)
|
|
for cur := end; cur != start; cur = parent[cur] {
|
|
path = append(path, cur)
|
|
}
|
|
path = append(path, start)
|
|
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
|
|
path[i], path[j] = path[j], path[i]
|
|
}
|
|
return path
|
|
}
|