Core User Guide: Customizing Graphs

You can start to utilize Graph out of the box but often you want to achieve a certain degree of customization. Basically, the following kinds of customization are eligible:

Altering Configuration Options

In the default implementation, adjacency lists are represented by ArraySets, a specific collection type included in Graph-core. ArraySets bank on JVM native arrays to provide higher performance.

Mostly you can go with the default ArraySet settings which were chosen by careful measurements. In production however, it may be desirable to tune them. Based on the node density and density distribution of your graphs you can determine up to which number of neighbors the underlying ArraySets should use arrays. Once this limit is reached, ArraySet will transparently switch from the array to hash set representation.

Let g be your Graph instance. Then

g.config

returns the immutable configuration for g. To override these settings, define your own implicit value prior to Graph creation: 

import scalax.collection.config.CoreConfig
import scalax.collection.mutable.ArraySet.Hints
implicit val myConfig = CoreConfig(orderHint = 5000, Hints(64, 0, 64, 75))

The first argument will be used for preallocations depending on the expected order of the graph. The second argument ensures that both the initial array capacity and the hash set limit are set to 64. These values would be preferable for Graphs with an average node degree of roughly 30 to 55 for the majority of nodes. For more details please refer to the Scaladoc of ArraySet.Hints.

Enriching Graph

You may want to add new methods to the library implementation of Graph or its inner traits InnerNodeLike, NodeSet, InnerEdgeLike or EdgeSet. Adding new methods to Graph may be achieved by the standard enrich my library pattern using implicit functions.

To enrich Graph with your own methods simply use the enrich-me pattern like: 

implicit class ExtGraph[N, E[X] <: EdgeLikeIn[X]](g: Graph[N,E]) {
  def foo = "bar"
}
Graph(1~2).foo

To enrich the inner type NodeT is more subtle: 

implicit class ExtGraphNode[N, E[X] <: EdgeLikeIn[X]](node_ : Graph[N,E]#NodeT) {
    type NodeT = graph.NodeT
    val graph = node_.containingGraph
    val node  = node_.asInstanceOf[NodeT]
    def foo = this.toString + "bar"
  }
  Graph(1~2).nodes.headOption map (_.foo)

For more sophisticated enrichment alternatives see TExtByImplicit.scala.

Defining Custom Edges

You may decide to bypass the predefined edge classes and design your own edge type. Recapping the Flight label example, it is also possible to define a custom edge type Flight. Armed with such a custom edge type you can create Graph instances of the type Graph[Airport, Flight]. For the sake of simplicity we design the Flight edge to have the single attribute flightNo. Given the node class 

case class Airport(val code: String) {
  override def toString = code // without Airport-prefix
}
val (ham, ny) = (Airport("HAM"), Airport("JFK")) // two nodes

assume we want to be able to write

val flight = ham ~> ny ## "007"	// flightNo 007 - doesn't work yet
val g = Graph(flight) // Graph[Airport, Flight] - doesn't work yet

Here is how to achieve the above requirements: 

case class Flight[+N](fromAirport: N, toAirport: N, flightNo: String)
  extends DiEdge[N](NodeProduct(fromAirport, toAirport))
  with    ExtendedKey[N]
  with    EdgeCopy[Flight]
  with    OuterEdge[N,Flight] 
{
  private def this(nodes: Product, flightNo: String) {
    this(nodes.productElement(0).asInstanceOf[N],
         nodes.productElement(1).asInstanceOf[N], flightNo)
  }
  def keyAttributes = Seq(flightNo)
  override def copy[NN](newNodes: Product) = new Flight[NN](newNodes, flightNo)
  override protected def attributesToString = s" ($flightNo)" 
}
object Flight {
  implicit final class ImplicitEdge[A <: Airport](val e: DiEdge[A]) extends AnyVal {
    def ## (flightNo: String) = new Flight[A](e.source, e.target, flightNo)
  } 
}

As to

  1. DiEdge should be the base of any directed custom edge. Airport is the node type.
  2. If any of the label attributes is part of the key of the edge type, ExtendedKey must be mixed in. An attribute is a key if it must be considered by equals. flightNo is such a key attribute because there may exist several flights from and to the same airport so we distinguished them by flightNo.
  3. All edge implementations must mix in EdgeCopy.
  4. All edge implementations must mix in OuterEdge.
  5. Key attributes must be added to this Seq.
  6. copy will be called by Graph transparently to create an inner edge. Thus copy plays the role of an inner edge factory. It must return an instance of the edge class.
  7. Establishes the Flight edge factory shortcut ## that propagates a directed edge to Flight.

Note that the supplied tests contain a more complete implementation of the flight example - see Flight.scala, TFlight.scala and FlightRouteMap.jpg in the repository.

In general, when deciding on how to define your custom edge, the following steps apply:

  1. Select a predefined edge class to derive from.
  2. If your edge type is labeled by one or more attributes, decide for each attribute whether it counts as a key or as a non-key attribute. You have to deal with key attributes only in case your graph is to be laid out for multi-edges. Then, similar to SQL database primary key design, the attributes making up the thought unique key must be defined as key attributes.
    If you have one or more key attributes, mix in ExtendedKey and enter all key attributes into the list returned by def keyAttributes which you must override.
    For any non-key attribute it is sufficient to be added as a constructor parameter.
  3. EdgeCopy must always be mixed in to override its abstract method copy.
  4. If you want to avoid any loop in your graph, you can achieve this by simply mixing in LoopFreeEdge.
  5. If weight is your single custom attribute go with either WUnDiEdge or WDiEdge. If you have more custom attributes you may select one of the predefined WL* edges but, for better type safety, you are recommended to implement your own custom edge.
  6. In your custom edge class you are free to override validate that is called at edge instantiation time. For instance, the predefined validate requires that no edge end equals to null.
  7. Optionally, customize toString. Notice that EdgeLike comes with several protected methods for prefixes, braces etc.such as attributesToString which just need to be overridden. Thus they remove the burden of programming toString from the bottom up.
  8. In the custom edge companion object, implement an implicit def to make edge creation more readable.
  9. Optionally, you are free to implement your custom edge factory shortcut. Doing this you may also opt to reuse any of standard edge factory shortcuts like ~ or ~>.

In case of mixed graphs, prefer an ADT of custom edge classes.

See also:
object scalax.collection.GraphEdge._
object scalax.collection.GraphPredef._

Defining User Constraints

Please refer to the Constrained User Guide.

Modifying Methods

You might want to modify methods of the library implementation of Graph or its inner traits InnerNodeLike, NodeSet, InnerEdgeLike or EdgeSet to alter their run-time behavior. However, be careful not to alter method semantics but add your own methods whenever applicable.

Providing new Implementations

Please refer to ExtNode.scala and TExtNode.scala respectively.