graph

Documentation

Index

• func IsAcyclic(g Graph) (is bool, cycle []int)
• type Graph

Functions

func IsAcyclic

func IsAcyclic(g Graph) (is bool, cycle []int)

IsAcyclic uses depth-first search to find cycles in a generic graph represented by Graph interface. If a cycle is found, it returns a list of nodes that are in the cyclic path, identified by their orders.

Types

type Graph

type Graph interface {
	// Order returns the total number of nodes in the graph
	Order() int

	// EdgesFrom returns a list of integers that each
	// represents a node that has an edge from node u.
	EdgesFrom(u int) []int
}

Graph represents a simple interface for representation of a directed graph. It is assumed that each node in the graph is uniquely identified with an incremental positive integer (i.e. 1, 2, 3...). A value of 0 for a node represents a sentinel err value.