Skip to content

Graphs

Underdog's Graphs module can be used for exploring graph theory problems.

Tutorial

Prerequisites

Dependencies

The modules required to follow this tutorial are the graphs and plots modules:

// graph data and algorithms
implementation 'com.github.grooviter:underdog-graphs:VERSION'

// graph visualization
implementation 'com.github.grooviter:underdog-plots:VERSION'

<!-- graph data and algorithms -->
<dependency>
    <groupId>com.github.grooviter</groupId>
    <artifactId>underdog-graphs</artifactId>
    <version>VERSION</version>
</dependency>
<!-- graph visualization -->
<dependency>
    <groupId>com.github.grooviter</groupId>
    <artifactId>underdog-plots</artifactId>
    <version>VERSION</version>
</dependency>

@Grapes([
    // graph data and algorithms
    @Grab('com.github.grooviter:underdog-graphs:VERSION'),
    // graph visualization
    @Grab('com.github.grooviter:underdog-plots:VERSION')
])

Creating a graph

Creating an empty graph without vertices and edges:

create a graph
import underdog.Underdog

def graph = Underdog.graphs().graph(String) {
    // vertices and edges here
}

The graph(Class) informs what is the type of the vertices this graph is going to have. This time vertices in this graph will be of type String but vertices could be potentially of any type.

Vertices / Nodes

Lets create a graph with two nodes without any edge between them:

adding vertices adding vertices

There are a couple of ways of adding more vertices to a graph. One is when creating the graph:

adding vertices at creation time
def graph = Underdog.graphs().graph(String) {
    vertex("A")
    vertex("B")
}

You can also add more vertices after the graph has been created:

adding vertices after creation
def graph = Underdog.graphs().graph(String) {}

graph.addVertex("A")
graph.addVertex("B")

You can add simple type vertices, but you can also add more complex objects. Imagine we can add the relationships between employees in a given company. First lets define the Employee class:

Employee
/*
 * @Canonical implements equals and hashcode among other things.
 * These methods will help the graph to id each node in the graph.
*/
@groovy.transform.Canonical
static class Employee {
    String name, department
}

Now we can create a Graph and add relationships between employees:

Adding employees
def john = new Employee("John", "Engineering")
def peter = new Employee("Peter", "Engineering")
def lisa = new Employee("Lisa", "Engineering")

def graph = Underdog.graphs().graph(Employee) {
    vertex(john)
    vertex(peter)
    vertex(lisa)
}

Edges

Graphs normally are not very useful without setting edges between nodes. Lets add an edge between two nodes:

adding edges adding edges

We can add vertices at creation time:

Adding edges at creation time
def graph = Underdog.graphs().graph(String) {
    // adding vertices first
    vertex('A')
    vertex('B')

    // then adding edges between vertices
    edge('A', 'B')
}

You can omit adding vertices before adding edges if all vertices are going to be included in edge(...) method calls. The following example produces the same graph as the previous one:

avoid using vertex(...)
def graph2 = Underdog.graphs().graph(String) {
    edge('A', 'B')
}

It's also possible to add edges after the graph has been created:

Adding edges after creation time
def graph = Underdog.graphs().graph(String) {
    // adding vertices 'A', 'B', 'C', 'D'
    ('A'..'D').each(delegate::vertex)
}

// adding edge between 'A' and 'B'
graph.addEdge('A', 'B')

You can also add several edges at once using edges(...)

adding edges adding edges

adding several edges
def graph = Underdog.graphs().graph(String) {
    // adding vertices first
    ('A'..'D').each(delegate::vertex)

    // then adding several edges
    edges(
        'A', 'B',
        'B', 'C',
        'C', 'D'
    )
}

We can at any point ask about how many vertices and edges there are in the graph:

shape
def graph = Underdog.graphs().graph(String) {
    ('A'..'D').each(delegate::vertex)
    edge('A', 'B')
    edge('B', 'C')
    edge('C', 'D')
}

// getting vertices and edges count
def (nVertices, nEdges) = graph.shape()

// or just println shape
println(graph.shape())

which prints:

output
4 vertices X 3 edges

Elements of a graph

  • vertices
  • edges
  • adjacent
  • degree

Lets create a graph first and then ask for its elements:

graph
def graph = Underdog.graphs().graph(Integer) {
    (1..10).each(delegate::vertex)
    edges(
        1, 2,
        1, 3,
        3, 4
    )
}

The lets ask for its vertices, edges, neighbors.

graph elements
//  getting graph vertices
graph.vertices.containsAll(1..10)

// getting graph edges
graph.edges.size() == 3

// getting neighbors of a specific vertex
graph.neighborsOf(1) == [2, 3]

Removing elements

Here there are some example on how to remove vertices and edges from a given graph. When using the operator minus (-) the result return the graph minus the element removed whereas the removeXXX(,,,) functions only return a boolean value: true if the element was successfully removed, or false if it couldn't be removed from graph.

removing elements
def graph = Underdog.graphs().graph(Integer) {
    (1..14).each(delegate::vertex)
    edges(
        3, 5,
        5, 7,
        7, 9,
        9, 11,
        11, 12,
        12, 14
    )
}

// removing vertices using - operator
def graph2 = graph - [2, 4, 6, 8, 10]
def graph3 = graph2 - 1

// removing vertices using function
graph3.removeVertex(3)
graph3.removeAllVertices([5, 7])

// removing edge using - operator
def graph4 = graph3 - graph3.edgesOf(9).first()

// removing edges
graph4.removeEdge(graph4.edgesOf(11).first())
// graph4.removeAllEdges(graph4.edgesOf(12)) <--- this fails: ConcurrentModificationException
graph4.removeAllEdges(graph4.edgesOf(12).toList()) // <--- this works

Graph types

You can create different types of graphs. There are a couple of methods you can use:

graph types
// graphs
def g = Underdog.graphs()

// undirected weighted
def graph1 = g.graph(String)

// directed weighted
def graph2 = g.digraph(String)

// directed weighted pseudo graph
def graph3 = g.multidigraph(String)

// weighted pseudo graph
def graph4 = g.multigraph(String)

Tip

Because graphs in underdog are using JGraphT underneath you can always create an instance of any type of graph directly using JGraphT api.

What to use as vertices

You can use almost anything as a vertex. The only mandatory condition is that the graph must be able to distinguish between vertices. For that your vertex should implement both equals and hashcode methods. In Groovy you can use the @Canonical annotation to get that.

Analyzing graphs

The structure of the graph can be analyzed by using various functions.

graph
def graph = Underdog.graphs().graph(String) {
    ('a'..'f').each(delegate::vertex)

    edges(
        'a', 'b',
        'a', 'c',
        'a', 'd',
        'b', 'e',
    )
}

What is the shape of the graph ?

shape
def (nVertices, nEdges) = graph.shape()

What is the clustering of the graph ?

clustering of the graph
def graphClustering = graph.clusteringGlobal()

What is the clustering avg ?

clustering average
def graphAvg = graph.clusteringAvg()

And what about the clustering of a given vertex ?

clustering of a vertex
def vertexClustering = graph.clusteringOf('a')

What is the vertex with max degree ?

max degree
String maxDegreeVertex = graph.maxDegree()

Lets say we want to sort vertices by degree in descending order:

sort vertices by degree (desc)
def sortedVertices = graph.vertices.sort { -graph.degreeOf(it) }

Traversal

To traverse a graph you can directly access the vertices or edges sets and use normal Groovy/Java mechanisms. In the following example we are looking in all vertices to find all vertices having the number two as a neighbor

collections (vertices)
def graph = Underdog.graphs().graph(Integer) {
    (1..10).each(delegate::vertex)
    edges(
        1, 3,
        1, 5,
        1, 7,
        1, 9,
        1, 2  // <--- looking here
    )
}

def answer1 = graph.vertices.findAll {
    graph.neighborsOf(it).any { it == 2 }
}
output
1

Now in the next example we are exploring boss-employee relationships and we'd like to find all the bosses names:

collections (edges)
def anna = new Person("Anna", 24)
def chris = new Person("Chris", 26)
def paul = new Person("Paul", 30)
def john = new Person("John", 28)

def employees = Underdog.graphs().graph(Person) {
    // adding people
    [anna, chris, paul, john].each(delegate::vertex)
    edge(chris, paul, "boss")
    edge(anna, john, "boss")
    edge(chris, anna, "mentor")
}

def bossesNames = employees.edges                        // search in all edges where...
    .findAll { it.relation == 'boss' }            // boss-employee relationship
    .collect { employees.verticesOf(it)[0].name } // get only the boss name

Sometimes the graph could be bigger and more complex and we could benefit from using breadthFirst (*) or depthFirst (**) algorithms:

depthFirst
def anna = new Person("Anna", 24)
def chris = new Person("Chris", 26)
def paul = new Person("Paul", 30)
def john = new Person("John", 28)

def dates = Underdog.graphs().graph(Person){
    // adding people
    [anna, chris, paul, john].each(delegate::vertex)

    // adding dates
    edges(
        anna, paul,
        anna, chris,
        chris, paul,
        anna, john
    )
}

def answer = dates.'**'.find { Person person ->
    // less than 30 years
    person.age < 30 &&
    // have dated John
    dates.neighborsOf(person).any { p -> p.name == "John"}
}

Introspection

You can ask the tree for different attributes such as the degrees:

max degree
def graph = Underdog.graphs().graph(String) {
    ('A'..'C').each {
        vertex(it)
    }

    edge('A', 'B')
    edge('A', 'C')
}

def node = graph.maxDegree()

Imagine a more complex example where our nodes are beans. Here we have a class representing a person:

Person
class Person {
    String name
    Integer age

    // this is used for destructuring eg:
    // def (name, age) = somePerson
    //       ^     ^
    //       |     |
    //       0     1
    Object getAt(Integer index) {
        return [name, age][index]
    }
}

This class implements the method getAt(int) which allows to extract the object attribute values via Groovy destructuring. That would become handy later on.

Note

You can learn more about Groovy destructuring in the Groovy docs

We create the graph:

Graph using complex objects
def john = new Person(name: "John", age: 23)
def elsa = new Person (name: "Elsa", age: 32)
def raul = new Person(name: "Raul", age: 28)

def graph = Underdog.graphs().digraph(Person) {
    vertex(john)
    vertex(elsa)
    vertex(raul)

    edge(john, elsa)
    edge(john, raul)
}

Then look for the person with more relationship and extract that person name and age:

Person with more relationships
def (name, age) = graph.maxDegree()

Do you remember we implemented destructuring for the Person class ? Here the maxDegree() function returns an instance of type Person, therefore we can access the properties name and age using destructuring knowing that the property in index 0 is the name and the property in index 1 is age.

Distances

Sometimes comes handy to know what is the shortest path from one node to another. It could be anything: How many people do I have to meet to meet a specific person ? How many cities do I have to visit before getting to a specific location ? ...etc

Here's a very naive example with cities. The following graph contains cities and the edges represent how many kilometers there are between them.

We'd like to use the graph as a route planner to get from point A to B. First we need to create our graph:

cities distances graph
def distances = Underdog.graphs().graph(String) {
    ["Madrid", "Guadalajara", "Cuenca", "Zaragoza", "Teruel", "Castellon"].each(delegate::vertex)
    edge("Madrid", "Guadalajara", weight: 66.4)
    edge("Madrid", "Salamanca", weight: 210)
    edge("Guadalajara", "Zaragoza", weight: 256.9)
    edge("Zaragoza", "Cuenca", weight: 290.2)
    edge("Cuenca", "Teruel", weight: 147.9)
    edge("Teruel", "Castellon", weight: 144.2)
}

distance between cities distance between cities

See how the weight of the edges represent the km between then. Then I'd like to know how many kilometers I'm going to drive if I'd like to go from Teruel to Madrid:

kms
def kmsDriven = distances
    .shortestPathEdges("Teruel", "Madrid")
    .sum { it.weight }

I've taken the edges and I've added up all weights to get the whole trip in kms:

output
761.4

To get the city names I'm asking for the shortest path getting the vertices this time:

cities visited
def citiesVisited = distances.shortestPathVertices("Teruel", "Madrid")
output
["Teruel", "Cuenca", "Zaragoza", "Guadalajara", "Madrid"]

distance between cities distance between cities

If you are not sure whether you are interested in vertices or edges, or maybe you are interested in both, just use shortestPath:

shortestPath
def shortestPath = distances.shortestPath("Teruel", "Madrid")

And access the resulting object:

shortestPath attributes
// kms
shortestPath.weight == 761.4

// steps (edges)
shortestPath.length == 4
shortestPath.vertexList == ["Teruel", "Cuenca", "Zaragoza", "Guadalajara", "Madrid"] // cities (vertices)

Operators

You can apply arithmetic operations over graphs. Here for example you can apply a union operation over two graphs using the + operator:

merging graphs
def names1 = Underdog.graphs().graph(String) {
    ["John", "Lisa", "Robert"].each(delegate::vertex)
}

def names2 = Underdog.graphs().graph(String) {
    ["Anna", "Vesper", "Tania"].each(delegate::vertex)
}

def names3 = names1 + names2

You can check how the result has all the vertices from the previous merged graphs:

output
assert names3.vertices == ["John", "Lisa", "Robert", "Anna", "Vesper", "Tania"] as Set