Throughout the library we use the terms
When dealing elements, we distinguish between
N
, outer edges have the type E[N]
.
g
,
inner nodes have the type g.NodeT
while inner edges have the type g.EdgeT
.
For a mnemonic remember that we call them "inner" elements because their type is an inner class.
For brevity, we call a graph
DiEdge[Int]
.
DiEdge
is generic with respect to the type of nodes it may connect.
Flight
is typed with respect to the type of nodes it connects, namely Airport
.
Both a mutable and an immutable implementation are at your disposal.
Unlike with standard collections it is not meaningful to use the immutable implementation by default because, unfortunately, its underlying data structure is not yet persistent. This means you need to carefully consider the run-time characteristics of the immutable implementation along with best practices.
Graphs are defined by
trait Graph[N, E <: Edge[N]]
N
the type of nodesE
the type of edges.Based on the four edge categories
we support
While nodes are labeled by nature, edges may be labeled or not.
You control the type of the graph by determining the edge type. You can use the provided edge classes to create generic graphs. However, it is often beneficial to roll out your own ADT of edges to constrain edge usage with respect to which nodes they are allowed to connect and what kind of labels they have. This will make your graphs more type safe, hence the term typed graph.
Graphs are not constrained other than by the type parameters N
and E[N]
.
This means that, currently, you yourself need to ensure that you graph which is, for instance,
supposed to represent a DAG, is really a DAG.
Graph for Scala is superior to the popular Property Graph Model in that
case class
,
will go with its distinct set of "properties".
Map[String, Any]
,
your graph becomes type safe thanks to the ability to accept your specific edge classes with properly typed
fields.
As an example, you can properly represent RDF with Graph for Scala while the Property Graph model is less suitable for this purpose.
While all possible non-labeled as well as weighted edge classes are available out of the box, for labeled edges you need to define your edge class yourself. This is pretty straightforward based on the provided abstract classes and mix ins. You will find plenty of examples paving your way.
Weighted edges are just specific labeled ones so why did we provide them? We did so because
Double
you now have ready-made edge classes for this use case
To achieve light-weight, unified syntax, it's a good idea to also add infix constructor and extractor support to your edge classes. Mix ins and examples help you to also get this right in minutes.
Finally you might wonder why there is no direct support for labeled edges. The reason is that
label: Any
instead of facilitating the definition
of your edge classes with properly named and typed fields fitting your needs.
Since the edge set of a graph is represented by a hash set internally, edge equality determines if a specific edge may be added to the graph. Edge equality is implemented in a transparent way, so you only need to take care of it when dealing with multigraphs.
Take a look at the following examples to get a basic idea about edge equality:
Comparing | with | yields | |
1 ~ 2 |
== |
2 ~ 1 |
true |
1 ~> 2 |
== |
2 ~> 1 |
false |
1 ~ 2 |
== |
1 ~> 2 |
false |
Looking at the endpoints of a hyperedge respectively the sources or targets of a directed hyperedge,
equality is 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. For this reason Graph for Scala supports two kinds of hyperedge equality semantics:
Some more examples:
Comparing | with | having semantics of | yields | |
HyperEdge(1, 2, 2) |
== |
HyperEdge(2, 2, 1) |
bag | true |
HyperEdge(1, 2, 2) |
== |
HyperEdge(2, 2, 1) |
ordered | false |
DiHyperEdge(sources = Several(1, 2), targets = Several(2, 3, 2)) |
== |
DiHyperEdge(sources = Several(1, 2), targets = Several(2, 2, 3)) |
bag | true |
DiHyperEdge(sources = Several(1, 2), targets = Several(2, 3, 2)) |
== |
DiHyperEdge(sources = Several(1, 2), targets = Several(2, 2, 3)) |
ordered | false |
DiHyperEdge(sources = Several(1, 2), targets = Several(2, 3, 2)) |
== |
DiHyperEdge(sources = Several(2, 3, 2), targets = Several(1, 2)) |
bag | false |
DiHyperEdge(sources = Several(1, 2), targets = Several(2, 3, 2)) |
== |
DiHyperEdge(sources = Several(2, 3, 2), targets = Several(1, 2)) |
ordered | false |