dot.go (1250B)
1 package dfa 2 3 import ( 4 "fmt" 5 "strings" 6 ) 7 8 // Dot returns a directed graph in [Graphviz] format that represents the finite 9 // join-semilattice ⟨S, ≤⟩. Vertices represent elements in S and edges 10 // represent the ≤ relation between elements. We map from ⟨S, ∨⟩ to ⟨S, ≤⟩ by 11 // computing x ∨ y for all elements in [S]², where x ≤ y iff x ∨ y == y. 12 // 13 // The resulting graph can be filtered through [tred] to compute the transitive 14 // reduction of the graph, the visualisation of which corresponds to the Hasse 15 // diagram of the semilattice. 16 // 17 // [Graphviz]: https://graphviz.org/ 18 // [tred]: https://graphviz.org/docs/cli/tred/ 19 func Dot[L Semilattice[Elem], Elem any](states []Elem) string { 20 var sb strings.Builder 21 sb.WriteString("digraph{\n") 22 sb.WriteString("rankdir=\"BT\"\n") 23 24 for i, v := range states { 25 if vs, ok := any(v).(fmt.Stringer); ok { 26 fmt.Fprintf(&sb, "n%d [label=%q]\n", i, vs) 27 } else { 28 fmt.Fprintf(&sb, "n%d [label=%q]\n", i, fmt.Sprintf("%v", v)) 29 } 30 } 31 32 var l L 33 34 for dx, x := range states { 35 for dy, y := range states { 36 if dx == dy { 37 continue 38 } 39 40 if l.Equals(l.Merge(x, y), y) { 41 fmt.Fprintf(&sb, "n%d -> n%d\n", dx, dy) 42 } 43 } 44 } 45 46 sb.WriteString("}") 47 return sb.String() 48 }