Core User Guide: Initializing Graphs


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:

Edge Type Hierarchy
Diagram: Edge Type Hierarchy.

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

  1. 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.
  2. Creates the very same undirected graph as a). Operator ~ is just a short-hand for invoking the factory UnDiEdge.
  3. 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.
  4. 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.
  5. 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.
  6. Creates a Graph from the Iterable values nodes and edges. This Graph instance  g3 equals to g1.
  7. 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

  1. 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.
  2. In absence of any edge arguments, Nothing is inferred for the edge type so you can add only nodes to this instance later on.
  3. 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].
  4. 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])


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.