How to generate a random connected graph?

Question

For running algorithms like Minimum Spanning Tree, we want to create a undirected weighted graph to test and the graph is very large like n vertices and m edges. How can we create a random graph with random number of vertices and edges, so that the graph is connected?

Answer 1

To start, you can generate a random, connected tree by doing a random walk, except each step of the walk actually creates a the edge. This approach runs in O(V).

Code in Python

#PRE: V for the number of vertices

#POST: creates a random connected graph with a V-1 edges

def generateRandomConnectedGraph(self, V):

    initialSet = set()

    visitedSet = set()

    vertices = set()

    edges = set()

    #generate the set of names for the vertices

    for i in range(V):

        initialSet.add(str(i))

        vertices.add(str(i))

    #set the intial vertex to be connected

    curVertex = random.sample(initialSet, 1).pop()

    initialSet.remove(curVertex)

    visitedSet.add(curVertex)

    #loop through all the vertices, connecting them randomly

    while initialSet:

        adjVertex = random.sample(initialSet, 1).pop()

        edge = (random.randint(WEIGHT_MIN,WEIGHT_MAX), curVertex, adjVertex)

        edges.add(edge)

        initialSet.remove(adjVertex)

        visitedSet.add(adjVertex)

        curVertex = adjVertex

    return vertices, edges

From there, you can add random edges to the graph. I have not found a great approach to this, so the current method I use is generate all possible edges that can be created (ignoring the weights) between any two nodes and then randomly choose from that list. That generation of combinations takes O(V²) time.

Code in Python:

#PRE: the number of elements in a list

#POST: generate a 2D array of all combinations

def generateCombination(n):

    com = []

    for i in range(n):

        for j in range(i+1, n):

            com.append([i,j])

            com.append([j,i])

    return com

In total, this whole process takes O(V) + O(V²) + O(E-A) where A is the number of edges left to generate after creating the initial tree. So a O(V²). Not great but currently good enough for my purposes.

Answer 2

If matrix can be used to represent the graph, one possible solution may be as follows("import java.util.Random;" is required):

step 1:

Generate a random number of vertices

public int generateV(int maxnumberV)

{

Random random = new Random();

int numberofV=random.nextInt(maxnumberV)%(maxnumberV)+1;

System.out.println("The number of vertices is: "+numberofV);

return numberofV;

}

step 2:

Generate a random number of edges

public int generateE(int numberofV,int maxnumberE)

{   Random random = new Random();

int numberofE=0;

while(numberofE<numberofV-1||numberofE>(numberofV-1)*numberofV/2)

{

numberofE=random.nextInt(maxnumberE)%(maxnumberE)+1;}

System.out.println("The number of edges is: "+numberofE);

return numberofE;

}

step 3:

Initialize the Matrix

public void initializeMatrix(int numberofV,int numberofE,

int[][] matrix,int infinity)

{   for(int i=0;i<numberofV;i++)

    {for(int j=0;j<numberofV;j++)

    {   if(i==j)

      {matrix[i][j]=0;}

        else

      {matrix[i][j]=infinity;}

    }}

}

Step 4:

Generate connected graph by adding new vertices and connect them to random previous vertices.  Moreover, return how many edges the graph has now.  

public int addNewVertices(int numberofV,int numberofE,

int[][] matrix,int maxweight,int minweight)

{ int randomExistingV=1;

      int currentNumberofE=0;

      Random random = new Random();

    for(int currentVertice=1;currentVertice<numberofV+1;currentVertice++)

    {if(currentVertice>1)

    randomExistingV=random.nextInt(currentVertice-1)%(currentVertice-1)+1;

    if(currentVertice!=randomExistingV)

    { matrix[currentVertice-1][randomExistingV-1]

     =matrix[randomExistingV-1][currentVertice-1]

          =random.nextInt(maxweight)%(maxweight-minweight+1)+minweight;

        currentNumberofE++;}

    }

    return currentNumberofE;

}

step 5:

After ensuring the graph is connected, add new edges to reach the required edge number.

public void addNewEdges(int numberofV,int numberofE,

int[][] matrix,int maxweight,int minweight,

int infinity,int currentNumberofE)

{     Random random = new Random();

while(currentNumberofE<numberofE)

   {  int m=random.nextInt(numberofV)%(numberofV) + 1;

      int n=random.nextInt(numberofV)%(numberofV) + 1;

      while(matrix[m-1][n-1]!=infinity)

      {

      n=random.nextInt(numberofV)%(numberofV) + 1;

      m=random.nextInt(numberofV)%(numberofV) + 1;

      }

      matrix[m-1][n-1]=matrix[n-1][m-1]

    =random.nextInt(maxweight)%(maxweight-minweight+1)+minweight;

      currentNumberofE++;

   }

}

step 6:

Show the matrix to see if anything goes wrong.

public void showM(int numberofV,int[][] matrix)

{     int k;

    int x;

    for(int i=0;i<numberofV;i++)

    {for(int j=0;j<numberofV;j++)

    {x=matrix[i][j];

        System.out.print(x);

       for(k=0;k<6-Integer.toString(x).length();k++)

       {

      System.out.print(" ");

       }

       if(j==numberofV-1)

    {System.out.println();}

   }}

}

We can test this in main faction:

public static void main(String[] args) {

// TODO Auto-generated method stub

     RandomGenerate r1=new RandomGenerate();

     int a[][];

     a=new int[15][15];

     r1.generateV(15);

     r1.generateE(15, 18);

     r1.initializeMatrix(15, 18, a, 66);

     r1.addNewVertices(15, 18, a, 9, 1);

     r1.addNewEdges(15, 18, a, 9, 1, 66, r1.addNewVertices(15, 18, a, 9, 1));

     r1.showM(15, a);

}

Comments

Is there a way to divide your method into smaller subroutines?