railpack

1package graph2 3import (4	"fmt"5)6 7// Node represents a node in a directed graph8type Node interface {9	GetName() string10	GetParents() []Node11	GetChildren() []Node12	SetParents([]Node)13	SetChildren([]Node)14}15 16// Graph represents a directed graph structure17type Graph struct {18	nodes map[string]Node19}20 21// NewGraph creates a new empty graph22func NewGraph() *Graph {23	return &Graph{24		nodes: make(map[string]Node),25	}26}27 28// AddNode adds a node to the graph29func (g *Graph) AddNode(node Node) {30	g.nodes[node.GetName()] = node31}32 33// GetNode retrieves a node by name34func (g *Graph) GetNode(name string) (Node, bool) {35	node, exists := g.nodes[name]36	return node, exists37}38 39// GetNodes returns all nodes in the graph40func (g *Graph) GetNodes() map[string]Node {41	return g.nodes42}43 44// ComputeProcessingOrder returns nodes in topological order45func (g *Graph) ComputeProcessingOrder() ([]Node, error) {46	order := make([]Node, 0, len(g.nodes))47	visited := make(map[string]bool)48	temp := make(map[string]bool)49 50	var visit func(node Node) error51	visit = func(node Node) error {52		if temp[node.GetName()] {53			return fmt.Errorf("cycle detected: %s", node.GetName())54		}55		if visited[node.GetName()] {56			return nil57		}58		temp[node.GetName()] = true59 60		// Visit parents first to ensure they are processed before this node61		for _, parent := range node.GetParents() {62			if err := visit(parent); err != nil {63				return err64			}65		}66 67		delete(temp, node.GetName())68		visited[node.GetName()] = true69		order = append(order, node)70		return nil71	}72 73	// Start with leaf nodes (nodes with no children)74	for _, node := range g.nodes {75		if len(node.GetChildren()) == 0 {76			if err := visit(node); err != nil {77				return nil, err78			}79		}80	}81 82	// Process any remaining nodes83	for _, node := range g.nodes {84		if !visited[node.GetName()] {85			if err := visit(node); err != nil {86				return nil, err87			}88		}89	}90 91	return order, nil92}93 94// ComputeTransitiveDependencies removes redundant edges from the graph95func (g *Graph) ComputeTransitiveDependencies() {96	for _, node := range g.nodes {97		var newParents []Node98		for _, parent := range node.GetParents() {99			isRedundant := false100			for _, otherParent := range node.GetParents() {101				if otherParent == parent {102					continue103				}104 105				visited := make(map[string]bool)106				var traverse func(Node)107				traverse = func(n Node) {108					if n == parent {109						isRedundant = true110						return111					}112					for _, p := range n.GetParents() {113						if !visited[p.GetName()] {114							visited[p.GetName()] = true115							traverse(p)116						}117					}118				}119				traverse(otherParent)120 121				if isRedundant {122					break123				}124			}125 126			if !isRedundant {127				newParents = append(newParents, parent)128			} else {129				// Remove child relationship from parent130				parentChildren := removeNodeFromSlice(parent.GetChildren(), node)131				parent.SetChildren(parentChildren)132			}133		}134		node.SetParents(newParents)135	}136}137 138// removeNodeFromSlice removes a node from a slice of nodes139func removeNodeFromSlice(nodes []Node, target Node) []Node {140	result := make([]Node, 0, len(nodes))141	for _, n := range nodes {142		if n != target {143			result = append(result, n)144		}145	}146	return result147}148 149// PrintGraph prints a human-readable representation of the graph structure150func (g *Graph) PrintGraph() {151	fmt.Println("\nGraph Structure:")152	fmt.Println("=====================")153 154	for name, node := range g.nodes {155		fmt.Printf("\nNode: %s\n", name)156		fmt.Printf("  Parents (%d):\n", len(node.GetParents()))157		for _, parent := range node.GetParents() {158			fmt.Printf("    - %s\n", parent.GetName())159		}160 161		fmt.Printf("  Children (%d):\n", len(node.GetChildren()))162		for _, child := range node.GetChildren() {163			fmt.Printf("    - %s\n", child.GetName())164		}165	}166	fmt.Println("\n=====================")167}168