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

[abe]

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/

After putting the following into build.gradle.kts

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

I could write this simple program:

            // 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

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):

The code above uses integers for demo purposes, but any type should be ok (including Vector2).
Nice guide and tons of methods to query the graph.

[abe]

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.

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.

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. 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.

[abe]

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

[dector]

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

[abe]

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