The igraph data model

Directed graphs
Undirected graphs
Examples

This section introduces the igraph data model. It is recommended that the reader should be familiar with this model of computation to understand the semantics of the igraph functions better.

An igraph graph is either directed or undirected, igraph cannot handle mixed graphs with both directed and undirected edges.

Directed graphs

The igraph data model is slightly different for directed and undirected graphs, we start with the directed case. In igraph vertices are identified by vertex ids: integer number between zero and |V|-1, if |V| is the number of vertices in the graph. Thus the numbering of vertex ids is always continual, all igraph operations on graphs keep this important property.

Directed igraph edges are ordered pairs or vertex ids. A directed graph is an ordered multiset of directed edges and some additional meta data: the number of vertices in the graph and a boolean tag to mark the graph as directed. Here is an example of a directed igraph graph:

  ( vertices: 6, 
    directed: yes,
    (
     (0,2),
     (2,2),
     (2,3),
     (3,3),
     (3,4),
     (3,4),
     (4,1)
    )
  )

Just like the vertices have vertex ids, igraph edges also have ids: edge ids are integer numbers between zero and |E|-1, |E| is the number of edges in the graph.

Undirected graphs

An undirected igraph edge is a two-element or one-element set of vertex ids. The two element set is a non-loop edge, ie. the edge connects different vertices, while loop edges are represented with a single-element set. An undirected graph is an ordered multiset of undirected edges, plus the usual meta data: the number of vertices and the fact that the graph is undirected. Here is an example for an undirected graph:

  ( vertices: 6,
    directed: no,
    (
     {0,2},
     {2},
     {2,3},
     {3},
     {3,4},
     {3,4},
     {4,1}
    )
  )

This graph contains both loop edges ({2} and {3}, ie. (2-2) and (3-3)) and multiple edges ({3,4} twice).

Examples

We give some simple examples on how this data model is used in computations. The first example is the are.connected() function, this decides whether two vertices are connected by an edge. Lets assume that G1 and G2 are the graphs from the previous two sections, G1 is the directed, G2 the undirected graph. Now if we check with are.connected() whether vertices 0 and 2 are connectedin G1, the function searches for the (0,2) directed pair, and since it finds it it returns positive result. If the same search is performed on G2, the function searches for the {0,2} set and the result is, again, positive. Now it is perhaps obvious by now that if we suppply the vertices in the opposite order, ie. 2 and 0 then in G1 the (2,0) ordered pair is requested, so the answer is negative. For G2 {0,2}={2,0} is searched again, the answer is still positive.

Another simple example is the neighbors() command, this can be used to find the neighboring vertices of a vertex. neighbors() (like many other functions in igraph) has a parameter called mode. This parameter defines how the search is performed in directed graphs. Let us assume that we are interested in the neighbors of vertex 3. If mode is out then the graph's edge list (which is a multiset) is searched for elements having 3 in the first position of the ordered pair and returns the vertex ids in the second position in these elements. So the answer is (3,4,4). Now if mode is in then the role of the first and second positions is exchanged and (2,3) is returned. The third possible value of mode is all, in this case pairs having 3 at either at the first or second positions are searched and the other vertex id in the pair is returned: (2,3,4,4). Note that 3 is returned only once even if it is found both ways. This of course corresponds to the normal graph theoretic conventions.

The mode argument is always ignored when dealing with undirected graphs, as these graphs store an edge as an unordered pair (ie. a set). For example running neighbors() on graph G2 and vertex 3, the result is (2,3,4,4).

Note that if we set mode to all on a directed graph that essentially means that we use the corresponding undirected graph for calculation. Also note that the corresponding undirected graph always have the same number of edges as the directed counterpart, eg. if the directed graph contains (3,4) and (4,3) these edges make two {3,4} edges in the undirected graph.

Some igraph functions have a mode for other purposes: eg. graph.tree() and graph.star().