com.phasmidsoftware.visitor.core

A trait representing an appendable structure that supports the addition of elements of type X and exhibits a fluent interface by returning itself after each append operation.

Implementing classes may define specific behavior for how elements are appended and may provide additional lifecycle management by extending AutoCloseable.

Type parameters

X: the type of elements that can be appended to the structure

Attributes

Supertypes: trait AutoCloseable

class Object

trait Matchable

class Any
Known subtypes: trait Journal[X]

trait IterableJournal[X]

class CameFromJournal[V]

class ListJournal[X]

class QueueJournal[X]

class AbstractMapJournal[K, V]

class FunctionMapJournal[K, V]

class MapJournal[K, V]

trait FunctionMappedJournal[X, Y]

trait IterableJournal[X]

class ListJournal[X]

class QueueJournal[X]

class AppendableWriter

class NonAppendable[X]
Show all

A journal that records the came-from relationship established during graph traversal.

For each discovered vertex v, map(v) is the vertex from which v was first discovered — i.e. the vertex that was being visited when v was added to the frontier. The start vertex is absent from the map (it has no predecessor).

This is sometimes called a "parent map" but "came-from" is more accurate: the relationship is an artifact of traversal order, not a structural property of the graph.

Used in conjunction with JournaledVisitor when came-from tracking is requested via the withQueueJournalAndCameFrom or withListJournalAndCameFrom factory methods.

Type parameters

V: the vertex type

Value parameters

map: the underlying came-from map: vertex → the vertex that discovered it

Attributes

Companion: object
Supertypes: trait Serializable

trait Product

trait Equals

trait IterableJournal[(V, V)]

trait Iterable[(V, V)]

trait IterableFactoryDefaults[(V, V), Iterable]

trait IterableOps[(V, V), Iterable, Iterable[(V, V)]]

trait IterableOnceOps[(V, V), Iterable, Iterable[(V, V)]]

trait IterableOnce[(V, V)]

trait Journal[(V, V)]

trait Appendable[(V, V)]

trait AutoCloseable

class Object

trait Matchable

class Any
Show all

Companion object for the CameFromJournal class.

Provides utility methods to work with the CameFromJournal, including initialization of an empty came-from journal.

Attributes

Companion: class
Supertypes: trait Product

trait Mirror

class Object

trait Matchable

class Any
Self type: CameFromJournal.type

Typeclass: after a node is settled (dequeued and marked visited) and its neighbours have been offered to the frontier, optionally update the priorities of frontier entries that have improved.

This typeclass exists to support decreaseKey in Dijkstra- and Prim-style traversals. It keeps all domain knowledge (cost maps, edge weights, the notion of "improvement") out of Traversal itself.

For DFS and BFS the default no-op given is resolved automatically. For Dijkstra and Prim, the GraphTraversal implementation supplies a concrete given CostUpdate[W, IndexedPrioQueue] (where W = (E, V)) that closes over a secondary vertex→cost map and calls IndexedPrioQueue.decreaseKey for any neighbour whose cost has improved since it was first offered.

Type parameters

F: the frontier container type (e.g. PrioQueue, Stack, Queue)
W: the frontier element type (e.g. (E, V) for weighted traversals, or plain V for DFS / BFS)

Attributes

Supertypes: class Object

trait Matchable

class Any

Controls whether DFS records a node before or after processing its children.

Pre: node is recorded before its children are expanded (default)
Post: node is recorded after all its descendants (useful for topological sort)

Attributes

Supertypes: trait Enum

trait Serializable

trait Product

trait Equals

class Object

trait Matchable

class Any
Show all

Typeclass: given a node of type V, extract an optional result of type R. This is the "what do we want to know about a node" concern.

Type parameters

R: the result type
V: the node type

Attributes

Supertypes: class Object

trait Matchable

class Any

Typeclass: abstracts over frontier data structures (Queue, Stack, PriorityQueue). The three implementations below give us BFS, DFS, and best-first / Dijkstra-style traversals for free — the traversal algorithm itself doesn't change at all.

Type parameters

F: the higher-kinded frontier container type

Attributes

Supertypes: class Object

trait Matchable

class Any
Known subtypes: object given_Frontier_IndexedPrioQueue

object given_Frontier_PrioQueue

object given_Frontier_Queue

object given_Frontier_Stack

Attributes

Companion: class
Supertypes: trait Product

trait Mirror

class Object

trait Matchable

class Any
Self type: IndexedPrioQueue.type

An immutable indexed priority queue ADT backed by BinaryHeap.

Extends the PrioQueue contract with O(log n) decreaseKey and O(1) contains, enabled by a Map[T, Int] index that tracks each element's current position in the heap array.

Unlike PrioQueue, duplicates are not permitted: offer is a no-op if the element is already present. Use decreaseKey to improve an existing entry's priority. This one-entry-per-key invariant is what makes the index meaningful and decreaseKey correct.

The index is rebuilt from heap.data (O(n)) after each structural operation (offer and take). This is acceptable because:

the O(n) rebuild cost is dominated by the O(E log V) traversal cost
the implementation remains simple, correct, and easy to reason about

Minimum element is dequeued first (or maximum via IndexedPrioQueue.emptyMax).

Type parameters

T: the element type

Value parameters

heap: the underlying binary heap
index: a map from element to its current 0-based position in heap.data

Attributes

Companion: object
Supertypes: trait Serializable

trait Product

trait Equals

class Object

trait Matchable

class Any
Show all

A trait that combines the functionalities of a Journal and Iterable, enabling append operations, lifecycle management, and iterable access to elements.

This abstraction is useful for scenarios where elements need to be managed sequentially, support append operations, and be accessed through iteration.

Implementing classes are expected to define the behavior for appending elements, providing iterators, and any optional lifecycle management such as resource closure.

Type parameters

X: the type of elements contained in the journal

Attributes

Supertypes: trait Iterable[X]

trait IterableFactoryDefaults[X, Iterable]

trait IterableOps[X, Iterable, Iterable[X]]

trait IterableOnceOps[X, Iterable, Iterable[X]]

trait IterableOnce[X]

trait Journal[X]

trait Appendable[X]

trait AutoCloseable

class Object

trait Matchable

class Any
Show all
Known subtypes: class CameFromJournal[V]

class ListJournal[X]

class QueueJournal[X]

A trait representing a journal for managing a collection of appendable elements of type X.

The Journal extends the behavior of Appendable, supporting the addition of elements while also introducing lifecycle management through the ability to close the journal.

Implementing classes can define additional behaviors, such as persistence, iteration, or other domain-specific functionalities.

Type parameters

X: the type of elements that can be managed by the journal

Attributes

Supertypes: trait Appendable[X]

trait AutoCloseable

class Object

trait Matchable

class Any
Known subtypes: trait IterableJournal[X]

class CameFromJournal[V]

class ListJournal[X]

class QueueJournal[X]

class AbstractMapJournal[K, V]

class FunctionMapJournal[K, V]

class MapJournal[K, V]

trait FunctionMappedJournal[X, Y]

trait IterableJournal[X]

class ListJournal[X]

class QueueJournal[X]
Show all

Attributes

Companion: class
Supertypes: trait Product

trait Mirror

class Object

trait Matchable

class Any
Self type: JournaledVisitor.type

Canonical immutable implementation of Visitor.

Optionally carries a CameFromJournal for tracking came-from relationships. When cameFromJournal is non-empty, discover records (v, cameFrom) pairs. The start vertex is absent from the came-from map — it has no predecessor.

Use the factory methods on the companion object to construct instances.

Value parameters

cameFromJournal: optionally, a journal recording came-from relationships.
journal: the visit journal (ListJournal or QueueJournal).

Attributes

Companion: object
Supertypes: trait Serializable

trait Product

trait Equals

trait Visitor[V, R, J]

class Object

trait Matchable

class Any
Show all

A case class representing a journal backed by a list, which maintains a sequence of elements.

This class provides methods to append elements to the journal and to iterate over its contents. It is immutable, meaning every modification creates a new instance.

Type parameters

X: the type of elements stored in the journal

Value parameters

xs: the list containing the elements of the journal

Attributes

Companion: object
Supertypes: trait Serializable

trait Product

trait Equals

trait IterableJournal[X]

trait Iterable[X]

trait IterableFactoryDefaults[X, Iterable]

trait IterableOps[X, Iterable, Iterable[X]]

trait IterableOnceOps[X, Iterable, Iterable[X]]

trait IterableOnce[X]

trait Journal[X]

trait Appendable[X]

trait AutoCloseable

class Object

trait Matchable

class Any
Show all

Companion object for the ListJournal class, providing utility methods for creating instances of ListJournal.

The ListJournal object serves as a factory for creating empty instances of ListJournal. ListJournal is used to maintain a sequence of elements in prepend (LIFO) order.

Attributes

Companion: class
Supertypes: trait Product

trait Mirror

class Object

trait Matchable

class Any
Self type: ListJournal.type

Typeclass: an associative binary operation with an identity element.

Extends Zero with combine. Mirrors the Cats Monoid typeclass but without the Cats dependency.

Primary use in Visitor/Gryphon:

Dijkstra needs both identity (seed cost) and combine (path cost accumulation).
Prim needs only identity — use Zero[E] for Prim, Monoid[E] for Dijkstra.

Type parameters

A: the element type

Attributes

Supertypes: class Object

trait Matchable

class Any
Known subtypes: object given_Monoid_Double

object given_Monoid_Float

object given_Monoid_Int

object given_Monoid_Long

Typeclass: given a structure H, yield the neighbouring nodes of type V. This is the "how do we traverse" concern — completely decoupled from domain.

For homogeneous graphs (node points to node), use GraphNeighbours[V] = Neighbours[V, V]. For trees, H might be Tree[A] and V might be A.

Type parameters

H: the container / structure type
V: the neighbour / child type

Attributes

Supertypes: class Object

trait Matchable

class Any

An immutable priority queue ADT backed by BinaryHeap.

Duplicates are permitted. The minimum element is dequeued first (or maximum via PrioQueue.emptyMax).

Ordering[T] is captured at construction time so that Frontier[PrioQueue] remains fully polymorphic — no Ordering context is needed at offer / take call sites.

For a priority queue that also supports O(log n) decreaseKey, see IndexedPrioQueue.

Type parameters

T: the element type

Value parameters

heap: the underlying binary heap

Attributes

Companion: object
Supertypes: trait Serializable

trait Product

trait Equals

class Object

trait Matchable

class Any
Show all

Attributes

Companion: class
Supertypes: trait Product

trait Mirror

class Object

trait Matchable

class Any
Self type: PrioQueue.type

An implementation of IterableJournal that uses a Queue to manage journal entries.

This class provides a mechanism for appending elements to a queue-based journal and iterating over the elements in a sequential order. It is particularly useful in scenarios where a first-in-first-out (FIFO) ordering of operations or entries is required.

Type parameters

X: the type of elements stored in the journal

Value parameters

q: the underlying queue used to store the journal's elements

Attributes

Companion: object
Supertypes: trait Serializable

trait Product

trait Equals

trait IterableJournal[X]

trait Iterable[X]

trait IterableFactoryDefaults[X, Iterable]

trait IterableOps[X, Iterable, Iterable[X]]

trait IterableOnceOps[X, Iterable, Iterable[X]]

trait IterableOnce[X]

trait Journal[X]

trait Appendable[X]

trait AutoCloseable

class Object

trait Matchable

class Any
Show all

Companion object for the QueueJournal class.

Provides utility methods such as creating an empty instance of QueueJournal.

Type parameters

X: the type of elements that the QueueJournal will store

Attributes

Companion: class
Supertypes: trait Product

trait Mirror

class Object

trait Matchable

class Any
Self type: QueueJournal.type

Attributes

Companion: trait
Supertypes: class Object

trait Matchable

class Any
Self type: Tracer.type

Typeclass for algorithm tracing. Implementations produce human-readable output showing the steps of a graph algorithm at a given nesting depth; the depth is used to indent output so that the logical structure of the algorithm is visible.

Each trace call provides two lazily-evaluated messages:

brief — a short summary (e.g. a count); always used by non-silent tracers
detail — a fuller description (e.g. collection elements); used only by verbose

The canonical no-op given (Tracer.silent) is resolved automatically, so existing call sites require no changes. Students opt in by summoning a tracer:

 given Tracer[Int] = Tracer.verbose()
 Kosaraju.stronglyConnectedComponents(graph)

Both brief and detail are by-name so that string interpolation is never evaluated in the silent case — zero overhead in production use.

Three built-in modes:

silent — no output, neither brief nor detail evaluated
summary — emits brief only, and only at depth 0
verbose — emits detail (falling back to brief if detail is empty), up to a configurable maxDepth

Type parameters

V: the vertex type (present so that, for example, a vertex tracer and an edge tracer can coexist in scope via their distinct type parameters)

Attributes

Companion: object
Supertypes: class Object

trait Matchable

class Any

The traversal engine. Knows only about Frontier, Neighbours, Evaluable, VisitedSet, Visitor, and CostUpdate. Zero domain knowledge.

The choice of frontier F determines the traversal order: F = Queue → BFS F = Stack → DFS F = PrioQueue → best-first (requires Ordering[V] in scope)

Two visitor events are fired during traversal:

visit(v) — when a vertex is settled (dequeued/popped)
discover(v, cameFrom) — when a vertex is first seen as a neighbour

NOTE that there are three independent traversal engines which should be maintained in parallel as much as possible: traverse, traverseTree, and dfs.

Attributes

Supertypes: class Object

trait Matchable

class Any
Self type: Traversal.type

Typeclass: a set of visited nodes, used to prevent revisiting in cycle-containing graphs. Immutable — markVisited returns a new instance.

Type parameters

V: the node type

Attributes

Supertypes: class Object

trait Matchable

class Any

A Visitor accumulates (V, Option[R]) pairs into a journal J as it traverses a structure.

Two members provide access to the accumulated journal:

journal — the raw journal value of type J; used internally by concrete implementations (e.g. JournaledVisitor.copy(journal = ...)) where the specific J type must be visible for polymorphic copying.
result — a public alias for journal, defaulting to journal; intended as the external API for consumers of a completed traversal. A concrete implementation could override result to apply post-processing (e.g. reversing a ListJournal) without affecting the internal journal.

Two events are distinguished:

visit(v) — called when a vertex is settled (dequeued/popped and processed). Records (v, ev.evaluate(v)) in the journal.
discover(v, cameFrom) — called when a vertex is first seen as a neighbour of cameFrom, before it is added to the frontier. Default implementation is a no-op; override in concrete implementations that track came-from pointers.

Type parameters

J: the journal type (must be Appendable of (V, Option[R]))
R: the result type extracted from each node
V: the node type

Attributes

Supertypes: class Object

trait Matchable

class Any
Known subtypes: class JournaledVisitor[V, R, J]

Typeclass: a type with an identity element.

Zero[A] is the minimal requirement for weighted graph traversals that need a seed cost but do not accumulate costs along a path — specifically Prim's MST algorithm. Prim needs identity to seed the frontier but never calls combine.

Monoid[A] extends Zero[A] by adding combine, making Zero the honest supertype for the two-context-bound pattern E: {Zero, Ordering}.

Any given Monoid[A] automatically satisfies Zero[A] through inheritance.

Type parameters

A: the element type

Attributes

Supertypes: class Object

trait Matchable

class Any
Known subtypes: object given_Zero_Double

object given_Zero_Float

object given_Zero_Int

object given_Zero_Long

Indexed priority-queue frontier: best-first traversal using IndexedPrioQueue.

Duplicates are not permitted — offer is a no-op if the element is already present. Supports decreaseKey via CostUpdate. Used by bestFirstWeighted (Dijkstra, Prim).

Supply given IndexedPrioQueue[T] = IndexedPrioQueue.empty[T] at the call site.

Attributes

Supertypes: trait Frontier[IndexedPrioQueue]

class Object

trait Matchable

class Any
Self type: given_Frontier_IndexedPrioQueue.type

Priority-queue frontier: best-first traversal using PrioQueue.

Duplicates are permitted. Used by bestFirst and bestFirstMax. Ordering[T] is captured at PrioQueue construction time.

Supply given PrioQueue[T] = PrioQueue.empty[T] (or emptyMax) at the call site.

Attributes

Supertypes: trait Frontier[PrioQueue]

class Object

trait Matchable

class Any
Self type: given_Frontier_PrioQueue.type

Implementation of the Frontier typeclass for the Queue data structure. This implementation provides a breadth-first search (BFS) traversal strategy due to the FIFO (First-In-First-Out) nature of Queue.

Functions:

empty — Constructs an empty Queue.
offer — Enqueues an element into the Queue.
take — Dequeues an element from the Queue, returning the element and the resulting Queue.
isEmpty — Checks if the Queue is empty.

Attributes

Supertypes: trait Frontier[Queue]

class Object

trait Matchable

class Any
Self type: given_Frontier_Queue.type

Implementation of the Frontier typeclass for a stack-based data structure. This implementation provides depth-first traversal behavior by leveraging the characteristics of a stack (LIFO - Last In, First Out).

Attributes

Supertypes: trait Frontier[Stack]

class Object

trait Matchable

class Any
Self type: given_Frontier_Stack.type

Additive monoid for Double.

Attributes

Supertypes: trait Monoid[Double]

class Object

trait Matchable

class Any
Self type: given_Monoid_Double.type

Additive monoid for Float.

Attributes

Supertypes: trait Monoid[Float]

class Object

trait Matchable

class Any
Self type: given_Monoid_Float.type

Additive monoid for Int.

Attributes

Supertypes: trait Monoid[Int]

class Object

trait Matchable

class Any
Self type: given_Monoid_Int.type

Additive monoid for Long.

Attributes

Supertypes: trait Monoid[Long]

class Object

trait Matchable

class Any
Self type: given_Monoid_Long.type

Attributes

Supertypes: trait Zero[Double]

class Object

trait Matchable

class Any
Self type: given_Zero_Double.type

Attributes

Supertypes: trait Zero[Float]

class Object

trait Matchable

class Any
Self type: given_Zero_Float.type

Attributes

Supertypes: trait Zero[Int]

class Object

trait Matchable

class Any
Self type: given_Zero_Int.type

Attributes

Supertypes: trait Zero[Long]

class Object

trait Matchable

class Any
Self type: given_Zero_Long.type

com.phasmidsoftware.visitor.core

Members list

Type members

Classlikes

Type parameters

Attributes

Type parameters

Value parameters

Attributes

Attributes

Type parameters

Attributes

Attributes

Type parameters

Attributes

Type parameters

Attributes

Attributes

Type parameters

Value parameters

Attributes

Type parameters

Attributes

Type parameters

Attributes

Attributes

Value parameters

Attributes

Type parameters

Value parameters

Attributes

Attributes

Type parameters

Attributes

Type parameters

Attributes

Type parameters

Value parameters

Attributes

Attributes

Type parameters

Value parameters

Attributes

Type parameters

Attributes

Attributes

Type parameters

Attributes

Attributes

Type parameters

Attributes

Type parameters

Attributes

Type parameters

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Attributes

Types

Attributes

Attributes

Attributes

Type parameters

Attributes

Givens

Givens

Attributes

Attributes

Attributes

Attributes

Attributes