Graph algorithms written in Go

Overview

Graph Algorithms in Go

Travis CI status

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

Implemented

Contributors

Issues
  • Flaky test: dfs_test.go

    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

    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!

    Thanks for reading, and I'd appreciate your comments. Cheers, James

    opened by purpleidea 1
  • Revise TopologicalSort API

    Revise TopologicalSort API

    I made this example:

    package main
    
    import (
       "fmt"
       "github.com/thcyron/graphs"
    )
    
    func main() {
       graph := graphs.NewDigraph()
       graph.AddEdge(2, 3, 0)
       graph.AddEdge(1, 2, 0)
       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

Yi Deng 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

Algorithms to Go 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

Hugo Bollon 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

youngzy 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

Broden Wanner 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

TutorialEdge 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

Manish R Jain 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

Coleman Word 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

Iovesophy 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

Nicolas A Perez 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

CERT.LV 29 May 26, 2022
:pushpin: State of the art point location and neighbour finding algorithms for region quadtrees, in Go

Region quadtrees in Go Region quadtrees and efficient neighbour finding techniques in Go Go-rquad proposes various implementations of region quadtrees

Aurélien Rainone 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

disksing 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:

Derek Parker 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

Priyank Chheda 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

Paul Fedorow 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

SkShahriarAhmedRaka 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

Arun Shaji 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

Bruno Melo 2 Feb 22, 2022