Dynamically adding to a graph data structure

Question

Let me first state that I just want direction, not necessarily actual code, unless a small snippet is the only way to get the point across.

I need to create a DIRECTED graph data structure using an adjacency list or matrix in C++, and add vertices/edges from standard input, which means dynamically.

I think I'd be able to create a graph fine if I was able to instantiate a set of Vertices first, then create edges and add them to the graph, but I don't understand how it is possible to add an edge which contains a vertex that hasn't been instantiated yet.

for example, the first line from standard input reads:

Miami -> New York/1100 -> Washington/1000 -> albuquerque/1700

How am I supposed to add an edge from Miami to New York if the New York vertex hasn't been added to the graph yet?

Thanks for the direction everyone!

Answer 1

how it is possible to add an edge which contains a vertex that hasn't been instantiated yet.

Simple: instantiate it..

I do not see any issue with this. Assume V to be the vertex set seen so far. V is initially empty. As you read the input x->y, you get its end points (x and y). If any one of them is not instantiated (i.e., not in V), you instantiate it and add it to the vertex set.

Another way to look to it: imagine we are defining the graph by its edge set E. By definition any edge is a pair of vertices which in turn defines the vertex set of the graph.

Answer 2

How about you resize the adjacency list each time a new unique node comes in? You can maintain a set of unique node values and use its size to adjust the size of the adjacency list each time you have to add a node. Below is a some code that does the same.

class Graph
{
    public:
    // Add links in the graph
    void addLink(int id1, int id2){
        // Add to hashset
        uniqueNodes.insert(id1);
        uniqueNodes.insert(id2);
        // Resize on the adjacency list based on how many nodes exists in the uniqueNodes set
        adjList.resize(uniqueNodes.size());
        // Make the connections assuming undirected graph
        adjList[id1].push_back(id2);
        adjList[id2].push_back(id1);
    }

    // Print the graph
    void printGraph(){
        for(int i = 0; i < adjList.size(); i++){
            cout << i << ":";
            for(auto it = adjList[i].begin(); it != adjList[i].end(); it++)
                cout << *it << "->";
            cout << "NULL\n";
        }
    }

    private:
    // Adjacency list for the graph
    vector<list<int>> adjList;
    // Hashset to help define the size of the adjacency list as nodes come in
    set<int> uniqueNodes;
};