Simon Palmer’s blog

SpringGraph

I came across the amazing SpringGraph developed by Mark Shepherd and documented on his blog. The code is license free and available for download. I duly did so.

We have an interesting problem in our software which is to do with aggregation. Our model is basically groups of nodes (planpoints) collected into folders (portfolios). The planpoints and portfolios have a classic parent-child relationship. Values stored on the child planpoints are aggregated together to give totals/averages etc. on the parent portfolio.

Dialectyx Aggregation Pathways Graph

This was all great but then someone said, hey, we’d like to make a new “super” portfolio and each planpoint inside it we want to represent a portfolio made elsewhere in the business. That’s fine, we said, go right ahead, there’s nothing stopping you. We recommend you institute a naming convention.

They did exactly that and were very happy. Shortly after they asked, is there any way we can get the software to take the numbers from the portfolios and move them automatically to the planpoints in the “super” portfolio. That question opened the door to aggregation, hierarchies, and everything else that comes with it.

Having spent a long time working for Cognos and thinking about exactly these problems, I decided that the last thing I wanted to do was reproduce an OLAP engine or try and tackle the enterprise wide aggregation issues that Planning tools like Hyperion, Cognos and others do. Basically I have better things to waste my life doing.

But the request was a genuine need from our users and one I could not ignore, so I set about adding a relationship between a planpoint and a portfolio which is not its parent and in so doing created the necessary relationships to form graphs in our data. With graphs come aggregation but also come circular references, multiple aggregation pathways but worse still, trees.

I hate trees. Not the leafy kind, the software kind. Trees are generally a lazy way of displaying data that suits the software devloper but not the end user. They are a demonstration of the model of the data rather than the processes that the data is supposed to support. There is always a better user interface solution than a tree. I have steadfastly avoided using trees in our product and was not going to start now.

I was searching for an alternative when I cam across SpringGraph and it allows me to draw our graph in a way which is appealing and informative and is not a tree. However, like every silver lining, there was a cloud. In this particular case the cloud was a CPU intensive timer which the graph implementation left running.

I found that the time could occupy 15% of my CPU basically just deciding to do nothing. Because the code was a free download from a blog I posted a request for a fix, but unfortunately didn’t get a reply. In case Mark Shepherd ever reads this, I cannot blame you for not watching replies on a 12 month old blog, so please, no criticism intended.

Being an algorithm hack myself I thought, well, I have the code, howhard can it be to fix it myself. So here’s my fix. I’m publishing it here because I have placed a back link on Mark Shepher’s blog in case anyone else finds the trail and needs a solution.

It’s actually embarrassingly simple and the reason for a long preamble is that I don’t have much code to post. The key is to not fire the timer if nothing happens, i.e. the graph is in a settled state. The underlying algorithm class ForceDirectedLayout contains a tick() method as does the SpringGraph class. In SpringGraph the tick method in turn kicks off the timer which calls tick() when the timer ends. This is the infinite timer loop that was consuming my CPU.

The tick() method in ForceDirectedLayout looks like this…

public function tick(): Boolean

{

    if (!(damper<0.1 && damping && maxMotion<motionlimit))

    {

        //trace("relax " + getTimer());

        relax();

        //trace("relax done " + getTimer());

        return true;

    } else {

        //trace("don't relax");

        return false;

    }

}

Importantly it returns a boolean stating whether it actually did anything. The tick() method in SpringGraph calls the ForceDirectedLayout method, but ignores its return status. If the autoFit flag is switched on (which I imagine will always be the case) the SpringGraph goes on to do very useful processing which keeps the graph on the viewing canvas, but it leaves the timer ticking forever.

My solution was to add a boolean return value to the autoFitTick() method and to check what came back from theForceDirectedLayout and also set the return value to true if the additional autofit processing caused any redrawing. My amended autofitTick() method is a bit too big to post here, but it simply sets a local boolean variable to true if anything changes during its processing and returns it.

The returned value is used by tick() to choose whether to re-fire the timer. If nothing happened it doesn’t do it…

        protected function tick(event:TimerEvent = null):void
        {
        	var done_something:Boolean = false;
        	if(_autoFit)
        	{
        		done_something = autoFitTick();
        	}
        	else
        	{
				done_something = forceDirectedLayout.tick();
        	}
        	if (done_something)
        	{
				this.invalidateDisplayList();
				startTimer();
				trace("springgraph - donesomething");
        	}
        	else
        	{
				trace("springgraph - NOT donesomething");
        	}
       }

This is all fine, except now that the timer has been stopped (or not re-started) it never re-starts. For my purposes I added a call to refresh() in the setter for the dataProvider of the graph to make sure that the whole timer process was restarted if the data on the graph changed. To do the job properly I would probably need to add similar logic elsewhere in the code to make sure that all data or layout changing events started the timer again, but it works for my purposes and I consider the matter fixed.

If you have come across this post and want my code please contact me directly.

Advertisements

2 Comments »

  1. Hi,

    Thank you for your post.
    It was very useful for me.

    Best Regards,
    Diyan.

    Comment by Diyan Gochev — July 13, 2010 @ 1:01 pm


RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: