Graph Theory

Currently implemented for the Jung library.

Eventually Axle will provide its own basic Graph implementation, which will remove Jung as a dependency of axle-core.

Directed Graph

Example with String is the vertex value and an Edge type with two values (a String and an Int) to represent the edges

val (a, b, c, d) = ("a", "b", "c", "d")

class Edge(val s: String, val i: Int)

Invoke the DirectedGraph typeclass with type parameters that denote that we will use Jung's DirectedSparseGraph as the graph type, with String and Edge as vertex and edge values, respectively.

import edu.uci.ics.jung.graph.DirectedSparseGraph
import axle.algebra._
import axle.jung._

val jdg = DirectedGraph.k2[DirectedSparseGraph, String, Edge]

Use the jdg witness's make method to create the directed graph

val dg = jdg.make(List(a, b, c, d),
  List(
    (a, b, new Edge("hello", 1)),
    (b, c, new Edge("world", 4)),
    (c, d, new Edge("hi", 3)),
    (d, a, new Edge("earth", 1)),
    (a, c, new Edge("!", 7)),
    (b, d, new Edge("hey", 2))))

import cats.implicits._
import axle.syntax.directedgraph.directedGraphOps
import axle.syntax.finite.finiteOps

dg.vertexProjection.size
// res1: Int = 4

dg.edgeProjection.size
// res2: Int = 6

dg.findVertex(_ === "a").map(v => dg.successors(v))
// res3: Option[Set[String]] = Some(value = Set("b", "c"))

dg.findVertex(_ === "c").map(v => dg.successors(v))
// res4: Option[Set[String]] = Some(value = Set("d"))

dg.findVertex(_ === "c").map(v => dg.predecessors(v))
// res5: Option[Set[String]] = Some(value = Set("a", "b"))

dg.findVertex(_ === "c").map(v => dg.neighbors(v))
// res6: Option[Set[String]] = Some(value = Set("a", "b", "d"))

Create a Visualization of the graph

import cats.Show

implicit val showEdge: Show[Edge] = new Show[Edge] {
  def show(e: Edge): String = e.s + " " + e.i
}

import axle.visualize._

val dVis = DirectedGraphVisualization[DirectedSparseGraph[String, Edge], String, Edge](
  dg,
  width = 300,
  height = 300,
  border = 10,
  radius = 10,
  arrowLength = 10,
  color = Color.green,
  borderColor = Color.black,
  fontSize = 12
)

Render as sn SVG file

import axle.web._
import cats.effect._

dVis.svg[IO]("docwork/images/SimpleDirectedGraph.svg").unsafeRunSync()

Undirected Graph

An undirected graph using the same dataa:

val (a, b, c, d) = ("a", "b", "c", "d")

class Edge(val s: String, val i: Int)

Invoke the UndirectedGraph typeclass with type parameters that denote that we will use Jung's UndirectedSparseGraph as the graph type, with String and Edge as vertex and edge values, respectively.

import edu.uci.ics.jung.graph.UndirectedSparseGraph
import axle.algebra._
import axle.jung._

val jug = UndirectedGraph.k2[UndirectedSparseGraph, String, Edge]

Use the jug witness's make method to create the undirected graph

val ug = jug.make(List(a, b, c, d),
  List(
    (a, b, new Edge("hello", 10)),
    (b, c, new Edge("world", 1)),
    (c, d, new Edge("hi", 3)),
    (d, a, new Edge("earth", 7)),
    (a, c, new Edge("!", 1)),
    (b, d, new Edge("hey", 2))))

import cats.implicits._
import axle.syntax.undirectedgraph.undirectedGraphOps
import axle.syntax.finite.finiteOps

ug.vertexProjection.size
// res9: Int = 4

ug.edgeProjection.size
// res10: Int = 6

ug.findVertex(_ == "c").map(v => ug.neighbors(v))
// res11: Option[Iterable[String]] = Some(value = Iterable("a", "b", "d"))

ug.findVertex(_ == "a").map(v => ug.neighbors(v))
// res12: Option[Iterable[String]] = Some(value = Iterable("b", "c", "d"))

Create a Visualization of the graph

import cats.Show

implicit val showEdge: Show[Edge] = new Show[Edge] {
  def show(e: Edge): String = e.s + " " + e.i
}

import axle.visualize._

val uVis = UndirectedGraphVisualization[UndirectedSparseGraph[String, Edge], String, Edge](
  ug,
  width = 300,
  height = 300,
  border = 10,
  color = Color.yellow)

Render as an SVG file

import axle.web._
import cats.effect._

uVis.svg[IO]("docwork/images/SimpleUndirectedGraph.svg").unsafeRunSync()