graph

package module
v1.0.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 16, 2023 License: Apache-2.0 Imports: 9 Imported by: 1

README

go-graph

Directed/Undirected graph implementation in golang

Documentation

Index

Constants

View Source 
const (
	Infinity = ^uint(0)
)

Variables

View Source 
var (
	ErrNoEdgesInGraph = errors.New("no-edges-in-graph")
	ErrNoNodesInHeap  = errors.New("no-nodes-in-heap")
	ErrNoPathInGraph  = errors.New("no-path-found-in-graph")
	ErrNoNodeInGraph  = errors.New("no-node-in-graph")
	ErrLoopInDag      = errors.New("loop-in-dag")
)

Functions

func IsVisited 

func IsVisited(visited []string, child string) ([]string, bool)

func NewPrioPathQueue added in v1.0.2 

func NewPrioPathQueue() prioShortestPaths

func NewPrioQueue added in v1.0.2 

func NewPrioQueue(nodes []string, less func(n1, n2 string) bool) *prioQueueImpl

Types

type Color 

type Color int
const (
	White Color = iota
	Gray
	Black
)

type DAG 

type DAG interface {
	Graph
	TopologicalSort() ([]NodeAndDepth, error)
}

type DFSData 

type DFSData struct {
	Prev      map[string]string
	Discover  map[string]int
	Finish    map[string]int
	NodeColor map[string]Color
	Time      int
}

type DagType added in v1.0.1 

type DagType int
const (
	Connected DagType = iota
	Unconnected
	DagTypeDefault = Connected
)

func (DagType) String added in v1.0.1 

func (t DagType) String() string

type DirectedGraphImpl 

type DirectedGraphImpl struct {
	sync.Mutex
	// contains filtered or unexported fields
}

func NewDirectedGraph 

func NewDirectedGraph(opts ...DagType) *DirectedGraphImpl

func (*DirectedGraphImpl) Add added in v1.0.2 

func (d *DirectedGraphImpl) Add(edge Edge) error

func (*DirectedGraphImpl) AddWithCost 

func (d *DirectedGraphImpl) AddWithCost(edge Edge) error

func (*DirectedGraphImpl) BFS 

func (d *DirectedGraphImpl) BFS(vertex string, visit func(v, w string, c uint) bool) ([]string, error)

func (*DirectedGraphImpl) Clone 

func (d *DirectedGraphImpl) Clone() *DirectedGraphImpl

func (*DirectedGraphImpl) DFS 

func (d *DirectedGraphImpl) DFS(vertex ...string) ([]NodeAndDepth, error)

func (*DirectedGraphImpl) DFSWithData 

func (d *DirectedGraphImpl) DFSWithData(vertex ...string) ([]NodeAndDepth, *DFSData, error)

func (*DirectedGraphImpl) FindAllShortestPaths 

func (d *DirectedGraphImpl) FindAllShortestPaths(from, to string) ([][]string, error)

func (*DirectedGraphImpl) FindAllShortestPathsAndCost 

func (d *DirectedGraphImpl) FindAllShortestPathsAndCost(from, to string) ([][]string, uint, error)

func (*DirectedGraphImpl) FindAllShortestPathsAndCostBFS 

func (d *DirectedGraphImpl) FindAllShortestPathsAndCostBFS(from, to string) ([][]string, uint, error)

func (*DirectedGraphImpl) FindAllShortestPathsBFS 

func (d *DirectedGraphImpl) FindAllShortestPathsBFS(from, to string) ([][]string, error)

func (*DirectedGraphImpl) GetEdge added in v1.0.2 

func (d *DirectedGraphImpl) GetEdge(nodeAndNeighbor NodeAndNeighbor) (Edge, error)

func (*DirectedGraphImpl) GetStronglyConnectedComponents added in v1.0.1 

func (d *DirectedGraphImpl) GetStronglyConnectedComponents() ([][]string, error)

func (*DirectedGraphImpl) IsStronglyConnected added in v1.0.1 

func (d *DirectedGraphImpl) IsStronglyConnected(vertex ...string) (bool, error)

func (*DirectedGraphImpl) KShortestPaths added in v1.0.2 

func (d *DirectedGraphImpl) KShortestPaths(from, to string, k int) ([]uint, [][]string, error)

func (*DirectedGraphImpl) New 

func (d *DirectedGraphImpl) New() Graph

func (*DirectedGraphImpl) Nodes 

func (d *DirectedGraphImpl) Nodes() []string

func (*DirectedGraphImpl) Order 

func (d *DirectedGraphImpl) Order() int

func (*DirectedGraphImpl) Path added in v1.0.2 

func (d *DirectedGraphImpl) Path() GraphPath

func (DirectedGraphImpl) PathLength added in v1.0.2 

func (g DirectedGraphImpl) PathLength(path []string) uint

func (*DirectedGraphImpl) Remove added in v1.0.2 

func (d *DirectedGraphImpl) Remove(nodeAndNeighbor NodeAndNeighbor) error

func (*DirectedGraphImpl) RemoveEdge 

func (d *DirectedGraphImpl) RemoveEdge(nodeAndNeighbor NodeAndNeighbor) error

func (*DirectedGraphImpl) ShortestPath 

func (d *DirectedGraphImpl) ShortestPath(v, w string) ([]string, error)

func (*DirectedGraphImpl) ShortestPathAndCost 

func (d *DirectedGraphImpl) ShortestPathAndCost(v, w string) ([]string, uint, error)

func (*DirectedGraphImpl) ShortestPathWithCost added in v1.0.2 

func (d *DirectedGraphImpl) ShortestPathWithCost(v, w string) ([]string, uint, error)

func (*DirectedGraphImpl) ShortestPaths 

func (d *DirectedGraphImpl) ShortestPaths(from string) (map[string]uint, map[string]string, error)

func (*DirectedGraphImpl) Size 

func (d *DirectedGraphImpl) Size() int

func (*DirectedGraphImpl) String 

func (d *DirectedGraphImpl) String() string

func (*DirectedGraphImpl) TopologicalSort 

func (d *DirectedGraphImpl) TopologicalSort() ([]NodeAndDepth, error)

func (*DirectedGraphImpl) Transpose added in v1.0.1 

func (d *DirectedGraphImpl) Transpose() (*DirectedGraphImpl, error)

func (*DirectedGraphImpl) Visit 

func (d *DirectedGraphImpl) Visit(vertex string, visit func(w string, c uint) bool) error

func (*DirectedGraphImpl) Walk 

func (d *DirectedGraphImpl) Walk(vertex string, visit func(w string, c uint) bool) error

type Edge 

type Edge struct {
	Node, Neighbor string
	Cost           uint
}

type Graph 

type Graph interface {
	Order() int
	Size() int
	Visit(vertex string, visit func(w string, c uint) bool) error
	Path() GraphPath
	BFS(vertex string, visit func(v, w string, c uint) bool) ([]string, error)
	DFS(...string) ([]NodeAndDepth, error)
	DFSWithData(...string) ([]NodeAndDepth, *DFSData, error)
	AddWithCost(Edge) error
	ShortestPath(v, w string) ([]string, error)
	ShortestPathAndCost(v, w string) ([]string, uint, error)
	ShortestPaths(v string) (map[string]uint, map[string]string, error)
	KShortestPaths(from, to string, k int) ([]uint, [][]string, error)
	RemoveEdge(NodeAndNeighbor) error
}

type GraphPath 

type GraphPath interface {
	New() Graph
	Nodes() []string
	Walk(v string, visit func(w string, c uint) bool) error
	Add(Edge) error
	Remove(NodeAndNeighbor) error
	GetEdge(NodeAndNeighbor) (Edge, error)
	ShortestPathWithCost(string, string) ([]string, uint, error)
}

type Node 

type Node struct {
	// contains filtered or unexported fields
}

type NodeAndDepth 

type NodeAndDepth struct {
	Node  string
	Depth int
}

type NodeAndNeighbor 

type NodeAndNeighbor struct {
	Node     string
	Neighbor string
}

type UndirectedGraph 

type UndirectedGraph interface {
	Graph
	AddWithCostBoth(Edge) error
}

type UndirectedGraphImpl 

type UndirectedGraphImpl struct {
	sync.Mutex
	// contains filtered or unexported fields
}

func NewUndirectedGraph 

func NewUndirectedGraph() *UndirectedGraphImpl

func (*UndirectedGraphImpl) Add added in v1.0.2 

func (g *UndirectedGraphImpl) Add(edge Edge) error

func (*UndirectedGraphImpl) AddBoth added in v1.0.2 

func (g *UndirectedGraphImpl) AddBoth(edge Edge) error

func (*UndirectedGraphImpl) AddWithCost 

func (g *UndirectedGraphImpl) AddWithCost(edge Edge) error

func (*UndirectedGraphImpl) AddWithCostBoth 

func (g *UndirectedGraphImpl) AddWithCostBoth(edge Edge) error

func (*UndirectedGraphImpl) BFS 

func (g *UndirectedGraphImpl) BFS(node string, visit func(v, w string, c uint) bool) ([]string, error)

func (*UndirectedGraphImpl) DFS 

func (g *UndirectedGraphImpl) DFS(vertex ...string) ([]NodeAndDepth, error)

func (*UndirectedGraphImpl) DFSWithData 

func (g *UndirectedGraphImpl) DFSWithData(vertex ...string) ([]NodeAndDepth, *DFSData, error)

func (*UndirectedGraphImpl) FindAllShortestPaths 

func (g *UndirectedGraphImpl) FindAllShortestPaths(from, to string) ([][]string, error)

func (*UndirectedGraphImpl) FindAllShortestPathsAndCost 

func (g *UndirectedGraphImpl) FindAllShortestPathsAndCost(from, to string) ([][]string, uint, error)

func (*UndirectedGraphImpl) FindAllShortestPathsAndCostBFS 

func (g *UndirectedGraphImpl) FindAllShortestPathsAndCostBFS(from, to string) ([][]string, uint, error)

func (*UndirectedGraphImpl) FindAllShortestPathsBFS 

func (g *UndirectedGraphImpl) FindAllShortestPathsBFS(from, to string) ([][]string, error)

func (*UndirectedGraphImpl) GetBridges added in v1.0.1 

func (g *UndirectedGraphImpl) GetBridges() []Edge

func (*UndirectedGraphImpl) GetEdge added in v1.0.2 

func (g *UndirectedGraphImpl) GetEdge(nodeAndNeighbor NodeAndNeighbor) (Edge, error)

func (*UndirectedGraphImpl) IsStronglyConnected added in v1.0.1 

func (g *UndirectedGraphImpl) IsStronglyConnected(vertex ...string) (bool, error)

func (*UndirectedGraphImpl) KShortestPaths added in v1.0.2 

func (g *UndirectedGraphImpl) KShortestPaths(from, to string, k int) ([]uint, [][]string, error)

func (*UndirectedGraphImpl) New 

func (g *UndirectedGraphImpl) New() Graph

func (*UndirectedGraphImpl) Nodes 

func (g *UndirectedGraphImpl) Nodes() []string

func (*UndirectedGraphImpl) Order 

func (g *UndirectedGraphImpl) Order() int

func (*UndirectedGraphImpl) Path added in v1.0.2 

func (g *UndirectedGraphImpl) Path() GraphPath

func (UndirectedGraphImpl) PathLength added in v1.0.2 

func (g UndirectedGraphImpl) PathLength(path []string) uint

func (*UndirectedGraphImpl) Remove added in v1.0.2 

func (g *UndirectedGraphImpl) Remove(nodeAndNeighbor NodeAndNeighbor) error

func (*UndirectedGraphImpl) RemoveBoth added in v1.0.2 

func (g *UndirectedGraphImpl) RemoveBoth(nodeAndNeighbor NodeAndNeighbor) error

func (*UndirectedGraphImpl) RemoveEdge 

func (g *UndirectedGraphImpl) RemoveEdge(nodeAndNeighbor NodeAndNeighbor) error

func (*UndirectedGraphImpl) RemoveEdgeBoth 

func (g *UndirectedGraphImpl) RemoveEdgeBoth(nodeAndNeighbor NodeAndNeighbor) error

func (*UndirectedGraphImpl) ShortestPath 

func (g *UndirectedGraphImpl) ShortestPath(v, w string) ([]string, error)

func (*UndirectedGraphImpl) ShortestPathAndCost 

func (g *UndirectedGraphImpl) ShortestPathAndCost(v, w string) ([]string, uint, error)

func (*UndirectedGraphImpl) ShortestPathWithCost added in v1.0.2 

func (g *UndirectedGraphImpl) ShortestPathWithCost(v, w string) ([]string, uint, error)

func (*UndirectedGraphImpl) ShortestPaths 

func (g *UndirectedGraphImpl) ShortestPaths(v string) (map[string]uint, map[string]string, error)

func (*UndirectedGraphImpl) Size 

func (g *UndirectedGraphImpl) Size() int

func (*UndirectedGraphImpl) String 

func (g *UndirectedGraphImpl) String() string

func (*UndirectedGraphImpl) Transpose added in v1.0.1 

func (g *UndirectedGraphImpl) Transpose() (*UndirectedGraphImpl, error)

func (*UndirectedGraphImpl) Visit 

func (g *UndirectedGraphImpl) Visit(node string, visit func(w string, c uint) bool) error

func (*UndirectedGraphImpl) Walk 

func (g *UndirectedGraphImpl) Walk(node string, visit func(w string, c uint) bool) error

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.