 # How to map between nodes in original graph and induced subgraph?

Hi,

I wonder how to map nodes between the original graph and induced sub graphs. If I understand it correctly the ids are between `[0, N_org)` and `[0, N_sub)`, so simply matching the IDs will not work.

I had to use `mathematica` as tag and could change it later to `C`

1 Like

I would expect that the order of vertices in the generated subgraph will be the same as in the vertex id list passed to the `induced_subgraph`. I was surprised to see that this was not documented. To be 100% confident that it is the case, I would have to go through the code … We should definitely document this.

1 Like

Probably this is only true for `IGRAPH_SUBGRAPH_CREATE_FROM_SCRATCH` and not `IGRAPH_SUBGRAPH_COPY_AND_DELETE` I would be surprised if the latter would care about creating that order when deleting random nodes.

Hi ObiWahn,

welcome to the forum!

In the `COPY_AND_DELETE`, the vertex ids should simply slide down towards zero as if you pulled the deleted vertices from under their feet. So if you have

0 1 2 3 4

and you want the subgraph induced by 2 and 4, then `2 -> 0` and `4 -> 1`. The code is a little twisted by that’s my understanding of it.

In case anyone wants to dig a little, here is the chain of functions called:

1. `igraph_induced_subgraph`
2. `igraph_induced_subgraph_map` (with no maps)
3. `igraph_i_subgraph_copy_and_delete`, which makes a copy of the graph and then deletes the vertices via…
4. `igraph_delete_vertices_idx` (again, no maps)

The last function has this code snippet (simplified a little):

``````    /* create vertex recoding vector */
for (remaining_vertices = 0, i = 0; i < no_of_nodes; i++) {
if (<vertex to be kept>) {
VECTOR(*my_vertex_recoding)[i] = remaining_vertices + 1; // <-- NEW VERTEX ID (+1)!
remaining_vertices++;
}
}

/* create edge recoding vector */
for (remaining_edges = 0, i = 0; i < no_of_edges; i++) {
long int from = (long int) VECTOR(graph->from)[i];
long int to = (long int) VECTOR(graph->to)[i];
if (VECTOR(*my_vertex_recoding)[from] != 0 &&
VECTOR(*my_vertex_recoding)[to  ] != 0) {
VECTOR(edge_recoding)[i] = remaining_edges + 1;
remaining_edges++;
}
}

/* start creating the graph */
newgraph.n = (igraph_integer_t) remaining_vertices;

for (i = 0, j = 0; j < remaining_edges; i++) {
if (VECTOR(edge_recoding)[i] > 0) {
long int from = (long int) VECTOR(graph->from)[i];
long int to = (long int) VECTOR(graph->to  )[i];
VECTOR(newgraph.from)[j] = VECTOR(*my_vertex_recoding)[from] - 1;
VECTOR(newgraph.to  )[j] = VECTOR(*my_vertex_recoding)[to] - 1;
j++;
}
}

``````
1 Like

Just wanted to chime in to confirm that the explanation of @iosonofabio is correct. Most of the time you don’t need to deal with this in higher-level interfaces (R, Python, Mathematica) because you can simply attach a node ID to each node with one line of code and these are preserved when taking the subgraph so you can easily track what went there. You can probably do the same in C, but the attribute handler is not that straightforward there.

There is also the undocumented `igraph_induced_subgraph_map()` function that works like `igraph_induced_subgraph()` but has two extra arguments of type `igraph_vector_t*`; if they are not null, these are used to return the mapping and the inverse mapping. We plan to document and make it public from the next release so feel free to use it - it won’t go away in upcoming versions.

1 Like