Graph Question

[Martin Albrecht]

If I create a Graph like this:

g = Graph(dict())

and show it with show(g), is it plotted using the spring algorithm of
NetworkX? My Graph looks kind of randomly layouted, while it should be well
structured. I converted an ideal basis of a block cipher to a graph where the
variables are the nodes and the equations result in edges, and thus it should
reflect the rounds of that cipher, I guess.

Martin

PS: Very cool, to have Graph theory in SAGE!
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_icq: 177334829
_jab: martinr...@jabber.ccc.de

[Robert Miller]

Martin,

You're right. The default layout used is the spring algorithm from
NetworkX. If you want to use your own position, make a dictionary with
vertex labels as keys and tuples for coordinates as entries. Then feed
this dictionary in to show as pos=...

For example, if you look at the code in graph_database.py, there are
many examples of custom layouts being used.

I'm not very familiar with ciphers; is this something that is done
often? Would it be useful to have a general function to do this?

[William Stein]

On Sat, 16 Dec 2006 16:39:38 -0800, Robert Miller <rlmil...@gmail.com> wrote:

>
> Martin,
>
> You're right. The default layout used is the spring algorithm from
> NetworkX. If you want to use your own position, make a dictionary with
> vertex labels as keys and tuples for coordinates as entries. Then feed
> this dictionary in to show as pos=...

Could you add something to the discussion about how to fine-tune the
spring layout algorithm? I.e., how to improve the quality of the layout,
etc.? I bet that's what he wants.

[Martin Albrecht]

On Sunday 17 December 2006 01:46, William Stein wrote:
> On Sat, 16 Dec 2006 16:39:38 -0800, Robert Miller <rlmil...@gmail.com>
wrote:
> > Martin,
> >
> > You're right. The default layout used is the spring algorithm from
> > NetworkX. If you want to use your own position, make a dictionary with
> > vertex labels as keys and tuples for coordinates as entries. Then feed
> > this dictionary in to show as pos=...
>
> Could you add something to the discussion about how to fine-tune the
> spring layout algorithm? I.e., how to improve the quality of the layout,
> etc.? I bet that's what he wants.

Yes, let me explain a bit: I'm representing block ciphers as quadratic
equation systems. These block ciphers have rounds, i.e. they repeat the same
operation $n$ times. The input of round $i+1$ is the output of round $i$. The
input of round 0 is the plaintext and the output of round $n-1$ is the
ciphertext. So, the equation systems produced by them are pretty clearly
structured. Variables from round 1 will probably not appear in the same
equations as variables from e.g. round 5. I translated the variables to nodes
and connected them if they appear in the same equation.

I was hoping the resulting graph would represent the structure of the equation
system well, so an automatic layout tweak would be appreciated. It's more
like a nice visualization to put in a presentation and I haven't seen it done
before, so it's absolutely not high priority or so.

Martin

[Robert Miller]

Martin,

The short answer is that the graph code in sage right now doesn't have
any options to tweak the automatic spring layout. In other words, my
wrapping isn't done. You can, however, reach through to NetworkX as in
the following example. Suppose I have some graph G:

G = graphs.RandomGNP(27,.4)

You can recover the NetworkX graph,

N = G.networkx_graph()

and utilize NetworkX's spring layout function directly:

import networkx
from sage.plot.plot import Graphics, GraphicPrimitive_NetworkXGraph
P = networkx.drawing.spring_layout(N, iterations=20, dim=2)
NGP = GraphicPrimitive_NetworkXGraph(graph=N, pos=P)
g = Graphics()
g.append(NGP)
g.show(axes=False)

Note that the default is iterations=50. The only real tweaking NetworkX
lets you do is in the number of iterations (you can also increase
dimension, but then you have to project back down to 2...) If you're
looking for formal symmetries, you might try

networkx.drawing.spectral_layout(G, dim=2, vpos=None, iterations=1000,
eps=0.001)

It uses the smallest eigenvectors from the Laplacian adjacency matrix,
which is the normal adjacency matrix with (negative degree) along the
diagonal. It may reveal the more algebraic aspects you're looking for.
This also has a few options to tweak (the values above are all
defaults).

I'll add many tweaks for graph plots in the future. One tweak will be
allowing someone to specify how many iterations the spring layout
should go, and another will be using different layout methods. Is there
anything else specific you would like them to do?

[Martin Albrecht]

On Sunday 17 December 2006 22:35, Robert Miller wrote:
> Martin,
>
> The short answer is that the graph code in sage right now doesn't have
> any options to tweak the automatic spring layout. In other words, my
> wrapping isn't done. You can, however, reach through to NetworkX as in
> the following example. Suppose I have some graph G:
>
> G = graphs.RandomGNP(27,.4)
>
> You can recover the NetworkX graph,
>
> N = G.networkx_graph()
>
> and utilize NetworkX's spring layout function directly:
>
> import networkx
> from sage.plot.plot import Graphics, GraphicPrimitive_NetworkXGraph
> P = networkx.drawing.spring_layout(N, iterations=20, dim=2)
> NGP = GraphicPrimitive_NetworkXGraph(graph=N, pos=P)
> g = Graphics()
> g.append(NGP)
> g.show(axes=False)
>
> Note that the default is iterations=50. The only real tweaking NetworkX
> lets you do is in the number of iterations (you can also increase
> dimension, but then you have to project back down to 2...) If you're
> looking for formal symmetries, you might try
>
> networkx.drawing.spectral_layout(G, dim=2, vpos=None, iterations=1000,
> eps=0.001)

This worked better (Though, there is no eps parameter). I sticked to 200-500
iterations as these layouts take pretty long to compute already. If anybody
wants to look at them:

http://sage.math.washington.edu/home/malb/graphics/ctc_ideal_basis_graphs/

Thanks,

[Robert Miller]

Martin,

Could we go back to your question on graph plotting for a moment? I'm
starting to implement more control over the appearance, and I was
wondering if you could give your input on this list:

Graph plot todos
node size
node color
node borders
other graphics objects as nodes (such as functions or who knows)
fix arrows on directed graphs (this is actually what NetworkX does)
font options for labels (does this matter?)
bounding coordinates
functions for setting positions
tachyon plotter

Robert M

[Martin Albrecht]

Hi Robert,

those look mainly like pure appearance options, which all will be great. If
you ask about my taste then I would say I really like the top graph on
https://networkx.lanl.gov/wiki .

Any chance the spring layout computation will be faster? Is it written in
Python or Pyrex/SageX/C ?

Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb

_jab: martinr...@jabber.ccc.de

[Robert Miller]

As a matter of fact, it's written in Python, and implementing it in
SageX will be my first venture in into the land of pyrex.