CODEWITHSUNDEEP
language-agnosticgraphicsgraphvisualization
David Rutten
David Rutten

Reputation: 4806

Drawing two-dimensional point-graphs

I've got a list of objects (probably not more than 100), where each object has a distance to all the other objects. This distance is merely the added absolute difference between all the fields these objects share. There might be few (one) or many (dozens) of fields, thus the dimensionality of the distance is not important.

I'd like to display these points in a 2D graph such that objects which have a small distance appear close together. I'm hoping this will convey clearly how many sub-groups there are in the entire list. Obviously the axes of this graph are meaningless (I'm not even sure "graph" is the correct word to use).

What would be a good algorithm to convert a network of distances into a 2D point distribution? Ideally, I'd like a small change to the distance network to result in a small change in the graphic, so that incremental progress can be viewed as a smooth change over time.

I've made a small example of the sort of result I'm looking for: Example Graphic http://en.wiki.mcneel.com/content/upload/images/GraphExample.png

Any ideas greatly appreciated, David

Edit:

It actually seems to have worked. I treat the entire set of values as a 2D particle cloud, construct inverse square repulsion forces between all particles and linear attraction forces based on inverse distance. It's not a stable algorithm, the result tends to spin violently whenever an additional iteration is performed, but it does always seem to generate a good separation into visual clusters:

alt text http://en.wiki.mcneel.com/content/upload/images/ParticleCloudSolution.png

I can post the C# code if anyone is interested (there's quite a lot of it sadly)

Upvotes: 5

Views: 433

Answers (3)

High Performance Mark
High Performance Mark

Reputation: 78316

You might want to Google around for terms such as:

  • automatic graph layout; and
  • force-based algorithms.

GraphViz does implement some of these algorithms, not sure if it includes any that are useful to you.

One cautionary note -- for some algorithms small changes to your graph content can result in very large changes to the graph.

Upvotes: 1

Andrew McGregor
Andrew McGregor

Reputation: 34602

The previous answers are probably helpful, but unfortunately given your description of the problem, it isn't guaranteed to have a solution, and in fact most of the time it won't.

I think you need to read in to cluster analysis quite a bit, because there are algorithms to sort your points into clusters based on a relatedness metric, and then you can use graphviz or something like that to draw the results. http://en.wikipedia.org/wiki/Cluster_analysis

One I quite like is a 'minimum-cut partitioning algorithm', see here: http://en.wikipedia.org/wiki/Cut_(graph_theory)

Upvotes: 1

moonshadow
moonshadow

Reputation: 89055

Graphviz contains implementations of several different approaches to solving this problem; consider using its spring model graph layout tools as a basis for your solution. Alternatively, its site contains a good collection of source material on the related theory.

Upvotes: 2

Related Questions