Table of Contents
Efficient visualization of graphs implies to manipulate the structure of the graph but also to extract part of this structure. Moreover, if one wants to visualize graphs and to use graphs for data analysis, one must take into account the values associated to the element (node or edge) of the graph. One other central point in a visualization system is to provide a way to compute parameters based on the intrinsic (or extrinsic) parameters of a given graph. We call intrinsic parameters those calculated by using the structure of the graph and extrinsic parameters those calculated using external information. For instance, if we consider a file system, the size of a file is an extrinsic parameter and the number of file in a directory is an intrinsic parameter because in can be computed by analyzing the structure of the tree representing the file system.
This chapter describes the Tulip data structure that takes into account all the requirement of a graph visualization system. For each part we describe precisely the general principle and then we give several examples explaining how it can be done using the Tulip library.
The core of the Tulip library provides an interface for the manipulation of graphs. This interface enables to access and to modify the structure of a graph. The purpose of this library is to be the more general as possible and thus this interface enables to manipulate a general class of graphs called directed pseudo-graph. In a pseudo graph, it can exists several edges between two nodes and it can exists several loops. A loop is an edge that links a node to itself. Furthermore, the links are directed, thus an edge linking a node u to a node v is different from an edge linking a node v to a node u.
Using of pseudo-graph implies that it can exist two edges between a node u and a node v. Thus, it is not possible to distinguish two edges using only the same source and the same target (u,v). To enable such a distinction, all the element in Tulip are entities (objects). Thus, even if two edges have the same source and the same target they are different.
Another important point to consider is that it is not possible to access to the structure of a graph through elements (node or edge). Thus, all operations on the graph structure must be done by querying the graph. For instance, if one wants to know the source of an edge e of graph G, one must ask to G what is the source of e. This characteristic makes the use of the library a little bit less intuitive but, it enables to store entities using the minimum space and to share them between sub-graphs. When using the Tulip data structure one must always keep in mind that building a container of elements corresponds to store a container of integers in memory. For instance, a std::vector<node> is equivalent to a std::vector<unsigned int>.
The library support access and modification of the graph structure. The access to the structure are made by using iterators, one very important point is that the iterator are not persistent. Thus, if one modify the graph structure all the iterators on the graph structure can be invalid. This property enables to prevent from cloning the data structure and thus enables better access to it. For ease of use, Tulip includes mechanism that enables to transform an iterator into stable iterator, one must keep in mind that it corresponds to clone the data structure and thus, it should be use only if it is necessary.
If one use Tulip only for the manipulation of one graph (no hierarchy), the list of available operations on the graph is given afterward. In the next section we will enhance the set of operations and the actions that they perform in order to manage a hierarchy of sub graphs
List of available modification operations
node addNode()
: it enables to create a new node in the graph.
edge addEdge(node,node)
: it enables to create a new edge in the graph.
void delNode(node)
: it enables to delete a node in the graph.
void delEdge(edge)
: it enables to delete an edge in the graph.
void reverse(edge)
: it enables to reverse an edge (swap source and target).
List of available access operations
unsigned int deg(node)
: returns the degree of a node.
unsigned int indeg(node)
: returns the in degree of a node.
unsigned int outdeg(node)
: returns the out degree of a node.
node source(edge)
: it returns the source of an edge.
node target(edge)
: it returns the target of an edge.
void opposite(edge,node)
: it enables to obtain the opposite of a node of an edge.
Iterator * getInNodes(node)
: returns an iterator on the nodes predecessors of a node.
Iterator * getOutNodes(node)
: returns an iterator on the nodes successors of a node.
Iterator * getInOutNodes(node)
: returns an iterator on the nodes neighbors of a node.
Iterator * getInEdges(node)
: returns an iterator on the edges predecessors of a node.
Iterator * getOutEdges(node)
: returns an iterator on the edges successors of a node.
Iterator * getInOutEdges(node)
: returns an iterator on the edges neighbors of a node.