oi math wizzes! (looking at you Braque)

[Bani]

If I know the n:m relations ("related yes/no and if related, how strong" ) of x objects, and then want to arrange the x objects on a 1- or 2-dimensional grid in such a way that related objects are close together, or at least as close as possible, how do I do that?
What's this optimization problem called in English? Is there a precise algorithm for large problems (1000 items with up to 1 billion relations)? A good heuristic? Usable (pseudo-) code?

I know I heard about this some time and it has to be one of the staples of relational analysis, but Google can't seem to help me, nor the textbooks I have here....

Thanks for any help

 

[Braque]

I know what your talking about - can't remember the name of the problem/solution, but one approach is to basically dump all the objects randomly distributed, attach them all together with springs with a tension proportional to the strength to the relationship, then run a physics sim and let them settle.

 

[Bani]

That's amazing

Unfortunately, I am not amazing enough to code that for a desktop PC in 5 days

 

[Braque]

That's amazing

Unfortunately, I am not amazing enough to code that for a desktop PC in 5 days

Sure you are, using someone else's physics code you can easily code that up in that timescale: http://www.ode.org/

EDIT:

That said, 1000s of objects and 1 billion relationships might prove to be a problem for this approach, you may have to build it up hierarchically using a clustering algorithm.

How "good" does the solution need to be, and how much time does the code need to create a solution in?

 

[Bani]

The solution doesn't have to be perfect by any means, runtime should be "overnight on a standard PC" at most. The 1 billion relationships is exaggerated though (can't even have more than 1 million ) , a typical case would be 1.000 objects and < 30.000 relationships.

Sadly, I code in VB, and the company isn't going to pay me to learn C++ well enough =/
I wish I was more of a programming geek, using nvidia CUDA and physics simulations in a business consulting project would be cool as hell and would instantly make me unfire-able

 

[Arly]

I love this thread. I'm currently changing from system tester back to system developer again, with the focus on C++, but I think it will be more as a monkeycoder implementing LTE in the start, but kudos to you for your knowledge Braque!

 

[Braque]

The physics solution might actually work in that case. Try it.

 

[Gink]

Man, do I feel stupid now, or what?

 

[Tbone]

welcome to my world, Gink

 

[Bani]

On a science-related note, I just noticed the goatse in the BBT intro

I used to skip it because the jingle is so atrocious, and now there's yet more reasons for it!

what has been seen cannot be unseen!

 

[Tbone]

rofl

 

[Lebuff]

wthwthwthwthwthwthwthwthwthwthwthwthwthwthwthwthwth

 

[Ayu]

It's no goatse