Re: [igraph] will igraph re-number vertices?

[Csardi Gabor]

Hi Matt,

On Wed, Oct 24, 2007 at 02:01:28PM -0400, Matt Bonner wrote:
> Heya,
> 
> Will igraph ever silently renumber vertices/change their vertex ID's  
> as a result of another operation?

yes, sometimes it does.

> For example, suppose I use decompose to eventually pull out the the  
> largest component. Presuming the largest component and the full graph  
> each have a vertex with ID 6, does vertex 6 in the component refer to  
> the same vertex in the full graph? 

Not necessarily, generally not.

> Is the behavior the same for the R  
> functions and the C functions?

Yes it is, the R functions usually just call the C routines.

> In simple tests with things like centrality measures, it seems like  
> igraph doesn't ever renumber vertices in this way. However, it would  
> be nice to KNOW that igraph isn't doing this for a given function, or  
> for any function.

Matt, it is very simple. In a graph the vertex ids always go from zero
to N-1, N is the total number of vertices. This means that if you
_change_ the graph then the vertex ids must usually change, as the number
of vertices might change as well. 

Renumbering occurs only then you _create_ a new graph. The new graph
gets its vertex ids and that's it, those never changes again. Again,
if you create another graph based on this, with decompose or subgraph
then the new graph might have different vertex ids. The old one does
not change. 

In the R package it is true that igraph never changes a graph supplied
as an argument, it just creates a new graph when needed. Eg.

subgraph(g, v)

never changes "g" but returns the new graph having only vertices "v".
(Usually with different vertex ids.)

If you want to keep track of the vertices, assign a vertex attribute
to the graph, those do not change, although some igraph functions
like as.undirected drop vertex attributes, which is not nice, but 
considered as a bug, so we're working on this.
Here is how it works:

g <- graph.ring(10)
V(g)$name <- letters[1:10]
g

g2 <- subgraph(g, 3:7)
g2

Hope it is clear now.
Gabor

> Thanks,
> 
> --Matt
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK