After a break of several years, I decided to continue the Hypergraph project. For those of you who don’t know Hypergraph: this is an open source Java framework which provides ways to model hyperbolic geometry and visualises graphs and trees using hyperbolic geometry. There has been some research on hyperbolic trees which shows that especially hierarchical data can be view very well using hyperbolic trees.
Every few weeks I received a mail asking for the current status of the project, whether it’s completely dead or whether certain enhancements can be made. There were also various (legitimate) complaints about the missing documentation of the project.
Hence I thought I should continue to work on the project at least if time allows it. Here I would like to give an overview about the next development steps and the reasons for this. I’m afraid, I can’t give a time estimation as I’m not working on this project on a regular basis.
Well, the next steps will be:
- Finish the refactoring to become independent of the UI (support at least AWT/Sing and SWT)
- Get rid of the graph data structure and algorithms; replace it by JgraphT
- Tidy up the existing graph layout algorithms
- Tidy up the example applications and add new examples
- Enhance the Javadoc
- Relaunch the website, including a better documentation
As you can see, I start with the parts which are more fun to me and end up with the (usually boring, but necessary) documentation.
Independence of the UI framework
The existing Hypergraph code consists of three parts: packages related to the graph structure, a package for the hyperbolic geometry and a package for the visualisation of the hyperbolic graphs and hyperbolic trees in a JPanel. At first sight, this sounds like a reasonable architecture, but if you look at the code in detail, you will find that this is not the case, here some examples:
- The colour attribute for edges and vertices are stored using java.awt.Colour. If you use this graph in frameworks which don’t use java.awt.Colour, this causes a problem.
- The projector which is responsible for projecting the hyperbolic plane to the screen coordinates depends on JComponent
- The animator which is responsible for smoothly translating the hyperbolic plane uses javax.swing.Timer.
If the code shall be used by different UI frameworks, these dependencies have to be resolved, which is the first aim. Large parts are already done and committed to the SWT branch, but there is still something to do.
Replacement of the Graph API by JGraphT
When I started in 2002/2003, I decided to write my own graph API. By now, there are some established projects written in Java which offer the functionality I need and I decided to use JGraphT.
The advantage is that I don’t need to worry about the (correct) implementation of any algorithms or data structure – there is no need to reinvent the wheel.
There are disadvantes though: I have to rewrite any code that depend on the existing graph data structure, which is quite a lot by the nature of the project. Also there doesn’t seem to be any reader for GraphML or GraphXML files, so need to implement them.
Tidying up the layout algorithms
The most striking issue with the hyperbolic layout algorithms is the poor quality of the code. I have to confess that I can’t read the code at all…
But there are some other deficiencies: the layout algorithms are graph layout algorithms. Well, that sounds tautologic, but for example the force directed layout is actually a generic multi dimensional scaling algorithm which could also be applied to other data than graphs. It will be interesting to see whether hyperbolic geometry can also be used for other visualisation besides hyperbolic trees and graphs.
This will happen more or less at the same time as the introduction of JGraphT as this is related.
Tidying up the example applications
Similar to the layout algorithms, the code quality of the applications is quite poor – the programs are a mixture of examples and proof of concept. Even the main applet to show hyperbolic trees should be tidied up.
I haven’t thought yet about which examples and which actual applications I should include in the distribution. If you have any proposals or if you would like to have an example for a specific concept in Hypergraph, please add a comment.
Enhancement of the Javadoc and relaunching the website
The need to enhance the Javadoc should be obvious to anybody who has worked with the code. The same applies to the website: it’s not complete at all.
Currently, it’s difficult or at least not comfortable to add new content to the website due to the way the html files are generated and deployed.
As I have also spent some time working with CouchDB, I might decide to use CouchDB as a storage and web server and create some mixture of blog and wiki for the new website.
Conclusion
As you can see, there is a lot to do and I hope to provide a new release soon which covers at least the first two issues. I will also try to write about how the issues are resolved, i.e. describe the new architecture of Hypergraph.
As a last remark, let me mention that I’m not very glad about the project’s name Hypergraph. When I created the project, I thought this is a nice combination of hyperbolic geometry and graphs. However, I completely ignored that hypergraph is actually a fixed notion in graph theory which can lead to confusion. I wonder whether there is some other name which hints at the main focus of the project: data visualisation using hyperbolic geometry. If you have any ideas, please add a comment.
. But apart of that, I don’t think it’s fit for purpose. Hypergraph, like other tools that show trees/graphs using hyperbolic geometry, is strong when there is some exponentially growing graph structure in the background. For example the organisational structure of a company or a class hierarchy are suitable.