1. ## Help w/ graph as adjacency matrix

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

2. I don't actually understand how your representation of the edge_matrix can work. What does edge_matrix[i][j] == true mean? What do i and j represent? The i'th and j'th verticies? It seems you need to give your vertices integer labels themself, so that your edge_matrix is meaingful.

3. i was just going to use the position of the vertices in the list as their values for the matrix.

4. If you represent the graph in that fashion without any augmenting data structures, your addEdge method will be slow. You need to rethink the data structure if you want it to be efficient.

5. okay thats what i was getting at is that add edge was going to be extremely slow implemented that way but I cant find any references for building this graph using adjacency matrix. However I think im just going to completely overhaul my code and try a new approach to recursively add vertices and there associated edges from within a nested for loop.