Can RandomGraph[DegreeGraphDistribution[{3, 3, 3, 3, 3, 3, 3, 3,3, 3, 3, 3, 3, 3, 3, 3,3,3,3,3}],EdgeStyle->Green,VertexStyle->Yellow] produce all 510489 non-isomorphic cubic graphs on 20 vertices if I put it in a while loop and toss out isomorphic ones that are already stored in, say, a list L?

I have a question that feels too small to post as a question, but Google and the Mathematica documentation don't seem to be clearing it up for me. Where can I find documentation of the rule number convention for CellularAutomaton for higher than 1 dimension? I understand the one-dimension convention, but I'd like a way to calculate the number for, say, a certain 5-state 2D automaton (even if the number is big)

Is there a way to detect if a graph is isomorphic to any graphs stored in a list?

@uwnojpjm Map[IsomorphicGraphQ[graph1,#]&,listofgraphs] should work. If that looks confusing to you, see mathematica.stackexchange.com/questions/18393/…

Lists are like array in Mathematica, right?

Yes

@uwnojpjm Yes.

@MarkS. Sounds like a perfectly good question for the main site.

@halirutan I may just have to do that. It would be unfortunate for Mathematica if it doesn't have an answer like "here's the page of documentation you missed", and unfortunate for me if it does.

So, if a list L = {g}, where g is a graph, then can I do IsomorphicGraphQ[L[i],j] where i is an index, say, 0 and j is another random graph?

@uwnojpjm Randomly taking graphs and hoping you get all instances doesn't sound like a good plan to me. I'm a bit rusty with graphs, but isn't there a better approach to sequentially move through all graphs of with n edges that all have degree 3?

After all, the adjacency matrix will always contain 3 entries in each row and column.

I'm open to efficiency.

@uwnojpjm OK, let me at least tell you my idea. Let's say we take a smaller graph with 6 edges.

Yeah.

The adjacency matrix might look like this

@MarkS., what is the "return value/object" for Map[IsomorphicGraphQ[graph1,#]&,listofgraphs]?

A list of True/False. You can pass it into Or if you just want to know if it's isomorphic to at least one.

@uwnojpjm When you now look at each column or row, you see that each of them contains exactly 3 ones and 3 zeros. Every column or row is a permutation of Permutations[{1, 1, 1, 0, 0, 0}]

There are only 20 in this simple example.

@MarkS., how's that?

@uwnojpjm For example, Apply[Or, {False, True, False}] returns True

If I leave the false part blank for an If conditional it does nothing, right? Like, If[x=y,y=3,]

Ok, I haven't tried this, but this is my idea to produce all 510489 non-isomorphic cubic graphs on 20 vertices:

gist.github.com/anonymous/…

Which no doubt has a HUGE run time.

@uwnojpjm Yes, if that works in theory, the run time is unmanageably large. It's far better to take halirutan's advice

I believe my idea is still too bruteforce and too large.

At least for the original problem.

I can only give a hint. When I see this right, then using the adjacency matrix the problem is similar to the famous queens problem.

The difference is the conditions: The sum of each row and each column must always be 3.

@MarkS., when you say unmanageably large what's that mean? Days? Weeks?

@uwnojpjm More like in the range "death of the universe"

What? Really? How'd you come to that conclusion?

@uwnojpjm You say there are about 500000 solutions, right?

Just assume for a second, you are able to collect 100000 of such graphs. You need to test each next graph against your 100000 already found solutions. Give it a quick test:

gr = Table[
   RandomGraph[
    DegreeGraphDistribution[{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
       3, 3, 3, 3, 3, 3}], EdgeStyle -> Green,
    VertexStyle -> Yellow],
   {100000}
   ];

IsomorphicGraphQ[gr[[1]], #] & /@ gr; // AbsoluteTiming

Takes about 5 seconds here. So each next graph you draw needs to be tested (in the worst case) against all your solutions and you are not even half way there.

Yeah, according to computationalcombinatorics.wordpress.com/2013/01/20/…

Can you rent processing power somewhere?

You know, send in your calculation, and let it run on a supercomputer, and check back in a week.

@uwnojpjm That won't help, believe me. The option you have is to read that paper and reimplement what they did.

And as I already assumed, you need a construction algorithm. Simply drawing from a random distribution won't help. Since they published a paper on it, I'm sure it's nothing you can do in 3 lines of Mathematica code.

Ok, well, what about reducing the size by limiting to only graphs that have a certain independent set size?

That increases the speed by skipping non matches.

If[Length[FindIndependentEdgeSet[g]]==10,KEEP,SKIP] where g=RandomGraph[DegreeGraphDistribution[{3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3}‌​]]

My little Wolfram development platform sandbox aborts my attempts because run time is limited for my account.

@uwnojpjm Ignoring any graph theory/size of the problem complexities, the idea of generating random things is simply not efficient for any purpose where you want to find all of something. With a theoretical supercomputer/large memory, you're better off generating, say, every single possible graph on 20 vertices and pruning them somehow. As halirutan says, you'll have to be a little smarter than that in constructing things, especially if you only want one graph per isomorphism class.

Reminds me of "bogosort"…

I know it's inefficient, but I'm trading "current lack of understanding of how to implement" with "long processing time".

@uwnojpjm Are you trying to generate all the half million graphs yourself, or do you just want to import them into mathematica?

If you just want to have them, then you can download their string identifiers here: hog.grinvin.org/Cubic

For the one with a half million graphs, I would not try to just Import the file, I would grab them one line at a time. Here is code that will generate 10,000 cubic graphs with 20 vertices,

Yes, and I want to sort them by connected ({20}) and unconnected ({8,12},{4,4,4,4,4},{4,4,4,8},{4,4,6,6},{4,4,12},{4,6,10},{4,8,8},{4,16},{6,6,8}‌​,{6,14}), and among the complete cubic graphs on 20 vertices I want to sort by independent vertex set size, so eights, nines, and tens (max).

@uwnojpjm importing the graphs would be the first step. You can grab all 500k graphs using the code posted above. All the links in the table here can be imported the same way: hog.grinvin.org/Cubic

What kind of graphs are these?

I'm looking for all not-necessarily-connected non-isomorphic cubic graphs on 20 vertices.

@uwnojpjm hog.grinvin.org/data/cubics/cub20.g6 has the 510,489 graphs that you mentioned in this comment

Me versus Rubio: imgur.com/a/ST631

Is there a Mathematica function that can connect the vertices of two isomorphic graphs with red edges? Like, if you had a cubic tetrahedral graph with vertices v1,v2,v3,v4 and a copy v'1,v'2,v'3,v'4, how could you connect like this: v1<->v'1,v2<->v'2,v3<->v'3,v4<->v'4 but still have the original respective tetrahedral graphs retain their edges. Seems like it would be something native, can't find.

Hi all, I posted a detailed answer, which I thought is informative, but surprisingly I am not getting votes. Let me know if I completely misunderstood the question. Thanks.

@VitaliyKaurov I think it is a great answer. Voted for it just now.

@C.E. ha! great to hear thank you! i was worried already I goofed ;-)

:)

Anyone on?

I' going crazy trying to understand how to plot a riemann surface of a function made up by the labert W

*lambert

the function is $w(z)^{d}+w(z)+z^{d-1}$

and the output should looks like this

what could be on the three axes?

the lambert W function is ProductLog[z] on Mathematica