2
$\begingroup$

I was trying to generate random connected planar graph for dome numerical experiment of some transportation problem. I have three types of nodes: supply, transshipment and demand. I have the number of nodes and edges; also, i have following rules:

  1. There is no arc from supply nodes driectly to demand nodes. The connection between these two must be through transshipment nodes.
  2. It must be a connected graph.
  3. The grapgh can be either directed or undirected.
  4. Total number of edges is given, but there is no specific rule about exact number of edges between different types of nodes.
  5. There are no edges between supply nodes; however, it is not the case for transshipment and demand nodes. Any ideas how to code it? (no matter in what language, i just want to have an understanding of the process)

Thanks

$\endgroup$
5
  • $\begingroup$ Do you really need the graph to be planar (meaning embeddable in $\mathbb{R}^2$ such that no two edges cross)? $\endgroup$
    – prubin
    Sep 7 at 19:17
  • 1
    $\begingroup$ stackoverflow.com/questions/3232048/… $\endgroup$ Sep 7 at 19:25
  • $\begingroup$ @JorisKinable Do any of the methods there allow you to specify which edges not to include? $\endgroup$
    – prubin
    Sep 7 at 20:26
  • $\begingroup$ @Vala, is the question still relevant? $\endgroup$
    – A.Omidi
    Sep 8 at 20:27
  • $\begingroup$ @A.Omidi, thanks to Dr. Rubin it is not anymore. $\endgroup$
    – Vala
    Sep 11 at 15:20

1 Answer 1

0
$\begingroup$

Here are two approaches, both for an undirected graph (but easily modified to handle a digraph).

Method 1: Start with a complete graph (in the sense that all legal edges exist). Compile a list of all edges and shuffle it randomly. While the number of edges exceeds your quota, pop the next edge and remove it. If the graph remains connected, continue; if not, replace the edge and continue. If you use up all the edges before reaching the target number of edges, start over with a new random seed.

Checking whether the graph remains connected after removing edge (i, j) is not as bad as it sounds. You just need to do a depth-first search for a surviving path from i to j.

Method 2: Write an integer linear program to selected a subset of $m$ edges such that the graph is connected ($m$ being your required edge count). The model will contain a binary variable for each edge. Assign each of those variables a randomly generated positive cost and set minimization of the total cost as the objective. Method 2 does not require restarts (unlike method 1), but does require an integer programming solver and is likely to be slower (possibly a lot slower).

$\endgroup$
3
  • 1
    $\begingroup$ Note that the OP also wants the graph to be planar. $\endgroup$
    – RobPratt
    Sep 7 at 17:58
  • $\begingroup$ Oops, missed that. $\endgroup$
    – prubin
    Sep 7 at 19:16
  • $\begingroup$ Thanks Dr. Rubin, I was able to apply both methods. As you mentioned, the second one takes much longer to solve. $\endgroup$
    – Vala
    Sep 11 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.