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)?
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)?
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))
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 +0100
Seen: 261 times
Last updated: Sep 16 '23