Okay I'm having trouble with this assignment where we are supposed to take a vector of strings such as:

Code:

" ****"
" ****"
"******* "
"M****H*****"
"**** ******"

and create a graph using the '*' as vertices. The vertices only have edges to other '*' above, below, left or right. Not diaganol. Now here is the header for my graph:

Code:

struct Vertex{
pair<int, int> loc;
char c;
};
class Graph{
public:
Graph(std::vector<std::string> &world);
~Graph();
void insertVertex(Vertex v);
void insertEdge(Vertex u, Vertex v);
private:
std::list<Vertex> vertex_list;
std::vector< std::vector<bool> > edge_matrix;
}

and I', trying to create the graph from the given vector 'world'.

Here is my constructor:

Code:

void Graph::Graph(vector<string> &world){
for(int i=0; i<world.size(); ++i){
for(int j=0; i<world[i].size(); ++j){
if(world[i][j] != " "){
Vertex v;
v->loc.make_pair(i, j);
v->c = world[i][j];
vertex_list.push_back(v);
}
}
}
}

Now in this code for every '*' or other non-space char I create a vertex containing the character and the location and put that vertex into my vertex list. Now here is my problem, how can I update the edge_matrix without building the entire vertex_list first? The easy solution seems to be create the entire vertex list and go thru one element at a time and using the give pair coordinates search the list for other vertices either above, below, left or right and make the necessary edges if they do not exist. Although this is easy searching a list of size n 4 times over for n elements seems extremely ineffecient to me. I was wondering if I am missing some big part of building graphs here or if this is just the way it is. My book is not very helpful with adjacency matrix representations but this is what my teacher is looking for.

Thanks for reading all this, I know it is pretty lengthy but I wanted to make my question and the reason for it clear.

-AC