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

Usage
1

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
2

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
3

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.

4

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;

    /* Add the edges */
    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
5

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