# Plot graph by distance from a given vertex

I have some graphs I'd like to be able to plot in such a way that I can set a "top" vertex $v$, and then make all vertices distance 1 from $v$ be maybe 1 cm/in lower down, the ones distance 2 away be twice and far, and so forth. As it happens, each such set of vertices have no edges between them, so this will look just like a Hasse diagram/lattice/whatever and be meaningful.

But I've racked my head and lambda functions and whatnot to get this to work, and every graph plotting option and use of distance seems to go awry. I need help. I bet someone else does a lot more graph visualization than I do and will have an easy answer. (I suppose as a last resort I could use a dictionary for the locations and concoct info for that, but I am hoping it will be something I can do without having to construct the graph first.)

edit retag close merge delete

Sort by » oldest newest most voted

Let me try something.

sage: g = graphs.PetersenGraph()
sage: t = Graph(g.min_spanning_tree(starting_vertex=1))
sage: g.set_pos(t.layout_tree(tree_root=1))
sage: g.show()


Oh, damn, this does not work. Maybe some variation could do the job ?

EDIT: here is a refined proposal, using a better spanning tree.

def BFS_custom(G, v):
"""
Perform a BFS and return edges.

Here G is a graph and v a vertex of G.

(Code by Nathann Cohen)
"""
seen = set([v] + G.neighbors(v))
next_layer = [(v, u) for u in G.neighbors(v)]
while next_layer:
for e in next_layer:
yield e
next_next_layer = []
for _, v in next_layer:
for u in G.neighbors(v):
if u in seen:
continue
next_next_layer.append((v, u))
next_layer = next_next_layer

def plot_by_distance(G, v):
"""
Plot the graph G using distance from vertex v as height function.
"""
t = Graph([e for e in BFS_custom(G, v)])
pos = t.layout_tree(tree_root=v)
G.set_pos(pos)
t.set_pos(pos)
return G.plot() + t.plot(edge_color='red')

more

Hmm, this is a new idea to me, but even with my even more regular examples this depends too much on the spanning tree. I mean, the most straightforward at this point would be to create a position dict based on distances, but I'm too lazy to do it as I don't need it *that* bad ... yet.

( 2014-10-24 22:21:00 +0200 )edit

On another note, the tree layout should definitely be configurable for *visual* distance, say if you have big vertices or something. Doesn't seem to be, though.

( 2014-10-24 22:21:49 +0200 )edit

This "works", for some value of "works".

G = my_cool_graph
u = my_special_vertex
HL = []  # height list
for h in range(G.diameter()+1): # for height in the range
HL.append([(v,h) for v in G if G.distance(u,v)==h])
# enumerate makes this work, but don't flatten the whole thing
HL = flatten([list(enumerate(hl)) for hl in HL],max_level=1)
HL = [(v[0], (i,3*v[1])) for i, v in HL] # rearrange in an ugly way and make the heights visible
HD = dict(HL) # need a dict to make a position dict
G.set_pos(HD) # here we go
G.show(figsize=15)  # acceptable but needs centering of each row to be really nice


Do you think this would be worth adding as an option for positioning or something? It seems so ugly to me.

more