#7004: Refactor the graph layout code, and add interface with graphviz
---------------------------------+------------------------------------------
Reporter: nthiery | Owner: nthiery
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.4
Component: graph theory | Keywords: graph layout, graphviz, acyclic
Author: Nicolas M. Thiéry | Upstream: N/A
Reviewer: vdelecroix | Merged:
Work_issues: |
---------------------------------+------------------------------------------
Description changed by nthiery:
Old description:
> Latest version of the patch on:
> http://combinat.sagemath.org/hgwebdir.cgi/patches/file/tip/trac_7004
> -graphviz-nt.patch
>
> Using the graphviz interface 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:
>
> * Fix a strange doctest failure that occurs when calling graphviz. Try
> sage -t bla.py, with bla.py a file containing just:
> {{{
> """
> EXAMPLES::
>
> sage: import dot2tex
> sage: x = dot2tex.dot2tex('graph{})
> sage: 1
> 1
> """
> }}}
>
> * Double check all the logic to make sure it is backward compatible
> - Done for the latex part (Rob)
>
> * What should be the default layout algorithm?
> * Planar layout when the graph is planar (not yet: the planar
> layout is not that nice looking; postponed for later when
> planar+spring will be implemented)
> * acyclic if acyclic
> * spring otherwise
>
> * The spring option for ranked layouts does not work nicely:
>
> {{{
> sage: G = posets.IntegerPartitions(5).hasse_diagram()
> sage: G = DiGraph({1:(2,3), 2:[4], 3:[4]}) # alternative
> example
> sage: G.plot(layout="acyclic_dummy", spring = True)
> }}}
>
> to be compared with:
>
> {{{
> sage: G.plot(layout="acyclic_dummy")
> sage: G.plot(layout="spring")
> }}}
>
> Thinking twice about it, this seems to be inherent. See the comments
> in the code.
>
> * 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.
New description:
Latest version of the patch on:
http://combinat.sagemath.org/hgwebdir.cgi/patches/file/tip/trac_7004
-graphviz-nt.patch
Using the graphviz interface 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
- Done for the latex part (Rob)
* What should be the default layout algorithm?
* Planar layout when the graph is planar (not yet: the planar
layout is not that nice looking; postponed for later when
planar+spring will be implemented)
* acyclic if acyclic
* spring otherwise
* The spring option for ranked layouts does not work nicely:
{{{
sage: G = posets.IntegerPartitions(5).hasse_diagram()
sage: G = DiGraph({1:(2,3), 2:[4], 3:[4]}) # alternative
example
sage: G.plot(layout="acyclic_dummy", spring = True)
}}}
to be compared with:
{{{
sage: G.plot(layout="acyclic_dummy")
sage: G.plot(layout="spring")
}}}
Thinking twice about it, this seems to be inherent. See the comments in
the code.
* 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:23>
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.
