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
Graph that are not adequately enforceable by the type system.
Examples for common constraints are
Based on this module you are free to implement your own custom constraint to cover your domain-specific requirements.
Predefined constraints are placed in
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
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)
Graphusing the above implicit value.
ebecomes empty because the total of the passed elements violates the constraint.
Graphaccepting the passed elements.
3is silently rejected because it would create an isolated node.
2 ~ 3is 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
and return an
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
Graph for Scala Constrained is supplied as an extra module
Among others, the constrained module is worth considering in the following situations:
Graphinstances. Typical examples are acyclic graphs or tree structures.
Graphinstances that occur in an uncontrolled way such as by
Graphcreation/modification – with respect to being proper or improper.
For the purpose of a comparison, let's first illustrate the "lifecycle" of an operation such as
+= on a non-constrained
In contrast, operations on constrained
Graphs 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
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
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:
or rolled back (return:
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
along with its accompanying test
Constraint implementations involve the following steps:
preCreate's default implementation calls
preAddfor 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.
preAdd(edge: E[N]). Make sure you have carried out all checks in this early phase.
preAdd(elems: GraphParamIn[N,E]*)is to be overridden. Here the same applies as for
preCreate: the default implementation just calls
postAddis 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.
ConstrainedCompaniontrait. Notice that the type constructor argument for
ConstrainedCompanionneeds be your custom constraint class.
applyof 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
fill an instance of your type with the computational results and return it in place of a simple
PreCheckResult instance. See
for an example.
If you feel the community could take benefit of your constraint implementation, please consider contribution.
Constraints may be composed by the
|| operators like:
implicit val conf: Config = Connected && Acyclic // ConstrainedConfig(...) val e = Graph.from(nodeList, edgeList)
By now you know when and how to implement constraints and how to pass them to
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
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.
withStringPrefix enables you to replace the default
toString with a custom prefix.