Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have the following problem: I'm developing a software for data visualization where I get a graph structure and represent it in 3D space. So far, I've been using force-based algorithms to draw graphs and it worked well, until I got requirement that my software should represent very big number of vertices and edges (few millions). It would be very impractical to hold all those in memory, so I'm looking for an algorithm that will enable me to stream small portions of graph as I "walk" through the space.

However, the main problem is in showing and dynamically repositioning of vertices, since I don't have already predefined positions, and I must calculate them.

Can you point me to some algorithms for incremental drawing and streaming of graph?

Thanks in advance!

share|improve this question
    
Cross-posted on cstheory –  Peter Taylor Aug 8 '11 at 14:35

2 Answers 2

I would do some calculations to actually show that it is infeasible to hold the graph in the memory that you have. As a quick estimate, if you have 25 million vertices and each one contains 12 ints (32 bytes), you are talking about roughly 1 GB of memory. What you are doing should be doable on a typical 4GB desktop.

What will be more problematic is the execution time. If you are looking at calculating a force between each pair of vertices, that is a N^2 algorithm. So if you increase the number of vertices from a thousand to a million (a factor of 1000), the execution time goes up by a factor of a million. This may make you current solution infeasible. There are other force calculation algorithms that are optimized for large numbers of vertices that you might consider.

share|improve this answer

are you holding them in memory, or calculating them as you go? If the latter, just drop old vertexes as new ones are needed.

The traditional algorithm for drawing a sub-set of a graph is a scene graph, used a lot in computer graphics to display just the visible parts of a 3d model, it basically clips parts of the model that are not in the visible area and ignores them.

I can't think of anything else that might be relevant without more detail.

share|improve this answer
    
Well, as I wrote, "It would be very impractical to hold all those in memory", since the number of vertices and edges is huge. I need the algorithm that will enable me to dynamically load edges and vertices, reposition them and show in 3D space. Hiding and releasing invisible parts from memory is not a problem, problem is in algorithm itself. I must use some version of the force-based GD algorithm, which draws vertices using positions of all others. So, at the end, algorithm I need would be able to use force-based approach and reposition specific parts of graph. I hope that's enough info :) –  Leon Wickliff Aug 8 '11 at 14:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.