# Using JGraphT for working with graphs (directed, undirected, weighted, etc...)

**URL:** <https://openrndr.discourse.group/t/using-jgrapht-for-working-with-graphs-directed-undirected-weighted-etc/188>\
**Category:** Tutorials\
**Created:** [January 12, 2021, 10:36am UTC](https://openrndr.discourse.group/t/using-jgrapht-for-working-with-graphs-directed-undirected-weighted-etc/188 "2021-01-12T10:36:16Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![abe](https://yyz2.discourse-cdn.com/free1/user_avatar/openrndr.discourse.group/abe/32/700_2.png) [@abe](https://openrndr.discourse.group/u/abe)\
**Post date:** [January 12, 2021, 10:36am UTC](https://openrndr.discourse.group/t/using-jgrapht-for-working-with-graphs-directed-undirected-weighted-etc/188/1 "2021-01-12T10:36:16Z")

</div>

Not specific about OPENRNDR or Kotlin, but I was only happy to discover this jvm library which can be useful for generative designs: [https://jgrapht.org/](https://jgrapht.org/)

After putting the following into `build.gradle.kts`

```auto
implementation("org.jgrapht", "jgrapht-core", "1.5.0")

```

I could write this simple program:

```auto
            // https://jgrapht.org/
            val g = SimpleGraph<Int, DefaultEdge>(DefaultEdge::class.java)

            for (i in 0..5) {
                g.addVertex(i)
            }
            for (i in 0..5) {
                g.addEdge(i, (i + 1) % g.vertexSet().size)
            }
            g.addEdge(0, 3)

            println("vertices and edges")
            println(g)

            println("loops")
            val cycles = PatonCycleBase(g)
            cycles.cycleBasis.cycles.forEach(::println)

```

Which outputs

```auto
vertices and edges
([0, 1, 2, 3, 4, 5], [{0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,0}, {0,3}])
loops
[(4 : 5), (3 : 4), (0 : 3), (5 : 0)]
[(1 : 2), (2 : 3), (0 : 3), (0 : 1)]

```

I will use it to find closed loops in a design like this (after splitting everything on the intersections):  
 ![8](https://global.discourse-cdn.com/free1/uploads/openrndr/original/1X/1c63b21acecbd93684f14efac3d9ba9750b01ed4.png)

The code above uses integers for demo purposes, but any type should be ok (including Vector2).  
Nice [guide](https://jgrapht.org/guide/UserOverview) and tons of [methods to query the graph](https://jgrapht.org/javadoc/org.jgrapht.core/module-summary.html).

---

<div class="post-metadata">

**Author:** ![abe](https://yyz2.discourse-cdn.com/free1/user_avatar/openrndr.discourse.group/abe/32/700_2.png) [@abe](https://openrndr.discourse.group/u/abe)\
**Post date:** [January 12, 2021, 11:34am UTC](https://openrndr.discourse.group/t/using-jgrapht-for-working-with-graphs-directed-undirected-weighted-etc/188/2 "2021-01-12T11:34:34Z")

</div>

Work in progress. Draw a bunch of lines, split them on intersections, store all segments in a graph, find loops, show loops with length 4.

 ![now.LetsGoChopping-2021-01-12-12.32.32](https://global.discourse-cdn.com/free1/uploads/openrndr/original/1X/ba76a33977ef3524886c18503a957906817224e4.png)

Next, figure out why some loops are not detected (1).

By the way, this is using `IntVector2` taken from the original vertices rounded with 0 decimals and then `vec2.toInt()`. If I use `Vector2` all the way then very few shapes are detected. I assume it’s because there’s no threshold used when comparing Vector2s. Maybe I can specify a custom comparator with JGraphT… [read this](https://jgrapht.org/guide/UserOverview#graph-comparisons).

ps. I think I found the reason for (1):

> Note that Paton’s algorithm produces a fundamental cycle basis while this implementation produces a [weakly fundamental cycle basis](https://en.wikipedia.org/wiki/Cycle_space#Fundamental_and_weakly_fundamental_bases). A cycle basis is called _weakly fundamental_ if there exists a linear ordering of the cycles in a cycle basis **such that each cycle includes at least one edge that is not part of any previous cycle**.

(emphasis mine). So I need to find the right algorithm. One in which you can specify the desired cycle length would be great as I assume it would be a good optimization: stop searching if the cycle grows too long.

And what is needed seems to be “finding all chordless cycles” in the graph. [Paper here](https://www.researchgate.net/publication/256423221_Efficient_Enumeration_of_All_Chordless_Cycles_in_Graphs).

---

<div class="post-metadata">

**Author:** ![abe](https://yyz2.discourse-cdn.com/free1/user_avatar/openrndr.discourse.group/abe/32/700_2.png) [@abe](https://openrndr.discourse.group/u/abe)\
**Post date:** [January 13, 2021, 5:52pm UTC](https://openrndr.discourse.group/t/using-jgrapht-for-working-with-graphs-directed-undirected-weighted-etc/188/3 "2021-01-13T17:52:55Z")

</div>

I ended up writing my own algorithm to find cycles of length 4. This is the first test.

 ![signal-2021-01-13-184544](https://global.discourse-cdn.com/free1/uploads/openrndr/original/1X/06ec533b4e9e0e90be7d6c13357e64fac8d3729a.jpeg)

---

<div class="post-metadata">

**Author:** ![dector](https://yyz2.discourse-cdn.com/free1/user_avatar/openrndr.discourse.group/dector/32/36_2.png) [@dector](https://openrndr.discourse.group/u/dector)\
**Post date:** [January 17, 2021, 3:02pm UTC](https://openrndr.discourse.group/t/using-jgrapht-for-working-with-graphs-directed-undirected-weighted-etc/188/4 "2021-01-17T15:02:35Z")

</div>

This is beautiful by itself! Do you use watercolors here?

---

<div class="post-metadata">

**Author:** ![abe](https://yyz2.discourse-cdn.com/free1/user_avatar/openrndr.discourse.group/abe/32/700_2.png) [@abe](https://openrndr.discourse.group/u/abe)\
**Post date:** [January 17, 2021, 4:08pm UTC](https://openrndr.discourse.group/t/using-jgrapht-for-working-with-graphs-directed-undirected-weighted-etc/188/5 "2021-01-17T16:08:19Z")

</div>

Thank you 🙂 I’m glad you like it. It’s black calligraphy ink diluted with water, but I have in mind trying watercolors too.