The downloadable binaries are named
Graph<module>_<Scalaversion><Graphversion>.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 Graphcore_*.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._
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 nonweighted, weighted (W
), keyweighted (Wk
),
labeled (L
) and keylabeled (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:
Type of graph 
Definition The graph contains... 
Edge Type ...or any corresponding custom edge type 
Simple  only undirected edges without multiedges 
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 multiedges 
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 multiedges 
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 multiedges  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 hashbased collections is not
specified if the value of an element is changed in a manner that affects equals
comparisons  see
java.util.Map.
(Having illdesigned 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.)
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
keylabeled with x

(1 ~%+# 2)(x) 
WLkUnDiEdge(1,2)(5,x) 
undirected edge between 1 and 2
with a weight of 5 and keylabeled 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:
Edge Category  Edge Class  Shortcut  Description 
Hyperedge  HyperEdge 
~  hyperedge 
WHyperEdge 
~%  weighted hyperedge  
WkHyperEdge 
~%#  keyweighted hyperedge  
LHyperEdge 
~+  labeled hyperedge  
LkHyperEdge 
~+#  keylabeled hyperedge  
WLHyperEdge 
~%+  weighted labeled hyperedge  
WkLHyperEdge 
~%#+  keyweighted labeled hyperedge  
WLkHyperEdge 
~%+#  weighted keylabeled hyperedge  
WkLkHyperEdge 
~%#+#  keyweighted keylabeled hyperedge  
Directed Hyperedge  DiHyperEdge 
~>  directed hyperedge 
WDiHyperEdge 
~%>  weighted directed hyperedge  
WkDiHyperEdge 
~%#>  keyweighted directed hyperedge  
LDiHyperEdge 
~+>  labeled directed hyperedge  
LkDiHyperEdge 
~+#>  keylabeled directed hyperedge  
WLDiHyperEdge 
~%+>  weighted labeled directed hyperedge  
WkLDiHyperEdge 
~%#+>  keyweighted labeled directed hyperedge  
WLkDiHyperEdge 
~%+#>  weighted keylabeled directed hyperedge  
WkLkDiHyperEdge 
~%#+#>  keyweighted keylabeled directed hyperedge  
Undirected Edge  UnDiEdge 
~  undirected edge 
WUnDiEdge 
~%  weighted undirected edge  
WkUnDiEdge 
~%#  keyweighted undirected edge  
LUnDiEdge 
~+  labeled undirected edge  
LkUnDiEdge 
~+#  keylabeled undirected edge  
WLUnDiEdge 
~%+  weighted labeled undirected edge  
WkLUnDiEdge 
~%#+  keyweighted labeled undirected edge  
WLkUnDiEdge 
~%+#  weighted keylabeled undirected edge  
WkLkUnDiEdge 
~%#+#  keyweighted keylabeled undirected edge  
Directed Edge  DiEdge 
~>  directed edge 
WDiEdge 
~%>  weighted directed edge  
WkDiEdge 
~%#>  keyweighted directed edge  
LDiEdge 
~+>  labeled directed edge  
LkDiEdge 
~+#>  keylabeled directed edge  
WLDiEdge 
~%+>  weighted labeled directed edge  
WkLDiEdge 
~%#+>  keyweighted labeled directed edge  
WLkDiEdge 
~%+#>  weighted keylabeled directed edge  
WkLkDiEdge 
~%#+#>  keyweighted keylabeled directed edge 
To bring the predefined weighted or labeled edge classes and the
corresponding shortcuts into scope you need additional import
s,
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)
.
Keyed edges (keyweighted and/or keylabeled 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 patternmatch 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 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
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
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.
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
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
.
~
is just a shorthand for invoking the factory UnDiEdge
.
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.
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.
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.
Graph
from the Iterable
values nodes
and edges
. This Graph
instance g3
equals to g1
.
Graph
instance with 100 edges {0~1, 1~2, ..., 99~100}.
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
Nothing
is inferred for both the node
and the edge type so you cannot add any nodes or edges to this instance later on.
Nothing
is inferred for the
edge type so you can add only nodes to this instance later on.
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]
.
[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.