Chair of
Computer Science I
Algorithms, Complexity and Knowledge-Based Systems
Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition
This page contains the source code and test data for our experiments in the following paper:- Fabian Lipp, Alexander Wolff, Johannes Zink: Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. In: E. Di Giacomo, and A. Lubiw (eds.) Graph Drawing and Network Visualization. pp. 52-59. Springer International Publishing (2015)
- Fabian Lipp, Alexander Wolff, Johannes Zink: Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. Algorithms. 2016; 9(3):53
Source code
Our Java source code is available for download in java.tar.gz. Necessary libraries can be installed automatically using Apache Ant and Apache Ivy. You need Java 8 to compile the code. To use our build script Apache Ant must be installed, additionally.
Run the following commands to compile the code (in the
graphdrawing directory):
-
ant install-ivy
to download Apache Ivy, if not installed on your system -
ant resolve
to download necessary libraries -
ant build-jung-libs
to compile the patched JUNG library -
ant
to compile the actual source code and pack the binaries together with needed libraries into a JAR file
dist directory, which
can be run by java -jar dist/graphdrawing-20160128.jar.
We integrated some improvements into the source code after publishing the conference paper. So the current program could perform differently compared to the results stated in the paper. You can find a short description on how to use the program in howto.pdf.
Data sets
The following list contains the data sets that we used for our experiments.
Our Java program expects them inside the data/graphs subdirectory.
Each data set contains a specification file in JSON format, which
describes some metadata used to process this it.
These specification files are expected in
data/graphs/specifications.
The data sets and specification files are put into the right
directories when you simply extract the downloaded archives in the same
directory as the Java source code.
The graph data itself can be in different formats, which is
automatically detected when accessing the data set from the Java
program.
In the following table, the labels DSx specify the name used to denote the data set in the journal version of the paper.
| Label | Filename | Description | #Graphs | Filesize |
|---|---|---|---|---|
| DS1 | rome | Contains the Rome graphs, a widely used benchmark set for graph drawing algorithms. Each of the graphs has between 10 and 100 vertices. Data was downloaded from http://graphdrawing.org/data.html. | 11528 | 3.6 MiB |
| DS2 | north | Contains the North graphs, a subset of the AT&T graph collection. Each of the graphs has between 10 and 100 vertices. Data was downloaded from http://graphdrawing.org/data.html. | 1277 | 367 KiB |
| lin40 | This set (denoted by ii) in the conference paper) contains 40 random graphs which were generated by the EppsteinPowerLawGenerator in JUNG. The graphs have 2,500, 5,000, …, 100,000 vertices and approximately 2.5 as many edges. We considered only the largest connected component of each graph. | 40 | 45 MiB | |
| DS3 | journal_rand1 | A set of 40 random graphs that we generated using the EppsteinPowerLawGenerator in JUNG, which yields graphs whose structure is similar to Web graphs. We considered only the largest connected component of each generated graph. We generated instances with 2,500, 5,000, 7,500, …, 100,000 vertices and approximately 2.5 times as many edges. | 40 | 45 MiB |
| DS4 | journal_rand2 | A set of 40 random graphs generated as (DS3). We fixed the number of vertices to 5,000 and generated approximately 1, 1.5, 2, …, 20, 20.5 times as many edges to be able to test graphs with different densities. | 40 | 15 MiB |
| journal_rand3 | A set of 40 random graphs generated as (DS3). We fixed the number of vertices to 1,000 and the number of edges to approximately 2,500. | 40 | 697 KiB | |
| DS5 | journal_rand4 | A set of 40 random graphs generated as (DS3). We fixed the number of vertices to 1,000 and the number of edges to approximately 10,000. | 40 | 2.5 MiB |
License
The package includes source code from the following libraries:-
JUNG 2
(guava branch from
https://github.com/jrtom/jung)
License according to http://jrtom.github.io/jung/:The license below is the BSD open-source license. See http://www.opensource.org/licenses/BSD-3-Clause with:
= Regents of the University of California and the JUNG Project = University of California = 2003 It allows redistribution of JUNG freely, albeit with acknowledgement of JUNG's being a component in the redistributed software. However, we would greatly appreciate it if you can let us know what you are doing with JUNG. -- THE JUNG LICENSE Copyright (c) 2003-2015, Regents of the University of California and the JUNG Project All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. * Neither the name of JUNG, nor that of the University of California, nor the names of its contributors, may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -
d2s-tools from Data2Semantics
(https://github.com/Data2Semantics/d2s-tools)
The MIT License (MIT) Copyright (c) 2013 Data2Semantics Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.