# Return to Question

 4 better error checking edited May 25 '15 at 17:17 Histograms 1,91177 silver badges2020 bronze badges I need to generate random connected simple graphs (no loops) with the constraint that exactly two vertices must only have a single edge. I can create many connected graphs (but very few will have the properties I want) like so: gps = Select[RandomGraph[{30, 70}, 512], ConnectedGraphQ];  This is a bit inefficient because it's rejection sampling. I'm no expert in graph theory so if you know a more efficient way that would be helpful. Here's a diagram of the kind of graph I need: I thought about using DegreeGraphDistribution but I don't care about specifying the interior vertices' exact degree as long as d>=2 and the 'input' and 'output' nodes have degree 1. Ideally, I'd like this to be as fast as possible, to generate an extremely large number of such graphs (tens of thousands if not more) quickly. UPDATE: best I've got so far is an inefficient rejection sampling approach (RandomInteger could be replaced with a Binomial variate maybe) but this fails sometimes because DegreeGraphDistribution isn't always guaranteed to generate a proper graph for given degrees... so I just evaluate the line a few times until it works: gpsWhile[Quiet[Check[gps = Select[ Quiet@RandomGraph[ Select[Quiet@ DegreeGraphDistribution[Join[RandomInteger[ RandomGraph[ DegreeGraphDistribution[ Join[RandomInteger[{2, 5}, 20]50], {1, 1}]], 10000], 10000] ConnectedGraphQ],  ConnectedGraphQ]; RandomGraph::argt]] === RandomGraph::argt];  I need to generate random connected simple graphs (no loops) with the constraint that exactly two vertices must only have a single edge. I can create many connected graphs (but very few will have the properties I want) like so: gps = Select[RandomGraph[{30, 70}, 512], ConnectedGraphQ];  This is a bit inefficient because it's rejection sampling. I'm no expert in graph theory so if you know a more efficient way that would be helpful. Here's a diagram of the kind of graph I need: I thought about using DegreeGraphDistribution but I don't care about specifying the interior vertices' exact degree as long as d>=2 and the 'input' and 'output' nodes have degree 1. Ideally, I'd like this to be as fast as possible, to generate an extremely large number of such graphs (tens of thousands if not more) quickly. UPDATE: best I've got so far is an inefficient rejection sampling approach (RandomInteger could be replaced with a Binomial variate maybe) but this fails sometimes because DegreeGraphDistribution isn't always guaranteed to generate a proper graph for given degrees... so I just evaluate the line a few times until it works: gps = Select[ Quiet@RandomGraph[ DegreeGraphDistribution[Join[RandomInteger[{2, 5}, 20], {1, 1}]], 10000], ConnectedGraphQ];  I need to generate random connected simple graphs (no loops) with the constraint that exactly two vertices must only have a single edge. I can create many connected graphs (but very few will have the properties I want) like so: gps = Select[RandomGraph[{30, 70}, 512], ConnectedGraphQ];  This is a bit inefficient because it's rejection sampling. I'm no expert in graph theory so if you know a more efficient way that would be helpful. Here's a diagram of the kind of graph I need: I thought about using DegreeGraphDistribution but I don't care about specifying the interior vertices' exact degree as long as d>=2 and the 'input' and 'output' nodes have degree 1. Ideally, I'd like this to be as fast as possible, to generate an extremely large number of such graphs (tens of thousands if not more) quickly. UPDATE: best I've got so far is an inefficient rejection sampling approach (RandomInteger could be replaced with a Binomial variate maybe) but this fails sometimes because DegreeGraphDistribution isn't always guaranteed to generate a proper graph for given degrees... so I just evaluate the line a few times until it works: While[Quiet[Check[gps = Select[Quiet@ RandomGraph[ DegreeGraphDistribution[ Join[RandomInteger[{2, 5}, 50], {1, 1}]], 10000], ConnectedGraphQ],  RandomGraph::argt]] === RandomGraph::argt];  3 update edited May 25 '15 at 16:48 Histograms 1,91177 silver badges2020 bronze badges I need to generate random connected simple graphs (no loops) with the constraint that exactly two vertices must only have a single edge. I can create many connected graphs (but very few will have the properties I want) like so: gps = Select[RandomGraph[{30, 70}, 512], ConnectedGraphQ];  This is a bit inefficient because it's rejection sampling. I'm no expert in graph theory so if you know a more efficient way that would be helpful. Here's a diagram of the kind of graph I need: I thought about using DegreeGraphDistribution but I don't care about specifying the interior vertices' exact degree as long as d>=2 and the 'input' and 'output' nodes have degree 1. Ideally, I'd like this to be as fast as possible, to generate an extremely large number of such graphs (tens of thousands if not more) quickly. UPDATE: best I've got so far is an inefficient rejection sampling approach (RandomInteger could be replaced with a Binomial variate maybe) but this fails sometimes because DegreeGraphDistribution isn't always guaranteed to generate a proper graph for given degrees... so I just evaluate the line a few times until it works: gps = Select[ Quiet@RandomGraph[ DegreeGraphDistribution[Join[RandomInteger[{2, 5}, 20], {1, 1}]], 10000], ConnectedGraphQ];  I need to generate random connected simple graphs (no loops) with the constraint that exactly two vertices must only have a single edge. I can create many connected graphs (but very few will have the properties I want) like so: gps = Select[RandomGraph[{30, 70}, 512], ConnectedGraphQ];  This is a bit inefficient because it's rejection sampling. I'm no expert in graph theory so if you know a more efficient way that would be helpful. Here's a diagram of the kind of graph I need: I thought about using DegreeGraphDistribution but I don't care about specifying the interior vertices' exact degree as long as d>=2 and the 'input' and 'output' nodes have degree 1. Ideally, I'd like this to be as fast as possible, to generate an extremely large number of such graphs (tens of thousands if not more) quickly. I need to generate random connected simple graphs (no loops) with the constraint that exactly two vertices must only have a single edge. I can create many connected graphs (but very few will have the properties I want) like so: gps = Select[RandomGraph[{30, 70}, 512], ConnectedGraphQ];  This is a bit inefficient because it's rejection sampling. I'm no expert in graph theory so if you know a more efficient way that would be helpful. Here's a diagram of the kind of graph I need: I thought about using DegreeGraphDistribution but I don't care about specifying the interior vertices' exact degree as long as d>=2 and the 'input' and 'output' nodes have degree 1. Ideally, I'd like this to be as fast as possible, to generate an extremely large number of such graphs (tens of thousands if not more) quickly. UPDATE: best I've got so far is an inefficient rejection sampling approach (RandomInteger could be replaced with a Binomial variate maybe) but this fails sometimes because DegreeGraphDistribution isn't always guaranteed to generate a proper graph for given degrees... so I just evaluate the line a few times until it works: gps = Select[ Quiet@RandomGraph[ DegreeGraphDistribution[Join[RandomInteger[{2, 5}, 20], {1, 1}]], 10000], ConnectedGraphQ];  2 added 1 character in body edited May 25 '15 at 16:08 Histograms 1,91177 silver badges2020 bronze badges I need to generate random connected simple graphs (no loops) with the constraint that exactly two vertices must only have a single edge. I can create many connected graphs (but very few will have the properties I want) like so: gps = Select[RandomGraph[{30, 70}, 512], ConnectedGraphQ];  This is a bit inefficient because it's rejection sampling. I'm no expert in graph theory so if you know a more efficient way that would be helpful. Here's a diagram of the kind of graph I need: I thought about using DegreeGraphDistribution but I don't care about specifying the interior vertices' exact degree as long as d>2d>=2 and the 'input' and 'output' nodes have degree 1. Ideally, I'd like this to be as fast as possible, to generate an extremely large number of such graphs (tens of thousands if not more) quickly. I need to generate random connected simple graphs (no loops) with the constraint that exactly two vertices must only have a single edge. I can create many connected graphs (but very few will have the properties I want) like so: gps = Select[RandomGraph[{30, 70}, 512], ConnectedGraphQ];  This is a bit inefficient because it's rejection sampling. I'm no expert in graph theory so if you know a more efficient way that would be helpful. Here's a diagram of the kind of graph I need: I thought about using DegreeGraphDistribution but I don't care about specifying the interior vertices' exact degree as long as d>2 and the 'input' and 'output' nodes have degree 1. Ideally, I'd like this to be as fast as possible, to generate an extremely large number of such graphs (tens of thousands if not more) quickly. I need to generate random connected simple graphs (no loops) with the constraint that exactly two vertices must only have a single edge. I can create many connected graphs (but very few will have the properties I want) like so: gps = Select[RandomGraph[{30, 70}, 512], ConnectedGraphQ];  This is a bit inefficient because it's rejection sampling. I'm no expert in graph theory so if you know a more efficient way that would be helpful. Here's a diagram of the kind of graph I need: I thought about using DegreeGraphDistribution but I don't care about specifying the interior vertices' exact degree as long as d>=2 and the 'input' and 'output' nodes have degree 1. Ideally, I'd like this to be as fast as possible, to generate an extremely large number of such graphs (tens of thousands if not more) quickly. 1 asked May 25 '15 at 14:49 Histograms 1,91177 silver badges2020 bronze badges