I am writing a program that processes batches of updates to a graph in the for of new nodes and edges. I recently incorporated a sliding window scheme that checks to see if the edges already in the graph are in the window, and if not deletes them. I am using a Edge and Node class as follows:
class Edge
{
public:
uint64_t source;
uint64_t target;
unsigned type;
std::string label;
uint64_t timestamp;
bool directed;
bool extracted;
Edge(){}
Edge(Edge *e);
Edge(uint64_t, uint64_t, unsigned, std::string, time_t, bool);
bool operator ==(const Edge *other)
{
return((this->source==other->source)&&(this->target==other->target)&& \
(this->type==other->type));
}
};
class Node
{
public:
uint64_t id;
unsigned type;
std::string label;
uint64_t timestamp;
std::vector<Edge *> adjacent_edges;
Node(){}
Node(Node *);
bool push_edge(Edge *e)
{
try
{
adjacent_edges.push_back(e);
}
catch(std::bad_alloc&)
{
std::cout<<"Error pushing edge"<<std::endl;
return false;
}
return true;
}
std::vector<Edge *>::iterator pop_edge(std::vector<Edge *>::iterator e_it)
{
return adjacent_edges.erase(e_it);
}
bool operator ==(const Node *other)
{
return (this->id == other->id);
}
};
On using a one dataset I get a segfault after processing 69 batch files with a sliding window size of 5 while trying to access an edge using an edge iterator. On using another dataset, I get a segfault after 69 batch files while trying to delete a non empty Edge pointer in the adjacency list (trying to free the memory). I am at my wit's end trying to figure out what is going wrong. The non-sliding window version of this program works just fine. Also I know that using a STL deque data structure would be better for sliding windows. However, I am working with pretty large code, and I would like to be able to solve this without having to use a deque. Thanks in advance. Edit: It happens on two different lines:
for (int i = 0; i < node_list.size(); i++)
{
vector<Edge *>::iterator adj_it;
for (adj_it = (node_list[i])->adjacent_edges.begin(); adj_it != (node_list[i])->adjacent_edges.end(); ++adj_it )
{
if ((max_batch_num - (*adj_it)->timestamp) > time_window)
{
deleteEdge(adj_it);
num_edges_deleted++;
--adj_it;
}
}
}
It happens on the line:
if ((max_batch_num - (*adj_it)->timestamp) > time_window)
on using the first dataset. The problem here is that even though the vector is non-empty, the pointers in the vector are pointing to memory that is not part of the application. When I use gdb to attempt to print out:
print (*adj_it)->timestamp
it gives : Attempt to take address of value not in memory
This shouldn't happen though as edges are being added to the adjacency list. And on using the second dataset the error happens when I use:
delete (*adj_it);
where adj_it is an iterator for the adjacency_list vector.
What is also weird is that if I increase the sliding window by say 'n', the same problem happens after 'n' batches.
Adding the deleteEdge function:
vector<FSM::Edge *>::iterator FSM::Graph::deleteEdge(vector<Edge *>::iterator e_it)
{
//cout<<"Deleting edge: e "<<e->source<<" -> "<<e->target<<endl;//DEBUG
FSM::Node *s = getNode((*e_it)->source);
FSM::Edge *e_tmp = (*e_it);
e_it = s->pop_edge(e_it);
if (e_tmp != NULL)
{
delete e_tmp;
}
else
{
std::cerr<<"Trying to delete an Edge pointer which is NULL"<<endl;
exit(1);
}
return e_it;
}
Also I previously used only indexes, and I tried it again after @Julius' answer. This is my new deletion loop.
for (int j = 0; j<(node_list[i])->adjacent_edges.size();j++)
{
if ((max_batch_num - ((node_list[i])->adjacent_edges[j])->timestamp) > time_window)
{
(node_list[i])->adjacent_edges.erase((node_list[i])->adjacent_edges.begin() + j);
--j;
num_edges_deleted++;
}
}
However, I am getting the same errors regardless.
BTW. I really appreciate all the comments so far. Thank you for your time.
Edit: Found memory leaks in a different part of the code using valgrind. Getting rid of that code (it wasn't really neccessary to the algorithm) got rid of it. I'm accepting @Julius' answer since it would have solved the problem according to my original statement. Also thanks to @RetiredNinja, @Beta, and @Golazo for their excellent comments.
