README
¶
Graph
Package graph is an implementation of various graphs.
Status
Everything in here is tested. However there are still
essential parts missing, such as a symbolic implementation of each graphs
and APIs to load the graphs with data from an io.Reader. This will be
implemented in a not too far future.
This library has also not been optimized. However, the graphs can handle sizes in the hundred millions vertices. Some algorithms will be very slow on such sizes, most will have an acceptable running time.
Credits
Pretty much all of the algorithms are taken from Algorithm 4th Ed, by Sedgewick and Wayne. The book is written in Java, I've ported it to Go as an exercise in studying the algorithms.
I hope to one day add more algorithms that could make use of the concurrent capabilities of Go.
License
The MIT License.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AvgDegree ¶
AvgDegree is the average degree in graph g. In a directed graph, this is the average out-degree in g.
func Degree ¶
Degree is the degree of vertex v in graph g. In a directed graph, this is the out-degree of v.
func DirectedCycle ¶
DirectedCycle returns a cycle in digraph di, if there is one.
func IsBipartite ¶
IsBipartite returns if every vertex in graph g can be colored with only two colors, while never sharing the same color of an adjacent vertex
Types ¶
type DAG ¶
type DAG struct {
*Digraph
}
DAG is a directed acyclic graph implemented with an adjacency list digraph.
type Digraph ¶
type Digraph struct {
// contains filtered or unexported fields
}
Digraph is a directed graph implementation using an adjacency list
func NewDigraph ¶
NewDigraph returns a digraph with v vertices, all disconnected
func ReadDigraph ¶
ReadDigraph constructs an undirected graph from the io.Reader expecting to find data formed such as:
v e a b c d ... y z
where `v` is the vertex count, `e` the number of edges and `a`, `b`, `c`, `d`, ..., `y` and `z` are edges between `a` and `b`, `c` and `d`, ..., and `y` and `z` respectively.
type Edge ¶
type Edge struct {
// contains filtered or unexported fields
}
Edge is a weighted edge in a weighted graph
type Graph ¶
type Graph interface {
fmt.GoStringer
// AddEdge adds an edge from v to w.
AddEdge(v, w int)
// Adj is a slice of vertices adjacent to v
Adj(v int) []int
// V is the number of vertices
V() int
// E is the number of edges
E() int
}
Graph is a graph with V vertices.
type Ungraph ¶
type Ungraph struct {
// contains filtered or unexported fields
}
Ungraph is an adjacency list undirected graph. It consumes 2E + V spaces.
func ReadGraph ¶
ReadGraph constructs an undirected graph from the io.Reader expecting to find data formed such as:
v e a b c d ... y z
where `v` is the vertex count, `e` the number of edges and `a`, `b`, `c`, `d`, ..., `y` and `z` are edges between `a` and `b`, `c` and `d`, ..., and `y` and `z` respectively.
type WeightGraph ¶
type WeightGraph struct {
// contains filtered or unexported fields
}
WeightGraph is a graph with weighted edges.
func NewWeightGraph ¶
func NewWeightGraph(v int) WeightGraph
NewWeightGraph creates an empty graph with v vertices
func ReadWeightGraph ¶
func ReadWeightGraph(input io.Reader) (WeightGraph, error)
ReadWeightGraph constructs an undirected graph from the io.Reader expecting to find data formed such as:
v e a b w0 c d w1 ... y z wN
where `v` is the vertex count, `e` the number of edges and `a`, `b`, `c`, `d`, ..., `y` and `z` are edges between `a` and `b`, `c` and `d`, ..., and `y` and `z` respectively, and `wN` is the weight of that edge.
func (*WeightGraph) AddEdge ¶
func (wg *WeightGraph) AddEdge(e Edge)
AddEdge adds weigthed edge e to this graph
func (*WeightGraph) Adj ¶
func (wg *WeightGraph) Adj(v int) []Edge
Adj gives the edges incident to v
func (*WeightGraph) Edges ¶
func (wg *WeightGraph) Edges() []Edge
Edges gives all the edges in this graph
func (*WeightGraph) GoString ¶
func (wg *WeightGraph) GoString() string
GoString represents this weighted graph
Source Files
Directories