Gryphon
API
Generated with
Gryphon/com.phasmidsoftware.gryphon/com.phasmidsoftware.gryphon.traverse

com.phasmidsoftware.gryphon.traverse

package com.phasmidsoftware.gryphon.traverse

Members list

Type members

Classlikes

abstract class AbstractEdgeTraversalResult[T](ts: List[T]) extends TraversalResult[Int, T]

Abstract base class for edge traversal within a graph. This class supports traversing edges in a graph-like structure by providing a specific implementation for edge traversal while delegating the vertex traversal to throw an exception, as it is not applicable for edge-based traversal.

Abstract base class for edge traversal within a graph. This class supports traversing edges in a graph-like structure by providing a specific implementation for edge traversal while delegating the vertex traversal to throw an exception, as it is not applicable for edge-based traversal.

Type parameters

T

the type representing the result of the edge traversal

Value parameters

ts

a list of elements of type T representing traversal data, typically associated with edges

Attributes

Supertypes
trait TraversalResult[Int, T]
class Object
trait Matchable
class Any
Known subtypes
class EdgeTraversalResult[V, E, T]
abstract class AbstractVertexTraversalResult[V, T](map: Map[V, T]) extends TraversalResult[V, T]

Abstract base class for edge traversal within a graph. This class supports traversing edges in a graph-like structure by providing a specific implementation for edge traversal while delegating the vertex traversal to throw an exception, as it is not applicable for edge-based traversal.

Abstract base class for edge traversal within a graph. This class supports traversing edges in a graph-like structure by providing a specific implementation for edge traversal while delegating the vertex traversal to throw an exception, as it is not applicable for edge-based traversal.

Type parameters

T

the type representing the result of the edge traversal

V

the type representing a vertex in the graph

Value parameters

map

the underlying map of vertex -> T elements

Attributes

Supertypes
trait TraversalResult[V, T]
class Object
trait Matchable
class Any
Known subtypes
class Connexions[V, E]
class TopologicalSort[V]
class VertexTraversalResult[V, T]
object AcyclicShortestPaths

Computes shortest paths in a weighted DAG using topological relaxation.

Computes shortest paths in a weighted DAG using topological relaxation.

The algorithm:

  1. Topologically sort the DAG.
  2. Relax all outgoing edges of each vertex in topological order.

Since edges are relaxed in topological order, every predecessor of a vertex has already been processed when we reach it — guaranteeing optimal substructure without a priority queue. This gives O(V+E) time and correctly handles negative edge weights (unlike Dijkstra).

The edge-weight type E requires only a Monoid (for the zero distance and addition) and an Ordering (for comparison) — a lighter constraint than Numeric, consistent with RelaxableVertex and WeightedUnionFind.

NOTE: the graph must be a DAG. If it contains a cycle, TopologicalSort.sort returns None and this method throws IllegalArgumentException.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
case class BFSTraversal[V]() extends GraphTraversal[V, Unit, V]

Breadth-first search traversal. E = Unit, R = V. Each visited vertex maps to itself in the result.

Breadth-first search traversal. E = Unit, R = V. Each visited vertex maps to itself in the result.

Type parameters

V

the vertex type.

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait GraphTraversal[V, Unit, V]
class Object
trait Matchable
class Any
Show all
object BellmanFord

Computes shortest paths in a weighted directed graph using the Bellman-Ford-Moore algorithm (queue-based Bellman-Ford).

Computes shortest paths in a weighted directed graph using the Bellman-Ford-Moore algorithm (queue-based Bellman-Ford).

Unlike Dijkstra, this algorithm correctly handles negative edge weights. Unlike AcyclicShortestPaths, it works on graphs with cycles. It detects negative cycles reachable from the source and returns None in that case.

Algorithm (Bellman-Ford-Moore):

  1. Seed a queue with start at distance zero.
  2. Dequeue vertex v; for each outgoing edge v→w: if dist(w) > dist(v) + weight, relax and enqueue w (if not already queued).
  3. Track enqueue count per vertex — if any vertex is enqueued V times, a negative cycle is reachable → return None.
  4. Terminate when queue is empty → return Some(result).

Time complexity: O(VE) worst case, much faster in practice due to early termination.

The edge-weight type E requires Monoid (zero + combine) and Ordering (comparison) — consistent with AcyclicShortestPaths.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
object Boruvka

Computes the minimum spanning tree of an undirected weighted graph using Borůvka's algorithm.

Computes the minimum spanning tree of an undirected weighted graph using Borůvka's algorithm.

The algorithm (historically the oldest MST algorithm, 1926):

  1. Start with each vertex as its own component.
  2. For each component, find the minimum-weight edge crossing to another component.
  3. Add all such edges to the MST (merging components).
  4. Repeat until only one component remains.

Each round halves the number of components, giving O(E log V) overall complexity.

NOTE: this is a direct iterative algorithm and does not use the Visitor traversal engine. The per-component minimum-edge scan in each round is embarrassingly parallel and could be parallelised using parallel collections or futures (TODO).

NOTE: intended for undirected weighted graphs only.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
Boruvka.type
object ConnectedComponents

Computes connected components of an undirected graph.

Computes connected components of an undirected graph.

Uses getConnexions (the manual parent-tracking DFS on Traversable) to explore each component in turn, labelling vertices with a monotonically increasing component ID.

NOTE: this implementation is intended for undirected graphs only. For strongly connected components of a directed graph, see StronglyConnectedComponents (Kosaraju's algorithm) — to be implemented.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
case class Connexions[V, E](connexions: Map[V, DirectedEdge[V, E]]) extends AbstractVertexTraversalResult[V, DirectedEdge[V, E]]

Represents a particular traversal of vertices within a graph resulting from a depth-first-search starting at a particular vertex. Each vertex that is reached (not including the start vertex) is represented in the connexions Map by a DirectedEdge where the "white" (first) vertex is the start of a followed edge and the "black" (second) vertex will be the same as the key vertex. NOTE that not all edges will be followed and different random seeds will result in different results.

Represents a particular traversal of vertices within a graph resulting from a depth-first-search starting at a particular vertex. Each vertex that is reached (not including the start vertex) is represented in the connexions Map by a DirectedEdge where the "white" (first) vertex is the start of a followed edge and the "black" (second) vertex will be the same as the key vertex. NOTE that not all edges will be followed and different random seeds will result in different results.

CONSIDER returning a directed, rooted tree of DirectedEdge.

Type parameters

V

the type representing a vertex in the graph.

Value parameters

connexions

a map where each key is a vertex of type V and its value is a tuple (V, V) representing the result associated with traversal from this vertex.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
trait TraversalResult[V, DirectedEdge[V, E]]
class Object
trait Matchable
class Any
Show all
object Connexions

Provides utility methods for creating and managing instances of the ProtoConnexions class, which represents a specific traversal of vertices within a graph resulting from a depth-first search starting at a particular vertex.

Provides utility methods for creating and managing instances of the ProtoConnexions class, which represents a specific traversal of vertices within a graph resulting from a depth-first search starting at a particular vertex.

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
Connexions.type
case class DFSTraversal[V]() extends GraphTraversal[V, Unit, V]

Depth-first search traversal. E = Unit, R = V. Each visited vertex maps to itself in the result.

Depth-first search traversal. E = Unit, R = V. Each visited vertex maps to itself in the result.

Type parameters

V

the vertex type.

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait GraphTraversal[V, Unit, V]
class Object
trait Matchable
class Any
Show all
case class DijkstraTraversal[V, E]()(using evidence$1: Monoid[E], evidence$2: Ordering[E]) extends WeightedTraversal[V, E, AttributedDirectedEdge[V, E]]

Dijkstra's shortest-path traversal. See Dijkstra's Algorithm.

Dijkstra's shortest-path traversal. See Dijkstra's Algorithm.

Uses cumulative path cost as the frontier priority. Only AttributedDirectedEdge instances are admitted — the result type is TraversalResult[V, AttributedDirectedEdge[V, E]], preserving full edge information without casts.

Requires E: {Monoid, Ordering} — Monoid extends Zero so the Zero requirement of WeightedTraversal is automatically satisfied, and combine is additionally available for cumulative path cost computation.

Type parameters

E

the edge-weight type; must have Monoid and Ordering.

V

the vertex type.

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
case class EdgeTraversalResult[V, E, T](ts: List[T]) extends AbstractEdgeTraversalResult[T]

A case class representing the concrete implementation of edge traversal for a graph-like structure.

A case class representing the concrete implementation of edge traversal for a graph-like structure.

This class enables the traversal of edges by providing a list of precomputed results of type T associated with each edge.

Edge traversal uses the defined behavior from the AbstractEdgeTraversalResult base class, where vertexTraverse throws an exception, and edgeTraverse retrieves the traversal result from the precomputed list based on the edge index.

Type parameters

E

the type representing an edge in the graph.

T

the type of results for the edge traversal.

V

the type representing a vertex in the graph.

Value parameters

ts

a list of elements of type T representing the computed results of edge traversal.

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait TraversalResult[Int, T]
class Object
trait Matchable
class Any
Show all
trait GraphTraversal[V, E, R]

A family of graph traversal algorithms unified under a single abstraction.

A family of graph traversal algorithms unified under a single abstraction.

All four classic algorithms — DFS, BFS, Dijkstra, Prim — share the same underlying Traversal engine from Visitor. They differ only in:

  • the frontier type (Stack, Queue, IndexedPrioQueue)
  • the frontier element type (V for DFS/BFS, (E,V) for Dijkstra/Prim)
  • the cost-update strategy (none, cumulative, edge-only)

Type parameters

E

the edge-attribute type (Unit for DFS/BFS)

R

the result type recorded per vertex

V

the vertex type

Attributes

Supertypes
class Object
trait Matchable
class Any
Known subtypes
class BFSTraversal[V]
class DFSTraversal[V]
class WeightedTraversal[V, E, R]
class DijkstraTraversal[V, E]
class PrimTraversal[V, E]
object Kosaraju

Computes strongly connected components of a directed graph using the Kosaraju-Sharir algorithm. See Kosaraju, 1962. See Kosaraju's Algorithm. See A Strong ConnectivityLazy Algorithm....

Computes strongly connected components of a directed graph using the Kosaraju-Sharir algorithm. See Kosaraju, 1962. See Kosaraju's Algorithm. See A Strong ConnectivityLazy Algorithm....

The algorithm makes two passes:

Pass 1 — post-order DFS over the reversed graph, collecting vertices in reverse finish order. Because ListJournal prepends, result.result.map(_._1).toList already yields vertices with the last-finished vertex at the head — exactly the seed order required for pass 2.

Pass 2 — DFS over the original graph, seeding vertices in the order produced by pass 1, with a shared visited set carried across seeds. Each DFS tree in pass 2 is exactly one SCC.

NOTE: intended for directed graphs only. For undirected graphs see ConnectedComponents.

When applied to a Directed Acyclic Graph (DAG), the result is a topologically sorted set of SCCs, each of which holds only one vertex.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
Kosaraju.type
object Kruskal

Computes the minimum spanning tree of an undirected weighted graph using Kruskal's algorithm. See Krusal's Algorithm.

Computes the minimum spanning tree of an undirected weighted graph using Kruskal's algorithm. See Krusal's Algorithm.

The complexity of this implementation is O(E log E), where E is the number of edges because the time is dominated by the sorting step.

The algorithm:

  1. Sort all edges by weight (ascending).
  2. Iterate through edges; for each edge (u, v, w): if u and v are not yet connected, add the edge to the MST and union their components.
  3. Stop when N-1 edges have been added (MST is complete).

Uses WeightedUnionFind for O(log n) connectivity queries and unions. Somewhat wastefully sorts all edges before starting. A priority queue would be more efficient in the average case, but would not improve the worst case.

NOTE: intended for undirected weighted graphs only.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
Kruskal.type
object MST

Computes minimum spanning trees using Prim's algorithm. Delegates to PrimTraversal from the GraphTraversal family.

Computes minimum spanning trees using Prim's algorithm. Delegates to PrimTraversal from the GraphTraversal family.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
MST.type
case class PrimTraversal[V, E]()(using evidence$1: Zero[E], evidence$2: Ordering[E]) extends WeightedTraversal[V, E, Edge[V, E]]

Prim's minimum spanning tree traversal. See Prim's Algorithm.

Prim's minimum spanning tree traversal. See Prim's Algorithm.

Uses individual edge weight (not cumulative) as the frontier priority, so the cheapest available edge to any unvisited vertex is always chosen next. All edge types are admitted — the result type is TraversalResult[V, Edge[V, E]].

Requires only E: {Zero, Ordering} — Prim never accumulates path costs so Monoid.combine is not needed. Zero.identity seeds the initial frontier cost for the start vertex, which is immediately replaced by actual edge weights.

Type parameters

E

the edge-weight type; must have Zero and Ordering.

V

the vertex type.

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class WeightedTraversal[V, E, Edge[V, E]]
trait GraphTraversal[V, E, Edge[V, E]]
class Object
trait Matchable
class Any
Show all
object ShortestPaths

Computes shortest paths in a weighted directed graph using Dijkstra's algorithm. Delegates to DijkstraTraversal from the GraphTraversal family.

Computes shortest paths in a weighted directed graph using Dijkstra's algorithm. Delegates to DijkstraTraversal from the GraphTraversal family.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
case class TopologicalSort[V](map: Map[V, Int]) extends AbstractVertexTraversalResult[V, Int]

Represents a "topological sort" of a directed acyclic graph, mapping each vertex to its position in topological order. NOTE that it would also be possible to get the same effect using the Kosaraju algorithm (see Kosaraju.stronglyConnectedComponents) especially if you're not sure that the directed graph is in fact acyclic. If you have significant doubt, it may be better to use Kosaraju instead. A DAG will result in a topologically sorted set of SCCs, each of which holds only one vertex.

Represents a "topological sort" of a directed acyclic graph, mapping each vertex to its position in topological order. NOTE that it would also be possible to get the same effect using the Kosaraju algorithm (see Kosaraju.stronglyConnectedComponents) especially if you're not sure that the directed graph is in fact acyclic. If you have significant doubt, it may be better to use Kosaraju instead. A DAG will result in a topologically sorted set of SCCs, each of which holds only one vertex.

Type parameters

V

the type representing a vertex in the graph.

Value parameters

map

a mapping of vertices of type V to their position (Int) in topological order.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
trait TraversalResult[V, Int]
class Object
trait Matchable
class Any
Show all
object TopologicalSort

Provides functionality for topological sorting of directed graphs using the Visitor V1.2.0 typeclass engine.

Provides functionality for topological sorting of directed graphs using the Visitor V1.2.0 typeclass engine.

Post-order DFS is used: a vertex is recorded only after all its descendants have been recorded, naturally yielding reverse topological order.

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
trait TraversalResult[V, T]

A trait that defines the behavior of traversal over vertices and edges within a graph-like structure.

A trait that defines the behavior of traversal over vertices and edges within a graph-like structure.

Type parameters

T

the resulting type after traversing a vertex or an edge.

V

the type representing a vertex in the graph.

Attributes

Companion
object
Supertypes
class Object
trait Matchable
class Any
Known subtypes
class EdgeTraversalResult[V, E, T]
class Connexions[V, E]
class TopologicalSort[V]
class VertexTraversalResult[V, T]
Show all
object TraversalResult

Provides graph traversal functionality using depth-first search (DFS) for vertex traversal.

Provides graph traversal functionality using depth-first search (DFS) for vertex traversal.

Attributes

Companion
trait
Supertypes
class Object
trait Matchable
class Any
Self type
object VertexTraversalResult

Provides utility methods for creating and working with instances of VertexTraversalResult.

Provides utility methods for creating and working with instances of VertexTraversalResult.

A VertexTraversalResult is a concrete implementation of the TraversalResult trait that uses a map to represent the traversal results for graph vertices. This object contains a factory method for creating an empty VertexTraversalResult instance.

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
case class VertexTraversalResult[V, T](map: Map[V, T]) extends AbstractVertexTraversalResult[V, T]

A concrete implementation of the TraversalResult trait that uses a map to represent vertex traversals. Each vertex in the graph is associated with a traversal result.

A concrete implementation of the TraversalResult trait that uses a map to represent vertex traversals. Each vertex in the graph is associated with a traversal result.

CONSIDER this class and its companion object are only used for unit testing. They could be eliminated.

Type parameters

T

The resulting type after traversing a vertex or an edge.

V

The type representing a vertex in the graph.

Value parameters

map

A map where each key is a vertex of type V, and the value is the corresponding traversal result of type T.

Attributes

Constructor

Creates a VertexTraversalResult with the given map of vertices and their associated traversal outputs.

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
trait TraversalResult[V, T]
class Object
trait Matchable
class Any
Show all
abstract class WeightedTraversal[V, E, R <: Edge[V, E]] extends GraphTraversal[V, E, R]

Abstract base class for weighted graph traversals using a tuple (E, V) frontier.

Abstract base class for weighted graph traversals using a tuple (E, V) frontier.

Encapsulates the shared structure of Dijkstra and Prim: both use an IndexedPrioQueue[(E, V)] frontier, CostUpdate with decreaseKey, and mutable pred/bestCost maps owned exclusively by CostUpdate.

The context bound is E: {Zero, Ordering} — both algorithms need a seed cost (Zero.identity) and a cost ordering (Ordering). Only Dijkstra additionally needs Monoid.combine for path cost accumulation; Prim never accumulates costs and so extends this class directly with E: {Zero, Ordering}. DijkstraTraversal extends this with the additional Monoid bound.

Concrete subclasses differ in exactly three ways:

  • edgeCost — how the frontier cost is computed from an edge: cumulative (Monoid.combine) for Dijkstra; edge weight only for Prim.
  • destination — how the destination vertex is extracted from an edge: always e.black for directed; e.other(v) for undirected.
  • filterEdge — which edges are admitted and what concrete R type they have: only AttributedDirectedEdge for Dijkstra; all edges for Prim.

NOTE on lazy evaluation: ev._1 and ev._2 must be extracted via strict val with explicit type ascriptions inside Neighbours. Using tuple pattern matching val (accCost, v) = ev can generate a lazy binding that captures incorrectly when the resulting Iterator is consumed lazily, causing edgeCost to receive zero instead of the actual accumulated cost (a Heisenbug).

Type parameters

E

the edge-weight type; must have Zero and Ordering.

R

the result type; must be a subtype of Edge[V, E].

V

the vertex type.

Attributes

Supertypes
trait GraphTraversal[V, E, R]
class Object
trait Matchable
class Any
Known subtypes
class DijkstraTraversal[V, E]
class PrimTraversal[V, E]

Types

type ConnectedResult[V, E] = (Connexions[V, E], Map[V, Int])

Type alias for the result of a connected-components analysis. The first element is a Connexions[V, E] tracking, for each non-root vertex, the directed edge via which it was discovered. The second element maps every vertex to its integer component ID (0, 1, 2, ...).

Type alias for the result of a connected-components analysis. The first element is a Connexions[V, E] tracking, for each non-root vertex, the directed edge via which it was discovered. The second element maps every vertex to its integer component ID (0, 1, 2, ...).

Attributes

type SCCResult[V] = Map[V, Int]

Type alias for the result of a strongly-connected-components analysis. Maps every vertex to an integer SCC id (0, 1, 2, ...). Vertices sharing the same id belong to the same SCC.

Type alias for the result of a strongly-connected-components analysis. Maps every vertex to an integer SCC id (0, 1, 2, ...). Vertices sharing the same id belong to the same SCC.

Attributes

Generated with