AndreasL has asked for the wisdom of the Perl Monks concerning the following question:

Fellow monks,

I'm looking for a solution of an visualisation problem. I want to print the clusters and machines in an computing environment to an overview page.
I have some 8-node clusters (one may grow soon to an 10-node cluster), much more 4-node and 2-node clusters and also standalone machines. We can assume even numbers of machines in the clusters.
I now want to create a printout which not distributes machines all over the printout, but groups the machines together, which are belonging to the same cluster. 
c? ... cluster
m? ... machine
[|-] ... separates clusters

@ca = qw (ma mb mc md me mf mg mh); # 8-node cluster
@cb = qw (mi mj mk ml mm mn mo mp); # 8-node cluster
@cc = qw (mq mr ms mt);             # 4-node cluster
@cd = qw (mu mv mw mx);             # 4-node cluster
@ce = qw (my mz);                   # 2-node cluster
@cf = qw (m1 m2);                   # 2-node cluster
@cg = qw (m3 m4);                   # 2-node cluster
@ch = qw (m5);                      # standalone
@ci = qw (m6);                      # standalone
@cj = qw (m7);                      # standalone
@ck = qw (m8);                      # standalone

[download]
I don't want this, as this would be the easy solution :-)
(assumed a 10 columns output, should be configurable) 
 -----------------------------
|ma mb mc md me mf mg mh|mi mj
 -----------------------------
 mk ml mm mn mo mp|mq mr ms mt|
 -----------------------------
|mu mv mw mx|my mz|m1 m2|m3 m4|
 -----------------------------
|m5|m6|m7|m8|
 -----------
What I'd like to have is this (or similar): 
 -----------------------------
|ma mb mc md|mi mj mk ml|mq mr|
|           |           |     |
|me mf mg mh|mm mn mo mp|ms mt|
 -----------------------------
|mu mv|my mz|m3 m4|m7|m8|
|     |-----|-----|-----
|mw mx|m1 m2|m5|m6|
 -----------------
My idea: take two lines per cluster, find the biggest clusters, that fit's into the current double line and fill the remaining columns with smaller clusters/standalone machines. Continue with the next two lines and fill in the remaining stuff. Any ideas about better algorithms (or even modules :-)) I could use?
Or some keywords to feed Google?

Thanks
Andreas
Update: fixed two times m1 in @cf

Replies are listed 'Best First'.
Re: Visualisation of environment
by PodMaster (Abbot) on Mar 21, 2004 at 15:13 UTC
[reply]
[d/l]
Re: Visualisation of environment
by BrowserUk (Patriarch) on Mar 21, 2004 at 16:49 UTC

    This gets a bit flaky at the lower limit, and this application screams for Perl6::Form--if your brave:). I still can't quite wrap my brain around spill fields.

    Read more... (4 kB)
    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
[reply]
[d/l]
Re: Visualisation of environment
by MidLifeXis (Monsignor) on Mar 22, 2004 at 17:35 UTC

    Would this be a knapsack problem? You have a grid X by Y, and want to fit blocks into that space, where, if P is the number of processors, then X' = floor(log2(P)) and Y' = P / floor(log2(P)) (there might be an off by one here...). You could also switch X' and Y' around to help "fit" them into your knapsack.

    --MidLifeXis

[reply]
[d/l]
[select]
      Thanks MidLifeXis,

      knapsack was the term, I was looking for, now I can feed Google, to get additional input on an suiting algorithm. Also Super Search brought some interesting hits.
      Also thanks to BrowserUk and PodMaster for their code contributions. I'll post my final solution earliest after next weekend.

      AndreasL
[reply]
Re: Visualisation of environment
by cyocum (Curate) on Mar 22, 2004 at 12:50 UTC

    I think the best way to do that is to use perl's format capabilities.

[reply]
Re: Visualisation of environment
by flyingmoose (Priest) on Mar 22, 2004 at 17:46 UTC
    This vaguely reminds me (I said vaguely) a problem an former AI professor said he had to solve at a map company ... efficient layout of labels on maps. This problem basically kept trying various things using simulated annealing until a certain measurably "tolerable overlap" was computed... but to do that, you need to be able to programatically compute some sort of neatness scale...which is hard.

    That's why I said 'vaguely'. It would be more closely relevant if you were trying to draw an organized network topology, or something like that. This is simpler by being fairly rectilinear.

    Still, it's an interesting problem. And those are the good kind.

[reply]

Back to Seekers of Perl Wisdom