#7004 closed enhancement (fixed)
Refactor the graph layout code, and add interface with graphviz
Reported by: | nthiery | Owned by: | nthiery |
---|---|---|---|
Priority: | major | Milestone: | sage-4.4.1 |
Component: | graph theory | Keywords: | graph layout, graphviz, acyclic |
Cc: | sage-combinat, ncohen, rlm | Merged in: | sage-4.4.1.alpha2 |
Authors: | Nicolas M. Thiéry | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Latest version of the patch on: http://combinat.sagemath.org/hgwebdir.cgi/patches/file/tip/trac_7004-graphviz-nt.patch and followups
Using the graphviz interface requires graphviz to be installed on the machine, as well as a dot2tex spkg which can be installed with:
sage -f http://sage.math.washington.edu/home/nthiery/dot2tex-2.8.7-dev.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.
Attachments (2)
Change History (36)
comment:1 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to assigned
- Summary changed from [with patch] Refactor the graph layout code, and add interface with graphviz for acyclic layout to [with patch, needs work] Refactor the graph layout code, and add interface with graphviz for acyclic layout
comment:2 Changed 9 years ago by
- Description modified (diff)
comment:3 Changed 9 years ago by
- Description modified (diff)
comment:4 Changed 9 years ago by
- Description modified (diff)
comment:5 Changed 9 years ago by
- Description modified (diff)
- Report Upstream set to N/A
- Status changed from needs_work to needs_review
- Summary changed from [with patch, needs work] Refactor the graph layout code, and add interface with graphviz for acyclic layout to [with patch, needs work] Refactor the graph layout code, and add interface with graphviz
comment:6 Changed 9 years ago by
- Summary changed from [with patch, needs work] Refactor the graph layout code, and add interface with graphviz to Refactor the graph layout code, and add interface with graphviz
comment:7 Changed 9 years ago by
- Description modified (diff)
comment:8 Changed 9 years ago by
- Description modified (diff)
comment:9 Changed 9 years ago by
- Cc ncohen added
comment:10 Changed 9 years ago by
I tried reproducing this:
G = posets.IntegerPartitions(3).hasse_diagram() G.plot(layout="acyclic_dummy", spring = True)
But I got:
AttributeError Traceback (most recent call last) /Users/rlmill/sage-4.3.2/devel/sage-main/<ipython console> in <module>() /Users/rlmill/sage-4.3.2/local/lib/python2.6/site-packages/sage/plot/misc.pyc in wrapper(*args, **kwds) 136 options['__original_opts'] = kwds 137 options.update(kwds) --> 138 return func(*args, **options) 139 140 /Users/rlmill/sage-4.3.2/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in plot(self, **options) 9137 """ 9138 from sage.graphs.graph_plot import GraphPlot -> 9139 return GraphPlot(graph=self, options=options).plot() 9140 9141 def show(self, **kwds): /Users/rlmill/sage-4.3.2/local/lib/python2.6/site-packages/sage/graphs/graph_plot.pyc in __init__(self, graph, options) 83 self._graph = graph 84 self._options = options ---> 85 self.set_pos() 86 self._arcs = self._graph.has_multiple_edges(to_undirected=True) 87 self._loops = self._graph.has_loops() /Users/rlmill/sage-4.3.2/local/lib/python2.6/site-packages/sage/graphs/graph_plot.pyc in set_pos(self) 183 self._pos = pos 184 --> 185 if not self._pos: 186 self._pos = generic_graph_pyx.spring_layout_fast(self._graph, iterations=self._options['iterations'], height=(self._options['heights'] is not None)) 187 AttributeError: 'GraphPlot' object has no attribute '_pos'
Looks like the first if of set_pos
needs an else
clause. But this wasn't the problem you indicated.
comment:11 Changed 9 years ago by
I tried this again, and now I am getting a different (!) error:
AttributeError Traceback (most recent call last) /Users/rlmill/sage-4.3.2/devel/sage-main/<ipython console> in <module>() /Users/rlmill/sage-4.3.2/local/lib/python2.6/site-packages/sage/plot/misc.pyc in wrapper(*args, **kwds) 136 options['__original_opts'] = kwds 137 options.update(kwds) --> 138 return func(*args, **options) 139 140 /Users/rlmill/sage-4.3.2/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in plot(self, **options) 9596 """ 9597 from sage.graphs.graph_plot import GraphPlot -> 9598 return GraphPlot(graph=self, options=options).plot() 9599 9600 def show(self, **kwds): /Users/rlmill/sage-4.3.2/local/lib/python2.6/site-packages/sage/graphs/graph_plot.pyc in __init__(self, graph, options) 91 self._graph = graph 92 self._options = options ---> 93 self.set_pos() 94 self._arcs = self._graph.has_multiple_edges(to_undirected=True) 95 self._loops = self._graph.has_loops() /Users/rlmill/sage-4.3.2/local/lib/python2.6/site-packages/sage/graphs/graph_plot.pyc in set_pos(self) 137 sage: t.plot(heights={0:[0], 1:[4,5,1], 2:[2], 3:[3,6]}) 138 """ --> 139 self._pos = self._graph.layout(**self._options) 140 141 def set_vertices(self, **vertex_options): /Users/rlmill/sage-4.3.2/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in layout(self, layout, pos, dim, save_pos, **options) 8952 8953 if hasattr(self, "layout_%s"%layout): -> 8954 pos = getattr(self, "layout_%s"%layout)(dim = dim, **options) 8955 elif layout is not None: 8956 raise ValueError, "unknown layout algorithm: %s"%layout /Users/rlmill/sage-4.3.2/local/lib/python2.6/site-packages/sage/graphs/digraph.pyc in layout_acyclic_dummy(self, heights, **options) 1482 levels = [sorted(z) for z in levels] 1483 heights = dict([[i, levels[i]] for i in range(len(levels))]) -> 1484 return self.layout_graded(heights = heights, **options) 1485 1486 def level_sets(self): AttributeError: 'DiGraph' object has no attribute 'layout_graded'
I'm baffled.
comment:12 Changed 9 years ago by
- Cc rlm added
Ooops, sorry Robert for the wasted time, I completely forgot to upload the latest version on trac yesterday night. I also screwed up in my example which too small. Please try instead:
G = posets.IntegerPartitions(5).hasse_diagram()
G = DiGraph({1:(2,3), 2:[4], 3:[4]})
Looking again at those pictures, it feels like the nodes of same height do not repulse each other, or at least not as much as in the pure spring layout.
comment:13 Changed 9 years ago by
- Description modified (diff)
comment:14 Changed 9 years ago by
comment:15 Changed 9 years ago by
All graphs used to plot as square plots, whether you wanted them to or not. This would stretch any plot into a square, so if the relative distances were larger in one dimension than in the other, this would not show in the plot.
The following adjustment seems to improve the situation a bit, but I'm really not sure what the "right" fix is here.
--- a/sage/graphs/generic_graph.py Thu Feb 11 15:36:58 2010 +0100 +++ b/sage/graphs/generic_graph.py Thu Feb 11 07:39:46 2010 -0800 @@ -9058,6 +9058,8 @@ # We restore back the original height. for x in self.vertices(): newpos[x][dim-1] = pos[x][dim-1] + for i in range(dim-1): + newpos[x][i] *= 10 pos = newpos return pos
comment:16 follow-up: ↓ 17 Changed 9 years ago by
Hi there,
Compiling the doc in our queue if found a missing r"""
in an """
, which prevented the doc to compile. I just pushed a trivial patch in our queue under the name
trac_7004-graphviz-doc-fix.patch
Nicolas: please upload or fold in yours at will.
comment:17 in reply to: ↑ 16 Changed 9 years ago by
Sorry for replying to myself... Reading the doc I noticed the following: Nicolas you probably want to add yourself in the list of authors to the file graph_latex.py
and probably some other files as well. Please seize the opportunity to fold my patch.
comment:18 Changed 9 years ago by
The uploaded patch folds in Florent's doc fix, adds me as author as he suggested, and adds a couple comments here and there.
comment:19 Changed 9 years ago by
- Description modified (diff)
comment:20 follow-up: ↓ 21 Changed 9 years ago by
- Reviewers set to vdelecroix
- Status changed from needs_review to needs_work
It's not clear from the graph documentation that we can use latex for the output. It could be clearer to have a link in the docstring of the plot method or in the one of the object (Graph or DiGraph?) itself.
An important option that I did not find
- be able to modifiate the layout
It could be nice to have pointers in the documentation:
- more documentation for the method .set_latex_options()... at least a list of options (or is it available somewhere else)
- have a view(G, ...) example somewhere in the docstring of the object or in the set_latex_options one.
comment:21 in reply to: ↑ 20 ; follow-up: ↓ 22 Changed 9 years ago by
It's not clear from the graph documentation that we can use latex for the output. It could be clearer to have a link in the docstring of the plot method or in the one of the object (Graph or DiGraph?) itself.
The documentation is quite clear and complete but in an "hidden" file: sage.graphs.graph_latex
The refactorization of the code is really good, I will just talk about the graphviz, string and latex possibilities. Perhaps for other tickets...
1) graph to text conversion
There is different standards format for string representations of graph objects. At least two or three
- graphml (http://graphml.graphdrawing.org) which uses XML
- dot (http://www.graphviz.org) which was created by graphviz
- xdot which is can be considered as an extension of dot with non standard options
From now, there exists a method graphviz_string. Could we prefer a dot_string ? and in the same manner think about a graphml_string ? The main problem with those two names is that there does not start with the same prefix... and we get a contradiction with the use of the tab completion. As the refactorization for layout is perhaps we can consider string_dot and string_gml ? and string(format='dot') string(format='gml')
2) latex generation
There is a intersection between the two format of GraphLatex? (which is written in the description). dot2tex is able to produce a lot of different format...
Couldn't we prefer in the GraphLatex? file some different methods
- picture_tikz
- picture_pstricks
- which can also be used from picture(format='tikz') picture(format='pstricks')
and have an option inside picture_tikz to consider whether we use dot2tex or we use the actual code ?
3) latency
It took one second to execute in a console
neato -Txdot my_graph.dot | dot2tex -ftikz | pdflatex
And almost one minute for
sage: G = MyGraph() sage: G.set_latex_options(format='dot2tex') sage: view(G)
Do you have an idea where the time is lost ?
4) graph editor
There is a java program which can be used to interact with graphviz: http://www.dynagraph.org/ The program is made of two things dynagraph and grappa. It could be really nice to have an applet inside the notebook to use it directly as graph_editor works !!
It is available under the Common Public License
comment:22 in reply to: ↑ 21 Changed 9 years ago by
Replying to vdelecroix:
It's not clear from the graph documentation that we can use latex for the output. It could be clearer to have a link in the docstring of the plot method or in the one of the object (Graph or DiGraph?) itself.
The documentation is quite clear and complete but in an "hidden" file: sage.graphs.graph_latex
+1 on adding appropriate links.
The refactorization of the code is really good,
:-)
I will just talk about the graphviz, string and latex possibilities. Perhaps for other tickets...
1) graph to text conversion
There is different standards format for string representations of graph objects. At least two or three
- graphml (http://graphml.graphdrawing.org) which uses XML
- dot (http://www.graphviz.org) which was created by graphviz
- xdot which is can be considered as an extension of dot with non standard options
From now, there exists a method graphviz_string. Could we prefer a dot_string ? and in the same manner think about a graphml_string ?
Yup. Note that there already exists methods graph6_string sparse6_string, and so on.
The main problem with those two names is that there does not start with the same prefix... and we get a contradiction with the use of the tab completion. As the refactorization for layout is perhaps we can consider string_dot and string_gml ? and string(format='dot') string(format='gml')
The ..._string convention is followed consistently; so it might be a bit late to change it. On the other hand, it could be nice indeed to have a string(format='...') method
2) latex generation
There is a intersection between the two format of GraphLatex? (which is written in the description). dot2tex is able to produce a lot of different format...
Couldn't we prefer in the GraphLatex? file some different methods
- picture_tikz
- picture_pstricks
- which can also be used from picture(format='tikz') picture(format='pstricks')
and have an option inside picture_tikz to consider whether we use dot2tex or we use the actual code ?
I see all those methods as internal (actually, maybe they should start with _), while the main entry point for the user is the latex method. With this in mind, each picture_* method should concentrate on a specific task (creating a tikz picture manually / creating a picture by calling dot2tex), whereas all the dispatching job should go in the latex method.
I would not mind if the latex method would take extra arguments (as a shortcut to calling set_latex_options).
3) latency
It took one second to execute in a console
neato -Txdot my_graph.dot | dot2tex -ftikz | pdflatexAnd almost one minute for
sage: G = MyGraph() sage: G.set_latex_options(format='dot2tex') sage: view(G)Do you have an idea where the time is lost ?
Ah, interesting! On extra thing that dot2tex does it to run latex on each node to get the dimension of its bounding box. In principle, this is done in one swoop for all nodes, so that should not be that bad. So we should check whether it is dot2tex or the interface to dot2tex which is to be blamed. Could you give me your example and/or run the dot2tex script on it?
4) graph editor
There is a java program which can be used to interact with graphviz: http://www.dynagraph.org/ The program is made of two things dynagraph and grappa. It could be really nice to have an applet inside the notebook to use it directly as graph_editor works !!
It is available under the Common Public License
+1 definitely!
It does not seem to have been very active recently though.
Cheers,
comment:23 Changed 9 years ago by
- Description modified (diff)
comment:24 Changed 9 years ago by
- Description modified (diff)
comment:25 Changed 9 years ago by
Calling view on a graph with dot2tex format can be a bit slow. But see #8707 for making it 5 times faster :-)
comment:26 Changed 9 years ago by
- Description modified (diff)
comment:27 Changed 9 years ago by
- Status changed from needs_work to needs_review
All test pass, documentation builds without warning and we get beautiful graphs!
comment:28 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:29 Changed 9 years ago by
Hi!
I made a micro fix in dot2tex_utils.py: the (assert_) have_dot2tex methods are now tested with # optional rather than random. This is slightly stronger, and otherwise the assert_have_dot2tex method was failing when dot2tex was not installed. All test still pass, so I leave the positive review, but please Vincent double check.
I also made micro changes in the patch header.
comment:30 Changed 9 years ago by
Tests still pass and doc still builds. It's OK for me.
comment:31 Changed 9 years ago by
- Merged in set to 4.4.1.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
comment:32 Changed 9 years ago by
- Reviewers changed from vdelecroix to Vincent Delecroix
comment:33 Changed 9 years ago by
- Merged in changed from 4.4.1.alpha2 to sage-4.4.1.alpha2
comment:34 Changed 6 years ago by
- Description modified (diff)
Cc me