CODEWITHSUNDEEP
c++searchgraphdijkstra
JohnA
JohnA

Reputation: 167

Given a set of vertices, how do you generate a strongly-connected directed graph with a near-minimal amount of edges?

I am trying to perform testing on my graph class's dijkstras algorithm. To do this, I generate a graph with a couple thousand vertices, and then make the graph connected by randomly adding thousands of edges until the graph is connected. I can then run the search between any two random vertices over and over and be sure that there is a path between them. The problem is, I often end-up with a nearly-dense graph, which because I am using an adjacency list representation, causes my search algorithm to be terribly slow.

Question : Given a set of vertices V, how do you generate a strongly-connected, directed graph, that has significantly less edges than a dense-graph over the same vertices would have?

I was thinking about simply doing the following :

vertex 1 <--> vertex 2, vertex 2 <--> vertex 3, ..., vertex n-1 <--> vertex n

And then randomly adding like n/10 edges throughout the graph, but this doesn't seem like an optimal way of coming up with random graph structures to test my search algorithms on.

Upvotes: 5

Views: 1673

Answers (2)

Sneftel
Sneftel

Reputation: 41513

One approach would be to maintain a set of strongly connected components (starting with |V| single-vertex components), and in each iteration, merge some random subset of them into a single connected component by connecting a random vertex of each one to a random vertex of the next one, forming a cycle.

This will tend to generate very sparse graphs, so depending on your use case, you might want to toss in some extra random edges as well.

EDIT: Intuitively I think you'd want to use an exponential distribution when deciding how many components to merge in a single iteration. I don't have any real support for that, though.

Upvotes: 2

DWilches
DWilches

Reputation: 23035

I don't know if there is a better way of doing it, but at least this seems to work:

  • I would add E (directed) edges between random vertices. This will generate several clusters of vertices.
  • Then, I need to connect those clusters to form a chain of clusters, so ensuring that from a cluster I can reach any other cluster. For this I can label a random vertex of each cluster as the "master"vertex, and join the master vertices forming a loop. Thus, you have a strongly-connected directed graph composed of clusters (not vertices yet). The last master should be connected back to the first master, thus creating a loop.
  • Now, in order to turn it into a strongly-connected digraph composed of vertices I need to make each cluster a strongly-connected digraph by itself. But this is easy if I run a DFS starting at the master node of a cluster and each time I find a leaf I add an edge from that leaf to its master vertex. Note that the DFS must not traverse outside of the cluster.

I think this may work, though the topology will not be truly random, it will loop like a big loop composed of smaller graphs joined together. But depending on the algorithm you need to test, this may come in handy.

EDIT:

  • If after that you want to have a more random topology, you can add random edges between vertices of different clusters. That doesn't invalidate the rules and creates more complex paths for your algorithm to traverse.

Upvotes: 1

Related Questions