5.2.5. Creating and storing graphs and the editor GraphWin

Learning objectives

Using the class GraphWin
The default representation for storing graphs
The edit-and-run scheme
Visualizing the output of graph algorithms
DFS numbering with DFS_NUM()
The graph generators complete_graph() and random_graph()

Until now, we built up the graphs in our programs step by step. Often, however, it is preferable or necessary to feed the graphs that we want to work on from “the outside” to the program or to create them automatically. Then the question is how to create, edit, and store graphs. In this section, we will get to know some possibilities for doing this.

Interactive input with the editor GraphWin

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

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!

Filename: GraphDrawer.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#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.

The standard format

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:

  1. The header section: It begins with the string LEDA.GRAPH. Then the data types of the node and edge information follow (if the underlying graph is of type GRAPH, otherwise void.)

  2. As of version 4.5 of LEDA: An optional line with information about whether the graph is directed or undirected. The number -1 indicates a directed graph, the number -2 an undirected graph. If the line is missing, the graph is considered directed. In versions < 4.5 of LEDA, the line is always missing and the graph is always considered directed.

  3. The node section: It begins with the number n of nodes. The nodes are numbered by their position in the node list V. The following n lines contain the information that are associated to this node, enclosed in |{...}|.

  4. The edge section: It begins with the number m of edges. m lines follow, one for every edge in the graph. Each of these lines consists of four entries in the following order: the number of the start node, the number of the target node, the number of the reversal edge (0, if there is none), and the information that is associated to the edge (enclosed in |{...}|). (We will get to know the concept of the reversal edge in Section 5.2.6.) The m lines for the m edges are ordered by two criteria: First by the number of the start node s, then by the position of the edge in the list adj_edges(s).

  5. The layout section: It begins with the comment version string. (A comment must not appear before!) This section contains information about the layout of the graph in a GraphWin. If it is empty, no layout is known.

Reading from and writing to a file

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.

Filename: GraphVisualizer.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#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

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.

Attributes of GraphWin

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:

  • position: an attribute of type point that defines the position of the center of the node in the user coordinate system.

  • shape: an attribute of type gw_node_shape that defines the shape of the node. Possible values are circle_node, ellipse_node, square_node, and rectangle_node.

  • width: an attribute of type int that defines the width of the node in pixels.

  • height: an attribute of type int that defines the height of the node in pixels.

  • color: an attribute of type color that defines the color that the inside of the node is filled with.

  • border_color: an attribute of type color that defines the color of the frame of the node.

  • border_width: an attribute of type int that defines the width of the frame of the node in pixels.

  • label_type: an attribute of type gw_label_type that defines which of the three possible labels of the node is displayed. Possible values are no_label, user_label, data_label, and index_label. Each node of a GraphWin has three associated labels: an index label, which corresponds to the internal numbering of the nodes in the node list V, a user label of type string, and a data label, which corresponds to the information associated to a node if the underlying graph is of type GRAPH.

  • user_label: an attribute of type string that defines the user label of the node.

  • label_color: an attribute of type color that defines the color of the label to be displayed. Colors can be specified by red-green-blue values; for example, color(255,0,0) codes the purest red. The header file that has to be included is color.h. An enumeration of 16 predefined color values, defined in this header file, offers another possibility for specifying colors; the names of these values are leda::black, leda::white, and so on.

  • label_pos: an attribute of type gw_position that defines the position of the label to be displayed, relative to the center of the corresponding node. Possible values are central_pos, northwest_pos, north_pos, northeast_pos, east_pos, southeast_pos, south_pos, and west_pos.

The most important edge attributes are the following:

  • direction: an attribute of type gw_edge_dir that defines whether the edge is drawn directed or undirected. Possible values are undirected_edge, directed_edge, redirected_edge (the edge is drawn directed from the target to the source), and bidirected_edge (the edge id drawn bidirected).

  • width: an attribute of type int that defines the width of the edge in pixels.

  • color: an attribute of type color that defines the color of the edge.

  • style: an attribute of type gw_edge_style that defines the line style of the edge. Possible values are solid, dashed, dotted, and dashed_dotted.

  • label_type: (see the node attribute of the same name.)

  • user_label: (see the node attribute of the same name.)

  • label_color: (see the node attribute of the same name.)

  • label_pos: an attribute of type gw_position that defines the position of the label to be displayed, relative to the corresponding edge. Possible values are central_pos, east_pos, and west_pos.

The programming interface of the class GraphWin

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]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.

An example: Visualizing DFS_NUM()

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

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.

Filename: DFS_NUMDemo.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#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.

Graph generators

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.

Further information

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.

Exercises

Exercise 56.

In Figure 5.8, a multiedge is drawn as a semicircle. Play around with a GraphWin until you find out how to manage this.

Exercise 57.

Use the edit-and-run scheme for visualizing bread first search: After each call of BFS(), the edges that specify the predecessor of every node reached on a shortest path back to the start node shall be drawn red colored. Additionally, the calculated distance to the start node shall appear in every node. The first node that has been input by the user shall be the start node. That is the first node in the node list V of the graph G associated to the GraphWin; this node is obtained by G.first_node(). Additionally, this node shall be made recognizable by a thick, green border.

Exercise 58.

Run the following experiment to compare the efficiency of node_array, node_map, and GRAPH with regard to the access to associated values: Create a random graph with one million nodes and zero edges and associate the value 0 to every node. Iterate 20 times over all edges of the graph and increase the associated value each time by 1. First iterate over the nodes in their natural order in V, then in a random order. (For this, you may permute an array<node> and then access the nodes indirectly via this array, for example.) Take and compare the running times.




Imprint-Dataprotection