Problem 1:
You are given a file (in the eclipse project under data/[login to view URL]) that contains the adjacency list representation of a simple undirected graph. There are 200 vertices labeled 1 to 200. The first column in the file represents the vertex label, and the particular row (other entries except the first column) gives all the vertices that the first vertex is adjacent to. So for example,
the 6th row looks like: "6 155 56 52 120 ......". This just means that the vertex with label 6 is adjacent to (i.e., shares an edge with) the vertices with labels 155,56,52,120,......,etc
Your task is to code up and run the randomized contraction algorithm for the min cut problem and use it on the above graph to compute the min cut. (HINT: Note that you'll have to figure out an implementation of edge contractions. Initially, you might want to do this naively, creating a new graph from the old every time there's an edge contraction. But you should also think about more efficient implementations.) (WARNING: As per the lectures, please make sure to run the algorithm many times, and remember the smallest cut that you ever find.)
Instructions:
1- Download the starting project from the course website. The file is named
[login to view URL]
2- Un-rar the file anywhere in your hard disk.
3- Open eclipse. Choose the workspace where you will store the project as current workspace (the eclipse workspace can be any folder in your hard disk that will be used by eclipse to store projects)..
4- Go to File-> Import->General->Existing project into workspace.
You should now have the project in your workspace. Navigate the project’s files to have an idea about the current code.
Note: (you must complete My original code ([login to view URL]))
In this project, you have a light-weight nice library (graphstream) that supports dynamic graph visualization, this is useful to illustrate how algorithms work for students for example
look upload files