#7004: [with patch, needs work] Refactor the graph layout code, and add
interface
with graphviz
---------------------------------+------------------------------------------
Reporter: nthiery | Owner: nthiery
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.3.3
Component: graph theory | Keywords: graph layout, graphviz, acyclic
Author: Nicolas M. Thiéry | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
---------------------------------+------------------------------------------
Changes (by nthiery):
* status: needs_work => needs_review
* upstream: => N/A
Old description:
> Experimental patch on:
> http://combinat.sagemath.org/hgwebdir.cgi/patches/file/tip/trac_7004
> -graphviz-nt.patch
>
> This also requires graphviz and a dot2tex spkg available from:
>
> http://sage.math.washington.edu/home/nthiery/dot2tex-2.8.7.spkg
>
> From the patch description:
>
> - Refactors the graph layout code, with:
>
> - A new main graph.layout() method, to be called by plot, latex, ...
> - Many layout methods, like graph._layout_circular()
> - Extends the graphviz_string method (latex labels)
> - Define a new layout method ._layout_acyclic() implemented by
> calling dot2tex and graphviz
> - Implement an alternative implementation of latex for graphs
> by delegating all the work to dot2tex (GraphLatex.dot2tex_picture)
> - Slightly simplifies the handling of default values for
> graph.latex_options
>
> - Makes some fixes to the poset code:
> - __repr__ -> _repr_
> - _latex_ by calling latex on the internal element
>
> TODO:
>
> - make layout(layout="bla") automatically lookup _layout_bla, so that
> subclasses can define new layout algorithms (e.g. acyclic for directed
> graphs).
>
> - Add an optional default_layout method that subclasses could
> override (like for the Petersen graph, ...). This would be better
> for them than to systematically construct the layout at
> construction time.
>
> - Move the layout code out of posets into a _layout_acyclic_spring in
> directed graphs, and have _layout_acyclic call it if dot2tex is not
> available.
>
> - Refactor the remaining layout functions (planar, ...) as above
>
> - Double check all the logic to make sure it is backward compatible
>
> - A lot of code is doing things very similar to dot2tex. Maybe things
> could be merged.
>
> - Finish to doctest everything
>
> - Implement the different options for both latex constructions
>
> - Add appropriate # optional comments
>
> - Make dot2tex.spkg into an optional sage package
New description:
Latest version of the patch on:
http://combinat.sagemath.org/hgwebdir.cgi/patches/file/tip/trac_7004
-graphviz-nt.patch
This also requires graphviz and a dot2tex spkg available from:
http://sage.math.washington.edu/home/nthiery/dot2tex-2.8.7.spkg
From the patch description:
- Refactors the graph layout code:
- Add a new main graph.layout() method, to be called by plot,
plot3d, latex, graph_editor, ...
- The various graph layout algorithms spread over the graph code
are systematically reorganized into as many layout methods that
can be called from layout():
- graph.layout_circular()
- graph.layout_spring()
- graph.layout_tree()
- graph.layout_ranked()
- graph.layout_acyclic()
- graph.layout_planar()
- graph.layout_default()
- Extends the graphviz_string method (latex labels)
and refactors its logic to make it simpler for subclasses
- Slightly simplifies the handling of default values for
graph.latex_options
- Visible user change: graph_editor, plot3d, ... all accept the
same layout options.
- Implements an interface to dot2tex/graphviz:
- Define a new layout method .layout_graphviz() implemented by
calling dot2tex and graphviz
- Implement an alternative implementation of latex for graphs
by delegating all the work to dot2tex (GraphLatex.dot2tex_picture)
- Makes some fixes to the poset code:
- __repr__ -> _repr_
- _latex_ by calling latex on the internal element
- Moved the level_sets method from HasseDiagram to DirectedGraph
Reimplemented to support properly non acyclic graph. It should be
quite faster (it just goes through the graph, without modifying it).
TODO, for this ticket or a later one:
- Double check all the logic to make sure it is backward compatible
- graph_editor was using iterations=1000 as default. Was there a
reason? If yes, do we want to set this up as default value for all
layouts?
- What should be the default layout algorithm?
- Planar layout when the graph is planar
- acyclic if acyclic
- spring otherwise
- The spring option for graded layouts does not work. Could someone
please debug this?
sage: G = posets.IntegerPartitions(3).hasse_diagram()
sage: G.plot(layout="acyclic_dummy")
sage: G.plot(layout="acyclic_dummy", spring = True)
- Find a better name for acyclic_dummy. Once the spring layout will
be functional, this could be set to the default value, and the
layout renamed to acyclic_spring.
- Choose a good option name for the direction of growth of acyclic
layout, an a good default value. Merge this with the option for
tree layout (tree_orientation).
orientation = "up" (as for tree) ?
rankdir = "BT" (as in graphviz)?
- A lot of code is doing things very similar to dot2tex. Maybe things
could be merged.
- Implement the various options for both latex constructions (tikz or
dot2tex)
- Implement the default layout of standard graphs using a
default_layout method rather than at construction time.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7004#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
