* ParseGraph Graph syntax is something like this: Group1 = node1, node2, node3 Group2 = node4, node5 Group1, Group2, OtherNode // Group1, Group2, OtherNode will all be interconnected, but not within Group1 or Group2 Group1, Group1 // every node is connected to every other node node8, node9 // n
(graph []string, nodes []string)
| 165 | nodes represents a set of unique terminal nodes that the graph will evaluate down to |
| 166 | */ |
| 167 | func ParseGraph(graph []string, nodes []string) ([]Pair[NodeId, NodeId], error) { |
| 168 | // why can't we just have unordered_set<Pair<NodeId, NodeId>> :( |
| 169 | |
| 170 | parsedPairings := make([]Pair[string, string], 0) |
| 171 | |
| 172 | groups := make(map[string][]string) |
| 173 | |
| 174 | symbols := slices.Clone(nodes) |
| 175 | |
| 176 | // pass 0, collect all symbols |
| 177 | |
| 178 | for _, line := range graph { |
| 179 | line = strings.ToLower(strings.TrimSpace(line)) |
| 180 | if strings.Contains(line, "=") { |
| 181 | // group definition |
| 182 | spl := strings.Split(line, "=") |
| 183 | if len(spl) != 2 { |
| 184 | return nil, fmt.Errorf("invalid graph: %s. group definition must contain one '='", line) |
| 185 | } |
| 186 | grp := strings.TrimSpace(spl[0]) |
| 187 | if slices.Contains(nodes, grp) { |
| 188 | return nil, fmt.Errorf("invalid graph: group name must not be a node name: %s", grp) |
| 189 | } |
| 190 | symbols = append(symbols, grp) |
| 191 | } |
| 192 | } |
| 193 | slices.Sort(symbols) |
| 194 | symbols = slices.Compact(symbols) |
| 195 | |
| 196 | // used for topological sorting |
| 197 | // map: group -> []<groups that the node depends on> |
| 198 | topo := make(map[string][]string) |
| 199 | expansion := make(map[string][]string) |
| 200 | |
| 201 | // pass 1, parse graph |
| 202 | for _, line := range graph { |
| 203 | line = strings.ToLower(strings.TrimSpace(line)) |
| 204 | if strings.Contains(line, "=") { |
| 205 | spl := strings.Split(line, "=") |
| 206 | grp := strings.TrimSpace(spl[0]) |
| 207 | if _, ok := groups[grp]; ok { |
| 208 | return nil, fmt.Errorf("invalid graph: duplicate group name: %s", grp) |
| 209 | } |
| 210 | lst, err := parseSymbolList(spl[1], symbols) |
| 211 | if err != nil { |
| 212 | return nil, err |
| 213 | } |
| 214 | // track dependencies |
| 215 | deps := make([]string, 0) |
| 216 | for _, l := range lst { |
| 217 | if !slices.Contains(nodes, l) { |
| 218 | // depends on a group |
| 219 | deps = append(deps, l) |
| 220 | } else { |
| 221 | expansion[grp] = append(expansion[grp], l) |
| 222 | } |
| 223 | } |
| 224 | slices.Sort(deps) |