problem with insert and push_back command for vector

[scigeek]

Hi,

I am running a subgraph counting code on some moderately large graphs as inputs (approximately 160000 nodes). The code I am running involves repeated calling of a method calls MatchSubgraph(). Inside, I have a vector which holds possible candidate nodes which can be matched to a node in the template graph. Each time, I call MatchSubgraph(), I have to initialize the vector candidate (vector<Vertex> candidate) and at the end, I clear it out (candidate.clear()).
Now, once I initialize the vector, after few iterations, which by the work perfectly, when I am trying to put nodes into vector using either insert() or push_back(), it segfaults. On closure scrutiny, I found out that only the fist element gets inserted into the vector, and then the segfault occurs. Note this happens, after 35 iterations. All the previous iterations, things worked fine. I couldn't figure out why.

I understand it is a bit hard to tell without looking at the code.
I have been doing this for few months now and basically, I am teaching myself C++. So any help would be greatly appreciated.

Thanks

[firedraco]

I understand it is a bit hard to tell without looking at the code.

Yeah, we are going to have to see the code.

[scigeek]

bool SubGraph::MatchSubgraph(Vsize i)
{
Vertex sv = BFSlist[i], u, v; // will find the mapping of sv in this function
cout << "MatchSubgraph("<<i<< "): sv is " << sv << endl;
Byte label = sg.label[sv];
//cout << "MatchSubgraph("<<i<< "): label[sv] is " << label << endl;
Vlist snbr = sg.nlist[sv], nbr, edr;
Vlist sedr = sg.eDir[sv];
//Vlist candidate;
Word *lidx;
Word ncand, csize, k, m, pos; // number of candidates
bool satisfied;

for (k=0; vmap[snbr[k]]==NONE; k++); // find the first matched neighbor of sv
cout << "MatchSubgraph("<<i<<"):first matched ngb of "<< sv << " " << vmap[snbr[k]] <<endl;
// cout << "Ngb of "<< sv << "in the subgph is " << snbr[k] << endl;
u = vmap[snbr[k]]; // u (in g) is matched with neighbor snbr[k] of sv
cout <<"MatchSubgraph("<<i<<"): Note: u = vmap[snbr[k]] "<< u << "is in g " << endl;
nbr = g.nlist[u];
edr = g.eDir[u]; //added
lidx = g.lindex[u];

csize = ncand = lidx[label+1] - lidx[label];

if (ncand==0)
return false;


vector<Vertex> candidate; //INITIALIZING CANDIDATE VECTOR
for(int j=0; j<ncand;++j){

//candidate.insert(candidate.begin()+j, nbr[j+lidx[label]]); //PROBLEM LINE

candidate.push_back(nbr[j+lidx[label]]); //PROBLEM LINE


}



cout << "MatchSubgraph("<<i<<"):deg[sv] " << sg.deg[sv] << endl;
// find the common neighbors of all mapped neighbors
for (; k<sg.deg[sv]; k++) { // these common neighbors are the cadidates for matching
if (vmap[snbr[k]] != NONE) { // find the subsequent mapped neighbors
cout << "MatchSubgraph("<<i<<"): snbr[k] " << snbr[k] << " vmap[snbr[k]] " << vmap[snbr[k]] << endl;
u = vmap[snbr[k]];
nbr = g.nlist[u];
edr = g.eDir[u];
lidx = g.lindex[u];
ncand = Intersection(candidate, ncand, nbr+lidx[label], (Word)(lidx[label+1] - lidx[label]));
}
}
cout << "MatchSubgraph("<<i<<"):ncand value after Intersection() "<< ncand << endl;
//for debugging purpose
cout << "MatchSubgraph("<<i<<"): candidate array before direction checking " << endl;
for(int j=0; j < ncand; ++j)
cout << "MatchSubgraph("<<i<<"): candidate[" << j << "]: " << candidate[j] << endl;


// cout << "MatchSubgraph("<<i<<"):DIRECTION CHECKING BEGINS" << endl;
/*** candidates only include those nodes which agree with direction ***/
/*** we further reduce the size of the candidate array based on direction ***/
for(int m=0; m < ncand; ++m)cout << "candidate[" << m << "] " << candidate[m]<< endl;
cout << "ncand " << ncand;
for(k=0; k < ncand; ++k){ //every candidate
cout << "MatchSubgraph("<<i<<"): candidate[k] is " << candidate[k] << endl;
nbr = g.nlist[candidate[k]];
edr = g.eDir[candidate[k]];
for(m = 0; m < sg.deg[sv]; ++m){// every snbr of sv
satisfied = true;
if(vmap[snbr[m]] != NONE){ //consider only those nbgs of candidate[k] who are the images of the nbg'rs of sv
cout << "MatchSubgraph("<<i<<"):snbr[m] is "<< snbr[m] << "vmap[snbr[m]]: " <<vmap[snbr[m]] << endl;
cout << "MatchSubgraph("<<i<<"):deg[candidate[k]] is " << g.deg[candidate[k]] << endl;
for(pos = 0; pos < g.deg[candidate[k]] && nbr[pos] != vmap[snbr[m]]; ++pos); //finds the position/index of mapped snbr[m] in nbr array
cout << "MatchSubgraph("<<i<<"): pos of mapped snbr[m] "<< pos << endl;
cout << "MatchSubgraph("<<i<<"): nbr[pos] "<< nbr[pos] << endl;
cout << "MatchSubgraph("<<i<<"): sedr[m]: " << sedr[m] << endl;
cout << "MatchSubgraph("<<i<<"): edr[pos]: " << edr[pos] << endl;
if(sedr[m] != edr[pos]) // matching the direction
satisfied = false;

}
cout << "MatchSubgraph("<<i<<"): satisfied : " << satisfied << endl;
if(!satisfied && ncand != 0){ // if the direction doesn't match, then candidate[k] needs to be discarted
//ncand--; //reduces the size of the candidate array
// cout << "MatchSubgraph("<<i<<"): satisfied : " << satisfied << " ncand: " << ncand << endl;
//Swap(candidate[k], candidate[ncand]);
candidate.erase(candidate.begin()+k); //NEW:reduces the size aswell.ref[cplusplus.com]
ncand--; //since candidate vector is reduced in size by 1
//k--;
}
//if(ncand == 0)return 0;

}

}
cout << "MatchSubgraph("<<i<<"):DIRECTION CHECKING ENDS " << endl;

/************************** end of direction checking *****************/

cout << "ncand: " << ncand << endl;
cout << "i+1 " << i+1 << endl;
cout << "sg.n " << sg.n << endl;
if (i+1 >= sg.n) {
for (k=0; k<ncand; k++) {

cout << "MatchSubgraph("<<i<<"):candidate[" << k << "]: " << candidate[k] << endl;
cout << "MatchSubgraph("<<i<<"):used[candidate[" << k << "]]: " << used[candidate[k]] << endl;
if (!used[candidate[k]])
{
count++;
cout << "MatchSubgraph("<<i<<"): count: " << count << endl;
//Hist[g.infecTime[vmap[i]]]++; //WRONG
}
}
}
else {
cout << "MatchSubgraph("<<i<<"): i+1 < " << sg.n << endl;
for (k=0; k<ncand; k++) {
v = candidate[k];
if (!used[v]) {
cout << "MatchSubgraph("<<i<<"):used[" << v << "] is FALSE " << endl;
vmap[sv] = v;
used[v] = true;
cout << "MatchSubgraph("<<i<<"):Call MatchSubgraph("<<i+1<<") next " << endl;
MatchSubgraph(i+1);
vmap[sv] = NONE;
used[v] = false;
}
}
}

candidate.clear();


cout << "MatchSubgraph("<<i<<"): is DONE. EXITING " << endl;
return false;
}

ULLI SubGraph::CountSubgraph()
{
for (i=0; i<g.n; i++) {

if (sg.label[0]==g.label[i]) {
vmap[0] = i;
used[i] = true;
MatchSubgraph(1);
Hist[g.infecTime[vmap[0]]] += (count-temp);
//cout << g.infecTime[vmap[0]] << " " << Hist[g.infecTime[vmap[0]]] << endl;
temp = count;
vmap[0] = NONE;
used[i] = false;


}
}
delete [] vmap;
delete [] used;

cout << "CountSubgraph: EXITING " << endl;
return count;
}

==============================
The problem occurs in lines marked with PROBLEM LINE in MatchSubgraph() method. There are other methods and a subgraph class (represented by sg) and a graph class (represented by g) which I have deleted for the sake of compactness.

Sorry, but I don't know how to reduce the size of the methods further.

[firedraco]

I'm guessing thatnbr[j+lidx[label]] is accessing out of bounds somewhere, try using a debugger to look at the value of j and lidx[label] at that point.