graffiti

Graffiti is generic graph library written in Go.

Prerequisites

• An installation of Go 1.18 or later (graffiti uses generics)

Features

Data structures

The Graph interface provides an abstract capability description of a graph:

type Graph[N any, E IHalfEdge] interface {
    NodeCount() int
    EdgeCount() int
    GetNode(id NodeId) N
    GetHalfEdgesFrom(id NodeId) []E
}

There are currently two implementations of the Graph interface:

• Adjacency List
• Adjacency Array

Shortest path algorithms

Shortest path algorithms aim at finding the shortest path between a source and a target node in a weighted graph. Graffiti implements Dijkstra's algorithm, which serves as a baseline. Beside that, the following speed-up techniques as well as the required preprocessing steps or heuristics (if applicable) are implemented:

• Bidirectional Dijkstra's algorithm
• A* search algorithm
  • Haversine Heuristic
  • ALT (A*, landmarks and triangular inequalities)
• Bidirectional A* search algorithm
• Dijkstra's algorithm with arc flags
• Bidirectional Dijkstra's algorithm with arc flags
• Dijkstra's algorithm with two-level arc flags
• Combination of A* search algorithm with arcflags
  • unidirectional A* search to avoid cumbersome stopping criterion
  • incorporates bidirectional arcflags

Demo

The osm-ship-routing repository features a REST-API for global ship navigation. The underlying graph is represented by graffiti's AdjacencyArrayGraph data structure and the graph search calls graffiti's BidirectionalArcFlagRouter.

License

Graffiti is licensed under the MIT License.

SPDX-License-Identifier: MIT