github.com/dominikbraun/graph
Package graph is a library for creating generic graph data structures and modifying, analyzing, and visualizing them. A graph consists of vertices of type T, which are identified by a hash value of type K. The hash value for a given vertex is obtained using the hashing function passed to New. A hashing function takes a T and returns a K. For primitive types like integers, you may use a predefined hashing function such as IntHash – a function that takes an integer and uses that integer as the hash value at the same time: For storing custom data types, you need to provide your own hashing function. This example takes a City instance and returns its name as the hash value: Creating a graph using this hashing function will yield a graph of vertices of type City identified by hash values of type string. Adding vertices to a graph of integers is simple. graph.Graph.AddVertex takes a vertex and adds it to the graph. Most functions accept and return only hash values instead of entire instances of the vertex type T. For example, graph.Graph.AddEdge creates an edge between two vertices and accepts the hash values of those vertices. Because this graph uses the IntHash hashing function, the vertex values and hash values are the same. All operations that modify the graph itself are methods of Graph. All other operations are top-level functions of by this library. For detailed usage examples, take a look at the README.
Readme
A library for creating generic graph data structures and modifying, analyzing, and visualizing them.
Are you using graph? Check out the graph user survey.
int
or City
.Store
implementation.Status: Because
graph
is in version 0, the public API shouldn't be considered stable.
This README may contain unreleased changes. Check out the latest documentation.
go get github.com/dominikbraun/graph
g := graph.New(graph.IntHash)
_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)
_ = g.AddVertex(4)
_ = g.AddVertex(5)
_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 4)
_ = g.AddEdge(2, 3)
_ = g.AddEdge(2, 4)
_ = g.AddEdge(2, 5)
_ = g.AddEdge(3, 5)
g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())
_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)
_ = g.AddVertex(4)
_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
_ = g.AddEdge(2, 3)
_ = g.AddEdge(2, 4)
_ = g.AddEdge(3, 4)
To understand this example in detail, see the concept of hashes.
type City struct {
Name string
}
cityHash := func(c City) string {
return c.Name
}
g := graph.New(cityHash)
_ = g.AddVertex(london)
g := graph.New(cityHash, graph.Weighted())
_ = g.AddVertex(london)
_ = g.AddVertex(munich)
_ = g.AddVertex(paris)
_ = g.AddVertex(madrid)
_ = g.AddEdge("london", "munich", graph.EdgeWeight(3))
_ = g.AddEdge("london", "paris", graph.EdgeWeight(2))
_ = g.AddEdge("london", "madrid", graph.EdgeWeight(5))
_ = g.AddEdge("munich", "madrid", graph.EdgeWeight(6))
_ = g.AddEdge("munich", "paris", graph.EdgeWeight(2))
_ = g.AddEdge("paris", "madrid", graph.EdgeWeight(4))
This example traverses and prints all vertices in the graph in DFS order.
g := graph.New(graph.IntHash, graph.Directed())
_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)
_ = g.AddVertex(4)
_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
_ = g.AddEdge(3, 4)
_ = graph.DFS(g, 1, func(value int) bool {
fmt.Println(value)
return false
})
1 3 4 2
g := graph.New(graph.IntHash)
// Add vertices and edges ...
scc, _ := graph.StronglyConnectedComponents(g)
fmt.Println(scc)
[[1 2 5] [3 4 8] [6 7]]
g := graph.New(graph.StringHash, graph.Weighted())
// Add vertices and weighted edges ...
path, _ := graph.ShortestPath(g, "A", "B")
fmt.Println(path)
[A C E B]
g := graph.New(graph.StringHash, graph.Weighted())
// Add vertices and edges ...
mst, _ := graph.MinimumSpanningTree(g)
g := graph.New(graph.IntHash, graph.Directed(), graph.PreventCycles())
// Add vertices and edges ...
// For a deterministic topological ordering, use StableTopologicalSort.
order, _ := graph.TopologicalSort(g)
fmt.Println(order)
[1 2 3 4 5]
g := graph.New(graph.StringHash, graph.Directed(), graph.PreventCycles())
// Add vertices and edges ...
transitiveReduction, _ := graph.TransitiveReduction(g)
g := graph.New(graph.IntHash, graph.PreventCycles())
_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)
_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
if err := g.AddEdge(2, 3); err != nil {
panic(err)
}
panic: an edge between 2 and 3 would introduce a cycle
The following example will generate a DOT description for g
and write it into the given file.
g := graph.New(graph.IntHash, graph.Directed())
_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)
_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
file, _ := os.Create("./mygraph.gv")
_ = draw.DOT(g, file)
To generate an SVG from the created file using Graphviz, use a command such as the following:
dot -Tsvg -O mygraph.gv
The DOT
function also supports rendering graph attributes:
_ = draw.DOT(g, file, draw.GraphAttribute("label", "my-graph"))
This graph has been rendered using the following program:
package main
import (
"os"
"github.com/dominikbraun/graph"
"github.com/dominikbraun/graph/draw"
)
func main() {
g := graph.New(graph.IntHash)
_ = g.AddVertex(1, graph.VertexAttribute("colorscheme", "blues3"), graph.VertexAttribute("style", "filled"), graph.VertexAttribute("color", "2"), graph.VertexAttribute("fillcolor", "1"))
_ = g.AddVertex(2, graph.VertexAttribute("colorscheme", "greens3"), graph.VertexAttribute("style", "filled"), graph.VertexAttribute("color", "2"), graph.VertexAttribute("fillcolor", "1"))
_ = g.AddVertex(3, graph.VertexAttribute("colorscheme", "purples3"), graph.VertexAttribute("style", "filled"), graph.VertexAttribute("color", "2"), graph.VertexAttribute("fillcolor", "1"))
_ = g.AddVertex(4, graph.VertexAttribute("colorscheme", "ylorbr3"), graph.VertexAttribute("style", "filled"), graph.VertexAttribute("color", "2"), graph.VertexAttribute("fillcolor", "1"))
_ = g.AddVertex(5, graph.VertexAttribute("colorscheme", "reds3"), graph.VertexAttribute("style", "filled"), graph.VertexAttribute("color", "2"), graph.VertexAttribute("fillcolor", "1"))
_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 4)
_ = g.AddEdge(2, 3)
_ = g.AddEdge(2, 4)
_ = g.AddEdge(2, 5)
_ = g.AddEdge(3, 5)
file, _ := os.Create("./simple.gv")
_ = draw.DOT(g, file)
}
It has been rendered using the neato
engine:
dot -Tsvg -Kneato -O simple.gv
The example uses the Brewer color scheme supported by Graphviz.
Edges may have one or more attributes which can be used to store metadata. Attributes will be taken into account when visualizing a graph. For example, this edge will be rendered in red color:
_ = g.AddEdge(1, 2, graph.EdgeAttribute("color", "red"))
To get an overview of all supported attributes, take a look at the DOT documentation.
The stored attributes can be retrieved by getting the edge and accessing the Properties.Attributes
field.
edge, _ := g.Edge(1, 2)
color := edge.Properties.Attributes["color"]
It is also possible to store arbitrary data inside edges, not just key-value string pairs. This data
is of type any
.
_ = g.AddEdge(1, 2, graph.EdgeData(myData))
The stored data can be retrieved by getting the edge and accessing the Properties.Data
field.
edge, _ := g.Edge(1, 2)
myData := edge.Properties.Data
Edge properties can be updated using Graph.UpdateEdge
. The following example adds a new color
attribute to the edge (A,B) and sets the edge weight to 10.
_ = g.UpdateEdge("A", "B", graph.EdgeAttribute("color", "red"), graph.EdgeWeight(10))
The method signature and the accepted functional options are exactly the same as for Graph.AddEdge
.
Vertices may have one or more attributes which can be used to store metadata. Attributes will be taken into account when visualizing a graph. For example, this vertex will be rendered in red color:
_ = g.AddVertex(1, graph.VertexAttribute("style", "filled"))
The stored data can be retrieved by getting the vertex using VertexWithProperties
and accessing
the Attributes
field.
vertex, properties, _ := g.VertexWithProperties(1)
style := properties.Attributes["style"]
To get an overview of all supported attributes, take a look at the DOT documentation.
You can integrate any storage backend by implementing the Store
interface and initializing a new
graph with it:
g := graph.NewWithStore(graph.IntHash, myStore)
To implement the Store
interface appropriately, take a look at the documentation.
graph-sql
is a ready-to-use SQL store implementation.
The full documentation is available at pkg.go.dev.
Are you using graph? Check out the graph user survey.
FAQs
Package graph is a library for creating generic graph data structures and modifying, analyzing, and visualizing them. A graph consists of vertices of type T, which are identified by a hash value of type K. The hash value for a given vertex is obtained using the hashing function passed to New. A hashing function takes a T and returns a K. For primitive types like integers, you may use a predefined hashing function such as IntHash – a function that takes an integer and uses that integer as the hash value at the same time: For storing custom data types, you need to provide your own hashing function. This example takes a City instance and returns its name as the hash value: Creating a graph using this hashing function will yield a graph of vertices of type City identified by hash values of type string. Adding vertices to a graph of integers is simple. graph.Graph.AddVertex takes a vertex and adds it to the graph. Most functions accept and return only hash values instead of entire instances of the vertex type T. For example, graph.Graph.AddEdge creates an edge between two vertices and accepts the hash values of those vertices. Because this graph uses the IntHash hashing function, the vertex values and hash values are the same. All operations that modify the graph itself are methods of Graph. All other operations are top-level functions of by this library. For detailed usage examples, take a look at the README.
We found that github.com/dominikbraun/graph demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 0 open source maintainers collaborating on the project.
Did you know?
Socket installs a GitHub app to automatically flag issues on every pull request and report the health of your dependencies. Find out what is inside your node modules and prevent malicious activity before you update the dependencies.