Notice

Due to the high volume of students downloading my code to use on school projects, I have temporarily taken down files which contain my code, until further notice. I encourage fellow students to write their own code. You can still compare the output of your code to the output of mine by running the testbench files I have included in this repository on your code. You can compare the outputs of your code to the output results of mine that I have uploaded to this repository.

Thank you for your understanding on this matter.

Project: K-L Tool

Dates: Sep-Dec 2015

Overview:

Software programming project to implement the Kernighan-Lin algorithm on files with nodes and edges that represent integrated circuits and their interconnects. The K-L algorithm is heuristic, so it does not find the exact solution, but will find the best solution with respect to initial conditions. In this case, the initial conditions are how the nodes are initially split, which is in half, down the middle. The graphic below illustrates the program run on a small set of data.

K-L Tool: KL_tool_LF.py
Benchmark test files (large data files):

• add20.txt
• bcsstk33.txt
• data.txt
• uk.txt

Input file format:

The input benchmark files are provided in the Chaco input file format. The initial (0th) line of the file contains two integers, representing the number of nodes and the number of edges in the graph. Each following (nth) line contains the list of nodes that share an edge with the nth node, separated by spaces.



The following example represents a complete graph on 6 vertices in this format.


6 15
2 3 4 5 6
1 3 4 5 6
1 2 4 5 6
1 2 3 5 6
1 2 3 4 6
1 2 3 4 5

Output on a slightly more complicated data set: