Vertex and Edge Sequences

Introduction
Smart Indexing
Vertex/Edge Sequences and Attributes
Even Smarter Indexing
More Examples
Internal Representation

Introduction

Vertex and edge sequences are basically numeric vectors containing vertex/edge ids. For many functions there is an argument which is a vertex or edge sequence. Eg. degree() calculates vertex degree and it has an optional argument called v giving the vertices of which the degree will be calculated. (In this particular case the default value is all vertices.) Everywhere in igraph if a vertex or edge sequence is expected a simple numeric can also be supplied instead of a vertex/edge sequence object.

A vertex sequence object can be created with the function V() giving a graph object as a parameter, the vertex sequence will contain all vertices in the graph in vertex id order. (It is thus hardly more than a vector from 0 to vcount(g)-1.) Similarly, the E() function creates an edge sequence with all edges

> g <- graph.ring(10)
> V(g)
 [1] 0 1 2 3 4 5 6 7 8 9
> E(g)
Edge sequence:
[0] 0 -- 1
[1] 1 -- 2
[2] 2 -- 3
[3] 3 -- 4
[4] 4 -- 5
[5] 5 -- 6
[6] 6 -- 7
[7] 7 -- 8
[8] 8 -- 9
[9] 0 -- 9

Note that even if an edge sequence is just a vector of edge ids, it is “pretty printed” in R, instead of the edge ids, the end points of the edges are listed, in a nice format. If you wish to see the edge ids use the as.vector() function on the edge sequence:

> as.vector(E(g))
 [1] 0 1 2 3 4 5 6 7 8 9

Smart Indexing

Of course selecting all vertices or all edges in a graph is not always what we want; they can be indexed in various flexible ways to create a subset of vertices. Vertex sequences can be indexed by numeric or logical vectors to select a subset of vertices:

> g <- barabasi.game(100)
> V(g) [ degree(g) > 5 ]
Vertex sequence:
[1]  0  3  6 14
> V(g) [ degree(g) > 5 ] [ 0:9 ]
Vertex sequence:
[1] 0 3 6

Here the first example selects vertices with (total) vertex degree higher than five by indexing with a logical vector. As the result of the indexing is also a vertex sequence, it can indexed again, like in the second example, this time with a numeric vector; we get all vertices with degree higher than five among the first 10 vertices as a final result.

There are some functions which make vertex sequence indexing easier, these cannot be use anywhere else, they are defined only in the indexing operation of vertex/edge sequences. For vertex sequences these are: nei(), adj(), from() and to() and for edge sequences: adj(), from() and to().

nei() takes a vertex sequence as a parameter (remember a simple vector of vertex ids is also allowed), and returns a logical vector which is TRUE for those vertices from the indexed vertex sequence which have at least one neighbor in the vertex sequence supplied as a parameter. To select those vertices which have vertex degree higher than five and are connected to vertex 0 one can write:

> V(g) [ degree(g) > 5 & nei(0) ]
Vertex sequence:
[1]  3 14

Of course more than one vertex can be supplied as an argument to nei(), all neighbors of vertices 0, 1 and 10:

> V(g) [ nei(c(0,1,10)) ]
Vertex sequence:
 [1]  0  1  2  3  5  7 10 12 14 21 22 42 45 53 64 70 73 88 89

For vertex sequences adj() takes an edge sequence as its single argument and it returns TRUE for those vertices which are adjacent to at least one edge in the parameter edge sequence. Here are the vertices adjacent to the edges with high edge betweenness:

> g <- barabasi.game(1000)
> es <- E(g) [ edge.betweenness(g) > 100 ]
> es
Edge sequence:
[0] 1 -> 0
[1] 2 -> 0
[2] 3 -> 0
[3] 4 -> 1
[14] 15 -> 12
[26] 27 -> 2
> V(g) [ adj(es) ]
Vertex sequence:
[1]  0  1  2  3  4 12 15 27

For edge sequences adj() is similar, is takes a vertex sequence as its argument and returns TRUE for edge which are adjacent to at least one vertex in the parameter.

The from() and to() functions are exactly the same as adj() for undirected graphs. For directed graphs they are a bit different, from() is only TRUE for those vertices/edge which are connected at the origin (source) of the edge, while to() is TRUE at the opposite end. For example to get all the outgoing edges of some vertices one can write:

> g <- erdos.renyi.game(100, 3/100, directed=TRUE)
> E(g) [ from(0:2) ]
Edge sequence:
[0] 0 -> 4
[1] 0 -> 15
[2] 0 -> 46
[3] 0 -> 97
[4] 1 -> 5
[5] 1 -> 79
[6] 1 -> 84
[7] 1 -> 86
[8] 2 -> 10
[9] 2 -> 12
[10] 2 -> 22
[11] 2 -> 52
[12] 2 -> 61
[13] 2 -> 91

Vertex/Edge Sequences and Attributes

Vertex and edge attributes can be used in a very powerful way via vertex/edge sequences: the “$” operator accesses the vertex/edge attributes for the vertices/edges in the sequence. This form can be be used for assigning new values as well. In the following example we assign uniformly random weights to the edges and set the color edge attribute to “red” for edges with high weight.

> g <- graph.lattice( c(10,10) )
> E(g)$weight <- runif(ecount(g))
> E(g)$color <- "grey"
> E(g)[ weight > 0.9 ]$color <- "red"
> plot(g, layout=layout.kamada.kawai,
       edge.color=E(g)$color, vertex.size=3, edge.width=2, label.dist=0.6)

The previous example also shows that attribute names can be used in index expressions, eg. giving weight in the index of an edge sequence means the weight attribute for those edges in the sequence.

Just like for the ordinary attribute assignment functions, if the vector (or list) giving the attribute values is shorter than the one giving the vertex/edge ids then if will be recycled:

> g <- graph.ring(10)
> V(g)$color <- c("red", "blue")
> plot(g, layout=layout.circle, vertex.color=V(g)$color)

Even Smarter Indexing

The E() function has two optional parameters which can be used often conveniently.

If the P parameter is given then E() creates an edge sequence based on the end points of the edges. Eg. to select the edge connecting vertices 0 and 1 one can write E(g, c(0,1)) (as P is the next positional argument after the graph, it is not required to write E(g, P=c(0,1)). The following example calculates the edge betweenness for a particular edge only:

> g <- barabasi.game(100, directed=FALSE)
> edge.betweenness(g, E(g, c(0,1)))
[1] 736

If the path argument is given then E() selects edges along the (directed or undirected) path in path. The path is given via the vertex ids visited. In the following example we use path() to set some edge attributes on edges along the longest geodesic (ie. diameter) in a graph:

> g <- barabasi.game(100, directed=FALSE)
> d <- get.diameter(g)
> E(g)$color <- "SkyBlue2"
> E(g)$width <- 1
> E(g, path=d)$color <- "red"
> E(g, path=d)$width <- 2
> V(g)$labelcolor <- V(g)$color  <- "blue"
> V(g)[ d ]$labelcolor <- V(g)[ d ]$color <- "red"
> plot(g, layout=layout.kamada.kawai, 
     edge.color=E(g)$color,edge.width=E(g)$width,
     vertex.color=V(g)$color, label.color=V(g)$labelcolor,
     label.dist=0.4, vertex.size=3)

There are other three special operators defined in the index expressions of edge sequences only: %->%, %<-% and %--%. These operators can be used effectively for selecting the edges connecting the vertices in two vertex sequences. For undirected graphs they are work the same way. For directed graphs %--% ignores the direction of the edges while %->% selects only edges pointing from the left hand side argument to the right hand side and the opposite for %<-%.

> g <- graph( c(0,1, 1,1, 1,2, 2,3, 3,1) )
> g
Vertices: 4 
Edges: 4 
Directed: TRUE 

Edges:
[0] 0 -> 1
[1] 1 -> 1
[2] 1 -> 2
[3] 2 -> 3
> E(g) [ 0:1 %--% 2:3 ]
Edge sequence:
[2] 1 -> 2
[4] 3 -> 1
> E(g) [ 0:1 %->% 2:3 ]
Edge sequence:
[2] 1 -> 2
> E(g) [ 0:1 %<-% 2:3 ]
Edge sequence:
[4] 3 -> 1

More Examples

TODO

Internal Representation

TODO