Graffiti is generic graph library written in Go.

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

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

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.

Graffiti is licensed under the MIT License.

SPDX-License-Identifier: MIT