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 ¶
- func IsCycle(path []*Vertex) bool
- func VisitAll(node *Vertex, visited map[string]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) EulerianCycle() []*Vertex
- func (a *AdjacencyList) EulerianPath() []*Vertex
- func (a *AdjacencyList) FirstNode() *Vertex
- func (a *AdjacencyList) Genus() int
- func (a *AdjacencyList) HamiltonianCycle() []*Vertex
- func (a *AdjacencyList) HamiltonianPath() []*Vertex
- func (a *AdjacencyList) HasNode(node Vertex) bool
- func (a *AdjacencyList) MinimalVertexCover() map[string]*Vertex
- func (a *AdjacencyList) NodeCount() int
- func (a *AdjacencyList) NodeWithMostEdges() *Vertex
- func (a *AdjacencyList) Nodes() map[string]*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[string]*Vertex
- type Vertex
- func (v *Vertex) AddNeighbor(node *Vertex)
- func (v *Vertex) Decrement()
- func (v *Vertex) Degree() int
- func (v *Vertex) FirstNeighbor() *Vertex
- func (v *Vertex) HasNeighbor(node Vertex) bool
- func (v *Vertex) ID() string
- func (v *Vertex) Increment()
- func (v *Vertex) Name() string
- func (v *Vertex) NeighborCount() int
- func (v *Vertex) Neighbors() map[string]*Vertex
- func (v *Vertex) RemoveNeighbor(node Vertex)
- func (v *Vertex) SetName(name string)
- func (v *Vertex) SetValue(value int)
- func (v *Vertex) Value() int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
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) EulerianCycle ¶ added in v0.0.8
func (a *AdjacencyList) EulerianCycle() []*Vertex
EulerianCycle returns a vertex slice, the traversal of which will touch each edge once, returning to the start vertex
func (*AdjacencyList) EulerianPath ¶ added in v0.0.8
func (a *AdjacencyList) EulerianPath() []*Vertex
EulerianPath returns a vertex slice, the traversal of which will touch each edge once
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) HamiltonianCycle ¶ added in v0.0.8
func (a *AdjacencyList) HamiltonianCycle() []*Vertex
HamiltonianCycle returns a vertex slice, the traversal of which will touch each vertex once
func (*AdjacencyList) HamiltonianPath ¶ added in v0.0.8
func (a *AdjacencyList) HamiltonianPath() []*Vertex
HamiltonianPath returns a vertex slice, the traversal of which will 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[string]*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[string]*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[string]*Vertex
Whiskers returns a map of vertices that have only one edge
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
Source Files