Next Up Previous Contents

4 Graph

Graph

4.1 Directed vs. undirected

Directed vs. undirected

As already mentioned in the beginning graphs can be used directed or undirected, even though internally they always will be directed. Mostly we are talking about directed graphs here, because they are more common.

Anyway the introductory chapters gave a short overview of what is affected by toggling the direction-flag of a graph. Mostly the notion of adjacency changes from ``adj=in+out'' (undirected) to ``adj=out'' (directed). This affects the counting of edges, i.e. the degree-functions n.indeg(), n.out_deg() and n.degree(), too.

4.2 Deletion

Deletion

Probably as important as the creation of nodes and edges is their deletion. The following methods are provided:

There are a few things to be kept in mind about these functions. First: the deletion of some node always implies, that all edges connected to it will be deleted, too. Second: the notion of a visible edge. This already suggests that there must be some functions to toggle the visibility of some edge:

To check wheter a certain node, say n, is hidden one can call n.is_hidden(). This is important, because the deletion of a hidden edge is not allowed. The idea behind this restriction is, that if a edge (or node) is hidden it isn't for the moment part of the graph. This means that it does not appear in the list of all edges (or nodes) and thus can't be obtained in a legal way.

4.3 Traversing nodes or edges

Traversing nodes or edges

One of the most common thing to do with graphs is to iterate through all its nodes or edges and perform some action on each of them them. Clearly the STL iterator concept is used for this task, like the following example shows:

    ...

   graph::node_iterator it = G.nodes_begin();
   graph::node_iterator end = G.nodes_end();
   list<node> found;

   while(it != end) {
     if(/* some condition on *it */) {
        found.push_back(*it);
     }

     ++it;
   }

   ...

Furthermore the number of nodes and edges can be determined using G.number_of_nodes() and G.number_of_edges() respectivley.

4.4 Hiding Edges and Nodes

Hiding Edges and Nodes

As mentioned above edges and nodes can either be visible or hidden. The main reason for this feature is that often some edges in graphs cause trouble when applying an algorithm to it. But it is inconvenient to delete these edges first, then apply the algorithm and create them again afterwards. This is why the possibility to hide and restore edges is provided. The following commands can be used:

By G.hide_edge(e) edge e in some graph G is hidden, i.e. the graph acts as if e would have been deleted. The operation has no effect if it is applied to a hidden edge. Using G.restore_edge(e) makes e visible. Again application of this operation to an edge already visible is ignored.

If you want to hide more than one edge or node please do not try the following:

   graph::edge_iterator it = G.edges_begin();
   graph::edge_iterator end = G.edges_end();

   while(it != end) {
     if(/* some condition on *it */) {
        G.hide_edge (*it);
     }

     ++it;
   }

This will definitly crash because hide implicitly removes the edge to be hidden from the list of all nodes, thus making it invalid. You can avoid this problem by either making a seperate list containing only the edges you want to hide and then run through this list and hide the edges, i.e.

   list<edge> to_be_hidden;
   graph::edge_iterator it = G.edges_begin();
   graph::edge_iterator end = G.edges_end();

   while(it != end) {
     if(/* some condition on *it */) {
        to_be_hidden.push_back (*it);
     }

     ++it;
   }

   list<edge>::iterator l_it = to_be_hidden.begin();
   list<edge>::iterator l_end = to_be_hidden.end();

   while (l_it != l_end) {
     G.hide(*l_it);
     ++l_it;
   }

The other way to achieve the same behaviour is to make a temporary copy of it and increase it before hiding, i.e.

   graph::edge_iterator it = G.edges_begin();
   graph::edge_iterator end = G.edges_end();
   graph::edge_iterator tmp;

   while(it != end) {
     if(/* some condition on *it */) {
        tmp = it;
        ++tmp;
        G.hide_edge (*it);
        it = tmp;
     } else {
        ++it;
     }
   }

Please note, that the same things apply to deleting as well.

4.5 Loading and Saving Graphs

Loading and Saving Graphs

GTL uses GML (Graph Modelling Language) as file-format. The following functions can be used to load or save a graph.

The load-functions open the file, parse it and if no error occurs assign the graph decribed in it to the graph they were called for. If an error occured the error-value as well as the line and column number are returned in a GML_error object. Please refer to the class reference for details.

A file in GML-format is a list of key-value pairs, storing arbitrary information. First the load-function scans the file for the key graph having a list of key-value pairs as value. This list is scanned for the keys directed, node and edge, where directed is expected to have an integer as value. The value of node has to be a list containing at least a key id, which gives this node a unique integer id. The value of edge must be a list containing at least the keys source and target both with an node id as value. The following example is a valid graph description:

# graph in GML-format 

graph [
  directed 1
  node [ id 0 ]
  node [ id 1 ]
  node [ id 2 ]
  node [ id 3 ]
  edge [ source 0 target 1 ]
  edge [ source 2 target 3 ]
  edge [ source 3 target 0 ]
]

Keys not mentioned above are simply ignored. There is no restriction on the order of the node and edge keys (though the order in the example is the most common). There is even some error correction, because if an id is only mentioned in source or target specification (i.e. not declared using a node key), a new node with that id is created.

The save-functions write exactly the format presented above to a file (or any ostream given)


Next Up Previous Contents