Is there an algorightm generating all digraphs with $n$ edges up to isomorphism whose underlying graph is not a tree? For example, for $n=3$, there are only two such digraphs, representable as $\text{Digraph}({[1,2],[2,3],[3,1]})$ and $\text{Digraph}({[1,2],[2,3],[1,3]})$.
2
-
$\begingroup$ Yes. 1) Generate all labeled digraphs whose underlying graph is not a tree. 2) Look for isomorphism, and remove copies. Both these steps can be done in finite time. You probably want to add more details to your question. $\endgroup$– Per AlexanderssonCommented Mar 25, 2019 at 21:43
-
$\begingroup$ @PerAlexandersson Okay I guess that's the best algorithm I can do. There are bruce force algorithms for both generating all digraphs with n edges and identifying the isomorphic digraphs. Thanks! $\endgroup$– David WangCommented Mar 25, 2019 at 22:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
There are algorithms that will directly enumerate non-isomorphic graphs, without duplicates, e.g. geng available as a part of nauty and it also have procedures to generate non-isomorphic digraphs with a fixed underlying graph,
one is directg (see chapter 15 of nauty manual)
Edit: nauty also have various convenient interfaces, e.g. from Python (SageMath and pynauty)
answered Mar 25, 2019 at 22:29