How to pick edge randomly from adjacency list representation of graph

Question

vector<int> adj[5]; // I have 5 nodes 

// some code for pushing nodes in adjacency list

for( int i = 0; i < 5; i++ )  // printing graph  
{
    for( int p = 0 ; p < adj[i].size(); p++ )
    {
        cout<< i << " , "<< adj[i][p] << endl;
    }
}

srand (time(NULL));
for( int k = 0 ; k < 3; k++ )  // just want to see random output multiple times, so using for loop 3 times.
{
    int i = rand() % 5; // picking node ( 1-5) randomly 
    int p = adj[i].size(); // calculating number of adjacent nodes 
    int j = rand() % p;   // here I am wrong, 
    cout<< " Random edge " << i+1 <<", " << j;
}

Actually I want to implement Kargar's Min cut program. For that I want to pick an edge randomly. But I am facing this problem:

I am getting a floating point exception. core dumped if I add above code to my program. I checked that the lines with int i and int p are calculating perfectly ( I printed them to see ) but if you add int j = rand() % p in the code it gives the floating point exception ( core dumped).

Can anyone help me?

Actually I am getting floating point exception. core dumped ( if I add above code in my program) I checked int i , int p are calculating perfectly ( I printed them and see ) but if you add int j = rand() % p in code it gives floating point exception ( core dumped) So I guess it is wrong — Tushar, Mar 31 '17 at 12:05
Interesting problem. If you add the last comment in the question by [edit]ing, it clarifies what did not work. — serv-inc, Apr 02 '17 at 18:57

score 0 · Answer 1 · answered Mar 25 '18 at 12:41

0

Your algorithm is not right if you want to pick an edge uniformly randomly. For example:

0: 1,2,3
1: 2
2: 3,4,5
3: 4,5
4: 5

In this case, the prob. of edge (1,2) is chosen is larger than edge (0,1).

As for the exception problem, I guess some adj[i].size() equals to 0.

Besides, although rand() doesn't return negative number, please be reminded that the modulus of a negative number can be negative, e.g. -3%5=-3.

answered Mar 25 '18 at 12:41

Aqua

1
1

Can you suggest an algorithm that /is/ correct? Perhaps that would be based on selecting an entry at random from a list of all (unique) edges? – rwp Mar 25 '18 at 13:07
If edges are stored in one array, that would be easy. If using adj lists, the problem is almost the same as weighted sampling. First sample a vertex according to its degree, and then uniformly choose a neighbor of this vertex. About weighted sampling, see [HowToPickAnItemByItsProbability](https://stackoverflow.com/questions/9330394/how-to-pick-an-item-by-its-probability) – Aqua Mar 26 '18 at 14:32

How to pick edge randomly from adjacency list representation of graph

1 Answers1