Automatic Placement algorithm, help needed

From: Chris Jones (chjones_at_dacafe.com)
Date: 02/26/04


Date: 26 Feb 2004 05:46:03 -0800


----- -----
| 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