Creating graphs

A graph consists of nodes which represent some objects or values and edges which express a relation between this objects.

graphs has a default builder --> that you can use with arbitrary node types. By importing this builder, you can instantly start creating simple graphs:

copysourceimport com.flowtick.graphs._
import com.flowtick.graphs.defaults._

val graph: Graph[Unit, String] =
  Graph.fromEdges(Set("A" --> "B", "B" --> "C", "D" --> "A"))

println(graph.edges)

Edges can also have values associated with them, for example a distance between nodes that represent locations.

Numeric edge values can be used in algorithms like Dijkstras algorithm to find the shortest path between two nodes.

copysourceval cities: Graph[Int, String] = Graph.fromEdges(
  Set(
    "Frankfurt" --> (85, "Mannheim"),
    "Frankfurt" --> (217, "Wuerzburg"),
    "Frankfurt" --> (173, "Kassel"),
    "Mannheim" --> (80, "Karlsruhe"),
    "Wuerzburg" --> (186, "Erfurt"),
    "Wuerzburg" --> (103, "Nuernberg"),
    "Stuttgart" --> (183, "Nuernberg"),
    "Kassel" --> (502, "Muenchen"),
    "Nuernberg" --> (167, "Muenchen"),
    "Karlsruhe" --> (250, "Augsburg"),
    "Augsburg" --> (84, "Muenchen")
  )
)

Core

In graphs the core type is the Graph type.

It is parametrized over three types:

• the value type of the edges (named E)
• the value type of the node (named N)

The meta value allows carrying additional information on the graph itself like a description or groups / layers of nodes. In graphs transformations are defined on nodes, which is why the node type is on the right side of the type parameter list.

A value of a graph instance of type Graph[Double, String] would be described as

a graph with edges of type Double value connecting nodes of type String

Graph has common methods to work with graph instances:

copysourcetrait Graph[E, N] {
  def nodeId: Identifiable[N]
  def edgeId: Identifiable[E]

  def edges: Iterable[Edge[E]]
  def nodes: Iterable[Node[N]]

  def nodeIds: Iterable[String]
  def edgeIds: Iterable[String]

  def findNode(id: String): Option[Node[N]]
  def findEdge(id: String): Option[Edge[E]]

  def updateNode(id: String)(f: N => N): Graph[E, N]
  def updateEdge(id: String)(f: E => E): Graph[E, N]

  def removeNodeById(nodeId: String): Graph[E, N]
  def removeEdgeById(edgeId: String): Graph[E, N]

  def removeNode(node: Node[N]): Graph[E, N] = removeNodeById(node.id)
  def removeEdge(edge: Edge[E]): Graph[E, N] = removeEdgeById(edge.id)

  def removeNodeValue(node: N): Graph[E, N] = removeNodeById(nodeId(node))

  def incoming(nodeId: String): Iterable[Edge[E]]
  def outgoing(nodeId: String): Iterable[Edge[E]]

  def successors(nodeId: String): Iterable[Node[N]] =
    outgoing(nodeId).flatMap(edge => findNode(edge.to))
  def predecessors(nodeId: String): Iterable[Node[N]] =
    incoming(nodeId).flatMap(edge => findNode(edge.from))

  def addNode(nodeValue: N): Graph[E, N] = withNode(Node(nodeId(nodeValue), nodeValue))
  def addNodes(nodeValues: Iterable[N]): Graph[E, N] = nodeValues.foldLeft(this)(_ addNode _)

  def addEdge(value: E, from: N, to: N): Graph[E, N] =
    withEdge(Edge.of(value, nodeId(from), nodeId(to))(edgeId))
      .addNode(from)
      .addNode(to)

  def withEdge(edge: Edge[E]): Graph[E, N]
  def withNode(node: Node[N]): Graph[E, N]

  def withEdgeValue(value: E, fromId: String, toId: String): Graph[E, N] =
    withEdge(Edge.of(value, fromId, toId)(edgeId))

  def withNodes(nodes: Iterable[Node[N]]): Graph[E, N] =
    nodes.foldLeft(this)(_ withNode _)
  def withEdges(edges: Iterable[Edge[E]]): Graph[E, N] =
    edges.foldLeft(this)(_ withEdge _)
}

Identity

Nodes and Edges have an id field of type String. Most of the graph API is built around this id. During graph creation, the id is derived from the node / edge value via the Identifiable type:

copysourcetrait Identifiable[-T] {
  def apply(value: T): String
}

object Identifiable {

  /** creates an instance of [[Identifiable]] using the provided function */
  def identify[T](f: T => String): Identifiable[T] = (a: T) => f(a)
}

The defaults contain some default identities for common primitive types, for complex custom types you need to provide a corresponding instance.

Custom Graph Types

Since the graph type itself is parametrized, you can just plug in your types:

copysourcefinal case class MyNode(id: String, someCustomProperty: String)

implicit val myNodeId: Identifiable[MyNode] = new Identifiable[MyNode] {
  override def apply(value: MyNode): String = value.id
}

val graph = Graph.fromEdges(
  Set(
    MyNode("first_node", "My first node") --> MyNode(
      "second_node",
      "My second node"
    )
  )
)

println(graph.edges)