graph

Package graph contains generic implementations of basic graph algorithms. The algorithms in this library can be applied to any graph data structure implementing the two Iterator methods: Order, which returns the number of vertices, and Visit, which iterates over the neighbors of a vertex. All algorithms operate on directed graphs with a fixed number of vertices, labeled from 0 to n-1, and edges with integer cost. An undirected edge {v, w} of cost c is represented by the two directed edges (v, w) and (w, v), both of cost c. A self-loop, an edge connecting a vertex to itself, is both directed and undirected. The type Mutable represents a directed graph with a fixed number of vertices and weighted edges that can be added or removed. The implementation uses hash maps to associate each vertex in the graph with its adjacent vertices. This gives constant time performance for all basic operations. The type Immutable is a compact representation of an immutable graph. The implementation uses lists to associate each vertex in the graph with its adjacent vertices. This makes for fast and predictable iteration: the Visit method produces its elements by reading from a fixed sorted precomputed list. This type supports multigraphs. The subpackage graph/build offers a tool for building virtual graphs. In a virtual graph no vertices or edges are stored in memory, they are instead computed as needed. New virtual graphs are constructed by composing and filtering a set of standard graphs, or by writing functions that describe the edges of a graph. The Basics example shows how to build a plain graph and how to efficiently use the Visit iterator, the key abstraction of this package. The DFS example contains a full implementation of depth-first search. Build a plain graph and visit all of its edges. Show how to use this package by implementing a complete depth-first search.
1 version
Latest release: about 3 years ago

View more package details: https://packages.ecosyste.ms/registries/proxy.golang.org/packages/github.com/streamingfast/graph

View more repository details: http://repos.ecosyste.ms/hosts/GitHub/repositories/streamingfast%2Fgraph