graph

Documentation

Index

• type Graph
  • func NewGraph[C comparable]() *Graph[C]
  • func (gr *Graph[C]) AddEdge(start C, end C)
  • func (gr *Graph[C]) AddVertex(vertex C)
  • func (gr *Graph[C]) Empty() bool
  • func (gr *Graph[C]) GetCycles() (vertices map[C][]C)
  • func (gr *Graph[C]) HasCycles() (bool, []C)
  • func (gr *Graph[C]) PrintGraph() string

Types

type Graph

type Graph[C comparable] struct {
	// contains filtered or unexported fields
}

Graph is a generic graph implementation.

func NewGraph

func NewGraph[C comparable]() *Graph[C]

NewGraph creates a new graph for the given comparable type.

func (*Graph[C]) AddEdge

func (gr *Graph[C]) AddEdge(start C, end C)

AddEdge adds an edge to the given Graph. It also makes sure that the vertices are added to the graph if not already present.

func (*Graph[C]) AddVertex

func (gr *Graph[C]) AddVertex(vertex C)

AddVertex adds a vertex to the given Graph.

func (*Graph[C]) Empty

func (gr *Graph[C]) Empty() bool

Empty checks whether the graph is empty or not.

func (*Graph[C]) GetCycles

func (gr *Graph[C]) GetCycles() (vertices map[C][]C)

GetCycles returns all known cycles in the graph. It returns a map of vertices to the cycle they are part of. We are using a well-known DFS based colouring algorithm to check for cycles. Look at https://cp-algorithms.com/graph/finding-cycle.html for more details on the algorithm.

func (*Graph[C]) HasCycles

func (gr *Graph[C]) HasCycles() (bool, []C)

HasCycles checks whether the given graph has a cycle or not. We are using a well-known DFS based colouring algorithm to check for cycles. Look at https://cp-algorithms.com/graph/finding-cycle.html for more details on the algorithm.

func (*Graph[C]) PrintGraph

func (gr *Graph[C]) PrintGraph() string

PrintGraph is used to print the graph. This is only used for testing.