Ask Your Question

Plot graph by distance from a given vertex

asked 2014-10-24 16:35:38 +0200

kcrisman gravatar image

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 flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted

answered 2014-10-24 21:01:16 +0200

FrédéricC gravatar image

updated 2014-10-29 20:21:52 +0200

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

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:
                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)
    return G.plot() + t.plot(edge_color='red')
edit flag offensive delete link 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.

kcrisman gravatar imagekcrisman ( 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.

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

answered 2014-10-29 18:51:28 +0200

kcrisman gravatar image

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  # 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.

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

1 follower


Asked: 2014-10-24 16:35:38 +0200

Seen: 1,002 times

Last updated: Oct 29 '14