Digraphs with Sage

digraph

asked 2023-09-15 20:49:14 +0100

klaaa
691 ●4 ●17 ●41

updated 2023-09-16 09:52:15 +0100

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)?

edit retag flag offensive close merge delete

add a comment

1

answered 2023-09-16 10:25:09 +0100

David Coudert
766 ●12 ●20 http://www-sop.inria.f...

updated 2023-09-16 10:29:40 +0100

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)]

edit flag offensive delete link

Comments

Thank you very much! Is the an easy way to impose the additional restriction that all indegrees and outdegrees of a vertex should be at most 2?

klaaa ( 2023-09-16 14:40:47 +0100 )edit

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))

David Coudert ( 2023-09-17 11:20:38 +0100 )edit

add a comment

0

answered 2023-09-16 14:52:49 +0100

klaaa
691 ●4 ●17 ●41

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.

edit flag offensive delete link

add a comment

Digraphs with Sage

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Digraphs with Sage edit

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Digraphs with Sage