2
$\begingroup$

I'm looking for a digraph dataset that can return all directed graphs satisfying certain requirements.

Following are some examples:

  1. All tournament with 12 vertices;
  2. All connected digraphs with 10 vertices;
  3. All digraphs with 9 vertices whose underlying undirected graph bipartite.

Is there a digraph dataset that can produce some examples mentioned above?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
6
$\begingroup$

There are 154108311168 tournaments on 12 vertices and you can make them with the tool gentourng that comes with nauty.

The number of connected digraphs on 10 vertices is more than 10^20, which is impossibly many. That's if you allow 2-cycles; otherwise the number is "only" about 10^15 and you can make them if you don't mind spending weeks of computer time.

The number of directed bipartite graphs on 9 vertices is 414967973 and if you don't allow 2-cycles there are only 1514031 (including disconnected). You can make them in seconds using geng+watercluster2 in the nauty package.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you so much for the quick reply. Actually, I'm a user of your Combinatorial Data. Thank you again for making all these wonderful data publicly visible. But there are only a few classes of digraphs available in this dataset. Recently, I need to generate all orientations (2-cycles are allowed) of some undirected graphs. For a graph with 15 edges, my method gives $3^{15}$ results. But I want to delete isomorphic graphs, which is quite time-consuming. $\endgroup$
    – hxiao
    Apr 20, 2016 at 12:40
  • $\begingroup$ I heard about nauty before, but haven't looked into it. I will take a good look and see what I can do. $\endgroup$
    – hxiao
    Apr 20, 2016 at 13:07
  • 1
    $\begingroup$ What you need is the utility "directg" in the nauty package - this orients a graph and removes duplicates. $\endgroup$
    – Gordon Royle
    Apr 20, 2016 at 13:13
  • 2
    $\begingroup$ And also $3^{15} = 14348907$ which is not a very large set to process. $\endgroup$
    – Gordon Royle
    Apr 20, 2016 at 14:10
  • 2
    $\begingroup$ @Han - writing a small script in your preferred language is your best option. Rather than guess the target format and write dozens of output routines all of which need debugging and updating, the UNIX philosophy is that the program should do one thing - orient graphs - really well, and any format changing should be left to the users. $\endgroup$
    – Gordon Royle
    Apr 20, 2016 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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