Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I'm working on a graph theory problem, and given $n$ vertices, I would like to be able to generate all non-isomorphic connected graphs (not necessarily simple) with $n$ vertices, each having degree 3. Currently I'm doing the graph finding in Sage, but the included graph packages have given me problems, so I've used dictionaries instead. My approach is to generate graphs with vertex degree at most three, and recurse on previous such lists, increasing edge number by 1 each time. This is not optimal, and is really time-intensive, mostly because of my primitive isomorphism-checking function.

So, I would like to know if it is possible to generate this type of list (connected graphs with maximal degree at most 3) in Mathematica, because I can actually plot them there easily as well. I've been using a converter (line 46 here) that gives the Mathematica command to plot the graphs from Sage, for example,

{GraphPlot[{1 -> 2, 1 -> 1, 2 -> 3, 2 -> 3}], 
 GraphPlot[{1 -> 2, 1 -> 1, 2 -> 3, 2 -> 4}], 
 GraphPlot[{1 -> 2, 1 -> 1, 2 -> 3, 3 -> 3}], 
 GraphPlot[{1 -> 2, 1 -> 1, 2 -> 3, 3 -> 4}], 
 GraphPlot[{1 -> 2, 1 -> 2, 1 -> 3, 2 -> 3}], 
 GraphPlot[{1 -> 2, 1 -> 2, 1 -> 3, 2 -> 4}], 
 GraphPlot[{1 -> 2, 1 -> 2, 1 -> 3, 3 -> 4}], 
 GraphPlot[{1 -> 2, 1 -> 3, 1 -> 4, 2 -> 3}], 
 GraphPlot[{1 -> 2, 1 -> 3, 1 -> 4, 2 -> 5}], 
 GraphPlot[{1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4}], 
 GraphPlot[{1 -> 2, 1 -> 3, 2 -> 4, 3 -> 5}]}

gives all the graphs with 4 edges and vertices of degree at most 3. Any help in this regard would be appreciated. For the past two hours Sage has been computing all such graphs with 5 edges, and I would like at least 9-edge graphs, so things are not looking hopeful in that direction.

Maybe there are nice packages to do this with? I've looked at Combinatorica, but the graph-manipulating functions don't seem well-suited to my needs, though that is from a cursory inspection.

share|improve this question
    
As a start, GraphData[n] enumerates all the n-vertex simple graphs. It only works up to $n=7$, though. To see the available graphs whose vertices all have degree 3, try GraphData["Cubic"]. –  J. M. Oct 12 '12 at 13:35
add comment

1 Answer 1

This might get you started. It generates (I think) all graphs of given number of vertices and degree, with the following caveats:

  • They are undirected.
  • They do not have self edges.
  • Edges only have weight 1 (that is, no duplicated edges).

You might be able to modify to add those features.

Also this makes no attempt to weed out isomorphic graphs.

stepJ[j_, n_, deg_, partial_] := Module[
  {tally, needs, possibles, edges},
  tally = ConstantArray[0, n];
  Map[tally[[#]] += 1 &, Flatten[partial]];
  needs = deg - tally[[j]];
  If[needs == 0, Return[{partial}]];
  If[n - j < needs, Return[{}]];
  possibles = Subsets[Range[j + 1, n], {needs}];
  res = Reap[Do[
      edges = possibles[[k]];
      If[And @@ Thread[tally[[edges]] < deg],
       Sow[Join[partial, Thread[{j, edges}]]]]
      , {k, Length[possibles]}]][[2]];
  If[res === {}, {}, res[[1]]]
  ]

makeGraphs[vert_, deg_] := Module[
  {subgraphs, newpartials},
  subgraphs = stepJ[1, vert, deg, {}];
  Do[
   subgraphs = Flatten[Reap[
       Do[newpartials = stepJ[j, vert, deg, subgraphs[[k]]];
        If[newpartials =!= {}, Sow[newpartials]];
        , {k, Length[subgraphs]}]][[2]], 2], {j, 2, vert}];
  subgraphs
  ]

In[227]:= Timing[res = makeGraphs[8, 3];]

(*Out[227]= {11.560000, Null}*)

In[228]:= Length[res]

(*Out[228]= 19355*)
share|improve this answer
    
Thanks, this shows a lot of the functionality of Mathematica I hadn't yet seen! The checking for isomorphisms is inescapably to be the most computation-intensive part of my function, however, so I'm still stuck there. –  jlv Oct 14 '12 at 1:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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