DOCSEARCHbyAlgolia
Submit Docs

graph

repository·main·Indexed 24 days ago

https://github.com/dominikbraun/graph

A generic Go library for creating, modifying, analyzing, and visualizing graph data structures. It supports any vertex type via custom hash functions and provides built-in algorithms including Depth-First Search (DFS), Strongly Connected Components, Shortest Path, Minimum Spanning Tree, Topological Sort, and Transitive Reduction. The library supports directed, acyclic, and weighted graphs, allows for custom storage backends via the Store interface, and provides Graphviz export capabilities through the graph/draw package.

Tokens
8.4K
Snippets
36
Records
65
Agent score
79%

What's inside graph

  1. Create a graph with custom types and hashes

    main

    The graph.New function requires a hash function to identify vertices. For built-in types like int, you can use graph.IntHash. For custom types, you must provide a function that returns a unique identifier (e.g., a string) for each instance of that type.

    type City struct {
    Name string
}

cityHash := func(c City) string {
    return c.Name
}

g := graph.New(cityHash)

_ = g.AddVertex(london)

  2. Implement a custom storage backend

    main

    You can use a custom storage engine by implementing the Store interface and initializing the graph with graph.NewWithStore(hashFunc, myStore). For a SQL-based implementation, see the graph-sql package.

    g := graph.NewWithStore(graph.IntHash, myStore)

  3. Configure graph traits (Directed, Acyclic, Weighted)

    main

    You can pass functional options to graph.New to define the properties of the graph. Common options include:

    • graph.Directed(): Creates a directed graph.
    • graph.Acyclic(): Creates an acyclic graph.
    • graph.PreventCycles(): Enables validation to prevent adding edges that would create a cycle.
    • graph.Weighted(): Enables support for edge weights.

  4. Visualize a graph using Graphviz

    main

    The graph/draw package allows you to export your graph to the DOT language. You can then use the Graphviz dot command to render it as an image (e.g., SVG).

    1. Generate the .gv file in Go: _ = draw.DOT(g, file)
    2. Render using CLI: dot -Tsvg -O mygraph.gv
    import (
	"github.com/dominikbraun/graph"
	"github.com/dominikbraun/graph/draw"
)

// ...
file, _ := os.Create("./mygraph.gv")
_ = draw.DOT(g, file)

  5. Visualize a graph using Graphviz (DOT)

    main

    The graph/draw package allows you to export your graph to the DOT language. You can then use the Graphviz dot command to render it as an SVG or other formats.

    To render an SVG from a generated .gv file:

    dot -Tsvg -O mygraph.gv

    To use the neato engine:

    dot -Tsvg -Kneato -O simple.gv
    file, _ := os.Create("./mygraph.gv")
_ = draw.DOT(g, file)

  7. How vertices and hashes work in graph

    main

    A graph consists of vertices of type T, which are uniquely identified by a hash value of type K.

    • The hash value is obtained using the hashing function passed to graph.New.
    • Most graph operations (like AddEdge, RemoveVertex, Vertex) accept and return the hash value (K) rather than the vertex instance (T).
    • For example, in a graph of integers using graph.IntHash, the vertex value and the hash value are identical.

  8. Configure graph traits using functional options

    main

    When creating a graph using graph.New, you can specify its properties (like being directed, weighted, or acyclic) by passing functional options. These options modify a Traits struct which governs how the graph behaves and how certain functions like Edge or AddEdge interpret their arguments.

    Common traits include:

    • Directed(): Sets IsDirected to true. Affects traversal and argument order in edge functions.
    • Acyclic(): Sets IsAcyclic to true. Note that this does not automatically prevent cycles; it simply marks the graph as acyclic.
    • Weighted(): Sets IsWeighted to true. Enables the use of weights via Edge and AddEdge functions.
    • Rooted(): Sets IsRooted to true. Useful for tree-like structures.
    • Tree(): A convenience alias that applies both Acyclic() and Rooted().
    • PreventCycles(): Applies Acyclic() and sets PreventCycles to true. This proactively prevents the creation of cycles during operations like AddEdge, though it may impact performance.

  9. Use the default in-memory Store

    main
    The library provides a memoryStore implementation of the Store[K, T] interface. While the memoryStore type is unexported, you can typically obtain a store instance through the library's graph constructors (which use newMemoryStore internally). The in-memory store is thread-safe, using a sync.RWMutex to manage concurrent access to vertices and edges.

  10. Initialize a new graph

    main

    To create a new graph, use graph.New. You must provide a hashing function that maps your vertex type T to a comparable hash type K.

    For primitive types, you can use predefined functions like graph.IntHash or graph.StringHash. For custom types, define your own Hash[K, T] function.

    Example for integers:

    g := graph.New(graph.IntHash)

    Example for custom types:

    type City struct {
	Name string
}

cityHash := func(c City) string {
	return c.Name
}

g := graph.New(cityHash)

  11. Create a weighted graph

    main

    To support edge weights, initialize the graph with the graph.Weighted() option. Use graph.EdgeWeight(value) when calling AddEdge or UpdateEdge to assign weights.

    g := graph.New(cityHash, graph.Weighted())

_ = g.AddVertex(london)
_ = g.AddVertex(munich)
_ = g.AddEdge("london", "munich", graph.EdgeWeight(3))

  12. Create a Directed Acyclic Graph (DAG)

    main

    To create a DAG, pass graph.Directed() and graph.Acyclic() as options to graph.New. This ensures the graph is directed and prevents the creation of cycles.

    g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())

_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddEdge(1, 2)