Ask Your Question
1

get graph combinatorial embedding from position of vertices

asked 2014-01-13 12:48:38 +0200

mf gravatar image

Lets say I have a graph and set positions for the veritces. Is it somehow possible to get the combinatorial embedding? I tried the following:

sage: H = Graph({0:[1,3,5,4],1:[0,2,3],2:[1,4,5],3:[0,1],4:[0,2,5],5:[0,2,4]})
sage: H.set_pos({0:[213,281],1:[93,171],2:[189,35],3:[35,315],4:[315,146],5:[197,158]})  
sage: H.get_embedding()

This gives me an ValueError: Graph on 6 vertices has been modified and the embedding is no longer valid. What I expect to get is a list like the one I used to define H, but with the neighbors ordered clockwise.

Imgur

edit retag flag offensive close merge delete

3 Answers

Sort by ยป oldest newest most voted
5

answered 2014-01-14 04:53:21 +0200

Nathann gravatar image

updated 2014-01-14 04:53:54 +0200

Hmmmmm.. Well it seems that obtaining the embedding from the positions is notimplemented yet (and it should not be complicated, so you are welcome to add it if you need it !), but you can obtain an embedding from a call to is_planar. This will give you a planar embedding, though it will use its own layout for the vertices of your graph.

sage: g=graphs.IcosahedralGraph()
sage: g.get_embedding()
...
ValueError: Icosahedron has been modified and the embedding is no longer valid
sage: g.is_planar(set_embedding=True)
True
sage: g.get_embedding()
{0: [1, 5, 11, 7, 8],
 1: [8, 2, 6, 5, 0],
 2: [8, 9, 3, 6, 1],
 3: [2, 9, 10, 4, 6],
 4: [3, 10, 11, 5, 6],
 5: [0, 1, 6, 4, 11],
 6: [1, 2, 3, 4, 5],
 7: [0, 11, 10, 9, 8],
 8: [0, 7, 9, 2, 1],
 9: [8, 7, 10, 3, 2],
 10: [9, 7, 11, 4, 3],
 11: [0, 5, 4, 10, 7]}
edit flag offensive delete link more
0

answered 2014-01-17 15:33:30 +0200

mf gravatar image

updated 2014-01-17 16:04:02 +0200

So I wrote a few lines that do what I wanted:

def angle(x):
    return arccos(sign(x[1])*(x[0])/(x.norm()))
def get_rotation_system(H):
    if not(H.get_pos()):
        return 'no positions known'
    rotation_system=dict()
    for v in H.vertex_iterator():
        anglelist=[[angle(vector(H.get_pos()[w])-(vector(H.get_pos()[v]))),w] for w in H[v]]
        anglelist.sort()
        rotation_system[v]=[w for a,w in anglelist]
    H.set_embedding(rotation_system)

This can be used as follows:

G = Graph({0:[1,5,3,4],1:[2,0,3],2:[1,4,5],3:[0,1],4:[0,2,5],5:[0,2,4]})
G.set_pos({0:[213,281],1:[93,171],2:[189,35],3:[35,315],4:[315,146],5:[197,158]})
get_rotation_system(G)
G.show(layout='planar')

Anyhow I think this would be a handy function to have, especially in combination with the graph editor. I will open a trac ticket soon.

edit flag offensive delete link more
0

answered 2020-11-10 09:09:34 +0200

Ingrid gravatar image

I am also having trouble with set_embedding. My Graph does not have a unique planar embedding, and I would like to set the embedding to a different one from that found by sage.

sage: D3half2=Graph({0:{1:'x2', 2:'x8', 3:'x9', 4:'x5'}, 1:{2:'x3'}, 2:{3:'x6', 4:'x4'}, 3:{4:'x12', 5:'x10'}, 4:{5:'x11'}})

sage: D3half2.is_planar()

True

sage:D3half2.is_planar(set_embedding=True) D3half2.set_embedding({0:{1, 4, 3, 2}, 1:{2, 0}, 2:{1, 0, 3, 4}, 3:{2, 0, 4, 5}, 4:{2, 5, 3, 0}})

ValueError Traceback (most recent call last) <ipython-input-11-78d1277ebcd7> in <module>() ----> 1 D3half2.set_embedding({Integer(0):{Integer(1), Integer(4), Integer(3), Integer(2)}, Integer(1):{Integer(2), Integer(0)}, Integer(2):{Integer(1), Integer(0), Integer(3), Integer(4)}, Integer(3):{Integer(2), Integer(0), Integer(4), Integer(5)}, Integer(4):{Integer(2), Integer(5), Integer(3), Integer(0)}})

/opt/sagemath-9.1/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in set_embedding(self, embedding) 2501 ValueError: vertices in ['s'] from the embedding do not belong to the graph 2502 """ -> 2503 self._check_embedding_validity(embedding, boolean=False) 2504 self._embedding = embedding 2505

/opt/sagemath-9.1/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in _check_embedding_validity(self, embedding, boolean) 2589 raise ValueError("vertices in {} from the embedding do not belong to the graph".format(list(set(embedding).difference(self)))) 2590 else: -> 2591 raise ValueError("vertices in {} have no corresponding entry in the embedding".format(list(set(self).difference(embedding)))) 2592 2593 if self._directed:

ValueError: vertices in [5] have no corresponding entry in the embedding

Thanks for any help!!!!

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2014-01-13 12:48:38 +0200

Seen: 566 times

Last updated: Jan 18 '14