Last Modified: April 15, 2004
|
C M S C 2 1 4 C o m p u t e r S c i e n c e I I S p r i n g 2 0 0 4 |
ilist[v] in any of the build* methods.
Make sure your operator< in EndPoint follows the directions in this FAQ and the header files correctly.
The comments were slightly convoluted. Here is an example with the < operator. In the EndPoint class, if the Vertex < other.Vertex, then return true. If they are not equal, return false. If they are equal, return the result of Cost < other.Cost. It works similarly. If cost < other.cost, return true. If they are not equal, return false. If they are equal, do the same things for v0, and then v1 if v0 are equal.
ilist[v] in any of the build* methods.
Since ilist[v] can potentially modify the ilist. So, the operator[] in the map class cannot be const (like the build methods). To actually access those methods, use a map const_iterator to get it, using the find function.
After reading a bunch of textbooks and looking at a few applets for BFS traversals, no one seems to have a universal agreement, as there are way too many ways to do it. For those of you wondering, as you add a Vertex to the list of edges that will be processed, whatever vertex you added it from (i.e. the vertex that you used to get to the other vertex), the edge is automatically added to the new spanning tree.
The output is the spanning tree created by a DFS or a BFS, not the exact path traversed.
I won't give away the answer, however, suppose we have map<int, set<float> > m, to insert 3 with an empty set, is simply m[3] = set<float>();
I guess I didn't bother with private member functions (except one), but others seem to want to use them. If you would like to use any of the standard template library structures in arguments to private member functions, please add them to the top of all of the cpp implementation files that includes them before all other includes. This way, that header file is included before the file that uses it is included. We will grep (type man grep on a unix shell) for all includes so we can add those to our test files, if necessary, at the top of each cpp implementation file. We will more than likely include the five STL structures we mentioned on the project page.
I have CHANGED Graph.h to include Edge.h at the beginning. Please update your files BEFORE submitting, regardless of whether or not you use an Edge in a private member function.
There is a multitude of online resources to find information on the standard template library. Google is your best friend. However, an even better best friend would be looking at the examples provided to you in the posting account for P5, and also a document in the posting account under the Handouts directory called assoc.containr.doc and assoc.containr.txt (txt has no graphics though). This will also be gone over in lecture tomorrow (04/20).
In lab, breadth first search (BFS) could have been done using either one of two criteria: alphabetically or chronologically. We'll use both as follows:
1 - you will be given a starting VertexI left out a few details, such as which node to connect each one printed to. That will be left up to you to figure out (based on which vertex you were at when you added it to the data structure.
2 - keep track of all nodes you need to process in some sort of ordered data structure, one which the first one inserted will always be the next one taken out of it, then the line moves up
3 - place the starting Vertex in that data structure
4 - while the data structure is not empty
4a - take the next element out of the data structure [chronological ordering, based on when they were added]
4b - print out that element
4c - for all of the verticies it is adjacent to and have not been printed yet and not added to that data structure, add them to that ordered data structure in alphabeitcal order
In the constructor, you can use initalization lists to instantiate the Vertex objects. Here is an example of using an instatiation list:
class Integer {
private:
int my_int;
public:
Integer(int i) : my_int(i) {}
void print() { cout << my_int << endl; }
};
class A {
private:
Integer my_int;
public:
A(int i) : my_int(i) {}
void print() { my_int.print(); };
};
For this project only, please send all clarification questions to Chris Almazan <bt214007@dc.umd.edu>. Please submit questions only if something is unclear in the project description, header files, or a mistake. Please come to one of the TA's office hours if you have any specific problems about your project. If you do need to see Chris, his office hours are Tuesday (11am-1pm) and Wednesday (1pm-2pm, 3pm-4pm). If necessary, he will schedule additional office hours.
Project #5 is due by 11pm on Friday, April 30th, 2004.
[02:25pm at 04/16] A small typo was found on the main project webpage. testEdges.cpp should be testEdge.cpp in the unit test section, and make p2 should be make p5 on the how to submit section. Sorry if this caused any confusion.
[02:51pm at 04/21] Graph.h has been updated. Please update your files, especially before you submit your project.
[01:18pm at 04/16] The posting account directory has been completed filled up. Please visit it. Also, if you did not make it all the way down the project description page, the stl examples are in the posting account for you to consume.
[08:51am at 04/15] If you notice in the posting account that tertiary.input and tertiary.output are not in there, that means an older copy of the project was placed in there. However, if you have already started, none of the C++ code has changed, so you can simply copy over the whole directory into your account when tertiary.input and tertiary.output appear (the header files have better clarifications).
|
See the class syllabus for policies concerning email Last Modified: April 15, 2004 |
|
|
|
|
|