# 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,
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()`````` 