LEDA offers the class window, which represents a platform independent interface for graphical input and output of fundamental geometric objects. This class helps to visualize and animate algorithms. We will not delve into this very powerful class here; rather, we describe the usage of the derived class GraphWin, which combines the possibilities of the classes graph and window.

An object of type GraphWin is simultaneously a window, a graph, and a (two dimensional) representation of this graph in this window. This class can be used, among other things, for constructing graphs by hand with a mouse and visualizing them, for storing graphs that have been constructed in this way, and for reading in such graphs, or for visualizing the results of a graph algorithm. Figure 5.8 shows a GraphWin.

Figure 5.8. Editing graphs with GraphWin

The following program opens such a GraphWin. For the rest of the section, it is useful to compile and start this program, and then to follow the usage notes on the screen. It is worthwhile to experiment a little with the user interface!

#include <LEDA/graph.h>
#include <LEDA/graphwin.h>

using leda::graph;
using leda::GraphWin;
using leda::window;
using std::cout;


int main()
{
  graph G;

  GraphWin gw(G, 500, 500, "Graph Drawer");
  gw.display(window::center, window::center);
  while(gw.edit()) { 
    // here we will fill in code for algorithms on G later
  }
}

We will deal with the interface of the class GraphWin later in this section. First, let us make familiar with the graphical user interface.

The left mouse button is used most frequently while editing in a GraphWin: A single click on the background creates a new node. A single click on a node selects this node as the source of a new edge to be inserted. The next click defines the target node of the new edge; this is either an already existing node or a new node (if the background is clicked). Before the target node is defined, bends may be inserted into the edge by clicking the middle mouse button. (On systems with only two mouse buttons, one has to press the ALT button and simultaneously click the left mouse button.) The creation of a new edge can be canceled by clicking the right mouse button.

Nodes can be moved by pulling them. For this, the node must be selected with the left mouse button and the button must be constantly pressed.

A double click on a node or an edge opens a dialogue box for changing the attributes of this node or this edge. These attributes essentially define the shape and the labeling; we will briefly discuss them later.

A click with the right mouse button on a node or on an edge opens a context menu. This makes it possible. among other things, to delete this node or this edge.

In the default menu of a GraphWin, we find the entries File, Edit, Graph, Layout, Window, Options, Help, Undo, Redo, and done.

The menu entry Help shows a help text that describes the interactive usage of GraphWin in detail.

For a start, only the menu File is important to us. This menu offers operations for reading and storing graphs. The entry Exit of this menu terminates the GraphWin.

Now let us enter the graph depicted in Figure 5.8 and store it via File → Save → gw_graph. This menu entry chooses the standard format as the representation. We chose graph.gw as the file name.

This creates a file in the so-called standard format. These files have the file name extension .gw. The file just created starts with the following lines:

LEDA.GRAPH
void
void
-1
3
|{}|
|{}|
|{}|
5
1 2 0 |{}|
1 2 0 |{}|
1 3 0 |{}|
2 3 0 |{}|
3 3 0 |{}|
# version string
GraphWin 1.400000
# scaling  wxmin  wymin  wxmax  wymax
0.9807129 -10 -3.6875 499.7656 460.1992
# node label font and size
0 13.25391
# edge label font and size
0 18.35156
# node index format
%d
# edge index format
%d
# multi-edge distance
4.078125
# 
...
(the remaining lines are left out; they contain further 
information about position, shape, etc. of nodes and edges)

Without describing this format in detail, we look briefly at the individual sections of this file. The four sections at the beginning could easily be created and edited with an ordinary text editor; doing so, a graph can be specified by hand without a GraphWin or as the output of a program. The order of the sections is as follows:

We want to modify this file a little by hand and demonstrate how a graph that is “burnt to disc” can be read in again and visualized.

We modify the file by hand in a text editor as follows:

LEDA.GRAPH
string
int
-1
4
|{Anja}|
|{Sabine}|
|{Bettina}|
|{Sibylle}|
6
1 2 0 |{42}|
1 2 0 |{666}|
1 3 0 |{32168}|
2 3 0 |{4711}|
3 3 0 |{1001}|
4 1 0 |{31415927}|

That is, we have removed the layout section completely, specified a GRAPH<string,int>, inserted a node and an edge, provided the nodes with the names of nice, female human beings (for example, with the names of the ones that support us every day with their work in our library), and written some insignificant integer numbers onto the edges.

We read in the graph thus specified with a call

G.read(filename);

from the file filename. Conversely, a graph can be written to the file filename by a call

G.write(filename);

If the file name is left out, read() reads from standard input and write() writes to it.

Now again, we want to visualize the graph with the help of a GraphWin. For this, we declare a GraphWin on G and tell it to display the so-called data labels in the nodes and on the edges. Additionally, we tell it that the nodes should be rectangular instead of circular, and we also set the size of these rectangles.

#include <LEDA/graph.h>
#include <LEDA/graphwin.h>
#include <LEDA/string.h>

using leda::GRAPH;
using leda::GraphWin;
using leda::window;
using leda::string;
using std::cout;


int main()
{
  GRAPH<string, int> G;

  int err;
  if((err = G.read("GraphData/graph_modif.gw"))) {
    cout << "Error " << err << " occured while reading .gw file.\n";
    exit(1);
  }

  GraphWin gw(G, 500, 500, "Graph Visualizer");

  gw.set_node_label_type(leda::data_label);
  gw.set_edge_label_type(leda::data_label);
  gw.set_node_shape(leda::rectangle_node);
  gw.set_node_width(100);
  gw.set_node_height(30);

  gw.display(window::center, window::center);
  while(gw.edit()) {
  }
}

A window opens. Because we have removed all layout information, we have to tell GraphWin to calculate a new layout. This is done, for example, by Layout → Simple Layouts → Circular Layout. GraphWin then creates the layout shown in Figure 5.9. Maybe we have to “straighten out” this layout slightly by hand.

Figure 5.9. Visualizing graphs with GraphWin

The method read() returns 1 if the given file does not exist, 2 if the node type or the edge type of the GRAPH does not match with the type specified in the file, 3 if the file does not code a graph, and 0 if everything is fine.

The node and edge attributes define how the nodes and edges are drawn. These attributes can be set by hand (with a double click on a node, for example) or with the corresponding set-methods of the programming interface. We used the latter in the program above to display the nodes as rectangles and to make visible the information associated to the nodes and edges.

We briefly list the most important node and edge attributes here (there are more). For further information, especially on the so-called user coordinate system and on the specification of color values, see the manual pages of the classes GraphWin, window, color and point. We will dwell on the user coordinate system in Section 5.3.8.

The most important node attributes are the following:

The most important edge attributes are the following:

The class GraphWin has a very powerful interface with many operations. We discuss only the most important of them here; they shall enable us to visualize the results of graph algorithms.

A GraphWin always has an associated graph G and an associated window W. Both may be specified or left out in the constructor of GraphWin. If G or W are not specified, GraphWin uses a (private) instance of its own.

The constructor that we typically use is

GraphWin gw(G, width, height, label);

That is, we additionally define the width and the height, and give a label to the window frame.

In this constructor, G may also be a GRAPH. In this case, every node and every edge has an associated data label, which can be displayed by GraphWin; this data label corresponds to the value associated to a node (an edge) in the GRAPH.

A GraphWin is opened and displayed by a call

gw.display(x, y);

This makes the window appear on the screen with its upper corner at pixel position (x,y).

A call

gw.display(window::center, window::center);

centers the window on the screen.

The interactive interface is started with

gw.edit();

Now the graph associated to gw can be edited. The editing process is terminated as soon as done is pressed or File → Exit is selected. In the first case, the method edit() returns the value true; in the second case, it returns false.

Thereby, the edit-and-run scheme for interactive testing of graph algorithms can be realized with a simple while loop: In an iterative process, first a graph is created in a GraphWin, then done is pressed, an algorithm runs on the graph just input, the result of the algorithm is visualized, the graph is edited in the GraphWin again, and so on. The basic shape of the scheme is always as follows:

while(G.edit()) {
  // let a graph algorithm run on G
  ...
  // visualize the results of the algorithm
  ...
}

The loop is left as soon as the user chooses File → Exit.

For visualizing the results, it is often necessary to change the attributes of certain nodes and edges. For example, after a call of BFS(), the edges that specify the predecessor of every reached node on a shortest path back to the start node could be drawn red colored and directed backwards.

The attributes of a certain node/edge can be read and changed with pairs of get-set methods. For example, the border width of a certain node v is set to the value 5 by the following call:

gw.set_border_width(v, 5);

The naming of the set methods always follows the pattern set_(name_of_attribute). These methods expect a node or an edge as an argument, followed by a value whose type corresponds to the type of the attribute value that is to be set. The same holds correspondingly for the get methods. These methods return a value whose type corresponds to the type of the attribute that is to be read.

Every attribute has a default value that is used in the creation of a new node and a new edge. It is often useful to change this default value. For example, the default border width of the nodes is set to 5 by the following call:

gw.set_node_border_width(5);

The naming of the set methods for setting the default value of a node attribute follows the pattern set_node_(name_of_attribute). The same holds correspondingly for the edge attributes with set_edge_(name_of_attribute). These methods have a second, implicit argument, which has the value true; this means that changing the default value concerns all existing nodes and edges, that is, their attribute value is changed subsequently. If this is to be avoided, false has to be specified as the second argument.

The graph algorithm may change the graph G, for example, by inserting or deleting nodes and edges. Concerning this, the following should be noted:

	Warning
	If the graph algorithm changes the underlying graph G, a gw.update_graph(); has to be executed before the next edit() so that the GraphWin is informed about the modifications and is able to adapt its internal data structures. Without this instruction, the program may crash!

A call

gw.redraw();

causes the GraphWin to redraw the graph according to all specified attributes. An edit() first calls redraw() automatically.

Some methods of GraphWin automatically trigger a redrawing of the graph. Sometimes one wants to make several changes to the graph or its attributes in series without immediate redrawing (because of performance reasons, for example). This is achieved by

gw.set_flush(false);

After this, a redrawing is triggered only by an explicit redraw(). A

gw.set_flush(true);

restores the original behavior.

A call

gw.message(msg);

displays a short message string on the top of the drawing area. A

gw.del_message();

makes this message disappear again.

To pause the program run intermediately for secs seconds

gw.wait(secs);

can be called. The argument of this method is of type float; if it is missing, the program waits until the user presses done.

As an example for the edit-and-run scheme, we want to make the function DFS_NUM() interactively usable and visualize its result.

With breadth first search, a graph can be traversed systematically. Another method is depth first search: From a node just visited, it immediately visits all adjacent nodes that are not yet visited. Visiting nodes is done by recursion. This method first runs from the start node deep into the graph, instead of running around the first node as does bread first search. In the recursive search process, every node v gets a DFS number, that is the number of the recursive call that this node v is reached in. This recursive call may start further recursive calls, which will be finished sometime. Not until that moment also the recursive call for v will be finished; thereby v gets its completion number, that is the moment when a node has been processed completely.

The LEDA function DFS_NUM() executes a depth first search on a directed graph and calculates the DFS number and the completion number for every node. A graph and two node arrays that are valid on it, dfsnum and compnum, have to be passed to the function as arguments. The function returns a list of the edges traversed during the search. As a whole, these edges form a tree (if the graph is connected), because depth first search does not step along cycles; if the graph is not connected, they form a collection of trees, which is called a forest. Figure 5.10 shows such a DFS forest.

Figure 5.10. A DFS forest, calculated with DFS_NUM() and visualized by GraphWin

The following program uses the edit-and-run scheme to calculate and display a DFS forest interactively by means of DFS_NUM() on a graph. If the user presses done, the forest is calculated. Then in the GraphWin, every edge of the forest is colored red and drawn with a width of 5, and every node is displayed such that it shows its DFS number and its completion number.

#include <LEDA/graph.h>
#include <LEDA/basic_graph_alg.h>
#include <LEDA/node_array.h>
#include <LEDA/graphwin.h>
#include <LEDA/list.h>
#include <LEDA/string.h>


using leda::graph;
using leda::node;
using leda::node_array;
using leda::GraphWin;
using leda::window;
using leda::list;
using leda::edge;
using leda::string;
using std::cout;


int main()
{
  graph G;

  GraphWin gw(G, 500, 500, "DFS Numbering");
  gw.display(window::center,window::center);
  gw.set_node_shape(leda::ellipse_node);
  gw.set_node_width(42);
  gw.set_node_label_type(leda::user_label);

  while(gw.edit()) {
    node_array<int> dfsnum(G);
    node_array<int> compnum(G);
    list<edge>  L = DFS_NUM(G, dfsnum, compnum);
    gw.set_width(L, 5);
    gw.set_color(L, leda::red);
    node v;
    forall_nodes(v,G) {
      string label1("%d",dfsnum[v]);
      string label2("%d",compnum[v]);
      gw.set_user_label(v, label1 + "|" + label2);
    }
  }
    
}

Instead of a single node or a single edge, also a list of nodes or edges can be assigned to the set methods for setting the attribute values. This is useful if - as in the example above - the attributes of many nodes or edges are to be set all at once.

LEDA also offers a completely different possibility for creating graphs: It is often useful - especially for testing own graph algorithms - to have the graphs be created automatically instead of specifying them laboriously by hand. For this purpose, LEDA provides graph generators; these are functions that create graphs. To use them, the header file graph_gen.h has to be included.

The function

void complete_graph(graph& G, int n);

creates a complete graph with n nodes. This is a graph that has an edge (v,w) for every pair (v,w) of nodes. So the graph has n·(n-1) edges.

The function

void random_graph(graph& G, int n, int m, 
                  bool no_anti_parallel_edges,
                  bool loopfree, 
                  bool no_parallel_edges);

creates a random graph with n nodes and m edges. If no_anti_parallel_edges is set, no reverse edges are created, if loopfree is set, no self-loops are created, and if no_parallel_edges is set, no multiedges are created.

These functions can be observed very closely in a GraphWin. The corresponding menu entry is Graph → Create.

More about the very powerful interface of the class GraphWin can be found on the corresponding manual page. The parent class window is also important for the general comprehension; a manual page of its own is dedicated to this class.

The standard format is explained in detail on a corresponding page in the LEDA-Guide.

Further information about LEDA's graph generators can be found on their manual page.