ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 29 Oct 2014 18:51:28 +0100Plot graph by distance from a given vertexhttps://ask.sagemath.org/question/24623/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.)Fri, 24 Oct 2014 16:35:38 +0200https://ask.sagemath.org/question/24623/plot-graph-by-distance-from-a-given-vertex/Answer by kcrisman for <p>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.</p>
<p>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.)</p>
https://ask.sagemath.org/question/24623/plot-graph-by-distance-from-a-given-vertex/?answer=24687#post-id-24687This "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.
Wed, 29 Oct 2014 18:51:28 +0100https://ask.sagemath.org/question/24623/plot-graph-by-distance-from-a-given-vertex/?answer=24687#post-id-24687Answer by FrédéricC for <p>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.</p>
<p>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.)</p>
https://ask.sagemath.org/question/24623/plot-graph-by-distance-from-a-given-vertex/?answer=24627#post-id-24627Let 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
seen.add(u)
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')
Fri, 24 Oct 2014 21:01:16 +0200https://ask.sagemath.org/question/24623/plot-graph-by-distance-from-a-given-vertex/?answer=24627#post-id-24627Comment by kcrisman for <p>Let me try something.</p>
<pre><code>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()
</code></pre>
<p>Oh, damn, this does not work. Maybe some variation could do the job ?</p>
<p><strong>EDIT</strong>: here is a refined proposal, using a better spanning tree.</p>
<pre><code>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
seen.add(u)
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')
</code></pre>
https://ask.sagemath.org/question/24623/plot-graph-by-distance-from-a-given-vertex/?comment=24629#post-id-24629On 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.Fri, 24 Oct 2014 22:21:49 +0200https://ask.sagemath.org/question/24623/plot-graph-by-distance-from-a-given-vertex/?comment=24629#post-id-24629Comment by kcrisman for <p>Let me try something.</p>
<pre><code>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()
</code></pre>
<p>Oh, damn, this does not work. Maybe some variation could do the job ?</p>
<p><strong>EDIT</strong>: here is a refined proposal, using a better spanning tree.</p>
<pre><code>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
seen.add(u)
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')
</code></pre>
https://ask.sagemath.org/question/24623/plot-graph-by-distance-from-a-given-vertex/?comment=24628#post-id-24628Hmm, 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.Fri, 24 Oct 2014 22:21:00 +0200https://ask.sagemath.org/question/24623/plot-graph-by-distance-from-a-given-vertex/?comment=24628#post-id-24628