After the planning phase, you have made a decision about the type of nodes and edges you will be using. Here you will learn how to set up and populate your graph in detail.
trait Graph[N, E <: Edge[N]]
N
type of the nodes like a concrete class
, a trait
or an ADT.
E
type of the edges like a concrete class
, a trait
or an ADT.
The node type is unconstrained. Normally you will opt for immutable nodes but sometimes mutable nodes might
make sense. When using mutable nodes, beware that only fields that are not used by the class'
equals
/hashCode
may be mutated.
Otherwise, you would be posed to observe issues on adding or looking up nodes.
This is because the behaviour of hashbased collections is not specified if the value of a field is changed
such that equals
/hashCode
are affected  see also
java.util.Map.
To get the appropriate edge type, look up your use case in the following decision tables. We use the term
Double
.
Note that, in general, edges always have a default weight of 1
and
you can also define a specific weight function for any custom edge.
Type of graph  import scalax.collections...  Edge type 
simple directed or undirected graph  edges._ 
DiEdge or UnDiEdge

simple directed or undirected hypergraph  hyperedges._ 
DiHyperEdge or HyperEdge

Type of graph  import scalax.collections...  Edge type 
simple directed or undirected graph  edges.labeled._ 
WDiEdge or WUnDiEdge

directed or undirected multigraph  edges.multilabeled._ 
WDiEdge or WUnDiEdge

simple directed or undirected hypergraph  hyperedges.labeled._ 
derive custom edge from LDiHyperEdge or LDiHyperEdge ,override def weight

directed or undirected multi hypergraph 
hyperedges.multilabeled._ ,generic.ExtendedKeyByWeight orgeneric.MultiEdge

derive custom edge from LDiHyperEdge or LDiHyperEdge ,override def weight ,if you need to add only weight to define eqauality mix in ExtendedKeyByWeight ,
otherweise mix in MultiEdge

Type of graph  import scalax.collections...  Edge type 
simple directed or undirected graph  edges.labeled._ 
derive custom edge from LDiEdge or LUnDiEdge

directed or undirected multigraph  edges.multilabeled._ 
derive custom edge from LDiEdge or LUnDiEdge ,implement def extendKeyBy

simple directed or undirected hypergraph  hyperedges.labeled._ 
derive custom edge from LDiHyperEdge or LHyperEdge

simple directed or undirected hypergraph with ordered hyperedges  hyperedges.ordered.labeled._ 
derive custom edge from LDiHyperEdge or LHyperEdge

directed or undirected multi hypergraph  hyperedges.multilabeled._ 
derive custom edge from LDiHyperEdge or LHyperEdge ,implement def extendKeyBy

directed or undirected multi hypergraph with ordered hyperedges  hyperedges.ordered.multilabeled._ 
derive custom edge from LDiHyperEdge or LHyperEdge ,implement def extendKeyBy

Type of graph  import scalax.collections...  Edge type 
simple directed labeled graph  generic.AbstractDiEdge 
derive custom edge from AbstractDiEdge

simple undirected labeled graph  generic.AbstractUnDiEdge 
derive custom edge from AbstractUnDiEdge

directed labeled multigraph 
generic.AbstractDiEdge ,generic.MultiEdge

derive custom edge from AbstractDiEdge ,mix in MultiEdge

undirected labeled multigraph 
generic.AbstractUnDiEdge ,generic.MultiEdge

derive custom edge from AbstractUnDiEdge ,mix in MultiEdge

simple directed labeled hypergraph  generic.AbstractDiHyperEdge 
derive custom edge from AbstractDiHyperEdge

simple undirected labeled hypergraph  generic.AbstractHyperEdge 
derive custom edge from AbstractHyperEdge

directed labeled multi hypergraph 
generic.AbstractDiHyperEdge ,generic.MultiEdge

derive custom edge from AbstractDiHyperEdge ,mix in MultiEdge

undirected labeled multi hypergraph 
generic.AbstractHyperEdge ,generic.MultiEdge

derive custom edge from AbstractHyperEdge ,mix in MultiEdge

Often your graph contains directed and also undirected edges/hyperedges.
To denote such a mixed graph, refer to the trait
s prefixed by Any
.
Once you have chosen your mixed edge types you will need to define their common ancestor
in terms of these Any*
traits:
Graph[MyNode, AnyEdge[MyNode]]
.sealed trait MyEdge extends AnyEdge[MyNode]
.
Graph contains  Edge type in scalax.collections... 
directed and undirected edges  generic.AnyEdge 
directed edges and hyperedges  generic.AnyDiHyperEdge 
directed and undirected edges and hyperedges  generic.AnyHyperEdge 
It is in your hands to follow library conventions or stay with the simplest possible, Javalike implementation. We provide separate traits for every aspect of those conventions to facilitate a finegrained selection.
Go for the syntactic sugar ~>
and its companions if you like. As per library convention
The infix constructor of  Uses the node operator  Like 
directed edges  ~> 
1 ~> 2 
undirected edges  ~ 
1 ~ 2 
directed hyperedges  ~~> 
more(1, 1) ~~> one(2) 
hyperedges  ~~ 
1 ~~ 1 ~~ 2 
and
The infix constructor of  Uses the label operator  Like 
weighted edges  % 
1 ~> 2 % 5.5 
weighted multiedges  %% 
1 ~ 2 %% 5.5 
any other nonmulti edge  :+ 
1 ~> 2 :+ labels 
more(1, 1) ~~> one(2) :+ labels 

any other multiedge  :++ 
1 ~ 2 :++ labels 
more(1, 1) ~~> one(2) :++ labels 
In case your custom edge is not labeled you can extend one of the following traits:
Edge type  Supporting trait in scalax.collections 
directed  generic.AbstractDiEdgeImplicits 
undirected  generic.AbstractEdgeImplicits 
hyperedge 
generic.AbstractHyperEdgeImplicits.FromAny generic.AbstractHyperEdgeImplicits.FromEdge

directed hyperedge  generic.AbstractDiHyperEdgeImplicits.FronOneOrMore 
Create the implicit conversion to employ a standard infix constructor like
case class MyDiEdge(source: String, target: String) extends AbstractDiEdge(source, target) implicit final class MyNodeImplicits(val source: String) extends AnyVal with AbstractDiEdgeImplicits[String, MyDiEdge, MyDiEdge.type] { protected def companion = MyDiEdge } "ab" ~> "cd" // MyDiEdge("ab", "cd")
For your labeled custom edge, reuse the corresponding node operator and define your label conversion operator like
case class MyLDiEdge(source: String, target: String, n: Int, s: String) extends AbstractDiEdge(source, target) import scalax.collection.edges.DiEdgeImplicits implicit class MyLDiEdgeInfixLabelConstructor(val e: DiEdge[String]) extends AnyVal { def :+(label_1: Int, label_2: String) = MyLDiEdge(e.source, e.target, label_1, label_2) } "ab" ~> "cd" :+ (1, "xy") // MyLDiEdge("ab", "cd", 1, "xy")
Whenever you opt for an infix constructor, do not miss the corresponding toString
representation.
This is also facilitated by convenience traits for every edge type like
case class MyLDiEdge(source: String, target: String, n: Int, s: String) extends AbstractDiEdge(source, target) with LDiEdgeToString { override protected def labelToString: String = s"($n, $s)" } ("ab" ~> "cd" :+ (1, "xy")).toString // "ab" ~> "cd" :+ (1, "xy")
To override the symbol :+
by :++
for multiedges you should further mix in
MultiLEdgeToString
.
Add more syntactic sugar to get edge patterns shine alike. Here is an example for how it works for the above
MyLDiEdge
:
type Node = String type Labels = (Int, String) object :~> extends UnapplyLabeledEdge[Node, MyLDiEdge, Labels] { protected def label(e: MyLDiEdge): Labels = (e.n, e.s) } object +: extends UnapplyLabel[Node, Labels] "ab" ~> "cd" :+ (1, "xy") match { case source :~> target +: (num, str) => }
You might wonder why the position of colons is mixed up in the infix edge extractor symbols. Unfortunately this is the only way to get the desired outcome due to operator precedence rules. To make the best of it, we recommend using the following infix extractors:
Edge type  Edge extractor  Further decompose by  Label extractor 
directed edge  :~> 
+: 

directed multiedge  :~> 
++: 

unirected edge  :~ 
+: 

undirected multiedge  :~ 
++: 

hyperedge  Several.Seq 
+: 

multi hyperedge  Several.Seq 
++: 

directed hyperedge  :~~> 
OneOrMore.Seq 
+: 
directed multi hyperedge  :~~> 
OneOrMore.Seq 
++: 
The supporting traits are not specific to edge types unless you have a custom generic edge.
case class Person(name: String) sealed trait Relation extends AnyEdge[Person] // Parent, Friends and Siblings extend Relation import scalax.collection.mutable.{Graph, TypedGraphFactory} type SocialGraph = Graph[Person, Relation] object SocialGraph extends TypedGraphFactory[Person, Relation] SocialGraph.from(Parent(kate, mike) :: Friends(kate, john) :: Siblings(kate, john) :: Nil) import People.OuterImplicits._ val g = People(kate, Parent(kate, mike), Friends(kate, john), Siblings(kate, john)) g += Friends(kate, susan)
As to
extends TypedGraphFactory
to support better type inference and more.
Iterable
of elements for performance reasons.
OuterImplicits
to facilitate type inference when calling apply
.
You can add or subtract nodes and edges one by one or in bulk just like you are familiar with from the standard library. Graph for Scala guarantees a consistent state of the node and edge sets after any operation including duplicate node/edge prevention:
val g = immutable.Graph(1, 2 ~ 3) // Graph(NodeSet(1, 2, 3), EdgeSet(2 ~ 3)) g + 1 // same as g g + 0 // Graph(NodeSet(0, 1, 2, 3), EdgeSet(2 ~ 3)) g + 1.2 // compile error g + 0 ~ 1 // Graph(NodeSet(0, 1, 2, 3), EdgeSet(0 ~ 1, 2 ~ 3)) g ++ List(1 ~ 2, 2 ~ 3) // Graph(NodeSet(1, 2, 3), EdgeSet(1 ~ 2, 2 ~ 3)) g ++ (0 :: Nil, 1 ~ 2 :: 2 ~ 3 :: Nil) // Graph(NodeSet(0, 1, 2, 3), EdgeSet(1 ~ 2, 2 ~ 3)) g  0 // Graph(NodeSet(1, 2, 3), EdgeSet(2 ~ 3)) g  1 // Graph(NodeSet(2, 3), EdgeSet(2 ~ 3)) g  2 // Graph(NodeSet(1, 3), EdgeSet()) g  2 ~ 3 // Graph(NodeSet(1, 2, 3), EdgeSet()) g  (2 :: Nil, 3 ~ 3 :: Nil) // Graph(NodeSet(1, 3), EdgeSet())
As to
1
won't be added because it is already present, so you get the same instance.
0
added.
Double
is incompatible with Int
so the compiler reports an error.
0 ~ 1
is added to a new Graph
instance.
Graph
instance.
Graph
instance.
0
cannot be removed because it is not contained, so you get the same instance.
1
removed. Edges won't be removed
because 1
had no incident edge.
2
along with 2 ~ 3
is "ripple" removed from a new Graph
instance.
2 ~ 3
is removed from a new Graph
instance leaving its incident nodes in place.
Graph
instance.
It is also possible to add elements to or subtract elements from the node and edge sets. Such operations always return a decoupled immutable set.
import mutable.Graph Graph(1, 2 ~ 3) += 0 // Graph(0, 1, 2, 3, 2 ~ 3) Graph[Int, AnyEdge](1, 2 ~ 3) += 3 ~> 1 // Graph(NodeSet(1, 2, 3), EdgeSet(2 ~ 3, 3 ~> 1))
0
is added to the same Graph
instance.
3 ~ 1
is added to the same Graph
instance.
Note how you facilitate mixed graphs by AnyEdge
.
When using apply
you pass just the higher kind,
but your graph will have the type Graph[Int, AnyEdge[Int]]
anyway.