I need to be able to generate random graphs (both general and bipartite). I require that the generated graph have a specified number of vertices and edges (in the bipartite case the number of vertices on each side is specified). My particular problem is that I also require that the graph be connected. I have found no research on this problem. Generating all graphs satisfying specifications and then selected from this set at random is not feasible for space reasons (I also don't know how to do this).
My plan is to generate a graph at random keeping track of the number of components until I only have d edges to add and the generated graph so far has (d + 1) components. Then add the remaining edges ensureing that each edge added joins two unconnected components of the graph. The difficulty is that now each time I generate a new edge at random I must discard it if both of its endpoints are on the same component of the graph. I have no idea how many edges I can be expected to discard by this approach and have not found anything in the literature on my approach or any other approach.
Is there a result that states how many edges I need to generate before the graph becomes connected?
Is there another approach that guarentees termination in a reasonable time (O(nlog n) or better)?
I rarely visit here so emailing me at rpboland@gmail.com might be useful.
Recommended Answers
Jump to PostIs there a result that states how many edges I need to generate before the graph becomes connected?
Well... one hint to this might be found in the definition of a
Jump to PostThe graph is being generated by selecting edges to add randomly and as a result many of the edges generated do not connect two components and thus must be discarded.
I guess the problems lies in your conception of "randomly". This is an extremely vague term. I assume …
Jump to PostYou didn't understand my algorithm at all. I'm working under the assumption that you are generating the vertices at random. If you are starting with a set of vertices that you cannot choose, then the problem is different and my algorithm does not apply directly (but you can fix that …
All 9 Replies
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.