Showing posts with label StructureGraphic. Show all posts
Showing posts with label StructureGraphic. Show all posts

Monday, January 17, 2011

[StructureGraphic] Drawing DAG's – Part 2

As I promised yesterday in my first post about drawing DAG's, today I’ll describe a big part of the “nice-looking” graph layout algorithm. It’s very simple and it’s described in the following video:


If you are reading this blog from a feed, click the link to the real post to see the video

Corrections:

  1. at 9:46 I said the result with iterating by the topological sorting would be uglier - I meant prettier...
  2. I somehow switched the image of the best result from the graph… Here is the Correct Image Result

[StructureGraphic] Drawing DAG's – Part 1

As I promised, it’s time to take StructureGraphic to the next level – drawing DAG’s. I have spent several hours today on formalizing what makes people think a graph layout is aesthetical, and how to make an algorithm that can draw a graph in such a way. You can see some quick sketches from the process below:

Quick: Just display connections, somehow
Better: Since it's a DAG, make all edges point down and try to
reduce the amount of edges that cross one another
Best: Align vertices to make it look better

Friday, January 7, 2011

StructureGraphic is now released!

After a short betta period, in which I sent the library only to few people for testing, I'm  now releasing the first public release of StructureGraphic! Students in the computer lab at my university are actually using this to debug their assignments in the data structures course - This makes me feel some pride :D

To those who haven't read the previous post about StructureGraphic, it's a library for visualizing data structures in java. Mainly, but not only, for debugging purposes.

Visualizations of a Binomial Heap (top) and a Red Black Tree (bottom)
Click to view fullsize
Feel free to dig into the source code and use the functions which are not yet documented. I'll complete the documentation of all the core functions later. Also, I'll try to make sure that any change in the library will be backwards compatiable - at least for the functions described in the official manual.

The library is currently licensed under GPLv3. If there are any projects which wish to use it, and have problems with that license, they can contact me.

Tuesday, December 21, 2010

Announcing - Project LibStructureGraphic

Note: This post is targeted mainly at programmers or people interested in visualization of data

As programmers, we often write very complex data structures. The hard part about maintaining complex data structures, is tracing bugs - since let's face it, in many places it's not practical to find which node out of several hundreds is deffected.

That's why I started a new project, called LibStructureGraphic. It's a library in Java, for visualizing data structures while making minimal or even no changes to their code. And since a picture is worth Ackermann(4,3) words (This is a programmers joke), here is an example:

Visualizations of a Binomial Heap (top) and a Red Black Tree (bottom)
Click to view fullsize

The idea is that having a visualization of the graph should help the programmer see more data at once, and speed up the times spent on finding bugs. I personally used custom code for drawing some data structures (for debugging) during my data structure course, and this was the source of this project. The visualization saved me hours of debugging!

The library requires a data structure to have the following properties in order to be visualized:
  1. For now (will change in the future), the data structure must be representable as a Tree, which means it's composed of nodes where each node has exactly 1 parent and zero or more children.
    Support for Directed-Acyclic-Graphs (DAGs) will be added in one of the next versions, and support for cyclic graphs is planned for the future
  2. Each node of the data structure should be represented by an object, which either implements a given interface (for finding the "children", "value" and "color" of the node), or has annotations on the fields that should be drawn. Ideally, the annotations are the preferred way since they mean you don't need to implement any custom functions; The interface is there only for nodes in which it's not possible.
    The nodes don't have to be of the same type - each node can be a completly different type of object!
The library will be released soon - I'm waiting only to see if one of the professors of my university will be willing to host it on its servers as an official project or not (Since this could be very useful in at least 3 mandatory courses). Non-Java versions (python, C#, C++, and potentially C with GObject) are not currently planned, but if enough people will want it, I will consider it ;)

And, the GIMP connection to this project (you didn't really expect me to write a post without mentioning GIMP, didn't you?) is that I'm working on a node-editor for GEGL. I knew I needed to implement a graph layout algorithm for it, and since I'm prototyping everything in Java, I thought of making a library from it.