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 ¶
- Variables
- func IsCycle(path []*Vertex) bool
- func IsPath(path []*Vertex) bool
- type AdjacencyList
- func (a *AdjacencyList) AddEdge(n1, n2 *Vertex)
- func (a *AdjacencyList) AddNode(node *Vertex)
- func (a AdjacencyList) Connected() bool
- func (a AdjacencyList) Copy() AdjacencyList
- func (a AdjacencyList) EdgeCount() int
- func (a AdjacencyList) FirstNode() *Vertex
- func (a AdjacencyList) Genus() int
- func (a AdjacencyList) HamiltonianPaths(minLength int, stopOnFirstPath bool, includeReverse bool) [][]*Vertex
- func (a AdjacencyList) HasNode(node Vertex) bool
- func (a AdjacencyList) MinimalVertexCover() map[uint64]*Vertex
- func (a AdjacencyList) NodeCount() int
- func (a AdjacencyList) NodeWithMostEdges() *Vertex
- func (a AdjacencyList) Nodes() map[uint64]*Vertex
- func (a *AdjacencyList) RemoveNode(node Vertex)
- func (a *AdjacencyList) RemoveOrphans()
- func (a AdjacencyList) Serialize(title string) string
- func (a AdjacencyList) ValueLowest() *Vertex
- func (a AdjacencyList) ValueSum() int
- func (a AdjacencyList) Whiskers() map[uint64]*Vertex
- type Path
- type Vertex
- func (v *Vertex) AddNeighbor(node *Vertex)
- func (v *Vertex) Decrement()
- func (v *Vertex) Degree() int
- func (v Vertex) Equal(node Vertex) bool
- func (v Vertex) FirstNeighbor() *Vertex
- func (v Vertex) HasNeighbor(node Vertex) bool
- func (v Vertex) ID() uint64
- func (v *Vertex) Increment()
- func (v Vertex) Name() string
- func (v Vertex) NeighborCount() int
- func (v Vertex) Neighbors() []*Vertex
- func (v *Vertex) RemoveNeighbor(node Vertex)
- func (v *Vertex) SetName(name string)
- func (v *Vertex) SetValue(value int)
- func (v Vertex) SortNeighbors()
- func (v Vertex) Value() int
Constants ¶
This section is empty.
Variables ¶
var ( RunningID int64 Lock sync.Mutex )
Functions ¶
Types ¶
type AdjacencyList ¶
type AdjacencyList struct {
// contains filtered or unexported fields
}
AdjacencyList implements an undirected graph
func (*AdjacencyList) AddEdge ¶
func (a *AdjacencyList) AddEdge(n1, n2 *Vertex)
AddEdge adds an edge, adding the nodes if they are not already present
func (*AdjacencyList) AddNode ¶
func (a *AdjacencyList) AddNode(node *Vertex)
AddNode adds a node to the adjacency list if not already present
func (AdjacencyList) Connected ¶ added in v0.0.8
func (a AdjacencyList) Connected() bool
Connected returns true if every vertex is reachable from every other vertex
func (AdjacencyList) Copy ¶
func (a AdjacencyList) Copy() AdjacencyList
Copy returns a copy of the AdjacencyList
func (AdjacencyList) EdgeCount ¶
func (a AdjacencyList) EdgeCount() int
EdgeCount returns the number of distinct edges in the adjacency list
func (AdjacencyList) FirstNode ¶
func (a AdjacencyList) FirstNode() *Vertex
FirstNode returns a node from the map
func (AdjacencyList) Genus ¶
func (a AdjacencyList) Genus() int
Genus returns the genus number of the adjacency list
func (AdjacencyList) HamiltonianPaths ¶ added in v0.0.9
func (a AdjacencyList) HamiltonianPaths(minLength int, stopOnFirstPath bool, includeReverse bool) [][]*Vertex
HamiltonianPaths returns paths, the traversal of which touch each vertex once
func (AdjacencyList) HasNode ¶
func (a AdjacencyList) HasNode(node Vertex) bool
HasNode returns true if the node is already in the adjacency list
func (AdjacencyList) MinimalVertexCover ¶
func (a AdjacencyList) MinimalVertexCover() map[uint64]*Vertex
MinimalVertexCover returns vertices that make a minimal (not guaranteed to be minimum) vertex cover
func (AdjacencyList) NodeCount ¶
func (a AdjacencyList) NodeCount() int
NodeCount returns the number of nodes in the adjacency list
func (AdjacencyList) NodeWithMostEdges ¶
func (a AdjacencyList) NodeWithMostEdges() *Vertex
NodeWithMostEdges returns the node with the highest edge count
func (AdjacencyList) Nodes ¶
func (a AdjacencyList) Nodes() map[uint64]*Vertex
Nodes returns the map of nodes in the adjacency list
func (*AdjacencyList) RemoveNode ¶
func (a *AdjacencyList) RemoveNode(node Vertex)
RemoveNode removes a node from the adjacency list
func (*AdjacencyList) RemoveOrphans ¶
func (a *AdjacencyList) RemoveOrphans()
RemoveOrphans removes all vertices that have no edges
func (AdjacencyList) Serialize ¶
func (a AdjacencyList) Serialize(title string) string
Serialize returns the adjacency list in graphviz format
func (AdjacencyList) ValueLowest ¶
func (a AdjacencyList) ValueLowest() *Vertex
ValueLowest returns the node with the lowest value
func (AdjacencyList) ValueSum ¶
func (a AdjacencyList) ValueSum() int
ValueSum returns the sum of all node values
func (AdjacencyList) Whiskers ¶
func (a AdjacencyList) 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 (*Path) PopNoTrack ¶ added in v0.0.9
func (*Path) PushNoTrack ¶ added in v0.0.9
type Vertex ¶
type Vertex struct {
// contains filtered or unexported fields
}
Vertex implements a graph Vertex
func (*Vertex) AddNeighbor ¶
AddNeighbor adds a neighbor vertex
func (*Vertex) Degree ¶ added in v0.0.8
Degree returns the degree of the incoming edges (loops count as 2)
func (Vertex) FirstNeighbor ¶
FirstNeighbor returns the first neighbor
func (Vertex) HasNeighbor ¶
HasNeighbor returns true if the given vertex is already a neighbor
func (Vertex) NeighborCount ¶ added in v0.0.8
NeighborCount returns the number of edges (neighbors)
func (*Vertex) RemoveNeighbor ¶
RemoveNeighbor removes a neighbor vertex
func (Vertex) SortNeighbors ¶ added in v0.0.9
func (v Vertex) SortNeighbors()
NeighborsSorted returns a sorted slice of all neighbors
Source Files