# 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`:

In contrast, operations on constrained `Graph`s have the following sophisticated lifecycle:

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) {
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.