# Constrained User Guide

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

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

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.