CODEWITHSUNDEEP
algorithmdata-structuresgraphprobability
Chandrapal Singh
Chandrapal Singh

Reputation: 93

Generate random graph with probability p

Write a function in main.cpp, which creates a random graph of a certain size as follows. The function takes two parameters. The first parameter is the number of vertices n. The second parameter p (1 >= p >= 0) is the probability that an edge exists between a pair of nodes. In particular, after instantiating a graph with n vertices and 0 edges, go over all possible vertex pairs one by one, and for each such pair, put an edge between the vertices with probability p.

How to know if an edge exists between two vertices .

Here is the full question enter image description here

PS: I don't need the code implementation

Upvotes: 1

Views: 609

Answers (1)

user1984
user1984

Reputation: 6838

The problem statement clearly says that the first input parameter is the number of nodes and the second parameter is the probability p that an edge exists between any 2 nodes.

What you need to do is as follows (Updated to amend a mistake that was pointed out by @user17732522):

1- Create a bool matrix (2d nested array) of size n*n initialized with false.
2- Run a loop over the rows:
  - Run an inner loop over the columns:
    - if row_index != col_index do:
        - curr_p = random() // random() returns a number between 0 and 1 inclusive
        - if curr_p <= p: set matrix[row_index][col_index] = true
          else: set matrix[row_index][col_index] = false
          - For an undirected graph, also set matrix[col_index][row_index] = true/false based on curr_p

Note: Since we are setting both cells (both directions) in the matrix in case of a probability hit, we could potentially set an edge 2 times. This doesn't corrupt the correctnes of the probability and isn't much additional work. It helps to keep the code clean.

If you want to optimize this solution, you could run the loop such that you only visit the lower-left triangle (excluding the diagonal) and just mirror the results you get for those cells to the upper-right triangle. That's it.

Upvotes: 3

Related Questions