CODEWITHSUNDEEP
c++algorithmrandomgraph
Chase R Lewis
Chase R Lewis

Reputation: 2307

Generating Random Constrained Graph

I need to generate a randomized graph with a fixed number of vertices. I'm having some difficulty getting a solution every time.

Graph Rules

  1. Each Vertex will have a random number of connections that is at most N-1 where N is the total number of vertices.
  2. The Vertices cannot contain direct connections to themselves
  3. The vertices cannot contain duplicate connections to other vertices.
  4. If a vertex A is connected to Vertex B then Vertex B must connect to Vertex A.
  5. Each vertex must connect to at least 3 other vertices. So each vertex will have between [3,N-1] edges.

I'm getting a correct solution about 70% of the time, but other times I get fairly far into the graph then no valid vertices are left. What constraints on the vertex connections do I need to guarantee a solution?

What I'm doing so far

  1. Randomize a number of connections for each vertex between [3,N-1].
  2. Check that the total number of connections is even. If A points to B and B points to A then the total number of connections in the graph should be even or else there is no solution. If it is odd modify a vertex so the total number is even.
  3. Fill in each vertex that is fully constrained. So a vertex that has N-1 connections must point to ALL other vertices. Fill in a connection from that vertex to all others and give all other vertices a connection to the fully constrained ones.
  4. Process each vertex by how tightly it is constrained. So process all vertices with N-2 connections then, N-3 connection, then N-4, etc by generated random vertex indexes.
  5. If The new random index is valid connect them then continue, if it is not valid rerandom the index until you get a valid value. (The graphs are only going to be 7-15 nodes or so maximum so this doesn't take extremely long).

Generally I get to the last 2 vertices but then have no valid values left with this method. Each needs 1 more connection but they are already connected to each other. Anyone have a better algorithm or an additional constraint on the number of connections values that would help me out?

There should BE many solutions given there is an even number of edges, but my algorithm above obviously doesn't guarantee that one will be found.

Upvotes: 4

Views: 419

Answers (1)

Doug Currie
Doug Currie

Reputation: 41220

  1. Create a vector of all vertices with fewer than 3 edges.
  2. Choose a vertex from the vector at random.
  3. Copy the vector with the chosen vertex removed (you could swap the chosen vertext and the last one and adjust the size).
  4. Also remove all target vertices already connected to the chosen vertex.
  5. Choose a vertex from the copied vector, and create an edge in each direction between the two chose n vertices
  6. Repeat steps 1..5 as long as the vector of all vertices with fewer than 3 edges is not empty

Upvotes: 1

Related Questions