Core User Guide: Edit Your Graph

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.

Choose the Type Parameters

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 hash-based 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

  • simple graph for non-multigraphs
  • weighted edge for edges with a single label of type 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.
  • ordered hyperedge for hyperedges that are treated equal only if they have the same ends in the same order. In contrast, unordered hyperedges have a bag semantic with respect to their ends.
  • ordered directed hyperedge for directed hyperedges that are treated equal only if they have the same sources and targets in the same order. In contrast, unordered directed hyperedges have a bag semantic with respect to their sources and targets.
Table: Generic non-labeled edges.
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
Table: Weighted edges.
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 or
generic.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
Table: Generic labeled edges with a single label field.
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
Table: Custom edges with any number and type of labels.
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 traits 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:

  • If your graph has generic edges, annotate its type like Graph[MyNode, AnyEdge[MyNode]].
  • If you go with an ADT of edges, let the base trait of your ADT extend the appropriate trait like sealed trait MyEdge extends AnyEdge[MyNode].
Table: Traits to annotate mixed graphs.
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

Touch up your custom edge

It is in your hands to follow library conventions or stay with the simplest possible, Java-like implementation. We provide separate traits for every aspect of those conventions to facilitate a fine-grained selection.

Add infix edge constructors

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 non-multi 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")

Override toString

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 infix edge extractors

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.

Populate your graph

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

  1. For typed graphs it is best practice to create a type specific singleton that extends TypedGraphFactory to support better type inference and more.
  2. Prefer instantiating and populationg your graph by calling a single method that accepts an Iterable of elements for performance reasons.
  3. Import OuterImplicits to facilitate type inference when calling apply.
  4. Here we add another edge to the social graph.

Add and subtract elements

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. Node 1 won't be added because it is already present, so you get the same instance.
  2. You get a new instance with node 0 added.
  3. Double is incompatible with Int so the compiler reports an error.
  4. Edge 0 ~ 1 is added to a new Graph instance.
  5. All edges contained in the right hand operand are added to a new Graph instance.
  6. All nodes and edges are added to a new Graph instance.
  7. Node 0 cannot be removed because it is not contained, so you get the same instance.
  8. You get a new instance with node 1 removed. Edges won't be removed because 1 had no incident edge.
  9. Node 2 along with 2 ~ 3 is "ripple" removed from a new Graph instance.
  10. Edge 2 ~ 3 is removed from a new Graph instance leaving its incident nodes in place.
  11. All listed nodes and edges are removed from a new 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))
  1. Node 0 is added to the same Graph instance.
  2. Edge 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.