Re: [igraph] Fw: why is igraph_rewire_edges so fast?

[Tamás Nepusz]

The first, prev and next vectors together form multiple doubly linked lists for the edges of the network. Each vertex has a linked list for the edges that it is incident on. The 'first' vector contains the index of the first edge that the vertex is incident on. The next and prev vectors are indexed by the edge indexes. next[i] = j and prev[j] = i if the edge with index j follows the edge with index i in the linked list of some vertex. Rewiring is done by updating the linked lists.

Actually, there is one more trick. All the values in first, prev and next are increased by 1 because we use zero as a special value to indicate a link pointing to nowhere.

T. 

On 14 Dec 2015, at 07:59, "sizheng0320" <address@hidden> wrote:

Well, BTW, I'm interested in rewiring a network because i'm doing some work on Null Model of complex networks, which is in fact is the randomized network of a complex network. 

however, some conditions can be added when selecting edges to rewire. that generates different orders of null models. igraph_rewire_edges of igraph can generate 0-order null models.

Gang Lu

------------------ Original ------------------

From:  "sizheng0320";<address@hidden>;

Date:  Fri, Dec 11, 2015 12:28 PM

To:  "igraph-help"<address@hidden>;

Subject:  why is igraph_rewire_edges so fast?

Hi everyone,

has anyone read the code of the function igraph_rewire_edges?

i'm doing this because i wonder why this function rewires a large network so fast.

it seems some indexing technique is used, because i have seen in the function igraph_i_rewire_edges_no_multiple in games.c, some vectors such as first, next, prev are used.

though i tracked the code with a small network of 5 nodes and 6 edges, i still don't understand the meaning of the three vectors. How do they work, please?

Thanks a lot!

Gang Lu

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help