3
$\begingroup$

I have a problem similar to Using GraphData to generate all directed graphs with n vertices. That is, I want to have all directed graphs with n vertices (particularly, for n = 4).

However:

  1. not up to the isomorphism,
  2. satisfying additional constrains, for example that vertex 1 have to be connected with vertex 4,
  3. strongly connected.

I've tried to modify formulas presented in mentioned post (especially from the second solution, which is visually much more useful for my purposes), but without good results.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Generate all possible adjacency matrices:

n = 4;
adjmat = Table[Partition[IntegerDigits[i, 2, n^2], 4], {i, 0, 2^(n^2) - 1}];

Remove ones containing self-loops:

adjmat = Select[adjmat, Diagonal[#] == ConstantArray[0, n] &];

Make graph list:

glist = AdjacencyGraph[#, DirectedEdges -> True] & /@ adjmat;

Remove isomorphic duplicates:

glist = DeleteDuplicates[glist, IsomorphicGraphQ];

Length[glist]
(* 218 *)

Looks good, there are supposed to be 218 different ones on 4 vertices.

WARNING: We could have done this differently. Instead of removing adjacency matrices with non-zero diagonals, we could have applied SimpleGraph to the graph list. But in that case not all duplicates will be removed because of a long-standing bug in IsomorphicGraphQ!

We could also have not generated adjacency matrices with non-zero diagonals but I was too lazy to do that.

Now all you need to do is filter glist down based on your conditions, i.e.

Select[glist, condition]

For example,

Select[glist, ConnectedGraphQ]

will take only strongly connected ones.

Note: there are some programs out there that can generate non-isomorphic graphs quickly, e.g. geng from the nauty package.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your answer. However, this is not what I am looking for. Probably my question was not precisely stated. I want to have something like that: i.stack.imgur.com/Ukooj.png (this is from post mentioned earlier). However, I want to have all graphs, not only non-isomorphic. Then my second requirement does make sense. $\endgroup$
    – wiktoria
    Nov 2, 2015 at 19:09
  • $\begingroup$ So is it possible to remove from that solution requirement that only non-isomorphic graphs are shown? And how add to it conditions 2 and 3? $\endgroup$
    – wiktoria
    Nov 2, 2015 at 22:14
  • $\begingroup$ @wiktoria Well, I have an explicit step for removing isomorphic duplicates. What's wrong with just skipping that? $\endgroup$
    – Szabolcs
    Nov 3, 2015 at 20:13

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.