Graph algorithms and data structures

Overview

Your basic graph GoDoc

Golang library of basic graph algorithms

Topological ordering

Topological ordering, image by David Eppstein, CC0 1.0.

This library offers efficient and well-tested algorithms for

  • breadth-first and depth-first search,
  • topological ordering,
  • strongly and weakly connected components,
  • bipartion,
  • shortest paths,
  • maximum flow,
  • Euler walks,
  • and minimum spanning trees.

The algorithms 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.

Graph data structures

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.

Virtual graphs

The subpackage graph/build offers a tool for building graphs of type Virtual.

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 following standard graphs are predefined:

  • empty graphs,
  • complete graphs and complete bipartite graphs,
  • grid graphs and complete k-ary trees,
  • cycle graphs and circulant graphs,
  • and hypergraphs.

The following operations are supported:

  • adding and deleting sets of edges,
  • adding cost functions,
  • filtering graphs by edge functions,
  • complement, intersection and union,
  • subgraphs,
  • connecting graphs at a single vertex,
  • joining two graphs by a set of edges,
  • matching two graphs by a set of edges,
  • cartesian product and tensor product.

Non-virtual graphs can be imported, and used as building blocks, by the Specific function. Virtual graphs don't need to be “exported‬”; they implement the Iterator interface and hence can be used directly by any algorithm in the graph package.

Installation

Once you have installed Go, run this command to install the graph package:

go get github.com/yourbasic/graph

Documentation

There is an online reference for the package at godoc.org/github.com/yourbasic/graph.

Roadmap

  • The API of this library is frozen.
  • Bug fixes and performance enhancement can be expected.
  • New functionality might be included.
  • Version numbers adhere to semantic versioning.

The only accepted reason to modify the API of this package is to handle issues that can't be resolved in any other reasonable way.

New features and performance enhancements are limited to basic algorithms and data structures, akin to the ones that you might find in a computer science textbook.

Stefan Nilsson – korthaj

You might also like...
Graph algorithms written in Go

Graph Algorithms in Go This repository contains implementations of various graph algorithms written in Go. I’ve written them to learn about these algo

Some algorithms in go: maxflow(min-cuts or graph-cuts), edit-distance.

Algorithms In this repository, some algorithms are implemented in go language. GoDoc link: ed maxflow About Max-flow problem: A flow network is repres

Graphoscope: a solution to access multiple independent data sources from a common UI and show data relations as a graph
Graphoscope: a solution to access multiple independent data sources from a common UI and show data relations as a graph

Graphoscope A solution to access multiple independent data sources from a common UI and show data relations as a graph: Contains a list of by default

Tutorial code for my video Learn to Use Basic Data Structures - Slices, Structs and Maps in Golang

Learn to Use Basic Data Structures - Slices, Structs and Maps in Golang Read text from a file and split into words. Introduction to slices / lists. Co

 A tree like tool help you to explore data structures in your redis server
A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

Probabilistic data structures for processing continuous, unbounded streams.

Boom Filters Boom Filters are probabilistic data structures for processing continuous, unbounded streams. This includes Stable Bloom Filters, Scalable

GoDS (Go Data Structures). Containers (Sets, Lists, Stacks, Maps, Trees), Sets (HashSet, TreeSet, LinkedHashSet), Lists (ArrayList, SinglyLinkedList, DoublyLinkedList), Stacks (LinkedListStack, ArrayStack), Maps (HashMap, TreeMap, HashBidiMap, TreeBidiMap, LinkedHashMap), Trees (RedBlackTree, AVLTree, BTree, BinaryHeap), Comparators, Iterators, Enumerables, Sort, JSON
This is the course materials for the Go Data Structures Crash Course!

Go Data Structures Course 👋 Welcome Gophers! This is the official repository that contains all of the data structures we cover in the Go Data Structu

Basic Implementation of Data-structures in Go

Data structures in Go v1.15.6 This repo consists the implementation of the following: Stacks Queues Linked Lists (Singly) Binary Search Trees Heaps (M

Comments
  • Detect cycles

    Detect cycles

    I apologies if your pkg can already do this, but I was perusing your docs and didn't see an easy way to. I'd like to tell which vertices contain cycles or paths back to themselves.

    I do know that you can tell me quickly if it is Acyclic, but I'd like to know which nodes have cycles.

    Is that possible and if not how would on add that?

    Thank you!

    opened by blacktop 1
  • ShortestPath memory improvement

    ShortestPath memory improvement

    Hi Korthaj, when i was using the ShortestPath function i noticed that it was using a significant amount of memory (I was processing a large graph). It seems that the closure is allocated (or a pointer to it) at each iteration of the loop which makes the function use more memory.

    name             old time/op    new time/op    delta
    ShortestPaths-8     154µs ± 0%      85µs ± 0%  -45.02%
    
    name             old alloc/op   new alloc/op   delta
    ShortestPaths-8    81.0kB ± 0%    41.1kB ± 0%  -49.26%
    
    name             old allocs/op  new allocs/op  delta
    ShortestPaths-8       849 ± 0%        17 ± 0%  -98.00%
    

    This package and your blog are awsome.

    -Rodrigo

    opened by rschio 4
  • Make ShortestPath faster

    Make ShortestPath faster

    I noticed that the performance of ShortestPath can be substantially improved. Instead of finding all the shortest paths from the initial vertex, we could terminate the search as soon as we found the path to the destination vertex.

    I've opened a pull request because I already have a patch.

    1. No API changes whatsoever;
    2. This performance enhancement is based on the original E. W. Dijkstra's paper (it's what should be found in a CS textbook).

    old/new comparison:

    benchmark                       old ns/op     new ns/op     delta
    BenchmarkShortestPath250-4      55089         31078         -43.59%
    BenchmarkShortestPath500-4      121956        51563         -57.72%
    BenchmarkShortestPath1000-4     206507        79512         -61.50%
    
    opened by amwolff 3
Releases(1.0.5)
Owner
Algorithms to Go
Code should be correct, clear and efficient. Prefer simple. Avoid clever.
Algorithms to Go
Algorithms and Data Structures Solved in Golang

Algorithms and Data Structures Solved in Golang Hi! I'm Bruno Melo and this repository contains a lot challenges solved on many plataforms using go as

Bruno Melo 3 Aug 13, 2022
Some data structures and algorithms using golang

Some data structures and algorithms using golang

null 62 Aug 13, 2022
Data structures and algorithms implementation from ZeroToMastery course

ZeroToMastery Data Structures & Algorithms course This repo includes all the data structure and algorithm exercises solutions and implementations. Ins

Fabio Bozzo 3 Jul 4, 2022
Practice-dsa-go - Data Structures and Algorithms for Interview Preparation in Go

Data Structures and Algorithms for Interview Preparation in Go Data Structures K

Sparsh Srivastava 2 Jul 3, 2022
Implementation of various data structures and algorithms in Go

GoDS (Go Data Structures) Implementation of various data structures and algorithms in Go. Data Structures Containers Lists ArrayList SinglyLinkedList

TopXeQ 0 Jan 25, 2022
Data Structures and Algorithms implementation in Go

Data Structures and Algorithms Clean and simple implementation in Go Implementation There are several data structures and algorithms implemented in th

Mykyta Paliienko 2.5k Sep 23, 2022
Data Structures & Algorithms in Go

Data Structures and Algorithms with Go The aim of this repository is to provide Gophers with how data structures and algorithms are implemented in the

Chris Gonzalez 0 Dec 28, 2021
Grokking-algorithms-go - Solutions to common Data Structures problems

This is a repository dedicated to study, learn and solve Data Structure algorith

Gabriel Magalhães 0 Apr 4, 2022
Golang string comparison and edit distance algorithms library, featuring : Levenshtein, LCS, Hamming, Damerau levenshtein (OSA and Adjacent transpositions algorithms), Jaro-Winkler, Cosine, etc...

Go-edlib : Edit distance and string comparison library Golang string comparison and edit distance algorithms library featuring : Levenshtein, LCS, Ham

Hugo Bollon 361 Sep 27, 2022
Go translations of the algorithms and clients in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Overview Go translations of the Java source code for the algorithms and clients in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin

youngzy 170 Oct 1, 2022