Open Graph Drawing Framework
current version:
v.2012.07 (Sakura)
     

Differences

This shows you the differences between two versions of the page.

gsoc2012 [2012/03/19 11:29]
carsten 		gsoc2012 [2012/04/24 12:23] (current)
carsten
Line 1: Line 1:
-====== Google Summer of Code 2012 ======+====== Google Summer of Code™ 2012 ======
-OGDF has been accepted as a mentoring organization for the [[http://www.google-melange.com/gsoc/homepage/google/gsoc2012|Google Summer of Code (GSoc) 2012]]!+[[http://www.google-melange.com/gsoc/org/google/gsoc2012/ogdf|OGDF]] has been accepted as a mentoring organization for the [[http://www.google-melange.com/gsoc/homepage/google/gsoc2012|Google Summer of Code™ (GSoc) 2012]]!
-If you are a student interested in one of our projects and don't know where to start, we've collected a list of [[gsoc-faq|frequently asked questions (FAQ)]]. +Student applications period (March 26 – April 6) is already over, and decisions on accepted applications have been made. Accepted students have been [[http://feedproxy.google.com/~r/GoogleOpenSourceBlog/~3/XTa4yjVfc6I/students-announced-for-google-summer-of.html|announced]] on the [[http://www.google-melange.com/gsoc/homepage/google/gsoc2012|GSoC web page]].
-===== Project Ideas ===== +There is a **[[:gsoc:main|special area]] for accepted students**, with some in-depth information and pages for reporting progress. //(restricted access)//
- +
-Our project ideas for OGDF range from projects that shall improve its usability to projects touching topics of current scientific research in graph drawing. For all these projects, participating students should be interested in the visualization of graphs and have some theoretical background in graph algorithms. +
- +
-This is a collection of project ideas we propose for GSoC 2012. Each project idea links to its detailed description below. If you have further project ideas and or want to discuss some of our proposed  +
- project please contact us by email (''info@ogdf.net''), or directly contact the responsible mentor(s). +
- +
-  * **Adding New Layout Algorithms to OGDF** +
-    * [[#Hypergraph Layout|Hypergraph Layout]] +
-    * [[#Stress Majorization|Stress Majorization]] +
-    * [[#Bertault Layout|Bertault Layout]] +
-    * [[#Orthogonal Grid Layout|Orthogonal Grid Layout]] +
-  * **Improving Layout Algorithms in OGDF** +
-    * [[#Parallelization of Layout Algorithms|Parallelization of Layout Algorithms]] +
-    * [[#Embedding Constraints|Embedding Constraints]] +
-    * [[#Simplified Orthogonal Layout]] +
-    * [[#Multi-Layer Crossing Minimization|Multi-Layer Crossing Minimization]] +
-  * **Tools and Utilities** +
-    * [[#OGDF Command Line Tool|OGDF Command Line Tool]] +
-    * [[#Viewer for Large Graphs|Viewer for Large Graphs]] +
- +
- +
-===== Detailed Project Descriptions =====+
 +===== Accepted Projects =====
==== Hypergraph Layout ==== ==== Hypergraph Layout ====
-**Brief description:** OGDF contains state-of-the-art crossing minimization heuristics for hypergraphs, based on the planarization approach. However, there's not yet a complete layout algorithm for drawing such graphs. Aim of this project is to implement a layout module for hypergraphs that uses this crossing minimization procedure and produces an orthogonal layout.+OGDF contains state-of-the-art crossing minimization heuristics for hypergraphs, based on the planarization approach. However, there's not yet a complete layout algorithm for drawing such graphs. 
 +Aim of this project is to implement a layout module for hypergraphs that uses this crossing minimization procedure and produces an orthogonal layout. 
 +The layout algorithm shall also support constraints for laying out electronic circuits, which is an important application for hypergraph layout.
-**Expected result:** A new layout module in OGDF for orthogonal hypergraph layout.+**Student:** //Ondrej Moriš// (Masaryk University, Brno, Czech Republic)\\ 
 +**Mentors:** [[http://ls11-www.informatik.uni-dortmund.de/staff/gutwenger|Carsten Gutwenger]], [[http://www.ae.uni-jena.de/Staff_Contact/Markus+Chimani.html|Markus Chimani]]
-**Rationale:** Hypergraphs are a straight-forward extension of usual graphs, where hyper-edges may connect more than two nodes. The typical layout style for hypergraphs is to draw edges in a tree-like fashion, thus connecting the endpoints of an edge with a tree. An important application area for hypergraphs is the layout of electronic circuits (here, some further constraints need to be observed). It has already been shown, that OGDF's hypergraph crossing minimization heuristics beat the current state-of-the-art for such circuits. Hence, we expect that extending these heuristics to a complete layout algorithm for hypergraphs will be a big step forward.+**Links:** [[:gsoc2012-ideas#hypergraph_layout|Original Project Idea]]
-**Literature:** +==== Parallelization of Layout Algorithms ====
-  * M. Chimani, C. Gutwenger, [[http://dx.doi.org/10.1007/978-3-540-77120-3_18|Algorithms for the Hypergraph and the Minor Crossing Number Problems]], in: Proc. of ISAAC 2007, LNCS 4835, Springer, 2007, pp. 184-195. +
-  * M. Chimani, [[http://www.ae.uni-jena.de/alenmedia/dokumente/ComputingCrossingNumbers_PhDthesis_Chimani_pdf.pdf|Computing Crossing Numbers]], Sections 7.2 and 9.1, PhD Thesis, Technical University Dortmund, 2008.+
-**Prerequisites:** C++, Subversion, good knowledge in algorithms and data structures+Several OGDF algorithms contain procedures that can be parallelized in a straight-forward way. 
 +E.g., the implementation of the crossing minimization steps in the planarization approach and Sugiyama's algorithm perform several runs (and then take the best result), 
 +which can be run in parallel, or some algorithms handle connected components independently. 
 +The aim of this project is to identify and parallelize these algorithms. 
 +The challenging part of this project is to keep the additional memory consumption for the parallel running threads low and to achieve a good speed-up.
-**Skill level:** high +**Student:** //Nick Vanbaelen// (Catholic University of Leuven, Belgium)\\ 
- +**Mentors:** [[http://www.informatik.uni-koeln.de/ls_juenger/people/mallach/|Sven Mallach]], [[http://www.informatik.uni-koeln.de/ls_juenger/people/gronemann/|Martin Gronemann]], [[http://ls11-www.informatik.uni-dortmund.de/staff/gutwenger|Carsten Gutwenger]]
-**Mentor:** [[http://ls11-www.informatik.uni-dortmund.de/staff/gutwenger|Carsten Gutwenger]] +
- +
- +
-==== Stress Majorization ==== +
- +
-**Brief description:** Distance-based layout methods like the classical Kamada-Kawai algorithm are well known to achieve aesthetically pleasing drawings. However, their runtime complexity is not suited for larger graphs. The stress-majorization approach by Gansner et al. is a distance-based layout algorithm that uses techniques from multi-dimensional scaling and has a much better runtime. Aim of this project is to make the stress majorization approach available in OGDF. +
- +
-**Expected result:** A new layout module implementing the stress-majorization approach for drawing (undirected) graphs. +
- +
-**Rationale:** Distance-based layout methods have shown to produce drawings with very good quality. In current research, variations and adaptions of these methods (e.g., sparse stress methods) are currently considered as alternatives to multi-level force-directed algorithms (like the fast-multipole multilvel method ''FMMMLayout'' in OGDF). Having an implementation of the original method by Gansner et al. available in OGDF would be a good starting point for further research. +
- +
-**Literature:** E. R. Gansner, Y. Koren, S. North, [[http://dx.doi.org/10.1007/978-3-540-31843-9_25|Graph Drawing by Stress Majorization]], in: Proc. Graph Drawing '04, LNCS 3383, Springer, 2004, pp. 239-250. +
- +
-**Prerequisites:** C++, Subversion, good knowledge in algorithms and data structures +
- +
-**Skill level:** high +
- +
-**Mentors:** [[http://ls11-www.informatik.uni-dortmund.de/staff/klein|Karsten Klein]], [[http://ls11-www.informatik.uni-dortmund.de/staff/gutwenger|Carsten Gutwenger]]+
 +**Links:** [[:gsoc2012-ideas#parallelization_of_layout_algorithms|Original Project Idea]]
==== Bertault Layout ==== ==== Bertault Layout ====
-**Brief description:** Classical force-directed layout algorithms do a good job in achieving uniform edge lengths and distributing the nodes on the drawing area, but are unable to consider edge crossings and thus often produce many crossings even for planar graphs. A good alternative is to combine planar drawing methods with force-directed algorithms, but this requires a force-directed layout algorithms that preserves the planar embedding of the graph. Bertault's algorithm is such a force-directed layout algorithm. Aim of this project is to implement Bertault's algorithm. +Classical force-directed layout algorithms do a good job in achieving uniform edge lengths and distributing the nodes on the drawing area, 
- +but are unable to consider edge crossings and thus often produce many crossings even for planar graphs. 
-**Expected result:** A new layout module implementing a force-directed algorithm that preserves a given planar embedding, e.g. Bertault's algorithm. +A good alternative is to combine planar drawing methods with force-directed algorithms, 
- +but this requires a force-directed layout algorithms that preserves the planar embedding of the graph. 
-**Rationale:** Combining planar and force-directed methods in order to achieve aesthetically pleasing drawings with few crossings is subject of current research. +Bertault's algorithm is such a force-directed layout algorithm. Aim of this project is to implement Bertault's algorithm and to combine it with OGDF's planar drawing algorithms.
- +
-**Literature:** +
-  * F. Bertault: [[http://dx.doi.org/10.1016/S0020-0190(00)00042-9|A force-directed algorithm that preserves edge-crossing properties]], Inf. Process. Lett. 74(1-2), 2000, pp. 7-13. +
- +
-**Prerequisites:** C++, Subversion, good knowledge in algorithms and data structures +
- +
-**Skill level:** medium+
 +**Student:** //Smit Dilashkumar Sanghavi// (DA-IICT, India)\\
**Mentor:** [[http://ls11-www.informatik.uni-dortmund.de/staff/klein|Karsten Klein]] **Mentor:** [[http://ls11-www.informatik.uni-dortmund.de/staff/klein|Karsten Klein]]
 +**Links:** [[:gsoc2012-ideas#bertault_layout|Original Project Idea]]
-==== Orthogonal Grid Layout ==== +===== Further Resources =====
- +
-**Brief description:** Though OGDF contains a state-of-the-art general orthogonal layout algorithm (in particular designed for nodes with different sizes), it lacks traditional grid-based methods. Many algorithms and data structures required for these methods are already contained in OGDF, e.g., min-cost flow, orthogonal representations, compaction algorithms. Aim of this project is to implement the classical Giotto algorithm by Tamassia et al. and the alternative quasi-orthogonal approach by Klau and Mutzel. The latter approach allows edges to be routed non-orthogonally around a vertex, so that vertices with degree greater than 4 can be placed on a single grid point, whereas the former expands high-degree vertices so that they span several grid points. +
- +
-**Expected result:** New grid layout modules for Giotto and quasi-orthogonal layout. +
- +
-**Rationale:** Orthogonal grid layout algorithms are classical planar graph drawing methods. Since our goal is to also provide a wide variety of established graph drawing methods in OGDF, adding these algorithms is desirable. +
- +
-**Literature:** +
-  * G. W. Klau, P. Mutzel, [[http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-013|Quasi-orthogonal drawing of planar graphs]], Technical Report MPI-I-98-1-013, Max-Planck-Institut für Informatik, 1998. +
-  * R. Tamassia, G. Di Battista, C. Batini, [[http://dx.doi.org/10.1109/21.87055|Automatic graph drawing and readability of diagrams]], IEEE Trans. Syst. Man Cybern. 18(1), 1988, pp. 61–79. +
- +
-**Prerequisites:** C++, Subversion, good knowledge in graph algorithms (in particular min-cost flow) and planar graphs +
- +
-**Skill level:** medium to high +
- +
-**Mentor:** [[http://ls11-www.informatik.uni-dortmund.de/staff/klein|Karsten Klein]] +
- +
- +
-==== Parallelization of Layout Algorithms ==== +
- +
-**Brief description:** Several OGDF algorithms contain procedures that can be parallelized in a straight-forward way. E.g., our implementation of the crossing minimization steps in the planarization approach and Sugiyama's algorithm perform several runs (and then take the best result), which can be run in parallel, or some algorithms handle connected components independently. The aim of this project is to identify and parallelize these algorithms. The challenging part of this project is to keep the additional memory consumption for the parallel running threads low and to achieve a good speed-up. +
- +
-**Expected result:** Automatic parallel execution of suitable parts of layout algorithms (i.e., system independent (OGDF already provides some classes for threads etc. to achieve this) and the implementation automatically decides how many threads should be started). +
- +
-**Rationale:** Multicore processors are now available everywhere, hence exploiting their true power by parallelizing algorithms is an important goal for algorithm libraries. +
- +
-**Prerequisites:** C++, Subversion, experience with parallel programming for multicore architectures (like OpenMP, native threads on Linux or Windows) +
- +
-**Skill level:** high +
- +
-**Mentors:** [[http://ls11-www.informatik.uni-dortmund.de/staff/gutwenger|Carsten Gutwenger]], [[http://www.informatik.uni-koeln.de/ls_juenger/people/mallach/|Sven Mallach]] +
- +
- +
-==== Embedding Constraints ==== +
- +
-**Brief description:** Embedding constraints allows us to compute planar embeddings satisfying certain conditions like hierarchically grouping the edges incident to a vertex and forces a certain order of the incident edges around a vertex. Gutwenger et al. presented an algorithm to test if a graph can be embedded subject to a given set of embedding constraints (//ec-planarity//), and an extension of the planarization approach for drawing graphs (in particular a crossing minimization procedure that respects embedding constraints). The aim of this project is to implement the ec-planarity test, and possibly to extent the planarization approach for graphs with embedding constraints. OGDF provides many advanced algorithms and data structures that will be needed for implementing these algorithms (e.g., decomposing a graph into its bi- and triconnected components, SPQR-trees, a planarization approach for usual graphs). +
- +
-**Expected result:** A suitable representation for embedding constraints, an ec-planarity test, and possibly a crossing minimization module for graphs with embedding constraints. +
- +
-**Rationale:** Real-world graph drawing problems frequently impose certain constraints on the drawing. Embedding constraints cover some of these constraints, in particular when certain edges around a vertex must appear in a fixed, clockwise order. Hence, implementing this approach may lead to a better acceptance of the powerful planarity-based drawing methods in practice. +
- +
-**Literature:** C. Gutwenger, K. Klein, P. Mutzel, [[http://jgaa.info/accepted/2008/GutwengerKleinMutzel2008.12.1.pdf|Planarity Testing and Optimal Edge Insertion with Embedding Constraints]],  J. Graph Algorithms Appl. 12(1), 2008, pp. 73-95. +
- +
-**Prerequisites:** C++, Subversion, good knowledge in algorithms, data structures, and planar graphs +
- +
-**Skill level:** high +
- +
-**Mentors:** [[http://ls11-www.informatik.uni-dortmund.de/staff/gutwenger|Carsten Gutwenger]], [[http://ls11-www.informatik.uni-dortmund.de/staff/klein|Karsten Klein]] +
- +
- +
-==== Simplified Orthogonal Layout ==== +
- +
-**Brief description:** The current implementation of orthogonal layout is quite complicated, since it also contains a lot of code which is only required for drawing UML diagrams. This makes the code confusing and unnecessarily bloated if you're only interested in usual graphs. Therefore, the aim of this project is to develop a clean implementation of orthogonal layout for usual graphs, by reusing the necessary parts of the current implementation. +
- +
-**Expected result:** Implementation of a new layout module for orthogonal layout of undirected graphs with a clear structure. +
- +
-**Prerequisites:** C++, Subversion, good knowledge in algorithms and data structures +
- +
-**Skill level:** medium to high +
- +
-**Mentors:** [[http://ls11-www.informatik.uni-dortmund.de/staff/klein|Karsten Klein]], [[http://www.informatik.uni-koeln.de/ls_juenger/people/mallach/|Sven Mallach]] +
- +
- +
-==== Multi-Layer Crossing Minimization ==== +
- +
-**Brief description:** OGDF's Sugiyama algorithm for hierarchical graphs implements the classical approach for crossing minimization, where crossings are iteratively (//layer-by-layer sweep//) minimized between neighbored layers (//two-layer crossing minimization//). However, recently this approach has been extended to consider "more layers at once" and to even allow nodes to change their layer if this saves crossings. Experimental results show that this approach can lead to much better results. Aim of this project is to implement these algorithms for k-layer crossing minimization and to make them available in OGDF's Sugiyama layout algorithm. +
- +
-**Expected result:** An extended ''SugiyamaLayout'' module that supports general, k-layer crossing minimization modules (layer-by-layer sweep could be one such module) and modules that implement global crossing minimization algorithms (see literature below). +
- +
-**Rationale:** OGDF's implementation of the Sugiyama framework is very flexible and provides various implementations for the different phases of the algorithm. Moreover, OGDF contains a new, sophisticated approach for drawing hierarchical graphs which is based on upward planarization. The latest scientific results show that, although upward planarization achieves the best results, more global k-level crossing minimization heuristics can come close and are much easier to implement. This project will enable us to integrate new algorithms and to perform a fair evaluation of the different approaches, which is of high interest both in theory and practice. +
- +
-**Literature:** +
-  * C. Bachmaier, F. J. Brandenburg, W. Brunner, F. Hübner, [[http://www.jgaa.info/accepted/2011/BachmaierBrandenburgBrunnerHubner2011.15.5.pdf|Global k-Level Crossing Reduction]], J. Graph Algorithms and Appl. 15(5), 2011, pp. 631-659. +
-  * C. Bachmaier, W. Brunner, A. Gleißner, [[http://www.infosun.fim.uni-passau.de/~chris/down/MIP-1103.pdf|Grid Sifting: Leveling and Crossing Reduction]], Technical Report MIP-1103, University of Passau, 2011. +
- +
-**Prerequisites:** C++, Subversion, good knowledge in algorithms and data structures +
- +
-**Skill level:** medium to high +
- +
-**Mentor:** [[http://ls11-www.informatik.uni-dortmund.de/staff/gutwenger|Carsten Gutwenger]] +
- +
- +
-==== OGDF Command Line Tool ==== +
- +
-**Brief description:** Implement a tool that allows the user to apply OGDF layout algorithms from the command line using a file-based interface. It shall be possible to select the layout algorithm and adjust its options; the graph shall be passed in GML and/or OGML. +
- +
-**Expected result:** The tool should support at least the most common OGDF layout algorithms and options that are important for the user (e.g., adjusting spacing between nodes, general behavior of the layout algorithm) and should run under all systems supported by OGDF (Windows, Linux, MacOS).  +
- +
-**Rationale:** OGDF is originally designed as a C++ library and hence using its layout algorithms requires to link against the OGDF library. However, for many applications (e.g., programs written in another programming language) it would be easier to have a simple (but powerful) file-based interface. With this command line tool, we want to extend the applicability of OGDF. +
- +
-**Prerequisites:** C++, Subversion +
- +
-**Skill level:** medium +
- +
-**Mentor:** [[http://ls11-www.informatik.uni-dortmund.de/staff/gutwenger|Carsten Gutwenger]] +
- +
- +
-==== Viewer for Large Graphs ==== +
- +
-**Brief description:** Implement a graph viewer that can display large graphs (e.g., graphs with 100,000 nodes and more). The viewer shall be optimized for performance (i.e., restricted formatting of nodes, edges, etc., straight-line edges) and support the following operations: Load a graph in GML/OGML file format (maybe also some simple file formats), panning, zooming, calling suitable OGDF layout algorithms. +
- +
-**Expected result:** A cross-platform stand-alone tool, preferably written in C++ using OpenGL. +
- +
-**Rationale:** Though there is a variety of graph editors and viewers around, only few can handle larger graphs, let alone huge graphs with 100,000 nodes and more. On the other hand, OGDF contains algorithms (like ''FMMMLayout'' and ''FastMultipoleMultilevelEmbedder'') which can draw such huge graphs within seconds. This tool shall give us the possibility to test and evaluate these algorithms, and allow OGDF's users to easily display their large and huge graphs. +
- +
-**Prerequisites:** C++, OpenGL, good knowledge in graphics programming +
- +
-**Skill level:** medium+
-**Mentors:** [[http://ls11-www.informatik.uni-dortmund.de/staff/gutwenger|Carsten Gutwenger]], [[http://www.informatik.uni-koeln.de/ls_juenger/people/gronemann/|Martin Gronemann]]+  * **[[https://groups.google.com/group/ogdf|OGDF Mailing List]]** 
 +  * **[[gsoc-faq|FAQ for potential GSoC students:]]** This FAQ is a collection of information for students interested in one of our projects.  
 +  * **[[gsoc2012-ideas|Project Ideas Page:]]** The project ideas we proposed for GSoC 2012.
 
gsoc2012.1332152957.txt.gz · Last modified: 2012/03/19 11:29 by carsten
This page is driven by DokuWiki