Repository files navigation

Grandalf is a python package made for experimentations with graphs drawingalgorithms. It is written in pure python, and currently implements two layouts:the Sugiyama hierarchical layout and the force-driven or energy minimization approach.While not as fast or featured asgraphviz or other libraries likeOGDF (C++),it provides a way towalk anddraw graphsno larger than thousands of nodes, while keeping the source code simple enoughto make it possible to easily tweak and hack any part of it for experimental purpose.With a total of about 1500 lines of python, the code involved indrawing the Sugiyama (dot) layout fits in less than 600 lines.The energy minimization approach is comprised of only 250 lines!

Grandalf does only 2 not-so-simple things:

• computing the nodes (x,y) coordinates(based on provided nodes dimensions, and a chosen layout)
• routing the edges with lines or nurbs

It doesn't depend on any GTK/Qt/whatever graphics toolkit.This means that it will help you findwhere todraw things like nodes and edges, but it's up to you to actually draw things withyour favorite graphics toolkit.

See examples listed in theWiki.

Here is a screenshot showing the result of rendering the control flow graph ofa function:

Grandalf suggests the following python packages:

• http://pypi.python.org/pypi/numpy, for the directed-constrained layout
• http://www.dabeaz.com/ply, for importing graphs fromgraphvizdot files.

Look for examples intests/. Here is a very simple example:

>>>fromgrandalf.graphsimportVertex,Edge,Graph,graph_core>>>V= [Vertex(data)fordatainrange(10)]>>>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)inX]>>>g=Graph(V,E)>>>g.C[<grandalf.graphs.graph_coreat0x7fb23a95e4c0>]>>>print([v.dataforving.path(V[1],V[9])])[1,4,5,9]>>>g.add_edge(Edge(V[9],Vertex(10)))<grandalf.graphs.Edgeobjectat0x7fb23a95e3a0>>>>g.remove_edge(V[5].e_to(V[9]))<grandalf.graphs.Edgeobjectat0x7fb23a95e0a0>>>>print([v.dataforving.path(V[1],V[9])])[1,3,6,8,9]>>>g.remove_vertex(V[8])<grandalf.graphs.Vertexobjectat0x7fb23a933dc0>>>>len(g.C)2>>>print(g.path(V[1],V[9]))None>>>foreing.C[1].E():print("%s -> %s"%(e.v[0].data,e.v[1].data))...9->10>>>fromgrandalf.layoutsimportSugiyamaLayout>>>classdefaultview(object):...w,h=10,10...>>>forvinV:v.view=defaultview()...>>>sug=SugiyamaLayout(g.C[0])>>>sug.init_all(roots=[V[0]],inverted_edges=[V[4].e_to(V[0])])>>>sug.draw()>>>forving.C[0].sV:print("%s: (%d,%d)"%(v.data,v.view.xy[0],v.view.xy[1]))...4: (30,65)5: (30,95)0: (0,5)2: (-30,35)1: (15,35)3: (-15,65)7: (-30,95)6: (15,125)>>>forlinsug.layers:...forninl:print(n.view.xy,end='')...print('')...(0.0,5.0)(-30.0,35.0)(15.0,35.0)(45.0,35.0)(-15.0,65.0)(30.0,65.0)(-30.0,95.0)(0.0,95.0)(30.0,95.0)(15.0,125.0)>>>fore,dinsug.ctrls.items():...print('long edge %s --> %s points:'%(e.v[0].data,e.v[1].data))...forr,vind.items():print("%s %s %s"%(v.view.xy,'at rank',r))...longedge3-->6points:(-15.0,65.0)atrank2(15.0,125.0)atrank4(0.0,95.0)atrank3longedge4-->0points:(0.0,5.0)atrank0(30.0,65.0)atrank2(45.0,35.0)atrank1

Contains the "mathematical" methods related to graphs.This module defines the classes:

• Vertex (and vertex_core)
• Edge (and edge_core)
• Graph (and graph_core)

A Vertex object is defined by a data field holding whatever you wantassociated to that vertex. It inherits from a vertex_core that --- when theVertex is added into a graph --- is holding the list of edges connected tothis Vertex and provides all methods associated to the properties of thevertex inside the graph (degree, list of neigbors, list of input edges,output edges, etc).Of course, unless a Vertex belongs to a graph, all properties are empty orNone.Example:

>>>v1=Vertex('a')>>>v2=Vertex('b')>>>v3=Vertex('c')>>>v1.data'a'

An Edge is defined by a pair of Vertex objects. If the graph is directed, thedirection of the edge is induced by the e.v list order otherwise the order isirrelevant. See Usage section for details.Example:

>>>e1=Edge(v1,v2)>>>e2=Edge(v1,v3,w=2)

Optional arguments includes a weight (defaults to 1) and a data holdingwhatever you want associated with the edge (defaults to None). Edge weightare used by the Dijkstra algorithm for finding 'shortest' paths withrespect to these weights.

A graph_core is used to hold a connected graph only. If the graph is notconnected (ie there exists two vertex that can't be connected by anundirected path), then an exception is raised.Use of the Graph class is preferable unless you really know that your graphis connected.Example:

>>>g=graph_core([v1,v2,v3],[e1,e2])

The graph object can be updated by g.add_edge(e), g.remove_edge(e) org.remove_vertex(v) which all raise an exception if connectivity is lost. Notethat add_edge() will possibly extend the graph's vertex set with at most onenew Vertex found in the added edge.See the Usage section for further details.

This is the main class for graphs. The resulting graph is stored as "DisjointSets" by processing the input lists of Vertex and Edge objects into a list ofgraph_core components.Example:

>>>v4,v5=Vertex(4),Vertex(5)>>>g=Graph([v1,v2,v3,v4],[e1,e2])

The graph object can be updated by g.add_vertex(v), g.add_edge(e),g.remove_vertex(v) and g.remove_edge(e) which all may result in updating agraph_core, creating a new graph_core, or removing a graph_core from thegraph's internal list.

Contains the "drawing" algorithms.This module defines the classes:

• Layer
• SugiyamaLayout
• DigcoLayout

This class performs a 2D hierarchical placement of a connected graph.The algorithm works only for directed acyclic graphs (DAG), so that a"feedback acyclic set" of edges is needed.To create a graph layout, you need to provide:

• a graph_core object where every Vertex has been equiped with a '.view'interface providing the width and height of the graphical representation ofthe Vertex (in our terminology, a Vertex equiped with a '.view' is a "node"of the graph)

To initiate the drawing (init_all) you will optionally provide:

• the list of "root" nodes
• the list of feedback acyclic edges
• constraint parameter related to how inverted edges are routed

In order to minimize edge crossings between each consecutive layers, thealgorithm uses several rounds of nodes reordering (draw(N)). Increasing thisparameter N can lead to layout with less crossings.For educational or debugging purpose, the drawing computation can be observedstep-by-step (draw_step).

This class performs a 2D hierarchical placement of a connected graph.The main difference with SugiyamaLayout is that this algorithm is based onoptimization theory rather than on heuristics. It computes the nodecoordinates by minimization of an "energy" function that describes the stressfactor associated to a layout.This approach allows to take into account new constraints on node placement.To create a graph layout, you only need to provide:- a graph_core object where every Vertex has been equiped with a '.view'

Contains the edge routing algorithms.This module defines the classes and functions:

• EdgeViewer
• route_with_lines
• route_with_splines

This class provides a default 'view' for edges. Edges with no view will beignored by the draw_edge method of the layouts. If a view is provided it mustbe equiped with a 'setpath' method to which a list of waypoints will bepassed.

This function allows to adjust the waypoints of the edge. It allows todraw a poly-line edge going through all points computed by the layout engineand adjusts the tail head position on the boundary of their nodes andprecomputes the head angle.To use this routing method, set the route_edge field of the layout instanceto this function (sug.route_edge = route_with_lines).

This function allows to draw edges by a combination of lines and beziercurves. The curves are computed such that corners of a poly-line edge givenby route_with_lines are rounded.To use this routing method, set the route_edge field of the layout instanceto this function (sug.route_edge = route_with_splines) and use the valuesreturned in the .splines field of the edge view :- an array of 2 points defines a line- an array of 4 points defines a bezier curve.

Provides utilities like partially ordered sets, linear programming solvers,parsers for external formats (Dot, etc.)This module defines :

• Poset
• Dot

and some general purpose functions like:

• intersect2lines
• intersectR
• getangle (computing the atan2 value for directed edge heading)
• intersectC
• setcurve (computing a nurbs locally interpolating a given set of points)
• setroundcorner

This class is used by graph_core for both efficiently detecting if a Vertexor Edge is in a graph (using builtin set()) and ensuring that elements ofthe set are iterated always in the same order (using builtin list()).Basically, a Poset is pair (set,list) that is kept synchronized.

This class contains a PLY lexer and parser for the graphviz dot format.The parser reads all graphs currently defined ingraphvizgraphs/{directed,undirected}/*.gvias well as the dg.dot and ug.dot databases (> 5000 graphs parsed OK)includinglatin1 andutf8 support (see russian.gv or Latin1.gv).

This function is used internally for edge routing. It is based on an methoddescribed in "The NURBS Book" (Les A. Piegl, Wayne Tiller, Springer 1997)implementing local interpolation of a given set of points with a set ofnon-uniform b-splines of degree 3. The non-uniform knots are ignored.

This function uses setcurve to smooth the polyline edge at each corner. Thismethod provides the best result for edge routing with the SugiyamaLayout.It is used in the route_with_splines function in routing.py.

Contains many testing procedures as well as some graph samples.

Rather than an exhaustive library reference with all methods for all classes,(see Python help() for that) we focus on a typical usage of grandalf and try toalso emphasize important notes.

Lets start by creating an empty graph:

>>>g=Graph()

Wether you first create the graph and add elements in it or create it after allVertex and Edge objects have been defined, is up to you.For the moment the graph has no components :

>>>g.order()0>>>g.C[]

Lets create some vertices now.

>>>v1=Vertex('a')>>>v2=Vertex('b')>>>v3=Vertex()>>>v3.data='c'>>>v1.data'a'

First, note that the 'data' field is optional and can be added anytime in thevertex. We are associating a string to this field so that it is easy toidentify a given vertex, but keep in mind that this data is not needed forgraph computations and drawings.For the moment, the vertex objects are "free" in the sense that they are notassociated with any graph_core object. When a vertex belongs to a graph_core,the reference to this graph_core is found in the 'c' field (component field).

To insert a Vertex in a Graph object we do:

>>>g.add_vertex(v1)

or we can add a new edge, then any new vertex it the edge will be attached tothe graph also:

>>>e1=Edge(v1,v2)>>>e2=Edge(v1,v3,w=2)>>>g.add_edge(e1)>>>g.add_edge(e2)>>>v2ing.C[0]True

Warning: Vertex and Edge objects MUST belong to only one graph_core object at atime. So you should never use the same Vertex/Edge into another graph withoutremoving it first from the current one !Of course, removing a vertex also removes all edges linked to it.

>>>g.remove_vertex(v1)>>>e1ingFalse>>>len(g.C)3

Removing v1 here has removed e1 and e2, and the graph g is now cut in 3components holding each one vertex only. Lets rebuild the graph and extend it:

>>>g.add_edge(e1)>>>g.add_edge(e2)>>>v4,v5=Vertex(4),Vertex(5)>>>g.add_edge(Edge(v4,v5))

Now g has two graph_core objects in g.C, and if

>>>g.add_edge(Edge(v5,v3))

the cores are merged in one component only.

There are many possible layouts when it comes to graph drawings.The current layout implemented is a hierarchical 2D layout suited fordirected graphs based on an method proposed by Sugiyama et al.Our implementation is derived from the paper by Brandes & Kopf (GD 2001.)This method is quite efficient but is based on many heuristics that are noteasy to tweak when you want to add some constraints like for example"I want that nodes with property P to be placed near each others."

The "dig-cola" method is based on a different approach where graph propertiesare expressed as constraints on node's coordinates, reducing the problem tosolving a set of inequalities with unknowns being the x,y coords of everynodes. With this approach, adding new contraints is very simple.The dig-cola method is implemented in old commits and is currently beingrewritten to match the design of SugiyamaLayout.

In Grandalf, a layout engine only applies on a graph_core object.Basically drawing a Graph() requires that you draw all its connex componentsand decide how to organize the entire drawing by moving each component whereyou want. Since some methods involve "dummy" nodes inserted in the graph, it isimportant to note that layout classes are completely separated from theoriginal : the underlying graph_core topology is never permanently modified.This means that redrawing a graph for whatever reason (vertex added, edgesadded, etc) is as simple as creating a new layout instance.Of course, if you know what you are doing, you can try to update the drawingbased on the current layout instance but unless modifications of the topologyare very simple, this can be very difficult (enhancing this adaptative drawingpart is definetly in the TODO list!).

Before creating a layout engine associated with a graph_core, each vertex MUSTbe equiped with what we call a 'view'. For a vertex v, such view must be anobject with attributes

• w (width) and
• h (height),
• xy (position)

and the layout engine will set the v.view.xy field with a (x,y) tuple valuecorresponding to the center of the node.In practice, this allows to useview objects that inherits from graphicwidgets (e.g. a rectangle in a Canvas) which will position the widget in thecanvas when the xy attribute is set.

If you want the layout to perform also edge routing, you MAY equipe edges alsowith a 'view' attribute. For an edge e, the view must have asetpath methodtaking a list of points as argument.The layout engine will provide the list of (x,y) routing points, starting bythee.v[0].view.xy, then all intermediate dummy vertices position throughwhich the edge drawing should go, including the e.v[1].view.xy last point.The routing.py module provides enhanced routing functions as well as arepresentative EdgeViewer class to help finding the exact position wheredrawing the 'tail' or the 'arrowhead' or define a set of splines made of Beziercurves so that almost any curve Canvas primitive can be used.

The Sugiyama layout draws a graph by separating the nodes in several layers.These layers are stacked one under the others. The first layer contains the"root" nodes.

Most of the time, you don't need to bother with these notions becauseinit_all() will find the needed root nodes and feedback edges. Still, in somecases it may help to know about these essential sets:

The Sugiyama layout is made for directed acyclic graphs. So the first requirementfor this layout is to have the list of inverted edges(aka the feedback acyclic set needed to make the graph acyclic when needed.)These edges are inverted in the graph_core only during some specific operationsand are reverted immediately after these computations.For example, the graph is made acyclic for ranking the nodes into hierarchicallayers.The graph_core class contains a method that computes the "strongly connectedsets" of the graph_core by using the Tarjan algorithm (get_scs_with_feedback).A strongly connected set is a subset of vertex where for any two vertices A B,there exist a directed path from A to B.Of course a cycle is a strongly connected set, but such set may contain severalinterlaced cycles. The algorithm constructs the "feedback acyclic set" bytagging the edges with the 'feedback' field set to True. It performs a DFSstarting from the given set of nodes.A good choice is of course to start with the set of nodes that have no incomingedges, but if this set is empty (because the graph is cyclic) you will have tochoose a preferred set :Hence,

>>>r=filter(lambdax:len(x.e_in())==0,gr.sV)>>>iflen(r)==0:r= [my_guessed_root_node]>>>L=gr.get_scs_with_feedback(r)>>>inverted_edges=filter(lambdax:x.feedback,gr.sE)

leads to L containing the SCS of thegr component, and the feedback set isthen obtained by filter edges with the feedback flag.

As mentioned before, drawing with the SugiyamaLayout engine also requires thatyou provide the list of "root" nodes.Its up to you to decide which nodes are the "roots", but the natural definitionis as stated before :

>>>gr=g.C[0]>>>r=filter(lambdax:len(x.e_in())==0,gr.sV)

that is, the list r of vertex with no incoming edges.Warning: if r is empty, you might want to use the set of edges computed beforeto temporarily remove cycles and retry (look at__edge_inverter method.)

Drawing the gr component by computing .view.xy coordinates just resumes to:

>>>sug=SugiyamaLayout(gr)>>>sug.init_all()>>>sug.draw()

This will perform ONE round of the drawing algorithm. A singleround means that the node placement has been performed from the top layer to thebottom layer and back to top. This may not be sufficient to reduce the edgecrossings, so you can draw again or simply provide the number of pass toperform:

>>>sug.draw(3)

If you want to be able to draw the graph while the engine is running, you canuse the draw_step() iterator which yields at each layer during the forward andbackward trip.

Then, drawing the graph with a graphical canvas can be done by drawing eachviews at their xy positions and either defining asetpath method that willbe called by grandalf draw_edges() with a set of routing points, or by usingpredefined functions inrouting.py likeroute_with_lines orroute_with_splines.

If you have installedmasr, just do:

$cd /path/to/grandalf$ ./masr-graph tests/samples/brandes.dot

When a node is focused, the SPACE key is bound to draw_step().next(). Thiswill show how the algorithm tries to reduce edge crossing in each layer bymodifying the layer ordering. Modified nodes will appear with green shadow.The P key will cycle through the 4 internal alignment policies(top-left, top-right, bottom-left, bottom-right.)

Optionally, inverted edges can be constrained to always start from the bottomof their init vertex, and end on the top of their terminal vertex.

$ ./masr-graph tests/samples/manhattan1.dot -ce

The DigcoLayout stands for "Directed Graph Constrained Layout". The method wasproposed by Dwyer & Koren in a paper presented at InfoVis 2005. It relies ona stress minimization approach (similar to force-driven layouts like /neato/)with hierarchical properties taken into account as additional constraints onnode coordinates.

Like for SugiyamaLayout, just do for example:

>>>dco=DigcoLayout(gr)>>>dco.init_all()>>>dco.draw(limit=100)

The init_all() method will take into account hierarchical information if thegraph is directed, and will randomly choose an initial distribution of nodecoordinates. The draw() method will then converge towards the optimal solutionby using a conjugate-gradient method.Thelimit parameter (defaults to gr.order() if not provided,) controls themaximum iteration count of the convergence loop.FIXME: In the current implementation, hierarchical levels are not taken intoaccount as additional constraints.

If you have installedmasr, just do:

$cd /path/to/grandalf$ masr-graph -digco -N 25 tests/samples/circle.dot

Or, you may visualize each step of the convergence by:

$ masr-graph -digco -N 1 tests/samples/circle.dot

Now mouse-focus one of the nodes and press SPACE to see the next iteration.Check out the masr/plugins/graph code to see how it works!

• add hierarchical constraints in DigcoLayout to support directed graphs
• add support for GraphML format import/export
• add support for pgf/tikz export
• provide facilities for efficient (interactive) edge re-routing

1. Why is there no 'add_vertex()' method in the graph_core class ?

Because graph_core are connected graphs, only add_single_vertex() makes sense.If you want to add a vertex directly into a graph_core, the vertex must beconnected with an edge to another vertex already in the graph_core(use add_edge()).However, if the graph is empty, the first vertex can be attached to the graphby using add_single_vertex().