Creating a "layered" layout

Nov 24, 2010 at 9:17 PM

I'm using version 1.0.1.136 of the NodeXL dlls to create graphs for me in a WPF application.  I have a class that houses a NodeXLControl.  When an object of this class is constructed, it is passed a "node" and then searches a data repository to find other items related to that node.  After finding these items, it creates the vertex and edge collections, assigns them to the NodeXLControl and then asks it to lay out and draw the graph.  The number of vertices in these graphs is pretty small; usually <10, and maybe as high as 50.

Ideally, I'd like to see items grouped in about 5 horizontal layers on the screen, with items of a particular type all in one layer.  When I add the vertex to the graph, I'd specify what layer it belongs in, but let NodeXL choose the exact position of items to group items together.  I suppose when I think of items grouped appropriately, it just means minimal edge crossings.  I understand that NodeXL would allow me to create my own layout to do just about anything, but I was hoping there might be a way to "tweak" something that existed already or use properties to customize the existing layouts.

So, based on that:

1) Do you have any suggestions for existing layouts that might help me?  The Sugiyama looked promising because it said it was layered, but I couldn't find any properties I could set to modify how it chooses layers.  Does the order in which I add the vertices matter?

2) Might the GraphBinner or RectangleBinner classes help me accomplish this?  If so, do you have any examples for how to use them?

3) If I do have to go down the fully custom layout route, I assume the hard part would be locating items to miminize the edge crossings.  I have no experience with doing that, so are there any code samples or references you point me to for efficient algorithms?

Thanks.  Any help is appreciated.

Brian

Nov 25, 2010 at 3:35 PM

Brian:

None of our layout or helper classes do what you need to do.  Sugiyama comes closest, but as you noted, it does not offer the control over layer content that you want.  Our Sugiyama implementation, which is based on work done by Lev Nachmanson at Microsoft Research, is a very old implementation, and I wondered whether the latest version might offer more control.  Unfortunately, from what I see at its Web site (http://research.microsoft.com/en-us/projects/msagl/faq.aspx), it does not.  (By the way, the order in which you add vertices does not matter.)

All I can suggest is to search for something like "graph layout layered minimize edge crossings" to see what kind of layout algorithms are out there.  You might also check various open-source graph packages for what types of layouts they implement.  Take a look at Jung, for example (http://jung.sourceforge.net/).

If you do add a new layout to NodeXL, instructions for doing so can be found in the file HowToAddANewLayout.txt in the NodeXL source code.  The latest version is available on NodeXL's Downloads tab.  (The Source Code tab has been abandoned due to the endless headaches I had with it.)

-- Tony

Nov 26, 2010 at 6:52 PM

Hi Tony,

Thanks for the quick reply; and on Thanksgiving Day, even!  I'll grab the source code to look at how to add a custom layout, and take a look at JUNG and whatever else I can find.  Thanks again - if I have any further questions, I'll let you know.

Brian

Nov 28, 2010 at 1:28 PM

Hi Tony,

I did a little reading about force-directed graphs, and also remembered reading in one of the other discussions that in your Fruchterman-Reingold implementation, you provide a call to do another 10 iterations of the algorithm: ForceLayout() I think it was.  Given that, I had a thought:  Would it be possible for me to give some starting positions of my own and then force the layout of the Fruchterman-Reingold?  All I'm thinking of doing is trying to start with some types of nodes near the top and others near the bottom.  If I start them out this way, it might find a local minimum that looks more like what I want.

Do you think this would be possible, or am I just dreaming?  To do it, would I just set the Location property of the vertices, do a few calls to ForceLayout() and then call DrawGraph() with the "layout first" argument false?

Brian

 

Nov 29, 2010 at 3:28 PM

Brian:

You can certainly try that.  I think this is how you would do it:

1. Set your Vertex.Location properties.

2. Set the ReservedMetadataKeys.LayoutBaseLayoutComplete key on the Graph object.  This tells FruchtermanReingoldLayout that the graph has already been laid out and that it shouldn't initialize the vertex locations to random values.

3. Optionally set the FruchtermanReingoldLayout.Iterations and C properties.  You would have to determine good values experimentally.

4. Call NodeXLControl.DrawGraph(true).  The true argument tells the control to lay out the graph.  Because of the ReservedMetadataKeys.LayoutBaseLayoutComplete key you set on the Graph object, FruchtermanReingoldLayout will use your initial Vertex.Location values as starting points.

I haven't actually tried this.  You can let me know if you run into problems with it.

Also, if you happen to have installed our NodeXL Excel Template application, you can experiment with the layout without having to write any code.  In the Template, you would:

1. Enter your edge list into the Edges worksheet.

2. Click Show Graph at the top of the graph pane.  (Internally, this sets the ReservedMetadataKeys.LayoutBaseLayoutComplete key on the Graph.)

3. Manually drag your vertices into a tree.

4. Optionally set NodeXL, Graph, Layout, Layout Options, Fruchterman-Reingold layout properties.

5. Click Lay Out Again at the top of the graph pane.

-- Tony

 

Nov 29, 2010 at 4:07 PM

Great.  I was thinking of using the FruchtermanReingoldLayoutSelectivelyRandomize key to achieve that - I didn't find the LayoutBaseLayoutComplete key in the ReservedMetadataKeys list in the help for version 136.  Is this a change between 136 and the current (156)?  I'll probably just update to the latest DLLs to be sure.

Good idea to try it out in Excel first.  Thanks for all the help!

Brian

Nov 29, 2010 at 4:10 PM

Whoops - jumped the gun a bit.  I see LayoutBaseLayoutComplete in version 136.

Nov 29, 2010 at 4:17 PM

Setting the FruchtermanReingoldLayoutSelectivelyRandomize key on the graph will have the same effect.  In fact, I see in my comments for the FruchtermanReingoldLayout class that that's actually the documented way of doing it.

-- Tony

Dec 11, 2010 at 5:54 PM

Hi Tony,

I've played a bit with creating my own layout.  As a first step, I based one off the Fruchterman-Reingold class, and added an additional attractive force towards the vertical centerline of the graph.  I had hoped that with a sample graph with just 2 vertices connected by an edge, I would see these two vertices aligned vertically in the center of the graph.  In the Fruchterman-Reingold layout, these two end up at opposite corners of the rectangular graph.  Despite the additional attractive force toward the center, they are laid out identically in my layout.

I have three questions:

1) Is there something in the base layout process that would cause this?  Though it's certainly possible I don't have my additional attractive force quite right, but I feel like I'm missing something.

2) Before starting my own laoyt, I was trying to figure out how set initial vertex locations programmatically like we discussed above.  However, I found it impossible to figure out the size of the graph's rectangle ahead of the layout.  Is there any way that you know of to determine this?  I'm guessing it is determined by Windows and then handed to the NodeXLControl at the time it needs to be rendered.  The control hands the dimensions to the graph through the LayoutContext.  Is this about right?

3) In order to debug whether my additional force in my custom layout is working properly, I wanted to be able to step through it.  But, as I have found with other experiments using the BackgroundWorker, that can't be done when the layout is being done with the BackgroundWork asynchronously.  What's the best way to force a synchronous layout so I can step through my custom layout code?

Thanks,

Brian

Dec 13, 2010 at 4:08 PM

Brian:

1) No, the base layout process does not modify the vertex locations; that's entirely up to the derived layout class.  I can't say how your additional force would or wouldn't work, as it all depends on where you inject it within the Fruchterman-Reingold algorithm and exactly what it does.

2) Yes, that's correct.  The derived layout class is told which rectangle to lay out the graph within via the LayoutContext object that gets passed to the LayOutGraphAsync() or LayOutGraph() method.  The rectangle is calculated by the system using WPF's layout engine, which differs significantly from the Resize/Paint scheme you might be thinking of when you talk about "at the time it needs to be rendered," but as a layout developer you don't need to be concerned about that.

3) In Visual Studio 2008 Professional, I can set breakpoints in multithreaded code with no problem.  I don't know why that isn't working for you, but I bet you could get a quick answer by posting a question to the Visual Studio Debugger forum at http://social.msdn.microsoft.com/Forums/en/vsdebug/threads.

-- Tony