AddEdge adds a new edge from a node to a node and returns an error if it would result in a cyclic graph
(fromID string, toID string)
| 141 | |
| 142 | // AddEdge adds a new edge from a node to a node and returns an error if it would result in a cyclic graph |
| 143 | func (g *Graph) AddEdge(fromID string, toID string) error { |
| 144 | from, ok := g.Nodes[fromID] |
| 145 | if !ok { |
| 146 | return errors.Errorf("fromID %s does not exist", fromID) |
| 147 | } |
| 148 | to, ok := g.Nodes[toID] |
| 149 | if !ok { |
| 150 | return errors.Errorf("toID %s does not exist", toID) |
| 151 | } |
| 152 | |
| 153 | // Check if cyclic |
| 154 | path := findFirstPath(to, from) |
| 155 | if path != nil { |
| 156 | return &CyclicError{ |
| 157 | path: path, |
| 158 | What: g.item, |
| 159 | } |
| 160 | } |
| 161 | |
| 162 | // Check if there is already an edge |
| 163 | for _, child := range from.Childs { |
| 164 | if child.ID == to.ID { |
| 165 | return nil |
| 166 | } |
| 167 | } |
| 168 | |
| 169 | from.Childs = append(from.Childs, to) |
| 170 | to.Parents = append(to.Parents, from) |
| 171 | return nil |
| 172 | } |
| 173 | |
| 174 | // find first path from node to node with DFS |
| 175 | func findFirstPath(from *Node, to *Node) []*Node { |