Code for random trivalent network generator. There are two integer parameters: n and k. There are 2n vertices and 3n edges, and n must be >1 since otherwise there is no such network. The algorithm selects one edge at a time by a certain procedure and adds it to the network; when there are k edges left to be added, it switches to a generate-all-possible-ways-to-complete-the-network-and-choose-one-of-
them-randomly procedure; k must be >5 since otherwise it is possible that there will be no way to complete the network. For fixed n, the higher k is the more random the algorithm. (At least one would hope that this would be the case if the algorithm is done correctly.)
The chief data structure used is of the form {{list(1),list(2),...,list(2n)},r,e}. This represents a partial network consisting of one component (including all of the edges and all vertices of degree>0) plus the vertices remaining to be added to the network (all vertices with degree 0). list(i) lists the vertices connected by an edge to vertex i. r is the number of edge connections that can be made to the current component. e is the number of edges needing to be added in order to complete the network. x_ below always refers to a structure of this sort, except in the case of CompleteNetwork, in which case x_ is a list of such structures all of whom have the same value for e.
them-randomly procedure; k must be >5 since otherwise it is possible that there will be no way to complete the network. For fixed n, the higher k is the more random the algorithm. (At least one would hope that this would be the case if the algorithm is done correctly.)
The chief data structure used is of the form {{list(1),list(2),...,list(2n)},r,e}. This represents a partial network consisting of one component (including all of the edges and all vertices of degree>0) plus the vertices remaining to be added to the network (all vertices with degree 0). list(i) lists the vertices connected by an edge to vertex i. r is the number of edge connections that can be made to the current component. e is the number of edges needing to be added in order to complete the network. x_ below always refers to a structure of this sort, except in the case of CompleteNetwork, in which case x_ is a list of such structures all of whom have the same value for e.
InitialNetwork[n_Integer]:={Flatten[{{{2},{1}},{}&/@Range[2n-2]},1],4,3n-1};
CanAddEdgeQ[x_,i_Integer,j_Integer]:=(Length[x[[1,j]]]<3)&&(i!=j)&&(!MemberQ[x[[1,j]],i])&&((x[[3]]==1)||(x[[2]]>2)||(Length[x[[1,j]]]==0));
UnWeightedList[x_,i_]:=Flatten[MapIndexed[If[CanAddEdgeQ[x,i,#2[[1]]],#2,{}]&,x[[1]]]];
WeightedList[x_,i_]:=Flatten[MapIndexed[Function[{y,z},If[CanAddEdgeQ[x,i,z[[1]]],NestList[(z[[1]])&,z[[1]],2-Length[y]],{}]],x[[1]]]];
FirstVertex[x_]:=Position[x[[1]],_?((0<Length[#]<3)&),{1},1,Heads->False][[1,1]];
AddEdge[x_,i_Integer,j_Integer]:=ReplacePartReplacePart x[[1]],Sort[Append[x[[1,i]],j]],i,Sort[Append[x[[1,j]],i]],j, If[Length[x[[1,j]]]==0,x[[2]]+1,x[[2]]-2],x[[3]]-1;
AddRandomEdge[x_]:=Module[{F,G},(F=FirstVertex[x];G=(#[[Random[Integer,{1,Length[#]}]]])&[WeightedList[x,F]];AddEdge[x,F,G])];
CompleteNetwork[x_]:=Module{F}, (If[x[[1,3]]==1,#,CompleteNetwork[#]])&UnionFlattenF=FirstVertex[#]; Map[Function[y,AddEdge[#,F,y]],UnWeightedList[#,F]]&/@x,1;
PseudoRandomNetwork[(n_Integer)?((#>1)&),(k_Integer)?((#>5)&)]:=MapIndexed (#2[[1]]->#1)&,(#[[Random[Integer,{1,Length[#]}]]])&CompleteNetwork {Nest[AddRandomEdge,InitialNetwork[n],Max[0,3n-k-1]]}[[1]];
Here is how I wrote up the procedure before programming it; it is still approximately the same.
1) Input an integer n>1. (The number of vertices in the completed network is 2n.)
2) Set up the following variables:
e = the number of edges which still need to be added to the graph;
r = sum(3-d_i) where i ranges over all vertices with degree>0 and d_i is the degree of vertex i.
The initial graph consists of vertices 1 and 2 and an edge between them. So at the start e = 3n-1 and r = 4.
3) If e<=K then enumerate every single way of completing the graph, choose one of them at random, and exit.
4) Let j be the first vertex in the graph with 0 < d_j < 3. Attach weights to all of the vertices as follows.
If r<=2 and e>1 then every vertex with degree zero gets weight 3 and every other vertex gets weight 0.
Otherwise:
a) vertex j gets weight 0.
b) any vertex currently connected to vertex j by an edge gets weight 0.
c) every other vertex gets weight 3-d where d is the current degree of the vertex.
Choose a vertex k at random, using these weights, and connect j to k with an edge. Let e=e-1. If k now has degree 1, let r=r+1; otherwise let r=r-2.
Go to step 3.
1) Input an integer n>1. (The number of vertices in the completed network is 2n.)
2) Set up the following variables:
e = the number of edges which still need to be added to the graph;
r = sum(3-d_i) where i ranges over all vertices with degree>0 and d_i is the degree of vertex i.
The initial graph consists of vertices 1 and 2 and an edge between them. So at the start e = 3n-1 and r = 4.
3) If e<=K then enumerate every single way of completing the graph, choose one of them at random, and exit.
4) Let j be the first vertex in the graph with 0 < d_j < 3. Attach weights to all of the vertices as follows.
If r<=2 and e>1 then every vertex with degree zero gets weight 3 and every other vertex gets weight 0.
Otherwise:
a) vertex j gets weight 0.
b) any vertex currently connected to vertex j by an edge gets weight 0.
c) every other vertex gets weight 3-d where d is the current degree of the vertex.
Choose a vertex k at random, using these weights, and connect j to k with an edge. Let e=e-1. If k now has degree 1, let r=r+1; otherwise let r=r-2.
Go to step 3.
It may actually be working. It really should implement partitions in CompleteNetwork instead of using unions, but I took the easy way out. Memory might be saved by doing this correctly. Also there is no real reason for CompleteNetwork to maintain copies of all of the different complete networks; it could just keep copies of the completions of the networks, and this would also save memory.
Example: here is a 100-vertex network and a 200-vertex network.
PseudoRandomNetwork[50,6]
{1{2,73,91},2{1,21,38},3{25,34,50},4{8,55,74},5{52,53,82},6{8,28,83},7{67,68,94},8{4,6,26},9{27,36,71},10{48,54,80},11{24,30,76},12{78,79,83},13{31,43,79},14{16,81,86},15{22,54,82},16{14,75,78},17{22,51,90},18{29,63,90},19{51,56,87},20{31,77,92},21{2,51,53},22{15,17,23},23{22,43,76},24{11,54,99},25{3,28,65},26{8,63,67},27{9,40,93},28{6,25,100},29{18,46,48},30{11,83,95},31{13,20,63},32{60,77,92},33{53,91,94},34{3,73,75},35{37,43,89},36{9,40,92},37{35,40,66},38{2,52,67},39{42,80,88},40{27,36,37},41{46,49,57},42{39,46,70},43{13,23,35},44{59,71,89},45{57,58,84},46{29,41,42},47{50,68,93},48{10,29,84},49{41,60,68},50{3,47,80},51{17,19,21},52{5,38,69},53{5,21,33},54{10,15,24},55{4,64,65},56{19,85,97},57{41,45,86},58{45,95,97},59{44,71,85},60{32,49,85},61{79,87,93},62{69,74,98},63{18,26,31},64{55,91,99},65{25,55,78},66{37,84,88},67{7,26,38},68{7,47,49},69{52,62,72},70{42,77,98},71{9,44,59},72{69,75,100},73{1,34,86},74{4,62,100},75{16,34,72},76{11,23,81},77{20,32,70},78{12,16,65},79{12,13,61},80{10,39,50},81{14,76,89},82{5,15,87},83{6,12,30},84{45,48,66},85{56,59,60},86{14,57,73},87{19,61,82},88{39,66,96},89{35,44,81},90{17,18,96},91{1,33,64},92{20,32,36},93{27,47,61},94{7,33,95},95{30,58,94},96{88,90,98},97{56,58,99},98{62,70,96},99{24,64,97},100{28,72,74}}
PseudoRandomNetwork[100,6]
This last one took maybe 3 minutes. Not bad; and the memory use isn't bad either:
MemoryInUse[]
1452608
MaxMemoryUsed[]
7065336
I haven't written a routine to check that the results are indeed connected, trivalent graphs with no self-edges and no parallel edges.