dag, hypergraph.. whatver

dag.go

package main

import (
	"errors"
	"fmt"
)

// Node represents a node in the DAG.
type Node struct {
	ID         int
	Value      interface{}
	Edges      []*Node
	ValidateFn func() error // Custom validation function
}

// Validate checks if adding an edge to the node creates a cycle and
// also validates the connected nodes' parameters.
func (n *Node) Validate(newEdge *Node) error {
	visited := make(map[*Node]bool)

	var dfs func(node *Node) error
	dfs = func(node *Node) error {
		visited[node] = true
		for _, edge := range node.Edges {
			if visited[edge] {
				return errors.New("Cycle detected in DAG")
			}
			if err := dfs(edge); err != nil {
				return err
			}
		}
		visited[node] = false // Reset for other paths
		return nil
	}

	for _, edge := range n.Edges {
		if edge == newEdge {
			return errors.New("Adding edge would create a cycle")
		}
	}

	if n.ValidateFn != nil {
		if err := n.ValidateFn(); err != nil {
			return err
		}
	}

	return dfs(n)
}

// DAG represents a Directed Acyclic Graph.
type DAG interface {
	AddNode(id int, value interface{}, validateFn func() error) *Node
	AddEdge(from, to *Node) error
	TopologicalSort() ([]*Node, error)
}

// DAGImpl is an implementation of the DAG interface.
type DAGImpl struct {
	Nodes []*Node
}

// AddNode adds a new node to the DAG.
func (d *DAGImpl) AddNode(id int, value interface{}, validateFn func() error) *Node {
	node := &Node{
		ID:         id,
		Value:      value,
		Edges:      []*Node{},
		ValidateFn: validateFn,
	}
	d.Nodes = append(d.Nodes, node)
	return node
}

// AddEdge adds a directed edge between two nodes in the DAG.
func (d *DAGImpl) AddEdge(from, to *Node) error {
	if err := to.Validate(from); err != nil {
		return err
	}
	from.Edges = append(from.Edges, to)
	return nil
}

// TopologicalSort performs a topological sort on the DAG and returns the sorted nodes.
func (d *DAGImpl) TopologicalSort() ([]*Node, error) {
	// ... (same as before)
}

func main() {
	dag := &DAGImpl{}

	node1 := dag.AddNode(1, "Node 1", nil)
	node2 := dag.AddNode(2, "Node 2", nil)
	node3 := dag.AddNode(3, "Node 3", func() error {
		// Custom validation for Node 3's connected nodes
		if len(node3.Edges) > 0 {
			return errors.New("Node 3 cannot have outgoing edges")
		}
		return nil
	})

	if err := dag.AddEdge(node1, node2); err != nil {
		fmt.Println("Error:", err)
		return
	}
	if err := dag.AddEdge(node2, node3); err != nil {
		fmt.Println("Error:", err)
		return
	}

	sortedNodes, err := dag.TopologicalSort()
	if err != nil {
		fmt.Println("Error:", err)
		return
	}

	for _, node := range sortedNodes {
		fmt.Printf("Node %d: %s\n", node.ID, node.Value)
	}
}