0

I've been working on this one issue for 3 days and I'm stumped. We have to implement prim's algorithm using 2 maps(string, Vertex(class) and string,vector). The first one stores a letter as the name and pi and key within the vertex class. The 2nd map stores the letter name of a vertex and a vector of all its neigbors. I'm getting compile errors and it's because I'm having trouble accessing the elements of the vector within the map. Anyways, here's my code. (n.weight I know is wrong because it's an iterator but I need that neighbor class within that spot in the vector to access the weight variable)

void Graph::mst(string start){
     string u;
     if(vertices.find(start) != vertices.end()){

        for (std::map<string,Vertex>::iterator it=vertices.begin(); it!=vertices.end(); ++it){
           it->second.key = 100;
           it->second.pi = "NIL";
        }
        vertices[start].key = 0;

        for (std::map<string,Vertex>::iterator it=vertices.begin(); it!=vertices.end(); ++it){
           minQ.insert(it->first, it->second.key);
        }
        u = minQ.extractMin();
        while(u != "empty"){
           cout << u << " " << vertices[u].pi << " " << vertices[u].key <<endl;
           for (std::vector<Neighbor>::iterator v = adjList.find(u)->second.begin();
                 v!=adjList.find(u)->second.end(); ++v){
              if(minQ.isMember(v->name) && vertices[u].key < (problem here)){


              }
           }
        }  

        u = minQ.extractMin();
     }  
  }
Deduplicator
  • 44,692
  • 7
  • 66
  • 118
Mike1982
  • 439
  • 10
  • 26
  • It looks like you are adding edges one way only, but this algorithm is for undirected graphs. You need to add an edge to the adjacency list for both ends. – Kenny Ostrom May 06 '17 at 03:31
  • 1
    You probably should not post line numbers with the code, in case someone tries to copy-paste. – Kenny Ostrom May 06 '17 at 03:44
  • ooo ty for the advice there kenny – Mike1982 May 06 '17 at 03:50
  • thanks kenny for your input. In my mst.cpp which I didn't post (sorry for not clarifying), I have a readGraph function and in the read Graph function it calls addVertex once (in a while loop until end of line) and addEdge twice (in a while loop to determine end of file). One with arguments passed for "to" and "from" and the 2nd time with values reversed. Would that work or would it be better to do it within the function itself? – Mike1982 May 06 '17 at 03:55
  • void MSTapp::readGraph(){ string vertices; string from; string to; int weight; while(cin >> vertices){ if(cin.peek() != '\n'){ myGraph.addVertex(vertices); } else{ myGraph.addVertex(vertices); break; } } while(cin >> from){ cin >> to; cin >> weight; myGraph.addEdge(from, to, weight); myGraph.addEdge(to, from, weight); } myGraph.mst("A"); } – Mike1982 May 06 '17 at 03:57
  • ah shoot it didn't format that one properly. It's the readGraph function – Mike1982 May 06 '17 at 03:57
  • sorry i'm new on here. I know when posting original question it's ctrl-k to format code, but that's not working when adding it to comment. – Mike1982 May 06 '17 at 04:00
  • You can edit the original question. So you add both ways elsewhere, I kinda suspected, so that's not the problem. No need to post the read graph function -- although you may want to write a main function which creates a small hardcoded graph which produces an incorrect answer. – Kenny Ostrom May 06 '17 at 04:05
  • Thanks again for your replies. readGraph is called from main() which starts taking input via cin. The test file I made is: A B C D E F G /n A B 3 /n A E 4 /n B C 7 /n, etc. My output should be A NIL 0 /n B A 3 /n etc, (no need to list it all out). It prints them all as A NIL 0, so my vertexes aren't getting updated properly and I've been playing with that if statement for a while. I'm sure it's there. Iterating through the adjecency list I'm confused with and checking weight of neighbors – Mike1982 May 06 '17 at 04:38
  • Oops sorry I just realized that if statement doesn't do anything right now, won't compile because .second I'm trying to use as a map function, but it's trying to use it as a vector function. I got it to compile once with something that logically shouldn't work anyways and won't update the values of key and pi. – Mike1982 May 06 '17 at 04:43
  • I'm not following your logic in Graph::mst(). I just woke up, but either I need more coffee, or you are iterating over vertices where you should be iterating over edges (which meet certain conditions). Maybe you should start over with pseudocode and good variable names, then fill in with the real code. – Kenny Ostrom May 06 '17 at 13:14
  • Also, your heap's decrease operation is O(n) and your insert uses your decrease (and is guaranteed to check the correct key last even though you know where it is). There's some good info at http://stackoverflow.com/questions/9209323/easiest-way-of-using-min-priority-queue-with-key-update-in-c if you want to improve that. – Kenny Ostrom May 06 '17 at 13:20
  • Are you talking about line 58? I'm iterating through the vector Neighbor and using adjList.find to find that vector within the map to iterate through. Is that part not correct logic? I'll run gdb again and make sure i'm getting the correct neighbor. Also, thanks for the advice on decreaseKey. you're right, it needs to run in O(lgn) time, so i don't think i need that first iterator – Mike1982 May 06 '17 at 16:04
  • hmm may need to wait until i get this prim one done first to fix the decreaseKey. Everything works right in that, but i don't see a way to do it without that for loop. When an id is passed, it has no idea what spot in the vector holds that id, so it needs to iterate first to find it and then do swaps. The pseudocode in the book assumes the ordering is numbered the same way the heap is. – Mike1982 May 06 '17 at 16:28
  • The link in my comment above tells how to handle that. However, can you implement without a heap, and then (once that is working on the test case) modify it to use a heap? Then fix the heap so it actually has heap performance. – Kenny Ostrom May 06 '17 at 19:57
  • That's a good idea. I was thinking that, but then I have to redo project 4 which was a prereq to this project. I would have to implement a priority queue a different way for use of this project. I think I'll just back track and redo the decrease key and get that working. I'm still stuck on iterating through the neighbors vector of the of a specific key in the map and getting weight of each neighbor though. Then I guess if I get that part working right and the decrease key fixed, I can figure out what values need to go in decreaseKey and it should work – Mike1982 May 06 '17 at 21:21
  • But prim's algorithm is a lot easier to do without the heap. – Kenny Ostrom May 06 '17 at 21:29
  • That's true, it took me a week to do just the minPriority project lol. It works properly, just not in the right time. I wanted to do it with a map, but the requirements she gave us stores an id and a key in a vector of Element classes. No way to keep track of spot in array for use in decrease key. Anyways, spent some time time on that and can't figure out how to do it in O(lgn) time, there are many suggestions on that link you gave me, but it seems they're doing it in a map, or the lazy delete which seems kind of inefficient (worse than the way i'm doing it). – Mike1982 May 06 '17 at 23:26
  • I'm updating original problem, made some changes still can't get it working. – Mike1982 May 06 '17 at 23:26
  • update on decreaseKey issue. I emailed my teacher, she said what I have is fine because even though decreaseKey is supposed to run in O(lgn) time, Lookup for a minHeap is O(n) time and in our case we are doing a lookup in our decreaseKey function and then decreasing the key. Usually you'd be given the old priority as an argument, but we're not. – Mike1982 May 07 '17 at 01:25
  • Haha figured it out, overthining it. so simple. v->weight. V is my iterator through the vector of neighbors, just dereferencing v will get me the weight from that neighbor – Mike1982 May 07 '17 at 01:54

0 Answers0