#4 Optimisation in ErdosR generator possible

closed-accepted
nobody
None
5
2005-06-28
2005-06-22
Dirk Koschuetzki
No

The ER generator has two point for an optimisation:

at first: the vertex is extracted from the indexer independently of
the use. If the check with the random number fails, then they are
ignored.

at second: I think the check for isNeighbour can not be true at all.
This is impossible, because the loop runs from i+1 to n for the j.
therefore 2->1 will never be created.

BTW: Is the optimization for J allowed? What is the exact
definition from ER?

Dirk

NEW CODE:

for (int i = 0; i < mNumVertices - 1; i++) {
for (int j = i + 1; j < mNumVertices; j++) {
if (mRandom.nextDouble() <
mEdgeConnectionProbability) {
Vertex v_i = (Vertex) id.getVertex(i);
Vertex v_j = (Vertex) id.getVertex(j);
g.addEdge(new UndirectedSparseEdge(v_i, v_j));
}
}
}

Discussion

    • milestone: 323170 -->
     
  • Logged In: YES
    user_id=709417

    The code's use of indexers can certainly be improved; I've done so.

    I believe you're right about the isNeighbor check; I've removed it.

    As for the optimization of the j index, I'd have to look up the Erdos-
    Renyi paper to make sure that we've correctly understood it, but since
    we're adding undirected edges (and no more than one between any pair
    of vertices), there's no point in iterating over the entire range for j.

    Joshua

     
    • labels: 552192 -->
    • status: open --> closed-accepted