Development

Plotting tools for networks, part I

In the first two installments in this series on plotting tools (which covered gnuplot and matplotlib), we introduced tools for creating plots and graphs, and used the terms interchangeably to refer to the typical scientific plot relating one set of quantities to another. In this article we use the term "graph" in its mathematical, graph-theory context, meaning a set of nodes connected by edges. There is a strong family resemblance among graph-theory graphs, flowcharts, and network diagrams—so much so that some of the same tools can be coerced into creating all of them. We will now survey several mature free-software systems for building these types of visualizations. At least one of these tools will likely be useful if you are ever in need of an automated way to diagram source-code interdependencies, make an organizational chart, visualize a computer network, or organize a sports tournament. We will start with a graphical charting tool and a flexible graphing system that can easily be called by other programs.

Flowcharting with Dia

A flowchart is a diagram of a process, algorithm, workflow, or something similar. Flowcharts for different fields often employ a specialized graphical language of symbols that represent entities common to the field. For example, a circuit diagram is a type of flowchart that uses special symbols for diodes, resistors, and other circuit elements. There are flowchart languages for logic circuits, chemical engineering, software design, and much more.

Dia, a free (in all senses) diagram editor for Linux and other systems, comes with symbol libraries encompassing all of these examples, plus many others, both common and exotic. And, if that's not sufficient, the program allows you to make your own symbols.

Dia is a GUI program that uses the GTK+ libraries. You use it somewhat like Inkscape or other drawing programs. However, to make effective use of the program you should remember that you are not creating a drawing, but, rather, defining a set of relationships between entities. These relationships are represented by lines and curves (perhaps with arrowheads or labels), and the entities take the forms of the various symbolic shapes we mentioned above, often with their own text labels.

The trick to defining these relationships through the graphical interface is to make the connections in the right way. Since it takes a while to extract these techniques from the documentation, we'll outline the steps here.

After selecting the desired shape from the panel and dragging it out in the canvas to the approximate size you think it should be, immediately press Return and type the text label for the shape. The label will be properly centered, the shape will grow as required to accommodate it, and the label will be permanently attached to the shape and move with it. To connect two entities with a line, draw the line between the centers of the entities; you know you've hit the correct spot when the shape glows yellow.

To attach a text label to a line (such as the "yes" and "no" labels in the screenshot) you need to follow a different procedure: with object snapping turned on, create a text entity using the text tool that looks like a "T", then drag it by its handle, connecting it to the line's attachment point. This point is indicated by a small "x" and is at the center of the line. A red glow will signal that you've made the attachment.

If you've defined all your labels, entities, and connections using these techniques, then you'll be able to move the nodes around at will on the canvas until the chart is neat and easy to follow. The topology of the graph, which carries the actual information in the flowchart, won't change but, by moving things around, you can change a tangle of crossed lines into a neat diagram where the flow is clear.

Dia saves your work in an XML file (a compressed one by default, though there is also an option to save it uncompressed), and can export it into a wide variety of image formats, including vector formats such as SVG.

The program should be available in your package manager. Development is steady but moves at a slow pace, so it's likely you'll get the current version even from a conservative distribution. If you need to, however, you can download sources or binaries from Dia headquarters.

Graphviz: infrastructure for graphs

Dia is a useful and versatile tool for creating and laying out a graph by hand. Sometimes, however, we begin with a (possibly large) set of data that we want to visualize as a network-style graph or flowchart. We may also want to experiment with different types of visualizations or to produce different graph styles that present the same data for different purposes.

Graphviz solves these problems by providing a declarative language, called "dot," that represents nodes and the connections between them as text. The dot language can accommodate a large set of visual and logical attributes of many types of nodes, their relationships, and their interconnections. Nevertheless, it's intuitive, with an easy-to-remember and readable syntax. Here is an almost-minimal example of a dot file that defines a simple graph:

      strict digraph "example" {
        A -> {B C};
        D [shape = box];
        C -> D;
        D -> C [color = blue];
      }

The keyword strict at the beginning means that no redundant edges are allowed; a digraph is a directed graph (meaning that the edges have a direction, often represented by an arrowhead at the end and, perhaps, at the beginning). The second line says that node A is connected with both nodes B and C, in the direction starting from A. The next line declares a new node called D and defines an attribute that specifies how D should be drawn. Then, we declare that C is connected to D, and that D is connected back to C. This last edge has an attribute specifying its color.

The Graphviz infrastructure also comes with several layout engines that interpret dot files and produce the actual graphs. Some of the engines are for directed graphs, some are for undirected graphs, and some handle both types. The problem of taking a graph specification—with perhaps thousands of nodes—and producing a usable visual representation is not trivial, and is the subject of continuing research. Each of Graphviz's engines has a mathematical theory [PDF] behind it, and each will generate a different type of graph.

For simple directed graphs such as the one represented in the dot file above, the engine called "dot" is usually best. We invoke it on the command line:

    dot -o simpledot.png -Tpng simpledot.dot

This generates a PNG output file (one of many choices), using simpledot.dot as the graph specification. If we store the code snippet above into this file, we get the output shown here:

It's clear how the definitions of nodes and edges have been translated into a picture. If we apply a different layout engine to the same dot file, for example fdp:

    fdp -o simpledot.png -Tpng simpledot.dot

we get the same information, but depicted in a different style:

A brief summary of the various layout engines that come with the system is provided in the dot man page. The dot engine produces a simple, hierarchical layout, whereas fdp, sfdp, and neato all treat the edges as springs. That is, they attempt to arrive at a neat arrangement by starting with a random layout and allowing the system to relax to a minimum energy configuration. The different engines will produce distinct results, as they are all based on different algorithms.

The use of a language to define graphs means that Graphviz can serve as the graphical engine for other systems or programs; they merely need to format their output in the dot language. There are many examples of this. Snakefood is a program that analyzes Python programs and determines their dependencies. You can point it at a directory of Python files and it will return the interdependencies among the files and to external modules, in its own format, which is a collection of Python tuples.

This output can be piped to a Snakefood utility that translates it into dot, which can then be processed by any of the Graphviz engines that can handle directed graphs—usually the dot engine is the best choice. Here is the result of applying the process to a directory holding the files for the bsddb package, an interface to the Berkeley DB library:

The dot file corresponding to this graph is available for further exploration.

You can also use Graphviz without using the dot language directly, by using one of its programming language interfaces. For example, the pygraphviz library for Python allows you to define a graph object, add nodes and edges to it, and create a graph image by calling the draw() method on the object. The Graphviz layout engine is selected with an argument passed to the draw() method.

We've barely scratched the surface of what Graphviz can do. Facilities for subgraphs, record nodes, adding labels in HTML, and more make this a general-purpose powerhouse for any type of automated graph creation. Graphviz is free software (as is Snakefood) and should be available through your package manager.

Stay tuned

In part 2 of this article we'll continue our survey of network graphing tools by looking at two sophisticated libraries. One is used within the LaTeX document-processing system to allow you to embed diagrams into your books and papers. The other is used with Python to allow you to explore the properties of general networks and plot the results.

Comments (31 posted)

Quotes of the week

— Jason Self

— Charles Stanhope, in reply to Jason.

Comments (2 posted)

KDE Ships Plasma 5.3 Beta

A beta version of Plasma 5.3 has been released. This release features enhanced power management, better Bluetooth capabilities, improved Plasma widgets, a tech preview of Plasma Media Center, big steps towards Wayland support, and lots of bug fixes.

Comments (19 posted)

Kallithea 0.2 available

Version 0.2 of the Kallithea source-code-management framework has been released. Many changes are included. "Notably, pull requests system have been improved, making contributing changes more robust. The visual appearance has also been refined: modern font-based symbolic icons from FontAwesome and GitHub Octicons have replaced the previously used bitmap icons, and revision graphs are now drawn with HiDPI display support."

Full Story (comments: none)

Geoclue 2.2.0 released

GeoClue 2.2.0 has been released. Among the many changes are speed and heading reporting on each location update, GPS fixes, and fixes for GeoIP location on machines without WiFi hardware.

Full Story (comments: none)

KDE Frameworks 5.9.0 released

KDE FRameworks version 5.9.0 is now available. Included are a new ModemManagerQt module, new features for KActivities, KIO, and KIconThemes, and bugfixes for many other modules.

Full Story (comments: none)

Development newsletters from the past week

• What's cooking in git.git (April 14)
• LLVM Weekly (April 13)
• OCaml Weekly News (April 14)
• OpenStack Community Weekly Newsletter (April 10)
• Perl Weekly (April 13)
• PostgreSQL Weekly News (April 12)
• Python Weekly (April 9)
• Ruby Weekly (April 9)
• This Week in Rust (April 13)
• Tor Weekly News (April 8)
• Tor Weekly News (April 15)
• Wikimedia Tech News (April 13)

Comments (none posted)

Turon: Fearless Concurrency with Rust

Aaron Turon has posted a lengthy introduction to concurrency in the Rust programming language. "Every data type knows whether it can safely be sent between or accessed by multiple threads, and Rust enforces this safe usage; there are no data races, even for lock-free data structures. Thread safety isn't just documentation; it's law."

Comments (23 posted)

Hubička: Link time and inter-procedural optimization improvements in GCC 5

Jan Hubička has posted a lengthy discussion of the optimization improvements found in the upcoming GCC 5.0 release. "Identical code folding is a new pass (contributed by Martin Liška, SUSE) looking for functions with the same code and variables with the same constructors. If some are found, one copy is removed and replaced one by an alias to another where possible. This is especially important for C++ code bases that tend to contain duplicated functions as a result of template instantiations."

Comments (10 posted)

The Document Liberation, one year after

The Document Foundation's project Document Liberation looks at its progress during the past year. "During 2014, members of the project released a new framework library, called librevenge, which contains all the document interfaces and helper types, in order to simplify the dependency chain. In addition, they started a new library for importing Adobe PageMaker documents, libpagemaker, written as part of Google Summer of Code 2014 by Anurag Kanungo. Existing libraries have also been extended with the addition of more formats, like libwps with the addition of Microsoft Works Spreadsheet and Database by Laurent Alonso. He is now working on adding support for Lotus 1-2-3, which is one of the most famous legacy applications for personal computers. Laurent has also added support for more than twenty legacy Mac formats to libmwaw."

Full Story (comments: 4)