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

com.phasmidsoftware.gryphon.adjunct

package com.phasmidsoftware.gryphon.adjunct

Members list

Type members

Classlikes

abstract class AbstractDisjointSet[V, W, This <: AbstractDisjointSet[V, W, This]](map: Map[V, W])(f: W => Option[V]) extends DisjointSet[V, This], Connected[V]

Abstract base class for disjoint-set implementations that relies on an immutable Map to associate objects with their parent disjoint set.

Abstract base class for disjoint-set implementations that relies on an immutable Map to associate objects with their parent disjoint set.

All operations are purely functional: every "mutation" returns a new instance constructed via unit, leaving the original unchanged. This makes instances persistent data structures — an old reference remains valid after any connect or put.

Each object V in map is associated with a value of type W. The function f extracts an optional parent V from a W value. If f(w) == None the object is the root of its own component.

The F-bound This &lt;: AbstractDisjointSet[V, W, This] ensures that connect, put, and remove all return the concrete subtype without casting at the call site. The only remaining asInstanceOf casts are in the short-circuit cases where this is returned unchanged — these are safe but unavoidable, since the compiler cannot prove this: This without them.

This abstract class does not perform path compression. For path compression, you must extend the subclass AbstractDisjointSetWithCompression.

Type parameters

This

the concrete subtype (F-bounded polymorphism).

V

the underlying object type.

W

the map value type (may equal Option[V] or compound it with extra data).

Value parameters

f

extracts the optional parent from a W value.

map

the component map: each V maps to its associated W.

Attributes

Supertypes
trait Connected[V]
trait DisjointSet[V, This]
class Object
trait Matchable
class Any
Known subtypes
class ConnectivityASP[V]
class ConnectivityLazy[V]
abstract class AbstractDisjointSetWithCompression[V, W, This <: AbstractDisjointSetWithCompression[V, W, This]](map: Map[V, W])(f: W => Option[V]) extends AbstractDisjointSet[V, W, This]

Abstract base class for disjoint-set implementations that relies on an immutable Map to associate objects with their parent disjoint set.

Abstract base class for disjoint-set implementations that relies on an immutable Map to associate objects with their parent disjoint set.

All operations are purely functional: every "mutation" returns a new instance constructed via unit, leaving the original unchanged. This makes instances persistent data structures — an old reference remains valid after any connect or put.

Each object V in map is associated with a value of type W. The function f extracts an optional parent V from a W value. If f(w) == None the object is the root of its own component.

The F-bound This &lt;: AbstractDisjointSet[V, W, This] ensures that connect, put, and remove all return the concrete subtype without casting at the call site. The only remaining asInstanceOf casts are in the short-circuit cases where this is returned unchanged — these are safe but unavoidable, since the compiler cannot prove this: This without them.

Subclasses that implement path compression should override findAndCompress. The default implementation simply delegates to getDisjointSet and returns this unchanged, so non-compressing subclasses need not override it. The connect method in this class calls findAndCompress for both arguments, so compression is applied automatically during every merge in subclasses that override it.

Type parameters

This

the concrete subtype (F-bounded polymorphism).

V

the underlying object type.

W

the map value type (may equal Option[V] or compound it with extra data).

Value parameters

f

extracts the optional parent from a W value.

map

the component map: each V maps to its associated W.

Attributes

Supertypes
class AbstractDisjointSet[V, W, This]
trait Connected[V]
trait DisjointSet[V, This]
class Object
trait Matchable
class Any
Show all
Known subtypes
object AttributedDirectedEdge

Companion object for the AttributedDirectedEdge class.

Companion object for the AttributedDirectedEdge class.

Provides factory methods for creating instances of AttributedDirectedEdge.

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
case class AttributedDirectedEdge[V, E](attribute: E, from: V, to: V) extends DirectedEdge[V, E]

Represents a directed edge in a graph structure, connecting a starting vertex (from) to an ending vertex (to) while carrying an associated attribute.

Represents a directed edge in a graph structure, connecting a starting vertex (from) to an ending vertex (to) while carrying an associated attribute.

Type parameters

E

the type of the attribute associated with the edge.

V

the type of the vertex attributes connected by the edge.

Value parameters

attribute

a value representing additional information or weight associated with the edge.

from

the vertex where the directed edge originates.

to

the vertex where the directed edge terminates.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
trait DirectedEdge[V, E]
trait Edge[V, E]
trait Connexion[V]
trait Attribute[E]
class Object
trait Matchable
class Any
Show all
object Connectivity

The Connectivity object provides factory methods for creating instances of Connectivity using different strategies for managing disjoint sets. These strategies include lazy and optimized implementations, each employing the "Weighted Quick Union" algorithm for efficient operations.

The Connectivity object provides factory methods for creating instances of Connectivity using different strategies for managing disjoint sets. These strategies include lazy and optimized implementations, each employing the "Weighted Quick Union" algorithm for efficient operations.

Attributes

Companion
trait
Supertypes
class Object
trait Matchable
class Any
Self type
trait Connectivity[V] extends DisjointSet[V, Connectivity[V]], Connected[V]

A trait that combines the functionalities of a disjoint set and connectivity queries.

A trait that combines the functionalities of a disjoint set and connectivity queries.

Connectivity extends both DisjointSet and Connected, allowing for efficient operations on disjoint sets as well as determining connectivity between elements.

This trait is useful for scenarios where a combination of union-find operations and connectivity checks is required, such as network connectivity, clustering, and graph algorithms like Kruskal's Minimum Spanning Tree (MST).

The type parameter V represents the type of elements in the disjoint set.

Type parameters

V

the type of elements managed by this connectivity structure.

Attributes

Companion
object
Supertypes
trait Connected[V]
trait DisjointSet[V, Connectivity[V]]
class Object
trait Matchable
class Any
Known subtypes
class ConnectivityASP[V]
class ConnectivityLazy[V]
object ConnectivityASP

Companion object for ConnectivityASP.

Companion object for ConnectivityASP.

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
case class ConnectivityASP[V](map: Map[V, Option[V]]) extends AbstractDisjointSet[V, Option[V], ConnectivityASP[V]], Connectivity[V]

Concrete disjoint-set implementation using "Quick Union" (lazy union), with the ASP (Arbitrary Substitution Principle) violation noted in the code.

Concrete disjoint-set implementation using "Quick Union" (lazy union), with the ASP (Arbitrary Substitution Principle) violation noted in the code.

Each object maps to Option[V]: None means the object is a root; Some(parent) means the object's parent in the component tree.

This is O(n) in the worst case due to potentially unbalanced trees. Prefer ConnectivityLazy for production use.

unit and put return ConnectivityASP[V] directly, with no overrides required, courtesy of the F-bounded type parameter.

Type parameters

V

the underlying object type.

Value parameters

map

the component map.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
trait Connectivity[V]
class AbstractDisjointSet[V, Option[V], ConnectivityASP[V]]
trait Connected[V]
class Object
trait Matchable
class Any
Show all
case class ConnectivityLazy[V](map: Map[V, ParentSize[V]]) extends AbstractDisjointSet[V, ParentSize[V], ConnectivityLazy[V]], Connectivity[V]

Concrete disjoint-set implementation using "Weighted Quick Union."

Concrete disjoint-set implementation using "Weighted Quick Union."

Each object maps to a ParentSize[V] carrying both its optional parent and the size of its component tree. When merging, the smaller tree is attached under the larger, keeping tree height O(log n) and all operations O(log n).

This implementation obeys the Arbitrary Substitution Principle (ASP): the choice of which root becomes the child is justified by tree size, not arbitrary.

unit and put return ConnectivityLazy[V] directly, with no overrides required, courtesy of the F-bounded type parameter.

Type parameters

V

the underlying object type.

Value parameters

map

the component map.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
trait Connectivity[V]
trait Connected[V]
class Object
trait Matchable
class Any
Show all
object ConnectivityLazy

Companion object for ConnectivityLazy.

Companion object for ConnectivityLazy.

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
case class ConnectivityOptimized[V](map: Map[V, ParentSize[V]]) extends AbstractDisjointSetWithCompression[V, ParentSize[V], ConnectivityOptimized[V]], Connectivity[V]

Concrete disjoint-set implementation using "Weighted Quick Union with Path Compression."

Concrete disjoint-set implementation using "Weighted Quick Union with Path Compression."

Extends ConnectivityLazy with path compression: during every findAndCompress traversal to the root, all nodes along the path are rewired to point directly to the root. This flattens the tree lazily, giving amortized near-O(1) performance (formally O(α(n)), where α is the inverse Ackermann function).

Path compression is implemented purely functionally: the rewired nodes are accumulated into a new immutable Map which is returned alongside the root as a fresh ConnectivityOptimized instance. No mutation occurs.

Note that after path compression, rank (tracked via ParentSize.size) becomes an upper bound on depth rather than the true depth — this is the standard behaviour of union-by-rank with path compression, and is why the field is called size (a weaker proxy) rather than depth.

unit and put return ConnectivityOptimized[V] directly, with no overrides required, courtesy of the F-bounded type parameter.

Type parameters

V

the underlying object type.

Value parameters

map

the component map.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
trait Connectivity[V]
trait Connected[V]
class Object
trait Matchable
class Any
Show all
object ConnectivityOptimized

Companion object for ConnectivityOptimized.

Companion object for ConnectivityOptimized.

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
trait DirectedEdge[V, E] extends Edge[V, E]

An abstract trait representing a directed edge in a graph.

An abstract trait representing a directed edge in a graph.

This trait extends the Edge trait, providing a specific implementation for the edgeType method, which always returns Directed. The directed edge represents a one-way connection between two vertices.

Type parameters

E

the type of the attribute associated with the edge.

V

the type of the vertices connected by the edge.

Attributes

Supertypes
trait Edge[V, E]
trait Connexion[V]
trait Attribute[E]
class Object
trait Matchable
class Any
Show all
Known subtypes
class OrderedEdge[V]
object DirectedGraph

Factory object for creating instances of DirectedGraph. This object provides utility methods to construct a directed graph from an edge list representation.

Factory object for creating instances of DirectedGraph. This object provides utility methods to construct a directed graph from an edge list representation.

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
case class DirectedGraph[V, E](vertexMap: VertexMap[V]) extends AbstractGraph[V], EdgeGraph[V, E]

Represents a directed graph structure that supports operations on vertexMap and edges. This class is a concrete implementation of the EdgeGraph trait, and models directed relationships between vertices with edges.

Represents a directed graph structure that supports operations on vertexMap and edges. This class is a concrete implementation of the EdgeGraph trait, and models directed relationships between vertices with edges.

Type parameters

E

the type of attributes for the edges in the graph (invariant).

V

the type of attributes for the vertexMap in the graph (invariant).

Value parameters

vertexMap

the VertexMap that represents this Graph.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
trait EdgeGraph[V, E]
trait EdgeTraversable[V, E]
class AbstractGraph[V]
trait Graph[V]
trait Traversable[V]
class Object
trait Matchable
class Any
Show all
Known subtypes
trait DAG[V, E]
trait DisjointSet[V, +This <: DisjointSet[V, This]]

Trait to model the behavior of a disjoint set. Thus, we provide put, connect, getDisjointSet, and size in addition to isConnected (from the super-trait).

Trait to model the behavior of a disjoint set. Thus, we provide put, connect, getDisjointSet, and size in addition to isConnected (from the super-trait).

The purpose of having a disjoint set representation of a "graph" is so that we can answer connectivity questions in close to O(1) time, rather than the O(n + m) time required for a full traversal of an edge-connected graph. The most typical application of this trait is Kruskal's MST algorithm.

The most typical concrete implementation of this trait is the ConnectivityLazy class (usually known as Union-Find).

The type parameter This is the F-bounded self-type, ensuring that put and connect return the concrete subtype rather than DisjointSet[V].

Type parameters

This

the concrete subtype (F-bounded polymorphism).

V

the underlying object type.

Attributes

Supertypes
class Object
trait Matchable
class Any
Known subtypes
class AbstractDisjointSet[V, W, This]
class ConnectivityASP[V]
class ConnectivityLazy[V]
trait Connectivity[V]
Show all
case class OrderedEdge[V](from: V, to: V) extends DirectedEdge[V, Unit]

Represents a directed edge in a graph connecting two vertices of type V. This implementation specifically models directed edges for graph structures, where the direction is indicated from a from vertex to a to vertex. The edge carries no additional attributes.

Represents a directed edge in a graph connecting two vertices of type V. This implementation specifically models directed edges for graph structures, where the direction is indicated from a from vertex to a to vertex. The edge carries no additional attributes.

Type parameters

V

the type of the vertices connected by the edge.

Value parameters

from

the originating vertex of the edge.

to

the terminating vertex of the edge.

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait DirectedEdge[V, Unit]
trait Edge[V, Unit]
trait Connexion[V]
trait Attribute[Unit]
class Object
trait Matchable
class Any
Show all
object ParentSize

Companion object for ParentSize.

Companion object for ParentSize.

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
ParentSize.type
case class ParentSize[V](parent: Option[V], size: Int)

Carries an optional parent reference and the size of the component tree.

Carries an optional parent reference and the size of the component tree.

Type parameters

V

the underlying object type.

Value parameters

parent

None if this object is a root; Some(p) otherwise.

size

the number of objects in this component tree (meaningful only at the root). With path compression active, this becomes an upper bound on depth (rank) rather than the precise tree size.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
case class UndirectedEdge[V, E](attribute: E, white: V, black: V) extends Edge[V, E]

Represents an undirected edge in a graph structure, connecting two vertices (white and black) equally, without a defined direction, and carrying an associated attribute.

Represents an undirected edge in a graph structure, connecting two vertices (white and black) equally, without a defined direction, and carrying an associated attribute.

Type parameters

E

the type of the attribute associated with the edge.

V

the type of the vertex attributes connected by the edge.

Value parameters

attribute

a value representing additional information or weight associated with the edge.

black

the other vertex connected by the undirected edge.

white

one of the vertices connected by the undirected edge.

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait Edge[V, E]
trait Connexion[V]
trait Attribute[E]
class Object
trait Matchable
class Any
Show all
object UndirectedGraph

Factory object for creating instances of DirectedGraph. This object provides utility methods to construct a directed graph from an edge list representation.

Factory object for creating instances of DirectedGraph. This object provides utility methods to construct a directed graph from an edge list representation.

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
case class UndirectedGraph[V, E](vertexMap: VertexMap[V]) extends AbstractGraph[V], EdgeGraph[V, E]

Represents a directed graph structure that supports operations on vertexMap and edges. This class is a concrete implementation of the EdgeGraph trait, and models directed relationships between vertices with edges.

Represents a directed graph structure that supports operations on vertexMap and edges. This class is a concrete implementation of the EdgeGraph trait, and models directed relationships between vertices with edges.

Type parameters

E

the type of attributes for the edges in the graph (invariant).

V

the type of attributes for the vertexMap in the graph (invariant).

Value parameters

vertexMap

the VertexMap that represents this Graph.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
trait EdgeGraph[V, E]
trait EdgeTraversable[V, E]
class AbstractGraph[V]
trait Graph[V]
trait Traversable[V]
class Object
trait Matchable
class Any
Show all
object WeightedUnion

Shared weighted-union logic for all ParentSize-based disjoint-set implementations.

Shared weighted-union logic for all ParentSize-based disjoint-set implementations.

Extracted here to avoid duplication between ConnectivityLazy and ConnectivityOptimized, both of which use identical merge strategies. A single point of change ensures the two implementations cannot silently diverge.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type

Types

type ADS[V, W, This <: AbstractDisjointSet[V, W, This]] = AbstractDisjointSet[V, W, This]
type ADSWC[V, W, This <: AbstractDisjointSetWithCompression[V, W, This]] = AbstractDisjointSetWithCompression[V, W, This]
Generated with