A Scala 3 graph algorithms library built on the Visitor typeclass traversal engine.

Gryphon provides clean, purely functional implementations of the classic graph algorithms from Sedgewick & Wayne, Algorithms (4th ed.), Chapter 4. All algorithms are implemented using Scala 3 idioms — typeclasses, given/using, and clean architectural separation between graph structure and traversal logic.

Gryphon is intended as an artefact of the DSAIPG repository that supports the author's own textbook Data Structures, Algorithms, and Invariants - a Practical Guide (published by Cognella).

However, in version 1.0.0, there are no Java interface methods.

Add Gryphon to your build.sbt:

libraryDependencies += "com.phasmidsoftware" %% "gryphon" % "1.0.0"

Gryphon requires Scala 3 and depends on Visitor (com.phasmidsoftware %% visitor), which is pulled in automatically.

Gryphon implements all eleven graph algorithms from Chapter 4 of Sedgewick & Wayne, Algorithms (4th ed.):

Additionally, some algorithms and graph properties that are not directly covered in that chapter:

• Cycle detection — Graph.isCyclic (undirected and directed)
• Bipartite checking — UndirectedGraph.isBipartite
• Connectivity — UndirectedGraph.isConnected
• Degree statistics — UndirectedGraph.degree, maxDegree, meanDegree
• Self-loop count — EdgeGraph.numberOfSelfLoops
• Union-Find — UnionFind, WeightedUnionFind (used internally by Kruskal)
• Graph reversal — DirectedGraph.reverse (used internally by Kosaraju)

Gryphon supports two concrete graph types, both backed by a VertexMap:

// Directed weighted graph
val g: DirectedGraph[Int, Double] = DirectedGraph.triplesToTryGraph(...).get

// Undirected weighted graph
val g: UndirectedGraph[Int, Double] = UndirectedGraph.triplesToTryGraph(...).get

Graphs are constructed from sequences of Triplet[V, E, EdgeType], typically parsed from a graph file using GraphParser:

val p = new GraphParser[Int, Double, EdgeType]
val triplets = TryUsing.tryIt(Try(Source.fromResource("mygraph.graph"))) { source =>
  p.parseSource[Triplet[Int, Double, EdgeType]](p.parseTriple)(source)
}.get
val graph = DirectedGraph.triplesToTryGraph[Int, Double](Vertex.createWithSet)(triplets).get

Graph files use a simple line-based format. Lines beginning with // are comments.

// Directed weighted graph
0 > 1 0.5
1 > 2 1.2
2 > 0 0.8

// Undirected weighted graph
0 = 1 0.16
1 = 2 0.19

The separator > means directed; = means undirected.

given Evaluable[Int, Int] with
  def evaluate(v: Int): Option[Int] = Some(v)

val visitor = JournaledVisitor.withQueueJournal[Int, Int]

// DFS from vertex 0
val dfsResult = graph.dfs(visitor)(0)
val visited = dfsResult.result.map(_._1).toSet

// BFS from vertex 0
val bfsResult = graph.bfs(visitor)(0)

// DFS over all components
val allVisited = graph.dfsAll(visitor).result.map(_._1).toSet

TopologicalSort.sort(dag) match
  case Some(order) => println(s"Topological order: $order")
  case None        => println("Graph contains a cycle")

given Monoid[Double] with
  def empty: Double = 0.0
  def combine(x: Double, y: Double): Double = x + y
given Ordering[Double] = scala.math.Ordering.Double.TotalOrdering

val result = ShortestPaths.dijkstra(graph, 0)
result.vertexTraverse(5).foreach(e => println(s"Shortest edge into 5: $e"))

val result = AcyclicShortestPaths.shortestPaths(dag, 0)
result.vertexTraverse(3).foreach(e => println(s"Shortest edge into 3: $e"))

BellmanFord.shortestPaths(graph, 0) match
  case Some(result) => result.vertexTraverse(3).foreach(println)
  case None         => println("Negative cycle detected")

val mstEdges: Seq[Edge[Double, Int]] = Kruskal.mst(undirectedGraph)
val totalWeight = mstEdges.map(_.attribute).sum

val sccResult: SCCResult[Int] = Kosaraju.components(directedGraph)
// sccResult maps each vertex to its SCC id
val numSCCs = sccResult.values.toSet.size

graph.isCyclic          // Boolean
graph.isBipartite       // Boolean (undirected only)
graph.isConnected       // Boolean (undirected only)
graph.degree(v)         // Int (undirected only)
graph.maxDegree         // Int (undirected only)
graph.meanDegree        // Double (undirected only) — equals 2*M/N
graph.numberOfSelfLoops // Int

Gryphon is structured in four layers:

com.phasmidsoftware.gryphon
  .core       — Graph, VertexMap, Vertex, Edge, Adjacency, Connexion,
                Connected, Traversable, EdgeTraversable
  .adjunct    — DirectedGraph, UndirectedGraph, DirectedEdge,
                UndirectedEdge, DisjointSet, UnionFind, WeightedUnionFind
  .traverse   — ConnectedComponents, Kosaraju, TopologicalSort,
                ShortestPaths, AcyclicShortestPaths, BellmanFord,
                Kruskal, TraversalResult, Connexions
  .parse      — GraphParser, BaseParser, Parseable

The traversal engine lives in the separate Visitor library, which provides the five orthogonal typeclasses that drive all traversals: Evaluable[V, R], Neighbours[H, V], VisitedSet[V], Frontier[F[_]], and Visitor[V, R, J].

• Scala 3 throughout — typeclasses with given/using, enum, type aliases, context bounds, and clean separation of concerns.
• Purely functional results — all algorithms return immutable result types; any internal mutable state is strictly local to the algorithm.
• Consistent type parameter ordering — V (vertex type) always precedes E (edge attribute type) throughout the API.
• E: {Monoid, Ordering} — edge weight constraints use Visitor's Monoid rather than Numeric, keeping the constraint as light as possible.
• No default implementations — abstract methods on Graph[V] are always abstract, forcing each graph type to provide a correct concrete implementation.

The library has 365 tests covering all algorithms, graph properties, and edge cases including:

• Disconnected graphs and forests
• Negative edge weights (Bellman–Ford, AcyclicShortestPaths)
• Negative cycle detection
• Self-loops
• Agreement between Bellman–Ford and Dijkstra on non-negative graphs
• Agreement between Prim and Kruskal on MST weight

sbt test

This project is licensed under the MIT License — see the LICENSE file for details.

• Visitor — the typeclass-based graph traversal engine that Gryphon builds on
• Number — complex number support (planned for a future quantum computing library)
• TableParser — tabular data parsing used in Northeastern University coursework