1

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

Alan Birtles
  • 32,622
  • 4
  • 31
  • 60
Chandrapal Singh
  • 63
  • 2
  • 6

1 Answers1

3

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.

user1984
  • 5,990
  • 2
  • 13
  • 32
  • Thanks . @user17732522 tried to explain me but you made it clear . – Chandrapal Singh Jan 17 '22 at 08:05
  • you're welcome, happy to help :D – user1984 Jan 17 '22 at 08:05
  • 1
    That's a bit unclear. If you set `matrix[x][y]` to `true`, but do not set `matrix[y][x]` at the same time, it means the node `x` is connected to the node `y` whilst node `y` remains _not_ connected to `x`. This implies you're building a _directed_ graph. That, however, has not been defined in the problem statement, so I would rather assume the graph should be undirected. – CiaPan Jan 17 '22 at 08:13
  • Thank you for pointing that you, @CiaPan I'll amend my answer accordingly – user1984 Jan 17 '22 at 08:14
  • It now sets edges with wrong probability. You should not have two chances of putting an any specific edge. – user17732522 Jan 17 '22 at 13:45
  • I was thinking since we do this for every node equally, the probability stays correct. @user17732522 – user1984 Jan 17 '22 at 13:47
  • For optimization, we can run the loop only on the lower left triangle mirror it on the upper right. – user1984 Jan 17 '22 at 13:48
  • With the current code in the undirected case, the probability that `matrix[0][1]` will be set is the probability that the random number in the iteration with col=0/row=1 _or_ in the iteration with col=1/row=0 is smaller than `p`. That probability is `1-(1-p)^2`. – user17732522 Jan 17 '22 at 13:50
  • You are right, @user17732522 the probability of all the nodes is biased towards not being connected compared to the given probability. Thank you for pointing that out. I learned a good lesson :D. I have to run. Will come back later and ammend that. Thanks again. – user1984 Jan 17 '22 at 13:55