<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>Graph::Easy - Manual - Layouter</title>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<meta name="MSSmartTagsPreventParsing" content="TRUE">
<meta http-equiv="imagetoolbar" content="no">
<link rel="stylesheet" type="text/css" href="../base.css">
<link rel="stylesheet" type="text/css" href="manual.css">
<link rel="Start" href="index.html">
<link href="http://bloodgate.com/mail.html" rev="made">
<!-- compliance patch for microsoft browsers -->
<!--[if lt IE 7]><script src="http://bloodgate.com/ie7/ie7-standard-p.js" type="text/javascript"></script><![endif]-->
</head>
<body bgcolor=white text=black>
<a name="top"></a>
<div class="menu">
<a class="menubck" href="index.html" title="Back to the manual index">Index</a>
<p style="height: 0.2em"> </p>
<a class="menuext" href="overview.html" title="How everything fits together">Overview</a>
<a class="menucur" href="layouter.html" title="How the layouter works">Layouter</a>
<a class="menuind" href="#overview" title="Overview">Overview</a>
<a class="menuind" href="#cells" title="Cells">Cells</a>
<a class="menuind" href="#ports" title="Cells">Ports</a>
<a class="menuind" href="#edges" title="Edge pices">Edges</a>
<a class="menuind" href="#crossings" title="Edge crossings">Crossings</a>
<a class="menuind" href="#joints" title="Edge joints">Joints</a>
<a class="menuind" href="a-star.html" title="A* algorithm (pathfinding)">A*</a>
<a class="menuext" href="hinting.html" title="Generating specific layouts">Hinting</a>
<a class="menuext" href="output.html" title="Output formats and their limitations">Output</a>
<a class="menuext" href="syntax.html" title="Syntax rules for the text format">Syntax</a>
<a class="menuext" href="attributes.html" title="All possible attributes for graphs, nodes and edges">Attributes</a>
<a class="menuext" href="errors.html" title="Error codes and explanations">Errors</a>
<a class="menuext" href="faq.html" title="Frequently Asked Questions and their answers">F.A.Q.</a>
<a class="menuext" href="tutorial.html" title="Tutorial for often used graph types and designs">Tutorial</a>
<a class="menuext" href="editor.html" title="The interactive interface">Editor</a>
</div>
<div class="right">
<h1>Graph::Easy - Manual</h1>
<h2>Layouter</h2>
<div class="text">
<p>
If you haven't done so, please read the <a href="overview.html">Overview</a> first.
</p>
<p>
Graph::Easy's layouter is responsible for converting a (internal) graph representation into
a specific layout. Here are two example layouts produced from the same graph:
</p>
<p>
<img src="img/example1.png" alt="Example layout of simple graph" style="float: left">
<pre class="graph">
+---+ +---+ +---+
| A | --> | C | --> | D |
+---+ +---+ +---+
|
|
v
+---+
| E |
+---+
</pre>
</p>
<div class="clear"></div>
<p>
The layouter works mostly automatic and this chapter explains some of its
inner workings. It might explain why certain outputs are generated in
the way they are, and will also help you understand how to better influence
the generated layout, which is discussed in the next
<a href="hinting.html">chapter</a>.
</p>
<p>
Note that the two output formats <code>as_txt()</code> (textual description) and
<code>as_graphviz()</code> (graphviz code) are not generated by the layouter,
they are merely dumps of the graph. In the case of graphviz code,
the actual layout will be performed by an external program, like "dot",
"neato" etc.
</p>
<a name="overview">
<h3>Overview</h3>
</a>
<p>
To generate a specific layout, the Graph::Easy layouter works in three phases:
</p>
<ul>
<li>
First, it categorizes the nodes and sorts them into groups according
to their group information, as well as their rank.
<li>
Then it creates chains of nodes, starting with nodes with as little incoming edges
as possible, and then progressing to the other nodes. The idea is to find the
longest consecutive chains of nodes as possible.
<li>
In the last phase, the layouter places the individual nodes on a checkered plane,
much like a chess board.
Once a nodes and its successors are placed, it tries to find the paths between the
nodes to generate the edge cells.
</ul>
<p>
The first two stages influence the order how the nodes are processed in the third stage.
<br>
Due to finding the longest chains, the layouter can de-tangle the graph and lay it out
in a straight line, if possible.
<br>
Here are two examples, the first one from pre-v0.24, the second one laid out by v0.25.
You can see the difference the chain-finding code makes :)
</p>
<pre class="wide">
+------------------------------+
v |
+---------+ +--------+ +--------+ +---------+
| Koblenz | <-- | Bonn | --> | Ulm | --> | Bautzen |
+---------+ +--------+ +--------+ +---------+
| | |
| | |
| v |
| +--------+ +--------+ |
+-----------> | Berlin | --> | Kassel | |
+--------+ +--------+ |
^ |
+-----------------------------+
</pre>
<pre class="wide">
+--------------------------------------------+
| v
+------+ +---------+ +---------+ +--------+ +--------+
| Bonn | --> | Ulm | --> | Bautzen | --> | Berlin | --> | Kassel |
+------+ +---------+ +---------+ +--------+ +--------+
| | ^
| | |
| v |
| +---------+ |
+--------> | Koblenz | ----------------------+
+---------+
</pre>
<a name="cells">
<h3>Cells and placement</h3>
</a>
<p>
Unlike other packages, Graph::Easy works on an infinite big checkered board layout.
Here are the first 7x3 cells with their coordinates:
</p>
<pre>
...........................................
: 0,0 : 1,0 : 2,0 : 3,0 : 4,0 : 5,0 : 6,0 :
...........................................
: 0,1 : 1,1 : 2,1 : 3,1 : 4,1 : 5,1 : 6,1 :
...........................................
: 0,2 : 1,2 : 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
...........................................
</pre>
<p>
Each node can occupy one or more cells. Likewise, an edge going from one
node to another can go via one or more cells. However, edges may only go
in straight lines, but not diagonal.
</p>
<p>
Here is an example with two nodes and a short edge. Empty cells are grey, cells occupied
by a node white and edge cells yellow:
</p>
<pre>
...........................................
: 0,0 : 1,0 : 2,0 : 3,0 : 4,0 : 5,0 : 6,0 :
...........................................
:<span class="node">+---+</span>:<span class="edge"> </span>:<span class="node">+---+</span>: : : : :
:<span class="node">| A |</span>:<span class="edge"> --> </span>:<span class="node">| B |</span>: 3,1 : 4,1 : 5,1 : 6,1 :
:<span class="node">+---+</span>:<span class="edge"> </span>:<span class="node">+---+</span>: : : : :
...........................................
: 0,2 : 1,2 : 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
...........................................
</pre>
<p>
Here is the same example with one more edge, this time with multiple cells. The new edge cells are
colored lightblue:
</p>
<pre>
...........................................
:<span class="cell"> </span>:<span class="cell"> </span>:<span class="cell"> </span>: : : : :
:<span class="cell"> +--</span>:<span class="cell">-----</span>:<span class="cell">--+ </span>: 3,0 : 4,0 : 5,0 : 6,0 :
:<span class="cell"> | </span>:<span class="cell"> </span>:<span class="cell"> v </span>: : : : :
...........................................
:<span class="node">+---+</span>:<span class="edge"> </span>:<span class="node">+---+</span>: : : : :
:<span class="node">| A |</span>:<span class="edge"> --> </span>:<span class="node">| B |</span>: 3,1 : 4,1 : 5,1 : 6,1 :
:<span class="node">+---+</span>:<span class="edge"> </span>:<span class="node">+---+</span>: : : : :
...........................................
: 0,2 : 1,2 : 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
...........................................
</pre>
<a name="ports">
<h3>Ports</h3>
</a>
<p>
As you can see from the example above, each <em>cell</em> has four ports, right, bottom, left and top
of it. These directions are labeled East, South, West and North, accodingly. Ports are shown
light purple here:
</p>
<pre>
...........................................
: :<span class="port"> </span>: : : : : :
: 0,0 :<span class="port">North</span>: 2,0 : 3,0 : 4,0 : 5,0 : 6,0 :
: :<span class="port"> </span>: : : : : :
...........................................
:<span class="port"> </span>:<span class="node">+---+</span>:<span class="port"> </span>: : : : :
:<span class="port">West </span>:<span class="node">| A |</span>:<span class="port"> East</span>: 3,1 : 4,1 : 5,1 : 6,1 :
:<span class="port"> </span>:<span class="node">+---+</span>:<span class="port"> </span>: : : : :
...........................................
: :<span class="port"> </span>: : : : : :
: 0,2 :<span class="port">South</span>: 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
: :<span class="port"> </span>: : : : : :
...........................................
</pre>
<p>
So, if a node occupies exactly one cell and one cell has four
ports, then there can only be four edges going from or to this node.
</p>
<p>
That is a serious limitation and to overcome it, nodes can occupy more
than one cell. Nodes are grown automatically to multiple cells when
they need to be bigger than one cell.
</p>
<p>
You can also explicitely specify how many rows/columns a node should at least
have, which is explained in detail in the <a href="hinting.html#size">next chapter</a>.
</p>
<p>
A multi-celled node has more than four ports. To create more strict layouts
it is possible to specifiy at which port an edge should start or end. The
details for that can be found in the <a href="hinting.html#ports">next chapter</a>.
</p>
<a name="edges">
<h3>Edge pieces</h3>
</a>
<p>
There are 11 basic edge cells, e.g. this one goes to eleven :)
</p>
<pre>
.........................
:<span class="edge"> </span>:<span class="edge"> | </span>:<span class="edge"> | </span>: :
:<span class="edge">-----</span>:<span class="edge"> | </span>:<span class="edge">--+--</span>: :
:<span class="edge"> </span>:<span class="edge"> | </span>:<span class="edge"> | </span>: :
.........................
:<span class="edge"> </span>:<span class="edge"> | </span>:<span class="edge"> | </span>:<span class="edge"> </span>:
:<span class="edge"> +--</span>:<span class="edge"> +--</span>:<span class="edge">--+ </span>:<span class="edge">--+ </span>:
:<span class="edge"> | </span>:<span class="edge"> </span>:<span class="edge"> </span>:<span class="edge"> | </span>:
.........................
:<span class="edge"> </span>:<span class="edge"> | </span>:<span class="edge"> | </span>:<span class="edge"> | </span>:
:<span class="edge"> </span>:<span class="edge"> v </span>:<span class="edge"> | </span>:<span class="edge"> | </span>:
:<span class="edge">--+--</span>:<span class="edge">--+--</span>:<span class="edge">->+ </span>:<span class="edge"> +<-</span>:
:<span class="edge"> ^ </span>:<span class="edge"> </span>:<span class="edge"> | </span>:<span class="edge"> | </span>:
:<span class="edge"> | </span>:<span class="edge"> </span>:<span class="edge"> | </span>:<span class="edge"> | </span>:
.........................
</pre>
<p>
Each of these edge pieces can be combined with (up to four) starting points (rendered invisible
for vertical edges, a space for horizontal edges) and (up to four) end points (rendered as an arrow
head). Not all combinations make sense, but they are automatically choosen to make the best
use of the available space.
<br>
Here are some of the possible combinations with an horizontal edge shown:
</p>
<pre>
.........................
:<span class="edge"> </span>:<span class="edge"> </span>:<span class="edge"> </span>:<span class="edge"> </span>:
:<span class="edge"> --> </span>:<span class="edge">---> </span>:<span class="edge"> ----</span>:<span class="edge"> <---</span>:
:<span class="edge"> </span>:<span class="edge"> </span>:<span class="edge"> </span>:<span class="edge"> </span>:
.........................
:<span class="edge"> </span>:<span class="edge"> </span>:<span class="edge"> </span>: :
:<span class="edge"> <-> </span>:<span class="edge"> --- </span>:<span class="edge">-----</span>: :
:<span class="edge"> </span>:<span class="edge"> </span>:<span class="edge"> </span>: :
.........................
</pre>
<p>
In addition, there are now four self-loop edge pieces. These are used on connections running
from one node back to the same node:
</p>
<pre>
.........................
:<span class="edge"> </span>:<span class="edge"> </span>:<span class="edge"> </span>:<span class="edge"> | ^ </span>:
:<span class="edge"> +- </span>:<span class="edge"> -+ </span>:<span class="edge"> </span>:<span class="edge"> +-+ </span>:
:<span class="edge"> | </span>:<span class="edge"> | </span>:<span class="edge"> </span>:<span class="edge"> </span>:
:<span class="edge"> +> </span>:<span class="edge"> <+ </span>:<span class="edge"> +-+ </span>:<span class="edge"> </span>:
:<span class="edge"> </span>:<span class="edge"> </span>:<span class="edge"> v | </span>:<span class="edge"> </span>:
.........................
</pre>
<p>
These four pieces always have exactly one end and one start point on them,
although they can have zero, one or two arrows, depending on whether
the edge is undirected, normal or bidirectional.
</p>
<h3>Edge labels</h3>
<p>
Vertical, horizontal and self-loop edge pieces can also have an attached
label. Where the label appears is automatically selected by they layouter.
</p>
<a name="crossings">
<h3>Edge crossings</h3>
</a>
<p>
Edges can cross themselves, although the layouter tries to avoid this as
much as possible.
</p>
<p>
There are, however, constraints on which edge can cross which and where.
Generally, an edge may cross another edge only at a horizontal or vertical
piece when it has no label.
<br>
Short edges (one cell) do not allow themselves to be crossed.
</p>
<p>
Consider the following forced layout - in praxis, the layouter would not create
such an layout unless forced to do so by blocking the space above the upper
row of nodes:
</p>
<pre>
+----------+ +---------+ +----------+ +----------+
| Koblenz | <.- | Bonn | --> | Ulm | --> | Bautzen |
+----------+ +---------+ +----------+ +----------+
^ : | |
| : +-----------+ |
| v | |
| +---------+ +----------+ | |
| | Berlin | --> | Kassel | | |
| +---------+ +----------+ | |
| ^ | |
+----------------+---------------------------+ |
| |
| |
+--------------------------------+
</pre>
<p>
Depending on which edge was created first, the crossing might
also turn out like this:
</p>
<pre>
+----------+ +---------+ +----------+ +----------+
| Koblenz | <.- | Bonn | --> | Ulm | --> | Bautzen |
+----------+ +---------+ +----------+ +----------+
^ : | |
| : +----------------+--+
| v | |
| +---------+ +----------+ | |
| | Berlin | --> | Kassel | | |
| +---------+ +----------+ | |
| ^ | |
| +--------------------------------+ |
| |
| |
+----------------------------------------------------+
</pre>
<p>
Note the edge from "Ulm" to "Koblenz" crossing the edge from "Bautzen" to "Berlin". A
seemingly much shorter way for it would be to cross the edge from "Bonn" to "Berlin",
but since that is a short edge, it may not be crossed.
</p>
<a name="joints">
<h3>Edge Joints</h3>
</a>
<p>
Whenever two (or more) edges share <b>one common start port</b> (not just one side, like
<code>south</code>), they will split up somewhere along their path.<br>
Likewise, when two or more edges share <b>one common end port</b>, the
edges will join up somewhere on their way to the target node:
</p>
<pre class="graphtext">
[ Potsdam ], [ Mannheim ]
--> { <em>end: back,0;</em> }
[ Weimar ]
--> { <em>start: front,0;</em> } [ Finsterwalde ], [ Aachen ]
</pre>
<div class="clear"></div>
<img src="img/joints.png" alt="Edge joints" title="Example of edge joints" class="float">
<pre class="graph">
+----------+ +--------+ +--------------+
| Mannheim | ------+-> | Weimar | -+-----> | Finsterwalde |
+----------+ | +--------+ | +--------------+
| |
| |
| |
+----------+ | | +--------------+
| Potsdam | ------+ +-----> | Aachen |
+----------+ +--------------+
</pre>
<p>
Please see the <a href="hinting.html#joints">chapter</a> for more details.
</p>
<a name="multicell">
<h3>Multi-celled nodes</h3>
</a>
<p>
Per default, a node is just one cell big. When necessary, the layouter
will grow the node to accomodate the edge connections. You can also
set a minimum size via the <a href="att_nodes.html#node_size">size</a>
attribute.
</p>
<pre>
...........................................
: :<span class="port"> </span>:<span class="port"> </span>: : : : :
: 0,0 :<span class="port">North</span>:<span class="port">North</span>: 3,0 : 4,0 : 5,0 : 6,0 :
: :<span class="port"> </span>:<span class="port"> </span>: : : : :
...........................................
:<span class="port"> </span>:<span class="node">+---------+</span>:<span class="port"> </span>: : : :
:<span class="port">West </span>:<span class="node">| A |</span>:<span class="port"> East</span>: 4,1 : 5,1 : 6,1 :
:<span class="port"> </span>:<span class="node">+---------+</span>:<span class="port"> </span>: : : :
...........................................
: :<span class="port"> </span>:<span class="port"> </span>: : : : :
: 0,2 :<span class="port">South</span>:<span class="port">South</span>: 3,2 : 4,2 : 5,2 : 6,2 :
: :<span class="port"> </span>:<span class="port"> </span>: : : : :
...........................................
</pre>
<pre>
...........................................
: :<span class="port"> </span>:<span class="port"> </span>: : : : :
: 0,0 :<span class="port">North</span>:<span class="port">North</span>: 3,0 : 4,0 : 5,0 : 6,0 :
: :<span class="port"> </span>:<span class="port"> </span>: : : : :
...........................................
:<span class="port"> </span>:<span class="node">+---------+</span>:<span class="port"> </span>: : : :
:<span class="port">West </span>:<span class="node">| |</span>:<span class="port"> East</span>: 4,1 : 5,1 : 6,1 :
:<span class="port"> </span>:<span class="node">| |</span>:<span class="port"> </span>: : : :
.......<span class="node">| A |</span>.........................
:<span class="port"> </span>:<span class="node">| |</span>:<span class="port"> </span>: : : :
:<span class="port">West </span>:<span class="node">| |</span>:<span class="port"> East</span>: 4,2 : 5,2 : 6,2 :
:<span class="port"> </span>:<span class="node">+---------+</span>:<span class="port"> </span>: : : :
...........................................
: :<span class="port"> </span>:<span class="port"> </span>: : : : :
: 0,3 :<span class="port">South</span>:<span class="port">South</span>: 3,3 : 4,3 : 5,3 : 6,3 :
: :<span class="port"> </span>:<span class="port"> </span>: : : : :
...........................................
</pre>
<h3>Pathfinding</h3>
<p>
To find a path from one node to another (or even the same node), the layouter uses two main approaches:
</p>
<ul>
<li>a heuristic (aka hack). For the following cases this heuristic kicks in:
<ul>
<li>When the other node can be reached in a straight way
<li>When it can be reached with at most one bend in the path
<li>When the "other" node is actually the same node and thus the path is a self-loop
</ul>
<li>For all other cases, and when the heuristic couldn't find a path, a general algortihm called <b>A*</b> is used.
</ul
<p>
Please see the page about the <a href="a-star.html">A* algorithm</a> for further details on pathfinding.
</p>
</div><div class="text next">
<p>
Now that you know some details about how the layouter works, you are ready to read the next
<a href="hinting.html">chapter</a> about generating specific layouts.
</p>
</div>
<div class="footer">
Page created <span class="date">2005-08-07</span> by <a href="http://bloodgate.com/mail.html">Tels</a>.
Last update: <span class="date">2007-09-09</span>
</div>
</div> <!-- end of right cell -->
</body>
</html>