Frequently Asked Questions about HW6


Q.
Do we need to use a sentinel (in the input) to know when there are no more edges? I.e., the input file does not indicate how many edges there are before it lists the edges.

A.
No sentinel is needed. If a file is redirected into a program, then EOF will be reported when the end is hit. The same is true if the data was typed at the keyboard, it's just that in that case the user has to signal end of file (this is done by typing Ctrl-D on UNIX and Ctrl-Z on PCs).


Q.
Since output is only going to the screen, why do the functions in the Appendix take outfileP's?

A.
Providing the outfileP parameter is the most generic way to write those functions. That way you can use them to print to any file (not just Standard Output).


Q.
For Homework 4, we did not use ADTs/CDTs. Should we change the stack so that it uses ADTs or can we just use it as it is?

A.
Just use it as it is (you will have to change the stack element type). It's good to practice a program in which the data structures followed different designs.


Q.
The graph is input in the format like:
n
1 2
3 4
5 6
Again, what does this represent?

A.
The n (a number) tells you that there are vertices 1 through n. Lines like "1 2" represent an edge, here from vertex 1 to vertex 2 (bidirectional). Note that n may indicate the existence of vertices for which there are no edges listed afterward.

(See below for additional comments about the other thing the program needs--the vertex whose component to print.)


Q.
Should we prompt the user for this input?

A.
A graph will either be entered at the keyboard or redirected in from a file, so printing prompts is not a bad idea. See above about how to know when there are no more edges to read in.


Q.
Can we traverse the component (as the graph is entered or later with the stack) in the main program?

A.
No. Even though we have given you flexibility in how you design your graph data structure, it should still be a good design. I.e., its interface should provide a function to do the component traversal AND the fact that a stack is being used for the traversal should be hidden in the module implementation.

In addition, the main program should not be poking into the representation of the graph, even if you choose not to use ADTs/CDTs. Note that using ADTs/CDTs prevents poking from happening.


Q.
Is recursion necessary for this homework?

A.
Recursion is not necessary since the only backtracking needed is with the component traversal, but that's taken care of by the stack.


Q.
For every test run that we do, we run the program for each one? So we prompt the user for the graph, construct the graph, prompt the user for what they want to find, print that out, then terminate the program? So in order to do the next trial run, we run the executable again, right?

A.
Yes. Remember that an additional thing you need as input is the vertex whose component to print. You can even read that in as the first (or second) thing if that makes inputting easier (recall that you don't know how many edges there are ahead of time). Just make sure your prompts and program documentation indicate the order in which that piece of info is expected.

You can also run your tests by redirecting in a file.


Q.
For the make file, who depends on the stack header besides the stack implementation?

A.
Ask yourself: Does the main program use any stack functions OR is the stack just used to implement part of the graph (and thus, is hidden from the main program, but also implies that something else depends on it)?


Q.
Although we don't have to, are we allowed to use ADTs/CDTs for the stack module?

A.
Yes.


Q.
When we print out the component of a vertex, can we print out that vertex itself? Also, do we need to print them out in any particular order, or can we just let them print out as the stack would print them out.

A.
The vertex itself is a member of its component (the example on the write-up does just that). Whatever order the stack and your implementation of the graph implies is is fine.


Q.
Is it possible to do a combination of file redirection and keyboard input? I want to use the keyboard input to ask for different components to print.

A.
Not without doing something that is not portable. Just have the program read in one graph and print out one component for the graph and then terminate.


Q.
What is GraphPrintComponentWith supposed to do? Does it print all the elements to which withElement is DIRECTLY connected? Or, does it print all the elements that are reachable from withElement via as many connections as is necessary?

A.
The 2nd (as many connections as is necessary).


Q.
Since I'm redirecting input in from a file, should I include that in my script file and submit it as well?

A.
Sure. You should "cat" it right before you run your program on it.


Q.
In my component traversal, after I pop out a vertex why do I have to push more in?

A.
Remember that you have to print out all vertices in the component, not just the ones that are one edge away from the starting point. So, when you pop off the first set of vertices, there may be more (connected from those vertices) to push on and process later.


Q.
Is it acceptable to print the comma separating vertices in the component in the GraphPrintComponentWith function, or is that not generic enough?

A.
Well, PrintElement does the printing, so it is best to resolve any printing issues in PrintElement. Commas are not necessary though.


Q.
For my graph module, if I'm adding an edge that already exists, should I print an error, or just return (sucessfully)?

A.
There's no reason why you can't have 2 edges (or more) from vertex 1 to vertex 2 (for example). So, add it as many times as they ask to.


Q.
Can we just set the visited flags to false when we create vertices?

A.
Well, what would happen if you set the visited flag only when you create a vertex, but then call your component traversal twice? Remember, we always want to write more generic, reusable code in our modules, even though a specific program may use it in limited ways (e.g., by only printing one component and then terminating).

So, a better design will set these flags to false in each algorithm that uses them.


BU CAS CS 113 - FAQ - HW6