Thread: Help w/ graph as adjacency matrix

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    89

    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. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    89
    i was just going to use the position of the vertices in the list as their values for the matrix.

  4. #4
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  5. #5
    Registered User
    Join Date
    May 2006
    Posts
    89
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  2. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 05:57 PM
  3. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 07:55 PM
  4. What is a matrix's purpose in OpenGL
    By jimboob in forum Game Programming
    Replies: 5
    Last Post: 11-14-2004, 12:19 AM