bdcht / grandalf Goto Github PK

View Code? Open in Web Editor NEW

214.0 18.0 44.0 1.12 MB

graph and drawing algorithms framework

License: Other

Python 100.00%

graphs drawings layout-engine

grandalf's People

Contributors

Stargazers

Watchers

Forkers

atbrox xqx12 pombredanne idkwim tempbottle shadown fabioz sjoerdtimmer janisgailis debug-orz sarvex abduld redreamality shubhamgupta2021 gitter-badger rojaster linearregression geoplexgis rachit138 lamondlab mayblue9 ejmolinelli zoran-cuckovic bwry bssrdf zhaobin74 efiop mdheller gaybro8777 bubble501 freemanzyq sthagen yk tirkarthi d-e-f-e-a-t mattmilten paulbrodersen davidsteiner fateshelled organizationusername ardevsha suimong cgy1992 avargas0831

grandalf's Issues

No source tarball for 0.7 on the PyPI.org site

https://pypi.org/project/grandalf/#files

Please push tests into your source distribution

This is important for source-preferred distributions like NixOS. NixOS/nixpkgs#54403

The tests should be in the source distribution so they can be executed.

Format code to obey pep8

We use Grandalf in our project of Nengo GUI and one of the things we're starting to check for is PEP8 compliance. It would be cool if Grandalf would obey PEP8.

Obviously, if I cared that much I should just make the changes myself, but I thought it might be useful to note.

Deprecation warning due to invalid escape sequences

Deprecation warnings are raised due to invalid escape sequences. This can be fixed by using raw strings or escaping the literals. pyupgrade also helps in automatic conversion : https://github.com/asottile/pyupgrade/

find . -iname '*.py' | xargs -P4 -I{} python3.8 -Wall -m py_compile {}
./tests/test_layouts.py:23: DeprecationWarning: invalid escape sequence \ 
  '''

grandalf layout seems to give horizontal layouts instead of more vertically-aligned layouts

As an example of what I mean, I'm attaching 2 files with the results I've gotten so far:

File 1 was generated by grandalf:

File 2 was generated by graphviz:

The .dot file example to generate this is available at: http://pastebin.com/K0EsAtFf

Do you think it's possible to improve this in grandalf?

Orthogonal Layout

Any chance you would implement the above?

ImportError: No module named linalg

When importing amoco:

>>> import amoco
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-1-5ce33a136b23> in <module>()
----> 1 import amoco

/home/user/.pyenv/versions/2.7.9/lib/python2.7/site-packages/amoco/__init__.py in <module>()
      2 
      3 from .config import conf
----> 4 from .main import *

/home/user/.pyenv/versions/2.7.9/lib/python2.7/site-packages/amoco/main.py in <module>()
      8 logger = Log(__name__)
      9 
---> 10 from amoco import cfg
     11 from amoco import code
     12 from amoco import system

/home/user/.pyenv/versions/2.7.9/lib/python2.7/site-packages/amoco/cfg.py in <module>()
     10 logger = Log(__name__)
     11 
---> 12 from grandalf.graphs import Vertex,Edge,Graph
     13 
     14 from amoco.system.core import MemoryZone

/home/user/.pyenv/versions/2.7.9/lib/python2.7/site-packages/grandalf/graphs.py in <module>()
      5 # published under GPLv2 license or EPLv1 license
      6 
----> 7 from .utils import Poset
      8 from operator import attrgetter
      9 

/home/user/.pyenv/versions/2.7.9/lib/python2.7/site-packages/grandalf/utils/__init__.py in <module>()
      1 from .poset import *
----> 2 from .geometry import *
      3 from .dot import *
      4 from .nx import *

/home/user/.pyenv/versions/2.7.9/lib/python2.7/site-packages/grandalf/utils/geometry.py in <module>()
     19     from math import cos,sin,pi
     20     deg2rad = lambda x: (x*math.pi/180.)
---> 21     from .linalg import array,matrix
     22 
     23 #  rand_ortho1 returns a numpy.array representing

ImportError: No module named linalg

Drawing graph left to right (horizontally) rather vertically (top to bottom)

Hi,
I did test on my project, and it seems grandalf will do the job. The only thing I was not able to find out in documentation is drawing
graph horizontally. Is this feature is implemented? Please let me know.
Actually I have tried rotating all the vertices 90 degree counter clock wise along to a pivot point but first you have to flip the graph horizontally, or else it won't do.

Cheers

Release a new version

Hi!

Thank you so much for creating and maintaining such an amazing and useful project! I am using it to create pure-python ASCII visualizations of a DAG for our project https://github.com/iterative/dvc . I've noticed that the currently released version has a bug where python3 and python2 produce different layout. Here is an example:

bad(python3):

                                      .--------------------.
                                      | data/Posts.xml.tgz |
                                      `--------------------'
                                      .
                                      .
                                      .
                                      .
                                      .
                                      .
                                      .----------------.
                                      | data/Posts.xml |
                                      `----------------'
                                      .
                                      .
                                      .
                                      .
                                      .
                                      .
                                      .----------------.
                                   .. | data/Posts.tsv |
                                 ..   `----------------'
                               ..               .....
                             ..                      ...
                           ..                           .....
                         ..                                  ...
                       ..                                       .....
                     ..                                              ..
                   .----------------------.                               .---------------------.
                   | data/Posts-train.tsv |                      ....     | data/Posts-test.tsv |
                   `----------------------'                ......         `---------------------'
                   .               ......            ......               .
                   .                     ............                     .
                   .                     ............                     .
                   .               ......            ......               .
                   .         ......                        ......         .
                   .     ....                                    ....     .
                   .---------------------.                                .--------------------.
                 . | data/matrix-train.p |                    .....       | data/matrix-test.p |
              ...  `---------------------'            ........            `--------------------'
             .          ..                    ........                    .
          ...             ..          ........                            .
         .                  ..........                                    .
      ...             ..........                                          .
     .        ........          ..                                        .
   ..    .....                    ..                                      .
 .--------------.                   .                                   ...
 | data/model.p |                   .                                ...
 `--------------'                   .                           .....
            ....                     .                       ...
                ....                 .                  .....
                    ....             .               ...
                        ....          .         .....
                            ....      .      ...
                                ...   .   ...
                                      .---------------.
                                      | data/eval.txt |
                                      `---------------'

good(python2):

                                      .--------------------.
                                      | data/Posts.xml.tgz |
                                      `--------------------'
                                      .
                                      .
                                      .
                                      .
                                      .
                                      .
                                      .----------------.
                                      | data/Posts.xml |
                                      `----------------'
                                      .
                                      .
                                      .
                                      .
                                      .
                                      .
                                      .----------------.
                                   .. | data/Posts.tsv |
                                 ..   `----------------'
                               ..           ..
                             ..               ..
                           ..                   ..
                         ..                       ..
                       ..                           ..
                     ..                               ..
                   .----------------------.              .---------------------.
                   | data/Posts-train.tsv |        ...   | data/Posts-test.tsv |
                   `----------------------'    ....      `---------------------'
                   .          ....         ....          .
                   .              .........              .
                   .              .........              .
                   .          ....         ....          .
                   .      ....                 ....      .
                   .   ...                         ...   .
                   .---------------------.               .--------------------.
                .. | data/matrix-train.p |            .. | data/matrix-test.p |
               .   `---------------------'          ..   `--------------------'
            ...          ..                       ..          ...
           .               ..                   ..               .
        ...                  ..               ..                  ...
       .                       ..           ..                       .
    ...                          ..       ..                          ...
   .                               ..   ..                               .
 ...                                  .--------------.                   ...
    ....                              | data/model.p |               ....
        ....                          `--------------'           ....
            ....                      .                      ....
                ....                  .                  ....
                    ....              .              ....
                        ....          .          ....
                            ....      .      ....
                                ...   .   ...
                                      .---------------.
                                      | data/eval.txt |
                                      `---------------'

So I've cloned the repo to start digging for the bug and after I've installed the upstream version of grandalf the problem disappeared 🎉 . Thus I'm wondering if you could release a new version on pypi
please?

Thank you in advance,
Ruslan

AttributeError in Tarjan algorithm

Hi,

displaying the following DOT graph (http://dl.free.fr/mQEUoqkT9) with masr-graph spits that trace :

$ ./masr-graph -c 3 perms.dot
257 verts, 78 root(s)
using tarjan algorithm to find inverted_edges...
Traceback (most recent call last):
File "./masr-graph", line 14, in
app.run(args=sys.argv)
File "masr/masr/plugins/utils.py", line 8, in wrapper
plugin.start(func.name,self,**kargs)
File "masr/masr/plugins/graph/main.py", line 39, in start
app.session.cg.Draw(1)
File "masr/masr/plugins/graph/main.py", line 127, in Draw
L = gr.get_scs_with_feedback(r)
File "/usr/local/lib/python2.7/dist-packages/grandalf/graphs.py", line 382, in get_scs_with_feedback
del v.lowlink
AttributeError: lowlink

Any enlightenment is welcome,
Cheers,

Mathieu

Render graph from draw

Hi,

Sorry if I ask a trivial question, but I would like to know how to draw a network after building the graph, say, using Matplotlib. I am providing a minimal code here?:

from grandalf.graphs import Vertex,Edge,Graph
from grandalf.layouts import SugiyamaLayout

import matplotlib.pyplot as plt


class defaultview(object): w,h = 10,10

V = [Vertex(data) for data in range(10)]
for v in V: v.view = defaultview()
X = [(0,1),(0,2),(1,3),(2,3),(4,0),(1,4),(4,5),(5,6),(3,6),(3,7),(6,8), (7,8),(8,9),(5,9)]

E = [Edge(V[v],V[w]) for (v,w) in X]

g = Graph(V,E)

sug = SugiyamaLayout(g.C[0])
sug.init_all(roots=[V[0]],inverted_edges=[V[4].e_to(V[0])])

sug.draw()

# ???
#plt.show()

Sugiyama layout fails with custom ranking

I was playing a bit with the layout and checking if I could get the Sugiyama layout to work better for me (because of #5), so, I was experimenting changing the initial ranking and I'm getting an exception I didn't expect (details below).

I created a failing test at:
https://github.com/fabioz/grandalf/blob/unfixed_issue_on_ranking_change_sugiyama/tests/test_layouts.py (method test_sugiyama_custom_ranking2), which mostly just sets the ranking which fails (and you can see in the same file the original ranking in test_sugiyama_custom_ranking2).

Note: I'm creating a pull-request for this so that you can see it better (and the tests are valid, albeit still failing), but I'm not sure it should be integrated before it's fixed...

File "X:\grandalf\tests\test_layouts.py", line 212
in test_sugiyama_custom_ranking2
sug.draw(N=10)
File "X:\grandalf\grandalf\layouts.py", line 329
in draw
for (l,mvmt) in self.ordering_step():
File "X:\grandalf\grandalf\layouts.py", line 464
in ordering_step
mvmt = l.order()
File "X:\grandalf\grandalf\layouts.py", line 138
in order
c = self._cc()
File "X:\grandalf\grandalf\layouts.py", line 242
in _cc
P.extend(sorted([g[x].pos for x in self._neighbors(v)]))
File "X:\grandalf\grandalf\layouts.py", line 215
in _neighbors
dum = self.layout.ctrls[e][tr][-1]
E KeyError: <grandalf.graphs.Edge object at 0x0000000003867400>

add `grandalf` to PyPI

grandalf is a useful package that liberates from the need to use GraphViz.
Using GraphViz from Python has several drawbacks:

Typically unnecessary, especially for graphs that will appear in print. No printed graph can have so many nodes that details (like avoiding edge-node overlaps) matter and it will cause performance issues with Python.
Need to be compiled, installed, be a compatible version (e.g., default GraphViz version on Linux is outdated).
Need an interface between Python and GraphViz. My choice has been pydot. However, pydot is unmaintained, malfunctional and outdated on PyPI, and messy code (it also uses pyparsing, instead of ply, which implies performance issues as things scale, because bottom-up parsing is more powerful). Other packages do not match the pydot API.
Interfacing to GraphViz is a nightmare for debugging, especially if wanting to produce TikZ graphics for LaTeX (the string delimiters and escape backslashes become unmanageable, see comments motivating nx2tikz). The reason is that flat is better than nested (PEP 20), and such an interface is a nested approach.
It is quite difficult to tell GraphViz customized information about node areas and shapes. This seems much easier in Python, even if one has to extend grandalf.

For the above reasons, I believe that grandalf should be made more widely available, through PyPI.

A related suggestion would be to merge it into networkx, so that its algorithms become widely available. However, I am not sure whether the networkx developers would support such a merge. Also, it seems that keeping it separate can make maintenance simpler, release cycles more frequent (unlike nx), and also make the grandalf algorithms available to any graph package, via a thin interface. For example, networkx can optionally import grandalf and itself use it for layout in matplotlib (thus avoiding overlapping edges in multi-digraphs).

If there is agreement on this, I could open a pull request for this purpose (and if needed, maintain the PyPI entry).

Please add a simple copy and past sample on the front page

Please just add an simple 10 line sample without those >>> that you can just copy and past and that generates an very simple graph plot.

python interpreter recursion limit can't be adjusted

well for the Linux platform its ok, but I've tested on OSX and an exception is raised at default depth (1000) without taking into account the setrecursionlimit call. This means that the SugiyamaLayout will fail during the recursive part of vertical alignment (__place_block step) whenever a "block" has more than 1000 aligned vertices.
Fix: either remove recursion (painful) or catch exception, forget about further alignment, and continue.