## 2. Graphs

The core of the Tulip library provides an interface for the manipulation of graphs. It enables one to access and modify the structure of a graph. The aim of this library is to be as general as possible and thus it manipulates a general class of graphs called directed pseudo-graphs. In a pseudo graph, there can be more than one edge between two nodes, and loops are permitted. A loop is an edge that links a node to itself. Furthermore, edges are directed, thus an edge u->v is distinct from an edge v->u.

Because we use pseudo-graphs, there can be more than one edge u->v, so it is not possible to distinguish two edges using only source and target (u,v). To make this possible, all the elements in Tulip are entities (C++ objects). Thus, even if two edges have the same source and the same target, they are distinct.

The elements of a graph are encapsulated in the graph. It is therefore not possible to access the graph's structure through elements, all operations must be done by querying the graph. For example, to know the source of an edge e of graph G, one must ask G, not e, what e's source is. This makes the use of the library less intuitive, but it minimizes memory usage for entities and allows to share them between subgraphs. Building a container of elements is cheap, because to handle elements, Tulip uses objects which use the same amount of storage as integers.

The library supports 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 uses Tulip only for the manipulation of one graph (no graph 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 subgraphs

List of available modification operations

• `node addNode()` : creates a new node in the graph and returns its identifier.

• `edge addEdge(node,node)` : create a new edge in the graph, given the source and target.

• `void delNode(node)` : deletes the given node.

• `void delEdge(edge)` : deletes the given edge.

• `void reverse(edge)` : reverses an edge (swaps source and target).

List of available access operations

• `unsigned int deg(node)` : returns the degree of a node (number of edges).

• `unsigned int indeg(node)` : returns the in degree of a node (number of times it is a target).

• `unsigned int outdeg(node)` : returns the out degree of a node (number of times it is a source).

• `node source(edge)` : returns the source of an edge.

• `node target(edge)` : returns the target of an edge.

• `node opposite(edge,node)` : it enables to obtain the opposite of a node of an edge.

• `Iterator * getInNodes(node)` : returns an iterator on the predecessor nodes of a node.

• `Iterator * getOutNodes(node)` : returns an iterator on the successor nodes of a node.

• `Iterator * getInOutNodes(node)` : returns an iterator on the neighbor nodes of a node.

• `Iterator * getInEdges(node)` : returns an iterator on the predecessor edges of a node.

• `Iterator * getOutEdges(node)` : returns an iterator on the successor edges of a node.

• `Iterator * getInOutEdges(node)` : returns an iterator on the neighbor edges of a node.