Constrained User Guide

Introduction

This module enables the user of Graph for Scala to seamlessly integrate predefined or custom constraints. Constraints are meant to ensure certain graph properties during the whole lifetime of graph instances which are not enforceable through type parameters. Examples for common constraints are connected, acyclic, tree, planar etc. Furthermore, the user is free to provide a custom constraint implementation covering any domain-specific requirements.

Predefined constraints are placed in scalax.collection.constrained.constraints but currently few predefined constraints are provided. We would certainly be obliged if you contributed your constraint implementation to enhance the library.

Graphs may be constrained dynamically or statically. A Graph is called dynamically constrained if a constraint has been passed to its factory method on creation or if it is a result of an operation based on a dynamically constrained Graph:

import scalax.collection.GraphPredef._,
       scalax.collection.GraphEdge._
import scalax.collection.constrained._ // replaces scalax.collection.Graph
import scalax.collection.constrained.constraints.Connected

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

In the above example, e, g, h and i are constrained by the Connected constraint. e remains empty because the initial elements would not result in a connected graph. Likewise, h becomes equal to g. Alternatives of error handling are covered in the following chapters.

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

A statically constrained Graph incorporates all validations necessary to impose the desired constraint on all operations. Thus no constraint needs to be passed to it on creation. Clearly, any dynamically constrained Graph could also be implemented statically once the constraint is known but dealing with constraints is more flexible and also cheaper to implement. A static implementation might be worthwhile whenever we face broad use and/or need to restrict type parameters such as in case of DAGs.

Graph for Scala Constrained is supplied as an extra module (Graph-constrained_<ScalaVer>-<GraphVer>.jar) depending on Graph-core_<ScalaVer>-<GraphVer>.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 must cope with the population or modification of Graph instances in an uncontrolled way such as
    • user input that is not fully validatable with respect to the Graph or
    • import of invalidated data from an external source.
  3. You want to log or monitor any kind of Graph creation/modification – 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 simple, non-constrained Graph:

Empty Lifecycle
Diagram: Empty Lifecycle of simple Graph operations.

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

Lifecycle
Diagram: Empty Lifecycle of constrained Graph operations.

Pre-check, post-check and handle depict the three groups of callback-methods to be defined by the implementer of the constraint class. Each group consists of a few concrete methods such as preAdd(node: N), preAdd(edge: E[N])etc.

The pre-check call-back methods are a means to inspect the underlying Graph and the arguments of the operation before the operation takes place. They take control over whether the operation is to be carried out or aborted (return: Abort). The carry-out case offers to carry out the operation either with (return: PostCheck) or without (return: Complete) a subsequent post-check.

In the post-check call-back methods one may inspect the underlying Graph as it would be after the operation and take control over whether the operation is to be committed (return: true) or rolled back (return: false).

Whenever the operation has been told by the constraint to be aborted, the appropriate constraint handler is called. It is up to the implementer to throw an Exception in the handler, to leave it silent or undertake any other desirable action.

Altering Existing Constraints

Modifying an existing constraint is as easy as supplying a new companion object with the modified behavior. For instance, to let the onAdditionRefused error handler of the predefined Acyclic constraint throw an exception on improper Graph creation or on addition of any improper elements, just proceed as follows:

object AcyclicWithException extends ConstraintCompanion[Acyclic] {
  def apply [N, E[X] <: EdgeLikeIn[X]] (self: Graph[N,E]) =
    new Acyclic[N,E] (self) {
      override def onAdditionRefused(refusedNodes: Iterable[N],
                                     refusedEdges: Iterable[E[N]],
                                     graph:        Graph[N,E]) = {
        throw new CycleException("Addition refused: " +
                  "nodes = " + refusedNodes + ", " +
                  "edges = " + refusedEdges)
      }
    }
}
class CycleException(msg: String) extends IllegalArgumentException(msg)

Implementing New Constraints

If none of the supplied constraints suffices 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 extending the Constrained trait.
    • Decide on each call-back method, whether abstract or concrete, whether and how to override it:
      • preCreate's default implementation calls preAdd for each node and edge. This will be insufficient for all cases where the set of these elements must be considered in its total. For instance, cycles cannot be detected by examining nodes and edges separately.
        If it is maintained that on loading the Graph it is already consistent, you can simply return PreCheckResult(Complete).
      • Implement preAdd(node: N) and preAdd(edge: E[N]). Ensure to make all checks possible at this early stage.
      • Decide on whether preAdd(elems: GraphParamIn[N,E]*) is to be overridden. Here the same holds as for preCreate, as the default implementation just calls preAdd element-wise.
      • Decide on whether postAdd is to be overridden. If you have made all necessary checks in the pre-checks concerned with addition, you need not do anything as postAdd's default return is true which advises Graph to commit the addition.
      • Do the same with respect to the call-back methods concerned with subtraction.
      • Decide on whether to override any of the error handlers onAdditionRefused or onSubtractionRefused. They return true by default meaning that operations that abort or roll back will be left without a notice.
  2. Constraint Companion Object
    • Create your constraint companion object by extending the ConstrainedCompanion trait. Ensure that the type constructor argument for ConstrainedCompanion is your custom constraint class.
    • Override apply in your constraint companion object to return an instance of your constraint class.
  3. Constraint Test

Although call-backs 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. Examine scalax.collection.constrained.constraints. Acyclic for an example.

Once again, if you feel the community could benefit of your constraint implementation, please consider contributing it.

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 go a step even further by calling the factory methods without repeatedly supplying your constraints.

Suppose you prefer writing

val t = Tree.from(nodeList, edgeList) // Tree(´┐¢)

in contrast to the example in 6. Well, you can do this right away because the Tree alias is already present in the constrained module. This is how it has been achieved:

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

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

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

CompanionAlias is a wrapper trait enabling you to easily construct constrained Graph companion module aliases. You may use it as long as the edge type of your Graph instances is constant. If you are using an edge type other than UnDiEdge, such as a labelled edge type in your Tree, you might consider defining your own alias with a labelled edge type parameter or simply forego using an alias.

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