Automatic Placement algorithm, help needed

[Chris Jones]

----- -----
| 1 |-----------| 5 |--------------------|
----- ----- |
| |
----- | -----
| 2 |-------------- | 7 |
----- -----
|
----- ----- |
| 3 |-----------| 6 |--------------------|
----- -----
|
----- |
| 4 |--------------|
-----


I have 7 bins, called bin1, bin2,..., bin7. And 7 nodes called node1,
node2, ..., node7. Bin2 is adjacent to bin 1, bin3 is adjacent to
bin2, etc. The distance between bin2 and bin1 is 1, The distance
between bin7 and bin3 is 4, etc.

Each of the bins is to contain one node.

The nodes are connected as per the graph above, ie node1 is connected
only to node5, node5 is connected to nodes1,2,7. Etc.

The goal is to pack the nodes into these bins with the smallest TOTAL
length.

The nodes selection procedure would be a greedy process whereby
(1) the node which has the maximum connectivity would be selected
first and put in the centre bin;
(2) the next node selected must have been connected to the last node,
and be the one with the maximum connectivity. Repeat until all nodes
are in bins.

Write a generalised procedure to effectively pack the nodes into the
bins in order to achieve the minimum length.

Good luck!

Thanks,
Chris

 

[Paul E. Black]

chjones@dacafe.com (Chris Jones) writes:

I have 7 bins, called bin1, bin2,..., bin7. And 7 nodes called node1,
node2, ..., node7. Bin2 is adjacent to bin 1, bin3 is adjacent to
bin2, etc. The distance between bin2 and bin1 is 1, The distance
between bin7 and bin3 is 4, etc.

Each of the bins is to contain one node.

The goal is to pack the nodes into these bins with the smallest TOTAL
length.

Maybe a Huffman coding-like procedure would work better. Huffman
coding tends to optimize clusters, letting the root take care of
itself. Perhaps: pick those *farthest* from the root and cluster (lay
out) those. Then lay out the clusters, etc.

I think the example you gave, with seven nodes in a balanced tree,
won't demonstrate the relative merits of some assignment schemes.

-paul-
--
Paul E. Black (p.black@acm.org)