0

I am trying to implement the karger random contraction algorithm which involves selection of 2 adjacent vertices of a graph at random and contracting them till only 2 vertices are left in total.I am using this code for random number generation

#include <time.h>
#include <stdlib.h>

srand(time(NULL));
int r = rand() % v; (v is the number of vertices in the graph and will decrease by 1 for every contraction)

my input data is like:

1 (adjacency list of 1)

2 (adjacency list of 2)

3 (adjacency list of 3) so on till 200 vertices and their adjacency lists.

Since i have to delete nodes on the go, the two random numbers i generate, i am using them for positions i.e. i will select the vertices at the two positions and contract those two if they are adjacent nodes

I have to run the algorithm approx c*(n log n) times to get the proper min cut,

but i am unable to get min cut < 20 ,What am i doing wrong?I think "Its not random enough" how can i improve my solution?

sarat
  • 185
  • 9
  • If you are calling `srand` *every time* you need a new random number, then you will not actually get random numbers. If that's not your problem, please show more code. – rici Nov 12 '14 at 17:19
  • 1
    *"What am i doing wrong?"* What are you doing, apart from selecting one vertex at random? Since you ask if `rand() % v` is random enough, I'll point out that it is biassed. To illustrate this, consider `rand() % 21845`. If `rand()` returns a number in the range 0..32767 you can see that there is twice the chance of a number < 10922 than a number >= 10922. Similarly for a smaller sample, unless `v` is a factor of 32768. – Weather Vane Nov 12 '14 at 17:22
  • @rici I am calling srand once in the main function and then i call my function kargermincut which gives the min cut of the graph,multiple times in a for loop.So effectively,i am calling `srand` only once but `rand()%v` multiple times.It wont give random numbers? – sarat Nov 12 '14 at 18:53
  • @WeatherVane Nice Explanation,Can you tell me how can i implement this as unbiased as possible? – sarat Nov 12 '14 at 18:55
  • @WeatherVane So Lets say The range is 1-200 inclusive,according to your explanation numbers <200 have more chance than numbers> 200 but numbers < 200 almost equally have more chance right? Is the difference significant enough to decrease my net efficiency in min cut.The correct answer is 17,my answer turned out to be 20.I am curious whether only this rand function flaw alone is effecting the answer or my logic of contracting vertices by selecting random vertices and combining them to a super vertex also is effecting it – sarat Nov 12 '14 at 19:08
  • 32767(max) % 200 gives a slight bias in favour of numbers < 167. The `rand()` bias alone is probably not responsible, but `rand()` is all you have given us to comment on. – Weather Vane Nov 12 '14 at 19:29
  • I meant anything wrong with contraction of nodes by choosing two random vertices? – sarat Nov 12 '14 at 20:07
  • Aren't you supposed to pick a random vertex and then the nearest? – Weather Vane Nov 12 '14 at 20:16
  • I wrote the code as follows: 1)i am storing in a multi-way linked list structure (all the nodes in a specific adjacency list have a pointer to that nodes adjacency list) 2) lets say 5 and 11 are the nodes at the random positions which i am going to contract 3) so i will read 5's adjacency list;scan through each node and change 5 in the adjacency list of that node to 11,and append this 5's adjacency list to 11's.Delete 5 and any other 11's in this new adjacency list of 11. 4) RESULT????? i have contracted the edge 5 and 11 and made a new Super vertex 11 now 5 doesnt exist anywhere in the graph – sarat Nov 12 '14 at 20:21
  • @WeatherVane Yeah i am supposed to contract a random edge,but i am doing it by choosing two random vertices checking them whether they are adjacent (by searching for any one vertex in the other ones adjacency list),if they are not i will call two random vertices again else i will contract the edge by the above algo i am using,Please suggest me a better solution if you are familiar with karger min cut algorithm – sarat Nov 12 '14 at 20:26
  • If you are trying to find the nearest vertex to a randomly selected vertex by checking them at random you are on a highway to nowhere. Just parse the array of vertices and find the nearest (except self). – Weather Vane Nov 12 '14 at 20:41

1 Answers1

0

If I understand correctly, something like this should work:

   int min = ( rand() % 20 ); //random number 0-20        
   int r = ( rand() % (range-min) ) + min; //random number will be greater than min but less than range 
   printf('%d', numSet[r]); //randomly select array position
AnchovyLegend
  • 12,139
  • 38
  • 147
  • 231