package constrained
Traits enabling to implement constraints and use constrained graphs.
Graphs may be constrained dynamically or statically.
Dynamically constrained means that a constraint is bound to a constrained Graph
instance at initialization time. The constrained Graph
will then delegate all calls
to the methods of ConstraintMethods
and ConstraintHandlerMethods
to the
corresponding methods of the constraint bound to it.
The immutable and mutable factories Graph
in this package yield dynamically
constrained graphs.
To make use of dynamically constrained graphs you may make use of the predefined
constraints or provide an own implementation of Constraint
along with its companion
object. To initialize a graph with one or several combined constraints just call
the graph factory methods of the constraint
package passing.
Statically constrained means that the graph class directly implements
the methods declared in ConstraintMethods
.
 Alphabetic
 By Inheritance
 constrained
 AnyRef
 Any
 Hide All
 Show All
 Public
 All
Type Members
 sealed trait BinaryOp extends Op

abstract
class
CompanionAlias
[E[X] <: EdgeLikeIn[X]] extends GraphConstrainedCompanionAlias[Graph, E]
Enables to quickly assemble immutable constrained graph companion modules.
Enables to quickly assemble immutable constrained graph companion modules. Example:
import scalax.collection.constrained.CompanionAlias import scalax.collection.constrained.constraints.Acyclic object DAG extends CompanionAlias[DiEdge](Acyclic withStringPrefix "DAG")

type
Config = ConstrainedConfig
Aims defining a constraint valid for
Graph
instances in the scope:Aims defining a constraint valid for
Graph
instances in the scope:implicit val config: Config = Acyclic val g = Graph(0 ~> 3) // g is constrained to Acyclic

trait
Constrained
[N, E[X] <: EdgeLikeIn[X]] extends ConstraintMethods[N, E] with ConstraintHandlerMethods[N, E]
Template to be mixed in by any constrained graph class.
Template to be mixed in by any constrained graph class.
The user of the dynamically constrained class scalax.collection.constrained.Graph or its mutable counterpart need not to be concerned about this trait because it has been mixed in there. She only needs to pass the companion object for her
Constraint
implementation.Implementors of statically constrained graph classes have to mix in this trait in their constrained graph implementations.
 See also
ConstraintMethods

abstract
class
Constraint
[N, E[X] <: EdgeLikeIn[X]] extends ConstraintMethods[N, E] with ConstraintHandlerMethods[N, E]
Template to be implemented and passed to a dynamically constrained graph class by the user.
Template to be implemented and passed to a dynamically constrained graph class by the user. Note that mutable state will be lost on any operation yielding a new graph. Thus it is essential to either design classes inheriting from
Constraint
in a pure immutable manner or taking internally care of whether the state has been lost. See also
ConstraintMethods
 class ConstraintBinaryOp [N, E[X] <: EdgeLikeIn[X]] extends ConstraintOp[N, E]

trait
ConstraintCompanion
[+CC[N, E[X] <: EdgeLikeIn[X]] <: Constraint[N, E[X]]] extends AnyRef
Base trait for ordinary
Constraint
companion objects. 
class
ConstraintCompanionBinaryOp
extends ConstraintCompanionOp
Facilitates binary operations on
ConstraintCompanion
s. 
abstract
class
ConstraintCompanionOp
extends ConstraintCompanion[Constraint]
Base class for any operation on
ConstraintCompanion
s. 
trait
ConstraintHandlerMethods
[N, E[X] <: EdgeLikeIn[X]] extends AnyRef
This template contains handler methods that are called by constrained graphs whenever a constraint has been violated.
This template contains handler methods that are called by constrained graphs whenever a constraint has been violated.
These methods must be overridden to get the handlers become active.
 Attributes
 protected

trait
ConstraintMethods
[N, E[X] <: EdgeLikeIn[X]] extends AnyRef
This template contains all methods that constrained graphs call to decide whether operations altering a mutable graph or operations yielding a new graph from an immutable or mutable graph are valid.
This template contains all methods that constrained graphs call to decide whether operations altering a mutable graph or operations yielding a new graph from an immutable or mutable graph are valid.
Constraint methods are called on graph creation and node/edge addition and subtraction at two points of time, respectively: prior to the operation and after the operation has taken place but still may be rolled back. Thus, constraint method names are prefixed by
pre
orpost
. Preckecks returnAbort
,PostCheck
orComplete
while postchecks return Boolean stating whether the operation should be committed or rolled back. Prechecks can inspect the operands only. In contrast, postchecks additionally allow to inspect the wouldbe graph after the operation has taken place but has not yet been committed.For performance reasons, implementations should prefer implementing precheck methods. If it's necessary to check not only the operands but the whole wouldbe graph, the appropriate postcheck methods should be overridden.
 abstract class ConstraintOp [N, E[X] <: EdgeLikeIn[X]] extends Constraint[N, E]

type
DAG[N] = Graph[N, DiEdge]
Default (immutable) directed acyclic
Graph
. 
type
Forest[N] = Graph[N, UnDiEdge]
Default (immutable) undirected acyclic
Graph
. 
trait
Graph
[N, E[X] <: EdgeLikeIn[X]] extends Set[Param[N, E]] with collection.Graph[N, E] with GraphLike[N, E, Graph]
A trait for dynamically constrained graphs.
A trait for dynamically constrained graphs.
 N
the type of the nodes (vertices) in this graph.
 E
the kind of the edges in this graph.

trait
GraphLike
[N, E[X] <: EdgeLikeIn[X], +This[X, Y[X] <: EdgeLikeIn[X]] <: GraphLike[X, Y[X], This] with Set[Param[X, Y[X]]] with Graph[X, Y[X]]] extends collection.GraphLike[N, E, This] with Constrained[N, E]
A template trait for graphs.
A template trait for graphs.
This trait provides the common structure and operations of immutable graphs independently of its representation.
If
E
inheritsDirectedEdgeLike
the graph is directed, otherwise it is undirected or mixed. N
the user type of the nodes (vertices) in this graph.
 E
the higher kinded type of the edges (links) in this graph.
 This
the higher kinded type of the graph itself.
 sealed trait Op extends AnyRef

class
PreCheckResult
extends AnyRef
The return type of any precheck.
The return type of any precheck.
followUp
contains the return status (followup activity).Constraint
implementations are encouraged to extend this class to contain further data calculated in course of the precheck and reusable in the following postcheck.  trait PreCheckResultCompanion extends AnyRef

type
Tree[N] = Graph[N, UnDiEdge]
Default (immutable) undirected connected acyclic
Graph
.  trait UserConstrainedGraph [N, E[X] <: EdgeLikeIn[X]] extends Graph[N, E]
Value Members

def
Config: ConstrainedConfig.type
Companion object to configure
Graph
instances in the scope includingArraySet.Hints
:Companion object to configure
Graph
instances in the scope includingArraySet.Hints
:implicit val config = Config(Acyclic)(ArraySet.Hints(64, 0, 64, 75)) val g = Graph(0 ~> 3) // g is constrained to Acyclic using the above optimization hints

implicit
def
constraintToConfig(constraint: ConstraintCompanion[Constraint])(implicit orderHint: Int = GraphConfig.defaultOrder, adjacencyListHints: Hints = ArraySet.Hints()): ConstrainedConfig
Converts
constraint
to an instance ofconfig.ConstrainedConfig
. 
def
dagConstraint: constrained.constraints.Acyclic.PrefixedConstraintCompanion
Constraint representing a DAG.

def
forestConstraint: constrained.constraints.Acyclic.PrefixedConstraintCompanion
Constraint representing a forest.

def
treeConstraint: constrained.ConstraintCompanionBinaryOp.PrefixedConstraintCompanion
Constraint representing an undirected tree.
 object And extends BinaryOp with Product with Serializable

object
DAG
extends CompanionAlias[DiEdge]
Companion module for default (immutable) directed acyclic
Graph
. 
object
Forest
extends CompanionAlias[UnDiEdge]
Companion module for default (immutable) undirected acyclic
Graph
. 
object
Graph
extends GraphConstrainedCompanion[Graph] with Serializable
Default factory for constrained graphs.
Default factory for constrained graphs. Graph instances returned from this factory will be immutable.
 object Or extends BinaryOp with Product with Serializable

object
PreCheckFollowUp
extends Enumeration
Enumerates the possible return statuses (also: followup activity) of a precheck:
Abort
instructs the caller to cancel the operation because the precheck failed;PostCheck
means that the postcheck (commit) still must be called;Complete
means that the operation can safely be completed without invoking the postcheck.  object PreCheckResult extends PreCheckResultCompanion

object
Tree
extends CompanionAlias[UnDiEdge]
Companion module for default (immutable) undirected connected acyclic
Graph
.