graphs

package
v0.0.10 Latest Latest
Warning

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

 Go to latest Published: Jan 14, 2024 License: MIT Imports: 6 Imported by: 0

README

Graphs

This implements a simple graph (network) package.

History

It was first written to support an implementation of the Dollar Game so it has some vagaries more applicable to that. Examples include: the Vertex object value is an int and has Increment() and Decrement() helper functions.

Resources

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	RunningID int64
)

Functions

func IsCycle added in v0.0.8 

func IsCycle(path []*Vertex) bool

IsCycle returns true if the nodes form a cycle

func IsPath added in v0.0.9 

func IsPath(path []*Vertex) bool

IsPath returns true if the nodes form a path

Types

type AdjList added in v0.0.10 

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

AdjList implements an undirected graph

func NewAL 

func NewAL() AdjList

NewAL returns a new, empty adjacdency list

func (*AdjList) AddEdge added in v0.0.10 

func (a *AdjList) AddEdge(n1, n2 *Vertex)

AddEdge adds an edge, adding the nodes if they are not already present

func (*AdjList) AddNode added in v0.0.10 

func (a *AdjList) AddNode(node *Vertex)

AddNode adds a node to the adjacency list if not already present

func (AdjList) Connected added in v0.0.10 

func (a AdjList) Connected() bool

Connected returns true if every vertex is reachable from every other vertex

func (AdjList) Copy added in v0.0.10 

func (a AdjList) Copy() AdjList

Copy returns a copy of the AdjacencyList

func (AdjList) EdgeCount added in v0.0.10 

func (a AdjList) EdgeCount() int

EdgeCount returns the number of distinct edges in the adjacency list

func (AdjList) FirstNode added in v0.0.10 

func (a AdjList) FirstNode() *Vertex

FirstNode returns a node from the map

func (AdjList) Genus added in v0.0.10 

func (a AdjList) Genus() int

Genus returns the genus number of the adjacency list

func (AdjList) HamiltonianPaths added in v0.0.10 

func (a AdjList) HamiltonianPaths(minLength int, stopOnFirstPath bool, includeReverse bool) [][]*Vertex

HamiltonianPaths returns paths, the traversal of which touch each vertex once

func (AdjList) HasNode added in v0.0.10 

func (a AdjList) HasNode(node Vertex) bool

HasNode returns true if the node is already in the adjacency list

func (AdjList) MinimalVertexCover added in v0.0.10 

func (a AdjList) MinimalVertexCover() map[uint64]*Vertex

MinimalVertexCover returns vertices that make a minimal (not guaranteed to be minimum) vertex cover

func (AdjList) NodeCount added in v0.0.10 

func (a AdjList) NodeCount() int

NodeCount returns the number of nodes in the adjacency list

func (AdjList) NodeWithMostEdges added in v0.0.10 

func (a AdjList) NodeWithMostEdges() *Vertex

NodeWithMostEdges returns the node with the highest edge count

func (AdjList) Nodes added in v0.0.10 

func (a AdjList) Nodes() map[uint64]*Vertex

Nodes returns the map of nodes in the adjacency list

func (*AdjList) RemoveNode added in v0.0.10 

func (a *AdjList) RemoveNode(node Vertex)

RemoveNode removes a node from the adjacency list

func (*AdjList) RemoveOrphans added in v0.0.10 

func (a *AdjList) RemoveOrphans()

RemoveOrphans removes all vertices that have no edges

func (AdjList) Serialize added in v0.0.10 

func (a AdjList) Serialize(title string) string

Serialize returns the adjacency list in graphviz format

func (AdjList) ValueLowest added in v0.0.10 

func (a AdjList) ValueLowest() *Vertex

ValueLowest returns the node with the lowest value

func (AdjList) ValueSum added in v0.0.10 

func (a AdjList) ValueSum() int

ValueSum returns the sum of all node values

func (AdjList) Whiskers added in v0.0.10 

func (a AdjList) Whiskers() map[uint64]*Vertex

Whiskers returns a map of vertices that have only one edge

type Path added in v0.0.9 

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

func NewPath added in v0.0.9 

func NewPath(maxLen int) Path

func (Path) Contains added in v0.0.9 

func (p Path) Contains(node Vertex) bool

func (Path) Get added in v0.0.9 

func (p Path) Get() []*Vertex

func (Path) Len added in v0.0.9 

func (p Path) Len() int

func (*Path) Pop added in v0.0.9 

func (p *Path) Pop() (*Vertex, int)

func (*Path) PopAndTrack added in v0.0.10 

func (p *Path) PopAndTrack() (*Vertex, int)

func (*Path) Push added in v0.0.9 

func (p *Path) Push(node *Vertex, depth int)

func (*Path) PushAndTrack added in v0.0.10 

func (p *Path) PushAndTrack(node *Vertex, depth int)

func (*Path) Reset added in v0.0.9 

func (p *Path) Reset()

type Vertex 

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

Vertex implements a graph Vertex

func NewVertex 

func NewVertex(name string, value int) *Vertex

NewVertex returns a new Vertex

func (*Vertex) AddNeighbor 

func (v *Vertex) AddNeighbor(node *Vertex)

AddNeighbor adds a neighbor vertex

func (*Vertex) Decrement 

func (v *Vertex) Decrement()

Decrement decrements the vertex value by 1

func (*Vertex) Degree added in v0.0.8 

func (v *Vertex) Degree() int

Degree returns the degree of the incoming edges (loops count as 2)

func (Vertex) Equal added in v0.0.9 

func (v Vertex) Equal(node Vertex) bool

Equal returns true if v and node are the same vertex

func (Vertex) FirstNeighbor 

func (v Vertex) FirstNeighbor() *Vertex

FirstNeighbor returns the first neighbor

func (Vertex) HasNeighbor 

func (v Vertex) HasNeighbor(node Vertex) bool

HasNeighbor returns true if the given vertex is already a neighbor

func (Vertex) ID 

func (v Vertex) ID() uint64

ID returns the id of the vertex

func (*Vertex) Increment 

func (v *Vertex) Increment()

Increment increments the vertex value by 1

func (Vertex) Name 

func (v Vertex) Name() string

Name returns the vertex name

func (Vertex) NeighborCount added in v0.0.8 

func (v Vertex) NeighborCount() int

NeighborCount returns the number of edges (neighbors)

func (Vertex) Neighbors 

func (v Vertex) Neighbors() []*Vertex

Neighbors returns a slice of all neighbors

func (*Vertex) RemoveNeighbor 

func (v *Vertex) RemoveNeighbor(node Vertex)

RemoveNeighbor removes a neighbor vertex

func (*Vertex) SetName 

func (v *Vertex) SetName(name string)

SetName sets the vertex name

func (*Vertex) SetValue 

func (v *Vertex) SetValue(value int)

SetValue sets the vertex value

func (Vertex) SortNeighbors added in v0.0.9 

func (v Vertex) SortNeighbors()

NeighborsSorted returns a sorted slice of all neighbors

func (Vertex) Value 

func (v Vertex) Value() int

Value returns the vertex value

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.