Constrained User Guide 1.13

Introduction

This module enables the user of Graph for Scala to seamlessly integrate predefined or custom constraints. A constraint aims at enforcing any graph properties during the whole lifetime of a Graph that are not adequately enforceable by the type system. Examples for common constraints are Connected, Acyclic, Tree, Planar etc. Based on this module you are free to implement your own custom constraint to cover your domain-specific requirements.

Predefined constraints are placed in scalax.collection.constrained.constraints. We certainly appreciate your contributing any additional constraint that may be of interest to the community.

To take advantage of constrained Graphs you need to change your import and pass any predefined or custom constraint at Graph creation time like: 

import scalax.collection.GraphPredef._
import scalax.collection.GraphEdge._
import scalax.collection.constrained.mutable.Graph
import scalax.collection.constrained.constraints.Connected

implicit val conf: Config = Connected
val e = Graph(1 ~ 2, 3 ~ 4) // Graph()
val g = Graph(1 ~ 2, 2 ~ 4) // Graph(1, 2, 4, 1~2, 2~4)
g += 3                      // Graph(1, 2, 4, 1~2, 2~4)
g += 2 ~ 3                  // Graph(1, 2, 3, 4, 1~2, 2~3, 2~4)

As to

  1. Choosing mutable constrained Graph.
  2. Referring to the predefined constraint Connected.
  3. Creates a connected Graph using the above implicit value. e becomes empty because the total of the passed elements violates the constraint.
  4. Creates a connected Graph accepting the passed elements.
  5. Adding 3 is silently rejected because it would create an isolated node.
  6. Adding 2 ~ 3 is carried out since the resulting graph remains connected.

All operations also known in non-constrained graphs will enforce the constraint but won't be responsive about whether the operation has been accepted or rejected. Whenever rejected, the Graph will silently remain unchanged.

If you are interested in whether or why an operation has been refused, simply call its verbose counterpart. These additional operators/methods are denoted by a ?/_? suffix and return an Either[ConstraintViolation, R] with R being the return type of the non-suffixed counterpart operator/method: 

val e = Graph.from_?(edges = 1 ~ 2, 3 ~ 4) // Left(...)
val g = Graph.from_?(edges = 1 ~ 2, 2 ~ 4) // Right(Graph(1, 2, 4, 1~2, 2~4))
g +=? 3                                    // Left(...)
g +=? 2 ~ 3                                // Right(Graph(1, 2, 3, 4, 1~2, 2~3, 2~4))

Constraints may also be combined by means of the && and || operators.

Graph for Scala Constrained is supplied as an extra module (graph-constrained_<ScalaVer>-<Graph4ScalaVer>.jar).

Use cases

Among others, the constrained module is worth considering in the following situations:

  1. You have to ensure that some constraints which cannot be achieved by type constructors are valid at any time for your Graph instances. Typical examples are acyclic graphs or tree structures.
  2. In addition to 1., you need to control the population or modification of Graph instances that occur in an uncontrolled way such as by
    • user input that is not fully validatable with respect to your Graph constraint or
    • import of invalidated data from an external source.
  3. You want to log or monitor Graph creation/modification – with respect to being proper or improper.

The constraint lifecycle

For the purpose of a comparison, let's first illustrate the "lifecycle" of an operation such as + or += on a non-constrained Graph:

Empty Lifecycle
Diagram: Trivial Lifecycle of non-constrained Graph operations.

In contrast, operations on constrained Graphs have the following sophisticated lifecycle:

Lifecycle
Diagram: Lifecycle of constrained Graph operations.

Pre-check and post-check depict the two groups of callback methods to be defined in any constraint implementation. Both groups have a few concrete methods such as preAdd(node: N), preAdd(edge: E[N]) etc.

The pre-check methods allow the implementation to inspect the underlying Graph and the arguments being passed to the operation before the operation effectively takes place. They take control of whether the operation is performed or aborted. For the latter Abort is to be returned. In case the pre-check method requests the operation to be performed, it may do so by either returning PostCheck) or Complete this way telling whether post-check is to be called or skipped.

In the post-check callback methods one may inspect the underlying Graph as it would be after the operation and take control of whether the operation is to be "committed" (return: Right) or rolled back (return: Left).

Implementing your own constraint

If none of the supplied constraints meets your needs you are encouraged to implement your own constraint.

To warm up, you might contemplate the rather simple predefined constraint Connected.scala along with its accompanying test TConnected.scala.

Constraint implementations involve the following steps:

  1. Constraint Class
    • Create your constraint class by extending the Constrained trait.
    • For each callback method, decide whether and how to override it:
      • preCreate's default implementation calls preAdd for each node and edge. This will be insufficient for any case where the set of these elements must be considered in its total. For instance, cycles cannot be detected by examining nodes and edges separately. So in such cases you are recommended to provide a separate implementation.
      • Implement preAdd(node: N) and preAdd(edge: E[N]). Make sure you have carried out all checks in this early phase.
      • Decide on whether preAdd(elems: GraphParamIn[N,E]*) is to be overridden. Here the same applies as for preCreate: the default implementation just calls preAdd element-wise.
      • Decide on whether postAdd is to be overridden. If you have already made all necessary checks in the pre-checks concerned with addition, use the default implementation that instructs Graph for Scala to commit the operation result without calling the corresponding post-check method.
      • Do the same with respect to the callback methods concerned with subtraction.
  2. Constraint Companion Object
    • Create your constraint companion object by extending the ConstrainedCompanion trait. Notice that the type constructor argument for ConstrainedCompanion needs be your custom constraint class.
    • Override apply of your constraint companion object to return an instance of your constraint class.

Although callbacks are designed to be passed all necessary arguments to decide on how to deal with the operation, sometimes you might desire to carry over intermediate results computed in a pre-check to the corresponding post-check. For this purpose, you just need to subclass Result, fill an instance of your type with the computational results and return it in place of a simple PreCheckResult instance. See scalax.collection.constrained.constraints.Acyclic for an example.

If you feel the community could take benefit of your constraint implementation, please consider contribution.

Composing constraints

Constraints may be composed by the && and || operators like: 

implicit val conf: Config = Connected && Acyclic // ConstrainedConfig(...)
val e = Graph.from(nodeList, edgeList)

Providing aliases

By now you know when and how to implement constraints and how to pass them to Graph values at instantiation time. You may wonder how to call factory methods without repeatedly supplying your constraint.

Would you prefer writing 

val t = Tree.from(nodes, edges)

with no preceding implicit declaration? Well, you can do this right away because the Tree alias is already present in the constrained module. Here is how it has been achieved: 

import scalax.collection.GraphEdge._
import scalax.collection.constrained.Graph

type Tree[N] = Graph[N,UnDiEdge]
object Tree extends CompanionAlias[UnDiEdge](Connected && Acyclic
                                             withStringPrefix "Tree")

Obviously, you can provide your own aliases by following the above pattern.

CompanionAlias is a wrapper trait enabling you to easily construct constrained Graph companion aliases. You can use such an alias if the edge type of your Graph instances does not vary.

Finally, withStringPrefix enables you to replace the default Graph prefix used by toString with a custom prefix.