Algorithms

graphs allows ad-hoc extension of graph instances so that you can execute some common operations and algorithms on it.

Currently, the following algorithms are supported:

Depth-first traversal

A depth first traversal visits every node per branch / path which means that for every node the first child will be visited and the search will be continued there, before going to its siblings.

Every node will be visited.

copysourcepackage examples

import com.flowtick.graphs._
import com.flowtick.graphs.algorithm._
import com.flowtick.graphs.defaults._

trait DfsExample {
  val graph = Graph.fromEdges(
    Set(
      "1" --> "2",
      "1" --> "9",
      "2" --> "6",
      "2" --> "3",
      "3" --> "5",
      "3" --> "4",
      "6" --> "7",
      "6" --> "8"
    )
  )

  println(graph.dfs("1").steps.map(_.node.id))
  // List(1, 9, 2, 6, 8, 7, 3, 5, 4)
}

Breadth-first traversal

A breadth first traversal visits every node per layer, which means that first all child nodes will be visited before continuing with their children.

Every node will be visited.

copysourcepackage examples

import com.flowtick.graphs._
import com.flowtick.graphs.algorithm._
import com.flowtick.graphs.defaults._

trait BfsExample {
  val graph = Graph.fromEdges(
    Set(
      "A" --> "D",
      "A" --> "C",
      "A" --> "B",
      "B" --> "E",
      "B" --> "F",
      "B" --> "G",
      "E" --> "H"
    )
  )

  println(graph.bfs("A").steps.map(_.node.id))
  // List(A, B, C, D, E, F, G, H)
}

Topological sorting using a depth-first approach

https://en.wikipedia.org/wiki/Topological_sorting:

“topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another”

copysourcepackage examples

import com.flowtick.graphs._
import com.flowtick.graphs.algorithm._
import com.flowtick.graphs.defaults._

trait TopologicalSortingExample {
  lazy val graph = Graph.fromEdges(Set("A" --> "B", "B" --> "C", "D" --> "A"))

  lazy val clothingDependencies = Graph.fromEdges(
    Set(
      "Underpants" --> "Pants",
      "Pants" --> "Coat",
      "Pullover" --> "Coat",
      "Undershirt" --> "Pullover",
      "Pants" --> "Shoes",
      "Socks" --> "Shoes"
    )
  )

  println(graph.topologicalSort)
  // List(D, A, B, C)

  println(clothingDependencies.topologicalSort)
  // List(Undershirt, Pullover, Underpants, Pants, Coat, Socks, Shoes)
}

Dijkstras algorithm for shortest paths

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm:

For a given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined.

copysourcepackage examples

import com.flowtick.graphs.Graph
import com.flowtick.graphs.algorithm._
import com.flowtick.graphs.defaults._

object DijkstraGraph {
  // example taken from https://de.wikipedia.org/wiki/Dijkstra-Algorithmus
  // #cities
  val 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")
    )
  )
  // #cities
}

trait DijkstraExample {
  println(DijkstraGraph.cities.dijkstra.shortestPath("Frankfurt", "Muenchen"))
  // ListBuffer(Frankfurt --> Wuerzburg[217], Wuerzburg --> Nuernberg[103], Nuernberg --> Muenchen[167])
}