Thursday, October 7, 2021

Graphing Prime Numbers

I enjoy toying with prime numbers and wanted to see how the Java GraphStream library worked.  Here is a short video of the result. 

 

 

Interestingly, it is little fun projects like this that often turn into moments of learning.  While working on some prime number related programs I learned of some tool limits I wasn't aware of before this.

  •  The max radix value for converting numbers to strings is 36.  From some searching, it sounds like that was chosen by being the number of values 0-9 + the 26 case-insensitive values a-z.  I found it odd when numbers I converted starting at radix 37 were identical.
    • Integer.toString(99999, 37)
  •  For a call to: com.google.common.collect.Sets.powerSet( aSet) , the "aSet" set parameter is limited to a max of 30 items.

 

 

I decided to try a variety of layout parameters to look for interesting results.  Here are a few of those results using GraphStream.

 






 Those were interesting but I decided to see if I could integrate different graphing libraries to look for other interesting features, etc.

My first attempt was to try integrating gephi but that didn't go well.   As I looked into other graphing libraries, I noted that many are not maintained.  This took way too much effort due to the version of netbeans libraries that had been used.  I ended up forcing newer versions which are hosted by Apache.  Eventually, I had code that built but no visual graph was produced - I noted some flakiness with one of my displays when trying to run it so I suspect an issue between older code and my display/drivers.  

Next, I decided to try Jgrapht.  This had an initial snag which was the fact that the original package was no longer maintained and wasn't available via maven.  I ended up finding a version that is either a fork or repackaging of it and is available via maven.  Now, things were much less difficult.  It also resulted in very few total dependencies - even after I reworked the code significantly and added in the picocli lib for command line arg handling. I also ended up needing to add in the jgrapht-ext and jgraphx libs to display resulting graphs.

Here are a couple examples from that. The first uses the pre-canned compact tree layout. It took some playing to get something useful to display though. The second graph uses the pre-canned circle layout and that was easy to setup but still not as visually appealing as I desired.



I'll keep looking and trying new settings to see if I can come up with something better but this does work at least.  From a visual graph standpoint, it doesn't scale very well it seems but maybe some tuning is possible.  I got the generation of the primes tuned much better now and could generate 1M primes quickly but trying to graph even 10k primes seems unrealistic / painful.  I'll probably end up terminating the running process before it ever gets to the point of displaying the graph.


[update] I added the ability to export my data into the Graph Modelling Language (GML) format and that is compatible with the yed tool. Yed has much richer layout support that what I have been working with from a Java library integration standpoint.  The downside is that really large datasets are time consuming to visualize.  I'm not sure how long it took for yed to complete this since I took a several hour break.  This was for 10k primes.