# Digraphs with Sage

Is there an easy way to obtain with Sage the following for a given n:

All connected Digraphs (up to isomorphism) with n points whose underlying undirected graph is a tree (simply-laced)?

Digraphs with Sage

Is there an easy way to obtain with Sage the following for a given n:

All connected Digraphs (up to isomorphism) with n points whose underlying undirected graph is a tree (simply-laced)?

add a comment

1

You can use `graphs.trees(n)`

to enumerate undirected trees of order `n`

.

```
sage: for g in graphs.trees(1):
....: print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 1, m = 0, E = []
sage: for g in graphs.trees(2):
....: print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 2, m = 1, E = [(0, 1)]
sage: for g in graphs.trees(3):
....: print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 3, m = 2, E = [(0, 1), (0, 2)]
sage: for g in graphs.trees(4):
....: print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 4, m = 3, E = [(0, 1), (0, 3), (1, 2)]
n = 4, m = 3, E = [(0, 1), (0, 2), (0, 3)]
sage: for g in graphs.trees(5):
....: print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 5, m = 4, E = [(0, 1), (0, 3), (1, 2), (3, 4)]
n = 5, m = 4, E = [(0, 1), (0, 3), (0, 4), (1, 2)]
n = 5, m = 4, E = [(0, 1), (0, 2), (0, 3), (0, 4)]
```

Then, for a given tree `g`

you can use `digraphs.nauty_directg(g, "-o")`

to enumerate its orientations.

```
sage: for g in graphs.trees(3):
....: print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: for h in digraphs.nauty_directg(g, "-o"):
....: print(f"\t{h.edges(labels=False)}")
n = 3, m = 2, E = [(0, 1), (0, 2)]
[(0, 1), (0, 2)]
[(0, 1), (2, 0)]
[(1, 0), (2, 0)]
sage: for g in graphs.trees(4):
....: print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: for h in digraphs.nauty_directg(g, "-o"):
....: print(f"\t{h.edges(labels=False)}")
n = 4, m = 3, E = [(0, 1), (0, 3), (1, 2)]
[(0, 1), (0, 3), (1, 2)]
[(0, 1), (0, 3), (2, 1)]
[(0, 1), (1, 2), (3, 0)]
[(0, 1), (2, 1), (3, 0)]
n = 4, m = 3, E = [(0, 1), (0, 2), (0, 3)]
[(0, 1), (0, 2), (0, 3)]
[(0, 1), (0, 2), (3, 0)]
[(0, 1), (2, 0), (3, 0)]
[(1, 0), (2, 0), (3, 0)]
```

Finally, you can combine that as follows:

```
sage: for g in digraphs.nauty_directg(graphs.trees(1), "-o"):
....: print(g.edges(labels=False))
[]
sage: for g in digraphs.nauty_directg(graphs.trees(2), "-o"):
....: print(g.edges(labels=False))
[(0, 1)]
sage: for g in digraphs.nauty_directg(graphs.trees(3), "-o"):
....: print(g.edges(labels=False))
[(0, 1), (0, 2)]
[(0, 1), (2, 0)]
[(1, 0), (2, 0)]
sage: for g in digraphs.nauty_directg(graphs.trees(4), "-o"):
....: print(g.edges(labels=False))
[(0, 1), (0, 3), (1, 2)]
[(0, 1), (0, 3), (2, 1)]
[(0, 1), (1, 2), (3, 0)]
[(0, 1), (2, 1), (3, 0)]
[(0, 1), (0, 2), (0, 3)]
[(0, 1), (0, 2), (3, 0)]
[(0, 1), (2, 0), (3, 0)]
[(1, 0), (2, 0), (3, 0)]
sage: for g in digraphs.nauty_directg(graphs.trees(5), "-o"):
....: print(g.edges(labels=False))
[(0, 1), (0, 3), (1, 2), (3, 4)]
[(0, 1), (0, 3), (1, 2), (4, 3)]
[(0, 1), (0, 3), (2, 1), (4, 3)]
[(0, 1), (1, 2), (3, 0), (3, 4)]
[(0, 1), (1, 2), (3, 0), (4, 3)]
[(0, 1), (2, 1), (3, 0), (3, 4)]
[(0, 1), (2, 1), (3, 0), (4, 3)]
[(1, 0), (1, 2), (3, 0), (3, 4)]
[(1, 0), (1, 2), (3, 0), (4, 3)]
[(1, 0), (2, 1), (3, 0), (4, 3)]
[(0, 1), (0, 3), (0, 4), (1, 2)]
[(0, 1), (0, 3), (0, 4), (2, 1)]
[(0, 1), (0, 3), (1, 2), (4, 0)]
[(0, 1), (0, 3), (2, 1), (4, 0)]
[(0, 1), (1, 2), (3, 0), (4, 0)]
[(0, 1), (2, 1), (3, 0), (4, 0)]
[(0, 3), (0, 4), (1, 0), (1, 2)]
[(0, 3), (0, 4), (1, 0), (2, 1)]
[(0, 3), (1, 0), (1, 2), (4, 0)]
[(0, 3), (1, 0), (2, 1), (4, 0)]
[(1, 0), (1, 2), (3, 0), (4, 0)]
[(1, 0), (2, 1), (3, 0), (4, 0)]
[(0, 1), (0, 2), (0, 3), (0, 4)]
[(0, 1), (0, 2), (0, 3), (4, 0)]
[(0, 1), (0, 2), (3, 0), (4, 0)]
[(0, 1), (2, 0), (3, 0), (4, 0)]
[(1, 0), (2, 0), (3, 0), (4, 0)]
```

You can at least use `graphs.nauty_gentreeg("5 -D4")`

to enumerate trees of order 5 with degree at most 4 and then filter the generated digraphs.

```
sage: for g in digraphs.nauty_directg(graphs.nauty_gentreeg("5 -D4"), "-o"):
....: if max(g.in_degree()) <= 2 and max(g.out_degree()) <= 2:
....: print(g.edges(labels=False))
```

0

I think I found another solution using Posets:

```
n=4
P=Posets(n)
U=[p for p in P if p.is_connected() and ((p.hasse_diagram()).to_undirected()).is_tree()]
UU=[p for p in U if max((p.hasse_diagram()).out_degree_sequence())<=2 and max((p.hasse_diagram()).in_degree_sequence())<=2]
[display(t) for t in UU]
display(len(U))
display(len(UU))
```

The list U answers the question (I hope) and the list UU is a sublist of U with all indegrees and outdegrees at most 2.

Please start posting anonymously - your entry will be published after you log in or create a new account.

Asked: ** 2023-09-15 20:49:14 +0200 **

Seen: **233 times**

Last updated: **Sep 16 '23**

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.