# Graph algorithms written in Go

### Related tags

Data Structures graphs

# Graph Algorithms in Go

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

## Implemented

• Data structues
• Graph and Digraph
• Flow network
• Set
• Sorting algorithms
• Spanning tree algorithms
• Shortest path algorithms
• Search algorithms
• Connected components algorithms
• Network algorithms
• Residual network

## Contributors

• #### Flaky test: dfs_test.go

The second test sometimes passes, sometimes fails. `t.Errorf("should visit 5 vertices; visited %d", walks)`

The stopping condition is

``````        if v == 5 {
*stop = true
}
``````

This means that if you reach vertex 5, then the walk should terminate. It's sure that we won't seen node 6 in this case, but there is no guarantee that we have already visited node 7. It depends on go's internal ordering of map keys.

opened by gszjulcsi 1
• #### Implementing topological sorting is not possible

I'm quite new to golang, pointers and topological sorting, so I could be quite wrong in my analysis, so please excuse any incorrectness.

I am working on some graph algorithms, and I decided to use your code as a base. In particular, I'm interested in implementing topological sorting which happens to be missing from this git repo!

I tried to implement the 1962 algorithm described here: https://en.wikipedia.org/wiki/Topological_sorting

For this algorithm, it seems you need to be able to "mark" vertexes. Since your Vertex doesn't have additional storage fields, I tried using my own type:

``````type Node struct {
Name    string
Comment string
Marking string
}
``````

I was able to make this work, until I got to actually setting the markings. I think the reason is that throughout your code, your pass around copies of the Vertex value, as opposed to references (pointers) of it. As a result, every time I set the struct value, it is not seen, since I've only made my changes on a copy.

My knowledge of pointers is quite weak, so if I've misunderstood this, please let me know!

Solutions:

1. Fix this graph library so that Vertex's are passed around by pointer (reference) so that this isn't an issue.
2. Maintain a separate map of unique Vertex identifier to the Node struct I want, and always do lookups/setters on this mapping. I don't think this is a very elegant.
3. I've greatly misunderstood this go code, pointers, and everything else.

Additional goals: I'd like to store additional data associated with each Vertex. If I'm able to do this with this library, that's great, but at the moment it seems to be difficult.

If there is a more appropriate library that I should be using for graph operations in golang, please let me know!

opened by purpleidea 1
• #### Revise TopologicalSort API

``````package main

import (
"fmt"
"github.com/thcyron/graphs"
)

func main() {
graph := graphs.NewDigraph()
list, _, err := graphs.TopologicalSort(graph)
if err != nil {
panic(err)
}
for e := list.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}
``````

I discarded the second return value, I suspect many people will not need that. Would you consider revising the API?

opened by 89z 0
##### Releases(v5.8.3)
###### 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

14 Apr 9, 2021
###### Graph algorithms and data structures

Your basic graph Golang library of basic graph algorithms Topological ordering, image by David Eppstein, CC0 1.0. This library offers efficient and we

9 Jan 25, 2021
###### 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

329 Jun 21, 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

167 May 28, 2022
###### Common algorithms written in Go.

Common Algorithms in Go This repository contains a collection of a variety of common algorithms implemented using Go. Algorithms Implemented Search Li

1 Dec 28, 2021
###### This repo is where I'll be attempting to capture some generic algorithms written in Go

Go Generic Algorithms Welcome friends! ?? This repo is where I'll be attempting

27 Apr 13, 2022
###### Go framework to simplify CRUD of structured data using Graph operations

gocrud Go framework to simplify creating, reading, updating, and deleting arbitrary depth structured data — to make building REST services fast and ea

314 Jun 28, 2022
###### dagger is a fast, concurrency safe, mutable, in-memory directed graph library with zero dependencies

dagger is a blazing fast, concurrency safe, mutable, in-memory directed graph implementation with zero dependencies

258 Jun 23, 2022
###### graph package by golang

graph-go sample package main import ( "fmt" "github.com/Iovesophy/graph-go" ) func main() { samplePlace := []graph.Node{ {ID: 1, Element: "plac

4 Oct 24, 2021
###### A Connected Graph Generator tool that construct graphs of some given size

graph graph is a Connected Graph Generator tool that construct graphs of some given size. Notice that it generates all possible connected, undirected

0 Nov 5, 2021
###### 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

29 May 26, 2022

120 Jun 22, 2022
###### Go implementation of C++ STL iterators and algorithms.

iter Go implementation of C++ STL iterators and algorithms. Less hand-written loops, more expressive code. README translations: 简体中文 Motivation Althou

157 Jun 15, 2022
###### Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Trie Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. Usage Create a Trie with: t := trie.New() Add Keys with:

592 Jun 24, 2022
###### Data Structure Libraries and Algorithms implementation

Algorithms Data Structure Libraries and Algorithms implementation in C++ Disclaimer This repository is meant to be used as a reference to learn data s

634 Jun 10, 2022
###### fim is a collection of some popular frequent itemset mining algorithms implemented in Go.

fim fim is a collection of some popular frequent itemset mining algorithms implemented in Go. fim contains the implementations of the following algori

8 Jun 15, 2022
###### Data structure,Algorithms implemented in Go (for education)

Data structure,Algorithms implemented in Go (for education) List of Content : 1. Math - 2. String - 3. Conversions - 4. Sort - 5. Search - 6. Data str

4 Jun 10, 2022
###### Tree algorithms in Golang

Tree Algorithms in Golang This is my humble attempt to share some of the tree algorithms in Golang. Pull requests are always welcome! :) Contents Tree

3 Oct 6, 2021
###### 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

2 Feb 22, 2022