How to populate a graph using objects

  c++

I have an object defined like:

class Item
{
    long id;
    CString type;
    long pointingTo;
};

std::list <Item> itemsFiltered;

And let’s say that I have 10 of them in the list. They form a graph using id and pointingTo values.

10000 - 10001  // id - pointingTo
10001 - 10002
10002 - 10003
10003 - 10004
10005 - 10000
10006 - 10007
10007 - 10003
10008 - 10009
10009 - 10005
10005 - 10000

And I’m trying to fill the graph like this:

Graph g = ((long)itemsFiltered.size());

for(auto &it : itemsFiltered)
{
    g.addEdge(it.id, it.pointingTo);
}

But this crashes (segmentation fault). Probably because I am out of adj array size.

How can I fix this? What would be better way to populate the graph in this case.

This is the implementation of graph that I use.

class Graph
{
    long V; // No. of vertices

    // Pointer to an array containing adjacency
    // lists
    std::list<long> *adj;
public:
    Graph(long V); // Constructor

    // function to add an edge to graph
    void addEdge(long v, long w);

    // prints BFS traversal from a given source s
    void BFS(long s, std::list<long> listOfIDs);
};

Graph::Graph(long V)
{
    this->V = V;
    adj = new std::list<long>[V];
}

void Graph::addEdge(long v, long w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

void Graph::BFS(long s, std::list<long> listOfIDs)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;

    // Create a queue for BFS
    std::list<long> queue;

    // Mark the current node as visited and enqueue it
    visited[s] = true;
    queue.push_back(s);

    // 'i' will be used to get all adjacent
    // vertices of a vertex
    std::list<long>::iterator i;

    while(!queue.empty())
    {
        // Dequeue a vertex from queue and print it
        s = queue.front();
        listOfIDs.push_back(s);
        queue.pop_front();

        // Get all adjacent vertices of the dequeued
        // vertex s. If a adjacent has not been visited,
        // then mark it visited and enqueue it
        for (i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            if (!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
}

Source: Windows Questions C++

LEAVE A COMMENT