Core User Guide: Initializing Graphs

Prerequisites

The downloadable binaries are named Graph-<module>_<Scala-version>-<Graph-version>.jar following the Scala convention. For each <module> (here: core) there is a separate User Guide. To run the examples in the current documentation ensure that Graph-core_*.jar is on your class path.

In most cases you need to import the following:

import scalax.collection.Graph // or scalax.collection.mutable.Graph
import scalax.collection.GraphPredef._, scalax.collection.GraphEdge._

Type Parameters

trait Graph[N, E[X] <: EdgeLikeIn[X]]

N is the type of the nodes of a graph instance.

E[X] is the kind of type (also: higher kinded type) of edges of a graph instance.

The trait Graph and most related templates have two type parameters: one for the contained nodes and one for the kind of contained edges. Graph doesn't impose any restriction on the type of nodes meaning that for the upper bound of the node type parameter any type including Any may be chosen. In contrast, the type parameter for edges is required to have at least the upper bound EdgeLikeIn.

When selecting between the predefined edge types it might help you to understand their inheritance relationships:

All edge classes derive from trait EdgeLike and, optionally, from trait DiEdgeLike. There are four edge categories: hyperedge, directed hyperedge, undirected and directed edge. Each of these categories has predefined edge classes representing any combination of non-weighted, weighted (W), key-weighted (Wk), labeled (L) and key-labeled (Lk). See 2.3 Edge Factories for examples and more details.

Based on the above inheritance hierarchy, graph types in the sense of graph theory are governed by the edge type parameter E[X] as follows:

Table: Graph types mapped to edge types.
Type of graph	Definition The graph contains...	Edge Type ...or any corresponding custom edge type
Simple	only undirected edges without multi-edges	`UnDiEdge` or any of its variants `W`, `L` or `WL*` where the user is responsible to avoid adding directed edges as the type system does not restrict she to do so
Mixed	more than one type of edges without multi-edges	`UnDiEdge` or its parent types such as `HyperEdge` or any of their variants except the keyed ones
	or, as a use case, directed and undirected edges without multi-edges	`UnDiEdge` or any of its variants except the keyed ones
Weighted	edges with the special label `weight`	any of the predefined edge classes containing `W` in its prefix
Multi	One or more edge types with multi-edges	any of the predefined edge classes containing `K` in its prefix

There is no constraint on the node type, but you should be especially careful when designing mutable nodes: equals/hashCode must be constant over their lifetime. This is because the behavior of hash-based collections is not specified if the value of an element is changed in a manner that affects equals comparisons - see java.util.Map. (Having ill-designed mutable nodes, you are still able to find them in the graph by calling find or filter, but these calls will cause a full scan.)

Edge Factories

Table: Edge factory examples.
Shortcut	Named Factory	Meaning
`1~2~3`	`HyperEdge(1,2,3)`	(undirected) hyperedge between `1, 2` and `3`
`1~>2~>3`	`DiHyperEdge(1,2,3)`	directed hyperedge from `1` to `2` and `3`
`"A"~"B"`	`UnDiEdge("A","B")`	undirected edge between `"A"` and `"B"`
`"A"~>"B"`	`DiEdge("A","B")`	directed edge from `"A"` to `"B"`
`1~2 % 5`	`WUnDiEdge(1,2,5)`	undirected edge between `1` and `2` with a weight of `5`
`1~>2 % 0`	`WDiEdge(1,2,0)`	directed edge from `1` to `2` with a weight of `0`
`(1 ~+> 2)(x)`	`LDiEdge(1,2)(x)`	directed edge from `1` to `2` labeled with `x`
`(1 ~+#> 2)(x)`	`LkDiEdge(1,2)(x)`	directed edge from `1` to `2` key-labeled with `x`
`(1 ~%+# 2)(x)`	`WLkUnDiEdge(1,2)(5,x)`	undirected edge between `1` and `2` with a weight of `5` and key-labeled with `x`

Edge factories are simply apply methods of companion objects of edge classes. They are typically called whenever an edge is passed to a Graph method as an argument. The above table contains factory examples for some of the predefined edge classes.

Apart from the four basic edge classes [Di]HyperEdge and [Un]DiEdge there are plenty of convenience edge class variants enabling easy creation of weighted and/or labeled edges:

Table: Predefined edge classes.
Edge Category	Edge Class	Shortcut	Description
Hyperedge	`HyperEdge`	~	hyperedge
	`WHyperEdge`	~%	weighted hyperedge
	`WkHyperEdge`	~%#	key-weighted hyperedge
	`LHyperEdge`	~+	labeled hyperedge
	`LkHyperEdge`	~+#	key-labeled hyperedge
	`WLHyperEdge`	~%+	weighted labeled hyperedge
	`WkLHyperEdge`	~%#+	key-weighted labeled hyperedge
	`WLkHyperEdge`	~%+#	weighted key-labeled hyperedge
	`WkLkHyperEdge`	~%#+#	key-weighted key-labeled hyperedge
Directed Hyperedge	`DiHyperEdge`	~>	directed hyperedge
	`WDiHyperEdge`	~%>	weighted directed hyperedge
	`WkDiHyperEdge`	~%#>	key-weighted directed hyperedge
	`LDiHyperEdge`	~+>	labeled directed hyperedge
	`LkDiHyperEdge`	~+#>	key-labeled directed hyperedge
	`WLDiHyperEdge`	~%+>	weighted labeled directed hyperedge
	`WkLDiHyperEdge`	~%#+>	key-weighted labeled directed hyperedge
	`WLkDiHyperEdge`	~%+#>	weighted key-labeled directed hyperedge
	`WkLkDiHyperEdge`	~%#+#>	key-weighted key-labeled directed hyperedge
Undirected Edge	`UnDiEdge`	~	undirected edge
	`WUnDiEdge`	~%	weighted undirected edge
	`WkUnDiEdge`	~%#	key-weighted undirected edge
	`LUnDiEdge`	~+	labeled undirected edge
	`LkUnDiEdge`	~+#	key-labeled undirected edge
	`WLUnDiEdge`	~%+	weighted labeled undirected edge
	`WkLUnDiEdge`	~%#+	key-weighted labeled undirected edge
	`WLkUnDiEdge`	~%+#	weighted key-labeled undirected edge
	`WkLkUnDiEdge`	~%#+#	key-weighted key-labeled undirected edge
Directed Edge	`DiEdge`	~>	directed edge
	`WDiEdge`	~%>	weighted directed edge
	`WkDiEdge`	~%#>	key-weighted directed edge
	`LDiEdge`	~+>	labeled directed edge
	`LkDiEdge`	~+#>	key-labeled directed edge
	`WLDiEdge`	~%+>	weighted labeled directed edge
	`WkLDiEdge`	~%#+>	key-weighted labeled directed edge
	`WLkDiEdge`	~%+#>	weighted key-labeled directed edge
	`WkLkDiEdge`	~%#+#>	key-weighted key-labeled directed edge

To bring the predefined weighted or labeled edge classes and the corresponding shortcuts into scope you need additional imports, for instance

import scalax.collection.edge.LDiEdge     // labeled directed edge
import scalax.collection.edge.Implicits._ // shortcuts

While simple directed and undirected edge shortcuts may be used without parenthesis like 1 ~> 2, weighted and/or labeled edge shortcuts implicitly map to calls of functions with two parameter lists thus requiring parenthesis like (1 ~+> 2)(x).

Multigraphs by keyed edges

Keyed edges (key-weighted and/or key-labeled edges) come into play whenever you are designing multigraphs. Upon edge insertion Graph for Scala checks for edge equality to ensure no duplicate exists in the edge set. Normally, edge equality is merely based on the edge endpoints. So to allow multiedges it is necessary to enhance edge equality by including additional attributes like a label. We denote such an edge `keyed`. For instance, (n1 ~+> n2)(label_1) is equal to (n1 ~+> n2)(label_2) while (n1 ~+#> n2)(label_1) is not equal to (n1 ~+#> n2)(label_2). You need the latter, keyed edges to include both edges in a multigraph.

If your labels are of a compound type in the sense that they are made up of several attributes you should carefully analyze which parts of your labels ensure uniqueness because only those should become part of the edge key. Unless the edge key includes all parts of such a compound label type you need to override equals and hashCode to reflect the actual key parts. For instance, when designing a label type Flight for the predefined edge class LkDiEdge, you might observe, that only flightNo needs to be part of the edge key. Otherwise it would be possible to connect two airports with arcs showing to the same direction and with the same flightNo if the edges only differ in its departure. To cope with this problem you have to override equals and hashCode as follows:

case class Flight(flightNo : String,
                  departure: DayTime  = DayTime (0,0),
                  duration : Duration = Duration(0,0))
{ override def equals(other: Any) = other match {
    case that: Flight => (that.flightNo eq this.flightNo) ||
                          that.flightNo == this.flightNo
    case _            => false
  }
  override def hashCode = flightNo.##
}

By the way, you can roughly achieve the same by defining your case class with two parameter lists. The difference is that you can only pattern-match and copy on the first parameter list:

case class Flight(flightNo : String)(
                  val departure: DayTime  = DayTime (0,0),
                  val duration : Duration = Duration(0,0))

(The full example is included in TEdge.scala.)

Labeled edges

Labeled edges contain a reference to a label object but the containing graph does not know about the actual label type. This is because edges of the same graph instance are allowed to have different types by design.

As a consequence, when using labeled edges you need to match against the label value. This conversion is supported by the trait LEdgeImplicits[L]:

import scalax.collection.Graph
import scalax.collection.edge.LUnDiEdge
case class MyLabel(i: Int)
val outerEdge = LUnDiEdge(1,3)(MyLabel(4))
outerEdge.label.i // all right: 4
outerEdge.i       // compiler error

val g = Graph(outerEdge)           // Graph(1, 3, 1~3 'MyLabel(4))
g.edges.headOption map (_.label.i) // does not work either

// install implicit conversion for MyLabel 
import scalax.collection.edge.LBase.LEdgeImplicits
object MyImplicit extends LEdgeImplicits[MyLabel]; import MyImplicit._

outerEdge.i                        // all right: 4
g.edges.headOption map (_.label.i) // yep: Some(4)
g.edges.headOption map (_.i)       // you can even omit label

Hyperedge equality

Looking at the endpoints of a hyperedge respectively the sources or targets of a directed hyperedge, equality is even more weird. For instance, would you say that HyperEdge(1, 2, 2) is equal to HyperEdge(2, 2, 1) or not? It turns out that depending on the use case both propositions may be desirable to hold.

Graph for Scala currently supports two kinds of endpoint collections: Bag and Sequence. With Bag being the default kind, the above hyperedges are in fact equal. The endpoint collection kind is controled by an implicit value of the type CollectionKind. Define Sequence as an implicit value to turn this kind on:

import scalax.collection.GraphEdge._
implicit val kind: CollectionKind = Sequence
HyperEdge(1, 2, 2) == HyperEdge(2, 2, 1) // false

Bypassing edge factories

What is more, mutable Graph instances provide edge creation methods to be called directly on Graph instances (addEdge, +~=, addAndGetEdge) or on inner nodes (connectWith, +~). These methods should save execution time since less conversion is necessary to complete edge creation.

Instantiating Graphs

val g1 = Graph(3~1, 5)            // Graph[Int,UnDiEdge](1, 3, 5, 3~1)
val g2 = Graph(UnDiEdge(3, 1), 5) // same as above
val gA = Graph(3~>1.2)            // Graph[AnyVal,DiEdge](3, 1.2, 3~>1.2)
val h = Graph(1~1, 1~2~3)         // Graph[Int,HyperEdge](1, 2, 3, 1~1, 1~2~3)
val (jfc, fra, dme) = (Airport("JFC"), Airport("FRA"), Airport("DME"))
val flights = Graph(
	(jfc ~+#> fra)(Flight("LH 400" ,10 o 25, 8 h 20)),
	(fra ~+#> dme)(Flight("LH 1444", 7 o 50, 3 h 10))
val nodes = List(5)
val edges = List(3~1)
val g3 = Graph.from(nodes, edges)
var n, m = 0; val f = Graph.fill(100)( {n = m; m += 1; n~m} )

As to

Creates an undirected graph of the type Graph[Int,UnDiEdge]with the node set {1, 3, 5} and the edge set {3~1}. The operator ~ is used to create undirected edges. N is inferred to be Int because both the edge ends and the single node are of type Int.
Creates the very same undirected graph as a). Operator ~ is just a short-hand for invoking the factory UnDiEdge.
Creates a directed graph of the type Graph[AnyVal,DiEdge] with the node set {3, 1.2} and the edge set {3~>1.2}. The operator ~> is used to create directed edges. N is inferred to be AnyVal because this is the smallest common super type of the edge ends.
Creates a hypergraph of the type Graph[Int,HyperEdge]with the node set {1, 2, 3} and the edge set {1~1, 1~2~3}. In 1~2~3 the second ~ operator creates an undirected hyperedge because the left operand is already an edge.
Creates an instance of Graph[Airport,LkDiEdge] with a node set containing the airports JFC, FRA and DME derived from the edge ends and an edge set containing two flights. The edges have labels of the type Flight, ~+#> is an edge factory shortcut to pass the labels. The Flight attributes are flight number, departure time and flight duration. See also 2.3 Edge Factories.
Creates a Graph from the Iterable values nodes and edges. This Graph instance g3 equals to g1.
Creates a Graph instance with 100 edges {0~1, 1~2, ..., 99~100}.

Type Parameter Inference

val g = Graph()                // Graph[Nothing,Nothing]
val g = Graph(1)               // Graph[Int,Nothing]
val g = Graph(1~>2); g += 1.2  // Graph[Int,DiEdge]; compiler error
Graph(1~>2) + 2~3              // compiler error

Calling the default Graph factory without type parameters is in general satisfactory if at least one edge is passed. Otherwise, analogously to regular Scala collection members, you are advised to explicitly define the type parameters:

As to

In absence of any arguments, Nothing is inferred for both the node and the edge type so you cannot add any nodes or edges to this instance later on.
In absence of any edge arguments, Nothing is inferred for the edge type so you can add only nodes to this instance later on.
To be able to add a Double to this instance, you must define its type parameters broader at creation time like Graph[AnyVal,DiEdge]. Also note that, due to the higher kinded nature of the E[X] type parameter, DiEdge is correctly inferred – even if some of you would expect DiEdge[Int].
This addition is rejected by the compiler because [Int,DiEdge] is inferred and 2~3 is not a directed but an undirected edge. Directed edges inherit from undirected edges but the opposite is not true.

As a final note, whenever you are implementing own functionality on top of Graph, the Scala type system requires to declaratively maintain type parameter bounds as shown in the following example:

def myFunction[N, E[X] <: EdgeLikeIn[X]](g: Graph[N,E])

Implementations

As common to members of scala.collection, Graph for Scala comes with separate implementations for immutable and mutable Graph's. For your convenience, the companion objects ensure the selection of an appropriate underlying default implementation so you normally don't have to take any specific action.