Acid
98 lines
2.1 KiB
Go
98 lines
2.1 KiB
Go
package graphs
|
|
|
|
import "slices"
|
|
|
|
// DAG -> Directed Acyclic Graph. Any edge that would introduce a cycle is
|
|
// rejected, so the acyclic invariant always holds.
|
|
type DAG[T comparable] struct {
|
|
adjList map[T][]T
|
|
}
|
|
|
|
// NewDAG() -> Creates a Directed Acyclic Graph
|
|
func NewDAG[T comparable]() *DAG[T] {
|
|
gp := &DAG[T]{
|
|
adjList: make(map[T][]T),
|
|
}
|
|
|
|
return gp
|
|
}
|
|
|
|
// AddIsolatedVertex() -> Creates an isolated Vertex returns True if ok ,
|
|
// false if vertex already exist
|
|
func (gp *DAG[T]) AddIsolatedVertex(newVertex T) bool {
|
|
_, ok := gp.adjList[newVertex]
|
|
if !ok {
|
|
gp.adjList[newVertex] = make([]T, 0)
|
|
return true
|
|
}
|
|
return false
|
|
}
|
|
|
|
// AddVertex() -> adds a directed edge from -> to, creating either vertex if it
|
|
// is missing. Returns false (and adds nothing) when the edge is a self loop,
|
|
// already exists, or would create a cycle.
|
|
func (gp *DAG[T]) AddVertex(from T, to T) bool {
|
|
// self loops are cycles of length 1
|
|
if from == to {
|
|
return false
|
|
}
|
|
|
|
gp.AddIsolatedVertex(from)
|
|
gp.AddIsolatedVertex(to)
|
|
|
|
if slices.Contains(gp.adjList[from], to) {
|
|
return false
|
|
}
|
|
|
|
// from -> to closes a cycle iff "to" can already reach "from".
|
|
if gp.hasPath(to, from) {
|
|
return false
|
|
}
|
|
|
|
gp.adjList[from] = append(gp.adjList[from], to)
|
|
return true
|
|
}
|
|
|
|
// hasPath() -> reports whether a directed path exists from src to dst.
|
|
func (gp *DAG[T]) hasPath(src T, dst T) bool {
|
|
visited := make(map[T]bool)
|
|
return gp.dfs(src, dst, visited)
|
|
}
|
|
|
|
func (gp *DAG[T]) dfs(current T, dst T, visited map[T]bool) bool {
|
|
if current == dst {
|
|
return true
|
|
}
|
|
|
|
visited[current] = true
|
|
|
|
for _, next := range gp.adjList[current] {
|
|
if !visited[next] && gp.dfs(next, dst, visited) {
|
|
return true
|
|
}
|
|
}
|
|
|
|
return false
|
|
}
|
|
|
|
// Order() -> returns the amount of Vertices
|
|
func (gp *DAG[T]) Order() int {
|
|
return len(gp.adjList)
|
|
}
|
|
|
|
// Size() -> returns the amount of Edges
|
|
func (gp *DAG[T]) Size() int {
|
|
var size int
|
|
|
|
// directed: each edge is stored once, so no halving.
|
|
for _, val := range gp.adjList {
|
|
size += len(val)
|
|
}
|
|
return size
|
|
}
|
|
|
|
// Display() -> returns adjList[map]T []T
|
|
func (gp *DAG[T]) Display() map[T][]T {
|
|
return gp.adjList
|
|
}
|