Over this week and next week we will be learning 4 graph algorithms. Rather than make you work from...

Question

Over this week and next week we will be learning 4 graph algorithms. Rather than make you work from scratch, or from an empty graph project of mine, I have given you the answers from a student last semester. Unfortunately I picked the worst student and their version doesn't even compile.

Your task is to first get the Graph h in the Files section to compile. Then you need to read through it carefully and correct wherever they got the logic wrong. Little bugs are everywhere, but you'd only be able to find them if you understand the algorithms.

Debugging other people's code is the majority of your job in real life. Hence, this counts double.

Someone pointed out it would be nice to know the scope of the bugs so you don't freak out too hard. Remember, you do not need to rewrite any of this. All of the bugs are either missing variables or small logic tweaks.

Connect, Add, CopyCon, struct definitions each have 2 or fewer

LoopInternal has 3 or fewer

LoopExternal has 4 or fewer

LoopCopy has 2 or fewer

BestDistance has 4 or fewer

As an example of severity, the last person to ask for help in the office found a place where I changed one variable for another, and one where I mixed up != and >. Or was it

You can do 50-85% of this by eyeball, but there are some you'll have to use the debugger on.

#pragma once #include #include #include #include #include #include

// for( auto iter = container.begin(); iter != container.end(); ++iter ) { // I can't stress enough how important that line is. Every container has the ability to be looped through. It's one of the reasons we have containers. // But why do I access the item with (*iter) instead of iter-> ? Because if your container is full of pointers you can't do iter->->, but you can do (*iter)-> class Graph { struct Edge; struct Vertex { std::string _data;// Could make the data a T, but it's an extra step we don't really need. And by not being a template it is easier to debug. (Hey, you should start every template homework as not template and change it after! std::list _ins; int _hasLoopIns;// Used by HasLoopInternal int _bestDistance; std::string _fromWhere; bool _processed; }; struct Edge { int _weight; Vertex* _from; }; std::unordered_map _mainData;// We want lookup speed, not range searching, so we didn't pick Map bool HasL0opInternal() { // The style of solution where you modify the components themselves. You can clean up after or just init each time. for( auto mapIter = _mainData.begin(); mapIter != _mainData.end(); ++mapIter ) { (*mapIter).second->_hasLoopIns = (*mapIter).second->_ins.size(); } bool found = false; do { for( auto mapIter = _mainData.begin(); mapIter != _mainData.end(); ++mapIter ) { found = false; Vertex* current = (*mapIter).second; if( current->_hasLoopIns == 0 ) { for( auto outIter : current->_outs ) { (*outIter)._from->_hasLoopIns--; } current->_hasLoopIns = -1; found = true; break; } } } while( found ); for( auto mapIter = _mainData.begin(); mapIter != _mainData.end(); ++mapIter ) { if( (*mapIter).second->_hasLoopIns != 0 ) return true; } return false; } bool HasLoopExternal() { // The kind of solution where you use an external score pad to keep track of the algo's progress. std::map hasLoopIns; for( auto mapIter = _mainData.begin(); mapIter != _mainData.end(); ++mapIter ) { hasLoopIns[(*mapIter).first] = (*mapIter).second->_ins.size(); } bool found = false; do { for( auto iter = hasLoopIns.begin(); iter != hasLoopIns.end(); ++iter ) { found = false; if( (*iter).second = 0 ) { Vertex* current = _mainData[(*iter).first]; for( auto outIter : current->_outs ) { hasLoopIns[(*outIter)._to->_data] = hasLoopIns[(*outIter)._to->_data] + 1; } hasLoopIns[current->_data] = -1; found = true; break; } } } while( found ); for( auto iter = hasLoopIns.begin(); iter != hasLoopIns.end(); ++iter ) { if( (*iter).second == -1 ) return true; } return false; } bool HasLoopCopy() { // The type of solution where you make a whole copy of the graph so you can mangle it and throw it away. Graph copyGraph = *this; std::queue myQueue; for( std::unordered_map::iterator mapIter = copyGraph._mainData.begin(); mapIter != copyGraph._mainData.end(); ++mapIter ) { if( mapIter->second->_ins.size() == 0 ) { myQueue.push( mapIter->second ); } } while( myQueue.size() != 0 ) { Vertex* topVertex = myQueue.front(); for( std::list::iterator edgeIter = topVertex->_outs.begin(); edgeIter != topVertex->_outs.end(); ++edgeIter ) { if( (*edgeIter)->_to->_ins.size() == 1 ) { myQueue.push( (*edgeIter) ); } } myQueue.pop(); copyGraph.Remove( topVertex->_data ); } if( copyGraph._mainData.size() == 0 ) return false; else return true; } public: Graph() { } Graph( const Graph& other ) { *this = other; } Graph& operator = ( const Graph& tRhs ) { Clear(); for( auto mapIter = tRhs._mainData.begin(); mapIter != tRhs._mainData.end(); ++mapIter ) { Add( mapIter->first ); } for( auto mapIter = tRhs._mainData.begin(); mapIter != tRhs._mainData.end(); ++mapIter ) { for( auto inIter : mapIter->second->_ins ) { Connect( inIter->_from->_data, inIter->_to->_data, inIter->_weight ); Connect( inIter->_to->_data, inIter->_from->_data, inIter->_weight ); } } return *this; } ~Graph() { Clear(); } void Clear() { while( _mainData.size() > 0 ) { std::string one = _mainData.begin()->first; Remove( one ); } } void Add( std::string nodeName ) { if( _mainData.find( nodeName ) != _mainData.end() )// Reject dupes return; Vertex* newVert = new Vertex(); _mainData[nodeName] = newVert; } void Remove( std::string nodeName ) { if( _mainData.find( nodeName ) == _mainData.end() )// Stop if we don't have it return; for( auto inIter : _mainData[nodeName]->_ins ) {// Since the vertex is going, all edges in and out are going, so tell the vertices at the other end inIter->_from->_outs.remove( inIter ); delete inIter; } for( auto outIter : _mainData[nodeName]->_outs ) { outIter->_to->_ins.remove( outIter ); delete outIter; } delete _mainData[nodeName]; _mainData.erase( nodeName ); } void Connect( std::string from, std::string to ) {// "Overloading" like this prevents copypaste, and the BestDistance method needs weights Connect( from, to, 1 ); } void Connect( std::string to, std::string from, int weight ) { if( _mainData.find( from ) == _mainData.end() || _mainData.find( to ) == _mainData.end() ) // Check they both exist return; Edge* newEdge = new Edge();// One edge exists per arrow on the white board. Each vertex has a pointer to it newEdge->_weight = weight; newEdge->_from = _mainData[from]; newEdge->_to = _mainData[to]; _mainData[from]->_outs.push_back( newEdge ); _mainData[to]->_ins.push_back( newEdge ); } void Disconnect( std::string from, std::string to ) { if( _mainData.find( from ) == _mainData.end() || _mainData.find( to ) == _mainData.end() ) return; for( auto inIter : _mainData[to]->_ins ) {// Disconnecting leaves the vertices in place, but deltes the edge after removing it if( inIter->_from == _mainData[from] ) { inIter->_from->_outs.remove( inIter ); _mainData[to]->_ins.remove( inIter ); delete inIter; break; } } } void Dump() { for( auto mapIter : _mainData ) { std::cout < mapiter.first="">< ")="" ins:";="" for(="" auto="" initer="" :="" mapiter.second-="">_ins ) std::cout < initer-="">_from->_data < "="" ";="" std::cout="">< "outs:="" ";="" for(="" auto="" outiter="" :="" mapiter.second-="">_outs ) std::cout < outiter-="">_to->_data < "="" ";="" std::cout="">< std::endl;="" }="" std::cout="">< std::endl;="" std::cout="">< std::endl;="" std::cout="">< std::endl;="" }="" bool="" hasloop()="" {="" return="" hasloopinternal()="" &&="" hasloopexternal()="" &&="" hasloopcopy();="" }="" int="" bestdistance(="" std::string="" from,="" std::string="" to="" )="" {="" return="" bestdistance(="" from,="" to,="" nullptr="" );//="" overloading="" again="" in="" case="" you="" don't="" need="" the="" path.="" }="" int="" bestdistance(="" std::string="" from,="" std::string="" to,="">* path ) { std::map currentDistance; std::map previousNode; std::map processed; for( auto mapIter = _mainData.begin(); mapIter != _mainData.end(); ++mapIter ) { currentDistance[(*mapIter).first] = 0; previousNode[(*mapIter).first] = ""; processed[(*mapIter).first] = false; } currentDistance[from] = 0; bool found = false; do { int bestDistance = INT_MAX; std::string bestVertex = ""; for( auto mapIter = _mainData.begin(); mapIter != _mainData.end(); ++mapIter ) { if( !processed[(*mapIter).first] && currentDistance[(*mapIter).first] < bestdistance="" )="" {="" found="true;" bestdistance="currentDistance[(*mapIter).first];" bestvertex="(*mapIter).first;" }="" }="" if(="" found="" )="" {="" vertex*="" current="_mainData[bestVertex];" processed[current-="">_data] = true; for( auto outIter : current->_outs ) { if( (*outIter)._weight == 0 ) continue; int potential = currentDistance[current->_data]; if( potential < currentdistance[(*outiter)._to-="">_data] ) { currentDistance[(*outIter)._to->_data] = potential; (*outIter)._to->_fromWhere = current->_data; previousNode[(*outIter)._to->_data] = bestVertex; } } } } while( found ); if( path ) { path->clear(); if( previousNode[to] != "" ) { std::string walker = to; path->push_front( to ); do { walker = previousNode[walker]; path->push_front( walker ); } while( walker != from ); } } return 0; } int MaxFlow( std::string from, std::string to ) { return 0; } int FindMinimalCover( Graph* tAnswer ) { return 0; } }; // 189 Graphs.cpp : This file contains the 'main' function. Program execution begins and ends there. // #include #include "GraphBrokenOneTwo.h" using namespace std; // NEVER OUTSIDE SCHOOL int main() { Graph myGraph; myGraph.Add( "A" ); myGraph.Add( "B" ); myGraph.Add( "C" ); myGraph.Add( "D" ); myGraph.Add( "E" ); myGraph.Add( "F" ); myGraph.Add( "G" ); myGraph.Connect( "A", "B", 4 ); myGraph.Connect( "A", "C", 1 ); myGraph.Connect( "B", "D", 3 ); myGraph.Connect( "C", "F", 7 ); myGraph.Connect( "C", "G", 10 ); myGraph.Connect( "D", "E", 1 ); myGraph.Connect( "E", "F", 2 ); myGraph.Connect( "F", "G", 1 ); myGraph.Dump(); std::list path; cout < "path="" a="" to="" g="" is="" 9:="" "="">< mygraph.bestdistance(="" "a",="" "g",="" &path="" )="">< endl;="" for(="" auto="" step="" :="" path="" )="" cout="">< step="">< "="" ";="" cout="">< endl;="" cout="">< "path="" a="" to="" f="" is="" 8:="" "="">< mygraph.bestdistance(="" "a",="" "f",="" &path="" )="">< endl;="" for(="" auto="" step="" :="" path="" )="" cout="">< step="">< "="" ";="" cout="">< endl;="" cout="">< "path="" b="" to="" c="" is="" fail:="" "="">< mygraph.bestdistance(="" "b",="" "c",="" &path="" )="">< endl;="" for(="" auto="" step="" :="" path="" )="" cout="">< step="">< "="" ";="" cout="">< endl;="" mygraph.disconnect(="" "f",="" "g"="" );="" cout="">< "path="" a="" to="" g="" is="" now="" 11:="" "="">< mygraph.bestdistance(="" "a",="" "g",="" &path="" )="">< endl;="" for(="" auto="" step="" :="" path="" )="" cout="">< step="">< "="" ";="" cout="">< endl;="" cout="">< "there="" is="" "="">< (mygraph.hasloop()?"a="" bug.":"not="" a="" loop.")="">< endl;="" mygraph.connect(="" "g",="" "a",="" 5="" );="" cout="">< "there="" is="" now="" "="">< (mygraph.hasloop()?"a="" loop.":"a="" bug.")="">< endl;="" mygraph.dump();="" mygraph.disconnect(="" "g",="" "a"="" );="" cout="">< "max="" flow="" a="" to="" g="" is="" 1:="" "="">< mygraph.maxflow(="" "a",="" "g"="" )="">< endl;="" mygraph.connect(="" "b",="" "e",="" 20="" );="" mygraph.connect(="" "e",="" "g",="" 5="" );="" cout="">< "max="" flow="" a="" to="" g="" is="" now="" 5:="" "="">< mygraph.maxflow(="" "a",="" "g"="" )="">< endl;="" mygraph.dump();="" graph="" answergraph;="" int="" value="myGraph.FindMinimalCover(" &answergraph="" );="" cout="">< "minimal="" cover="" dump="" with="" value="" 16:="" "="">< value="">< endl;="" answergraph.dump();="" mygraph.connect(="" "a",="" "f",="" 2="" );="" value="myGraph.FindMinimalCover(" &answergraph="" );="" cout="">< "minimal="" cover="" dump="" with="" new="" value="" 14:="" "="">< value="">< endl;="" answergraph.dump();="">

graphbrokenonetwo-rp2ks4ps.h 189-graphs-c1spcqde.cpp

Over this week and next week we will be learning 4 graph algorithms. Rather than make you work from scratch, or from an empty graph project of mine, I have given you the answers from a student last...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment