Write a Placement Algorithm for Directed Acyclic Graph (DAG) to be placed on XY- plane such that cost of the placement is minimized and the solution s optimized.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Write a Placement Algorithm for Directed Acyclic Graph (DAG) to be placed on XY- plane such that cost of the placement is minimized and the solution s optimized.

 

ijaag 18 6 2
21
32
43
54
65
76
8 17
g 18
10 7 2 3
ii 8 3 4
12 9 5 6
13 10 7 8
14 11 1 10
15 12 10 9
16 13 12 8
17 14 1 12
18 15 11 13
1g 16 13 9
20 17 14 15
21 18 7 16

Input File format:

Figure 1

The input file describes a directed acyclic graph (DAG), and all the internal nodes (i.e., nodes other than the PI and PO nodes) in the DAG have exactly two inputs. The first line contains the string “aag” followed by three integers, m, i, and o. m denotes the total number of nodes in the DAG. i denotes the number of primary input nodes (PIs). o denotes the number of primary output nodes (POs). The following i lines list the node ID PI node. The next o lines list the node ID of each PO node. The following lines indicate the (x y z), where y and z are input nodes to x.

nods_IvI
23456
89
12
14
16
18
oj
ill
27
3 10
4 11
s 13
6 15
7 17
B
9

The nodes should be placed according to their levels. Levels of the above DAG can be:

Figure 2

 

Cost Function: Sum of distance between all the edges (Manhattan Distance).

 

As per the above Figure 2, the DAG is been divided into several groups based on their levels.

Levels

Level 1: all the input nodes (1, 2, 3, 4, 5, 6).

Level 2: Output of input nodes (7, 8, 9).

Level 3: Output of level 2 nodes (10)

 

Level 7: output nodes (17, 18)

placement: Each level should be placed on each Column of XY-plane such that the cost function is minimized i.e., the solution is optimized as shown below:

Note that the graph is Directed and Acyclic. Consider two nodes A and B. B is the output node of A ( A → B), if A is placed on x-axis X = 1, then B cannot be placed on X

=1. It should at least be placed on X=2 i.e Nodes of different level cannot be placed on same column.

For example:

Solution 1:

 

Initially, we have to place nodes of each level on same column. Then we have to find the best location of each node based on their adjacent nodes such that the total Manhattan distance is minimized.

Both, solution 1 and solution 2 are accepted. But solution 2 is more optimized.

In solution 1, Level 1 nodes are placed on Column 1, Level 2 are placed on column 2 and so on. Then best location of each nodes is been found based on their adjacent connected nodes.

 

In solution 2, node 1 of column 1 can be placed on column 3 as it is then placed close to its adjacent node 11.

Implement an algorithm to optimize your solution.

Output Format

Environment Issue

The official evaluation platform will be an Ubuntu workstation, gcc and g++ compilers are available. We do not use Windows platform for evaluation, so please include your Makefile.

Project Submission

Source codes and the files should be compressed to .tar file. Please include a Makefile for compiling the codes and a Readme file for relevant information in using the codes. You also need to submit a report which describes and analyzes the algorithm you used.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of