Package

scalax.collection

constrained

Permalink

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.

Linear Supertypes
Content Hierarchy Learn more about scaladoc diagrams
Ordering
  1. Alphabetic
  2. By inheritance
Inherited
  1. constrained
  2. AnyRef
  3. Any
  1. Hide All
  2. Show all
Visibility
  1. Public
  2. All

Type Members

  1. sealed trait BinaryOp extends Op

    Permalink
  2. abstract class CompanionAlias[E[X] <: EdgeLikeIn[X]] extends GraphConstrainedCompanionAlias[Graph, E]

    Permalink

    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")
  3. type Config = ConstrainedConfig

    Permalink

    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
  4. trait Constrained[N, E[X] <: EdgeLikeIn[X]] extends ConstraintMethods[N, E] with ConstraintHandlerMethods[N, E]

    Permalink

    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

  5. abstract class Constraint[N, E[X] <: EdgeLikeIn[X]] extends ConstraintMethods[N, E] with ConstraintHandlerMethods[N, E]

    Permalink

    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

  6. class ConstraintBinaryOp[N, E[X] <: EdgeLikeIn[X]] extends ConstraintOp[N, E]

    Permalink
  7. trait ConstraintCompanion[+CC[N, E[X] <: EdgeLikeIn[X]] <: Constraint[N, E[X]]] extends AnyRef

    Permalink

    Base trait for ordinary Constraint companion objects.

  8. class ConstraintCompanionBinaryOp extends ConstraintCompanionOp

    Permalink

    Facilitates binary operations on ConstraintCompanions.

  9. abstract class ConstraintCompanionOp extends ConstraintCompanion[Constraint]

    Permalink

    Base class for any operation on ConstraintCompanions.

  10. trait ConstraintHandlerMethods[N, E[X] <: EdgeLikeIn[X]] extends AnyRef

    Permalink

    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
  11. trait ConstraintMethods[N, E[X] <: EdgeLikeIn[X]] extends AnyRef

    Permalink

    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 or post. Pre-ckecks return Abort, PostCheck or Complete while post-checks return Boolean stating whether the operation should be committed or rolled back. Pre-checks can inspect the operands only. In contrast, post-checks additionally allow to inspect the would-be graph after the operation has taken place but has not yet been committed.

    For performance reasons, implementations should prefer implementing pre-check methods. If it's necessary to check not only the operands but the whole would-be graph, the appropriate post-check methods should be overridden.

  12. abstract class ConstraintOp[N, E[X] <: EdgeLikeIn[X]] extends Constraint[N, E]

    Permalink
  13. type DAG[N] = Graph[N, DiEdge]

    Permalink

    Default (immutable) directed acyclic Graph.

  14. type Forest[N] = Graph[N, UnDiEdge]

    Permalink

    Default (immutable) undirected acyclic Graph.

  15. trait Graph[N, E[X] <: EdgeLikeIn[X]] extends Set[Param[N, E]] with collection.Graph[N, E] with GraphLike[N, E, Graph]

    Permalink

    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.

  16. 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]

    Permalink

    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 inherits DirectedEdgeLike 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.

  17. sealed trait Op extends AnyRef

    Permalink
  18. class PreCheckResult extends AnyRef

    Permalink

    The return type of any pre-check.

    The return type of any pre-check. followUp contains the return status (follow-up activity). Constraint implementations are encouraged to extend this class to contain further data calculated in course of the pre-check and reusable in the following post-check.

  19. trait PreCheckResultCompanion extends AnyRef

    Permalink
  20. type Tree[N] = Graph[N, UnDiEdge]

    Permalink

    Default (immutable) undirected connected acyclic Graph.

  21. trait UserConstrainedGraph[N, E[X] <: EdgeLikeIn[X]] extends Graph[N, E]

    Permalink

Value Members

  1. object And extends BinaryOp with Product with Serializable

    Permalink
  2. def Config: ConstrainedConfig.type

    Permalink

    Companion object to configure Graph instances in the scope including ArraySet.Hints:

    Companion object to configure Graph instances in the scope including ArraySet.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
  3. object DAG extends CompanionAlias[DiEdge] with Serializable

    Permalink

    Companion module for default (immutable) directed acyclic Graph.

  4. object Forest extends CompanionAlias[UnDiEdge] with Serializable

    Permalink

    Companion module for default (immutable) undirected acyclic Graph.

  5. object Graph extends GraphConstrainedCompanion[Graph] with Serializable

    Permalink

    Default factory for constrained graphs.

    Default factory for constrained graphs. Graph instances returned from this factory will be immutable.

  6. object Or extends BinaryOp with Product with Serializable

    Permalink
  7. object PreCheckFollowUp extends Enumeration

    Permalink

    Enumerates the possible return statuses (also: follow-up activity) of a pre-check: Abort instructs the caller to cancel the operation because the pre-check failed; PostCheck means that the post-check (commit) still must be called; Complete means that the operation can safely be completed without invoking the post-check.

  8. object PreCheckResult extends PreCheckResultCompanion

    Permalink
  9. object Tree extends CompanionAlias[UnDiEdge] with Serializable

    Permalink

    Companion module for default (immutable) undirected connected acyclic Graph.

  10. package config

    Permalink
  11. implicit def constraintToConfig(constraint: ConstraintCompanion[Constraint])(implicit orderHint: Int = GraphConfig.defaultOrder, adjacencyListHints: Hints = ArraySet.Hints()): ConstrainedConfig

    Permalink

    Converts constraint to an instance of config.ConstrainedConfig.

  12. package constraints

    Permalink

    Predefined constraints that may be passed to constrained Graphs.

  13. def dagConstraint: constrained.constraints.Acyclic.PrefixedConstraintCompanion

    Permalink

    Constraint representing a DAG.

  14. def forestConstraint: constrained.constraints.Acyclic.PrefixedConstraintCompanion

    Permalink

    Constraint representing a forest.

  15. package generic

    Permalink
  16. package immutable

    Permalink
  17. package mutable

    Permalink

    Mutable constrained graph templates.

  18. def treeConstraint: constrained.ConstraintCompanionBinaryOp.PrefixedConstraintCompanion

    Permalink

    Constraint representing an undirected tree.

Inherited from AnyRef

Inherited from Any

Ungrouped