write a C/C++/Java/Python program to implement Kernighan-Lin's bi- partitioning algorithm. The objective is to minimize the...

 

Transcribed Image Text:

write a C/C++/Java/Python program to implement Kernighan-Lin's bi- partitioning algorithm. The objective is to minimize the number of edges in the cut. Input: A text file describing a set of even number of nodes and a set of edges. If there are n nodes, the node indices are continuous integers from 1 to n. Input file format: • The first line has two numbers- the number of nodes followed by the number of edges. • Each of the following lines has two numbers that are indices of two nodes of an edge. For example: 32 12 23 Requirement: • The initial solution must be partition (1, 2) and +1, +2. n). • • The input filename should be taken as the argument at command line in Linux/UNIX. Please submit source code, which includes at most one .c file and at most one.h file, and the executable code that can run on an ECE server (Linux/UNIX). Please avoid using file compression, which may corrupt files. • Please name your files by your last name followed by the last 4 digits of your UIN. For example, if your last name is Rao and your UIN is 7070567, your executable filename should be ra00567 and the source code files are rao0567.c and rao0567.h. • The output should be displayed to screen in a self-clear format. Output: • Two partitions, each of which is described by the indices of its member nodes. • Cut set, represented by the edges in the cut, an edge is denoted by a pair of node indices. Grading: Your executable code will be evaluated by certain testcases on an ECE server. The grading will consider your program speed besides the solution correctness and completeness. write a C/C++/Java/Python program to implement Kernighan-Lin's bi- partitioning algorithm. The objective is to minimize the number of edges in the cut. Input: A text file describing a set of even number of nodes and a set of edges. If there are n nodes, the node indices are continuous integers from 1 to n. Input file format: • The first line has two numbers- the number of nodes followed by the number of edges. • Each of the following lines has two numbers that are indices of two nodes of an edge. For example: 32 12 23 Requirement: • The initial solution must be partition (1, 2) and +1, +2. n). • • The input filename should be taken as the argument at command line in Linux/UNIX. Please submit source code, which includes at most one .c file and at most one.h file, and the executable code that can run on an ECE server (Linux/UNIX). Please avoid using file compression, which may corrupt files. • Please name your files by your last name followed by the last 4 digits of your UIN. For example, if your last name is Rao and your UIN is 7070567, your executable filename should be ra00567 and the source code files are rao0567.c and rao0567.h. • The output should be displayed to screen in a self-clear format. Output: • Two partitions, each of which is described by the indices of its member nodes. • Cut set, represented by the edges in the cut, an edge is denoted by a pair of node indices. Grading: Your executable code will be evaluated by certain testcases on an ECE server. The grading will consider your program speed besides the solution correctness and completeness.

Answer rating: 100% (QA)

Below is an example implementation of KernighanLins bipartitioning algorithm in Python Save this code in a file named rao0567py Make sure to replace r... View the full answer