URGENT...This is an Algorithm that needs to be implemented (Force Directed Algorithm) in C++ followed by implementing Lee's routing Algorithm.


Part1 of the assignment involves creating a Dynamic grid with spacing one unit each and cells of dimensions 6 units width and 6 units height need to be placed in the grid based on the Force Directed Algorithm. The size of the grid used for placement will vary dynamically based on the number of cells to be placed. The minimum distance of separation between adjacent cells (The closest they can be placed) is 1 unit. Each cell has 4 terminals (two on top and two in the bottom that occupies 1 grid space each. each of the 4 terminals of a cell are connected to the other terminals of other cells that are placed (connections). The input file to the program will consist of


1. no.of cells to be placed in the grid


2. no.of connections between the cells (between the terminals of each cell)


3. followed by a list of individual connections specifying which terminal number of which cell is connected to the which other terminal of the other cell on the other end of the connection.


NOTE: it possible that some terminals may not be connected at all and may just be free, it also possible that some cells maybe free standing and may not be connected to any other cells.

Sample Input Format:


First Line: no.of cells (C)


Second Line: no.of connections/Nets (N)


Next N lines specify the Nets


(Each Net is specified in the following format- Net num , cell num, terminal num, cell num, terminal num)


eg:


3 (3 cells to be placed)


4 ( 4 connections/nets exist between them)


11113 (connection#1, cell 1, terminal#1, cell 1, terminal#3)


21431 (connection#2, cell 1, terminal#4, cell 3, terminal#1)


32332 ....


41221 ....

Part2:


Once the cells have been placed based on the Force Directed Algorithm, the cell terminals in the connection list need to be connected (wired). Wires cannot intersect. to avoid intersection, Two layers are available to connect. All cells are placed in one layer and connections are made as much possible in single layer. those wires that cannot be connected without overlapping(intersecting a previously laid connection) will be stopped before the point of intersection in that layer and continued towards its destination terminal in layer two. It is implicitly assumed that the terminals of the cells that were placed in layer 1 are also available in layer 2 directly above.So a wire that was continued in layer 2 (as it was intersecting a previously laid connection in layer 1) can stop right above the terminal of a particular cell in layer 1 to complete connection in layer 2.

Design rules:


The minimum spacing between adjacent wires/nets is 1 unit


the minimum spacing between a cell and a wire is 1 unit.

The output of the program must be of the type .mag file for viewing the placed and connected cells in Magic software. The output should give the total wire length used in overall connection process, no.of transitions of wires from layer 1 and layer 2, overall execution time and memory used in executing the program.

THE ALGORITHM WILL BE PROVIDED WITH DETAIL EXPLANATION AND SAMPLE WORKED OUT EXAMPLE TO BETTER AID THE PROGRAMMER UNDERSTAND THE OPERATION. PDFs WITH DIAGRAMATIC WORKING WILL ALSO BE MADE AVAILABLE TO THE PROGRAMMER. THIS PROJECT IS OF URGENT NATURE AND NEEDS TO BE COMPLETED BY 28TH fEBRUARY 2010.