Dec
20
2008
0

Graph Fun

connections two
I enjoy graphs, not the charts that Excel can generate, but Graph Theory Graphs.  The kind of graphs that you can use to calculate dependency matrices, identify network problems, and design flow charts.  The kind of graphs that can contain millions of vertices and millions of edges. This was made possible by finding JGraphT.  It’s a java graph API that focuses on handling the data structure of graphs.  My API wraps a ListenableGraph and creates cooresponding Components for the vertices and edges.

I bring this up because I may have finally wrote a decent Graph API for Java Swing.  Its not much of an API at the moment, but it does allow positionable labels on edges and draging of vertices around.  The API doesn’t do Canvas drawing like some of my prior attempts, nor does it mix Components with manual painting.  It creates a component for every displayable element in a graph.  Currently I have 3 main components with 3 extended JPanels containers to layer the 3 components, VertexComponent, EdgeComponent, and EdgeLabelComponent.  The VertexComponent ideally will be styleable by storing Objects that implement the Map API as the Edges and Vertices in the data structure.  The EdgeLabelComponent will have a Event/Listener framework for updating it or attribute based updating.  I am currently leaning toward not implementing the attribute based labels since the underlying JLabel’s preferred size will resize as contents change and it would be unwise to do that in the middle of repainting.

If there is any interest in the above API email me, I may actually try to finish it.

Enough Java, time for rant.  Graph theory means alot to me because it has so many ties into our daily lives without knowing about it.  For instance, as a play on XKCD’s 173. Imagine trying to plan for a thanksgiving dinner with 3 immediate family members and 27 additions (spouses, children, cousins, “family” friends). Now trying planning out optimal seating so that everyone has appropriate conversation and all kids are near a responsible adult without seating cousin Eddie next to Mother In-Law due to personality conflicts. These issues can be addressed using a Force-Directed Layout algorithm. This will only work if you can assign numeric values to who needs to sit next to who and who should be clustered, and who should be as far away from each other as possible without being obvious. Graph theory has the ability to solve problems from optimal building plans, any complex scheduling (think college & high school class assignments), and near infinite other problem sets. Nature’s circle of life operates using a dependency graph with built in priorities. Due to the wide reaching aspects of Graph Theory if one can simplify it such that it can help average people solve complicated problems you have a fairly wide reaching business model on the condition you can profit from it.

Written by ruckc | Tags: , , ,

WordPress | Aeros | Extplorer