ProductPromotion
Logo

Go.Lang

made by https://0x3d.site

GitHub - yourbasic/graph: Graph algorithms and data structures
Graph algorithms and data structures. Contribute to yourbasic/graph development by creating an account on GitHub.
Visit Site

GitHub - yourbasic/graph: Graph algorithms and data structures

GitHub - yourbasic/graph: Graph algorithms and data structures

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

Articles
to learn more about the golang concepts.

Resources
which are currently available to browse on.

mail [email protected] to add your project or resources here 🔥.

FAQ's
to know more about the topic.

mail [email protected] to add your project or resources here 🔥.

Queries
or most google FAQ's about GoLang.

mail [email protected] to add more queries here 🔍.

More Sites
to check out once you're finished browsing here.

0x3d
https://www.0x3d.site/
0x3d is designed for aggregating information.
NodeJS
https://nodejs.0x3d.site/
NodeJS Online Directory
Cross Platform
https://cross-platform.0x3d.site/
Cross Platform Online Directory
Open Source
https://open-source.0x3d.site/
Open Source Online Directory
Analytics
https://analytics.0x3d.site/
Analytics Online Directory
JavaScript
https://javascript.0x3d.site/
JavaScript Online Directory
GoLang
https://golang.0x3d.site/
GoLang Online Directory
Python
https://python.0x3d.site/
Python Online Directory
Swift
https://swift.0x3d.site/
Swift Online Directory
Rust
https://rust.0x3d.site/
Rust Online Directory
Scala
https://scala.0x3d.site/
Scala Online Directory
Ruby
https://ruby.0x3d.site/
Ruby Online Directory
Clojure
https://clojure.0x3d.site/
Clojure Online Directory
Elixir
https://elixir.0x3d.site/
Elixir Online Directory
Elm
https://elm.0x3d.site/
Elm Online Directory
Lua
https://lua.0x3d.site/
Lua Online Directory
C Programming
https://c-programming.0x3d.site/
C Programming Online Directory
C++ Programming
https://cpp-programming.0x3d.site/
C++ Programming Online Directory
R Programming
https://r-programming.0x3d.site/
R Programming Online Directory
Perl
https://perl.0x3d.site/
Perl Online Directory
Java
https://java.0x3d.site/
Java Online Directory
Kotlin
https://kotlin.0x3d.site/
Kotlin Online Directory
PHP
https://php.0x3d.site/
PHP Online Directory
React JS
https://react.0x3d.site/
React JS Online Directory
Angular
https://angular.0x3d.site/
Angular JS Online Directory