6
$\begingroup$

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 get them from graph.

Can you point me to some algorithms for incremental drawing and streaming of graph? (and yes, I Googled a lot :))

Thanks in advance!

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ Cross-posted on programmers $\endgroup$
    – Peter Taylor
    Commented Aug 8, 2011 at 14:35
  • 1
    $\begingroup$ interesting problem but its not clear what you mean by "streaming" or if you are hoping to display all vertices (which seems impossible). by "stream" do you mean "view the graph locally & move through it based on adjacent vertices"? there are some examples of apps out there that do that. one that comes to mind is at thesaurus.com where you can traverse the massive synonym graph of the english language "locally"... so it seems to me this may be more a UI design/interface problem. $\endgroup$
    – vzn
    Commented Feb 5, 2012 at 19:37
  • 1
    $\begingroup$ one strategy would be to look at the general trend of convergence for force-based algorithms. my suspicion, I havent seen anyone look at this, they would tend to coverge to an MST (minimum spanning tree) like structure with the "center" of the MST in the center of the display space. therefore if you compute the MST & use it as a starting pt for your vertexes & just initially place them in a nonoptimal greedy way it might be acceptable. $\endgroup$
    – vzn
    Commented Feb 5, 2012 at 19:40

2 Answers 2

Reset to default
2
$\begingroup$

I would suggest using some Graph database like neo4j and have a look into the paper running large graph algorithms

Improve this answer
$\endgroup$
0
$\begingroup$

Probably you do not need to stream the graph.

You can run your algorithm to displace the graph in 3d space assigning positions do all nodes and then you can combine it with a Octree for culling the nodes that will not be seen by the camera.

Navigate the camera through space and query the Octree wich nodes are visible in a given moment.

As a side optimization you can group "far" nodes in one "reference" node to guide the user and when he goes near the group it splits and show the real content of the node group

Refs:

http://en.wikipedia.org/wiki/Octree http://developer.nvidia.com/GPUGems2/gpugems2_chapter37.html

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for your answer, eduardo. However, it is not solving my problem. I can't reposition all vertices at once, because the graph is huge and my app should be working on a modest desktop computer in real time. It would be quite easy to implement the solution if I had positions of vertices :). I must stream graph and reposition vertices as I'm moving through the space. $\endgroup$
    – Leon Wickliff
    Commented Aug 8, 2011 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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