代写Graph相关的算法作业，需要编写DFS(Depth-first search)和SCC(strongly connected
component)两个算法。
Reading
Read the text, sections 7.1 - 7.4 for explanations of what the dfs skeleton
and dfsTrace functions are are doing. This has been covered in lectures and
will be covered further in sections.
Depth-first search (DFS) is a major topic for this course.
Read the text, section 7.5 for explanations of how the the SCC algorithm is
based on DFS. The SCC algorithm will be covered in lectures before the
assignment is due, and further in sections.
Depth-first search (DFS) and the strongly connected component algorithm (SCC)
are major topics for this course.
Several online Unix tutorials are mentioned on the class web page.
Information Sources
Same as ho04.txt and ho07.txt, the 1st and 2nd program assignments.
There are usually quite a few questions and clarifications about programs on
the “C101” mailing list, so keep up. Consider the source when evaluating a
message, because there is no screening of the postings.
Program Requirements
You will implement Depth First Search as explained in the text, Ch. 7. This
will be the DFS skeleton for directed graphs, with some added code to carry
accomplish the functions described. The procedure will correspond closely to
DFS Trace in the text.
The added work after DFS Trace works is to find the strongly connected
components (SCCs) for unweighted graphs.
dfsTrace1.c
Implement dfsTrace (Algorithm 7.4, which is a refinement of Algorithm 7.3) on
a directed graph represented as an array of adjacency IntVecs. (Note that
graph02.c and the associated files in pa02, your second program assignment,
read a directed graph from input, create the array of IntVecs, and print the
graph, so you can simply copy this code from your WORKING pa02. If pa02 was
working correctly, this allows you to concentrate on DFS and SCC parts of the
program.)
intVec.h should be commented as found in the class locker. It is almost the
same as in pa02, but has one new constructor.
Although intList.h and intList.c are not actually used in this assignment,
they should be programmed and working, as assigned in pa02. They will be part
of the grading for pa03.
In this assignment, your intVec.o will be tested with other students’ programs
and their intVec.o will be tested with yours. So use the standard names in
this class. A starter intVec.h is in the course locker, but you need to copy
it and put in your comments, as indicated by the questions in the file. The
starter for pa02 is there too, named intVec.h-pa02, so you can see what
changed with “diff”.
Reuse the main c file from pa02
Right from pa02, graph02.c can be renamed to scc03.c and compiled into scc03,
for pa03; it contains main() and probably other functions. Several other C and
.h files can be used right from pa02.
Of course, for pa03, the “main” procedure will be changed to do different
things after the graph is loaded. Also, the loadGraph functionality will be
separated, as assigned in pa02.
High-level flow
main() should read and interpret the command-line parameters, which are
different from in pa02, then open the input file and interact with loadGraph.c
functions to input the graph, as in pa02. main() should call a function to
print the graph, as in pa02.
To compute SCCs, main calls a function with a name like findSCCs() that is
also in scc03.c to manage the SCC computation. findSCCs() should call the main
subroutines dfsTrace1(), transposeGraph(), dfsPhase2(), as well as calling the
printing functions. In particular, dfsTrace1(), transposeGraph(), dfsPhase2()
will not print anything. Their job is to compute data structures.
findSCCs() in scc03.c will allocate the arrays filled by its subroutines.
Because there are two runs of dfsTrace now, name the arrays filled by
dfsTrace1(): discoverTime1, finishTime1, parent1, and finishStk1, or
recognizable abbreviations, such as dtime1, etc.
Also findSCCs() allocates adjVerticesT for the transpose graph. Finally, it
will allocate the arrays filled by the second dfs,
which works on the transpose graph and finds the SCCs: discoverTime2,
finishTime2, parent2, dfstRoot2 (or abbreviations).
Other procedures will output the contents of the arrays after each dfsTrace
has completed.
Allocating all the arrays in scc03.c makes it easier to pass them as arguments
to functions in other files, without making any global arrays. However, if you
already have working code that allocates and returns an array from a different
file (such as loadGraph.c) it is okay to use and build upon that code.
A more sophisticated way to pass several run-time parameters is that main() or
findSCCs() creates a struct with fields for all of them, and then a pointer to
that struct is passed around. For this technique you should declare the struct
AS A TYPE in scc03.h. Then scc03.c and loadGraph.c and maybe others #include scc03.h .
Write dfsTrace1.h to declare the function prototypes in dfsTrace1.c that are
called from a different C file. State the pre- and post-conditions in
dfsTrace1.h.
In pa03 dfsTrace1.c should be a separate file and you should have it working
before copying it into dfsPhase2.c as a starter.
It is better to copy working code than debug both versions.
Aside from intVec.h, intVec.c, scc03.c and scc03, the names of files,
functions and arrays should be understandable but do NOT need to be strictly
the same as this handout.
Command-line arguments
If your program receives no command-line arguments, it should print a usage
message and exit. If your program receives incorrect command-line arguments,
such as an unknown flag or no file name, it also should print a usage message
and exit with a positive exit code, such as 1 or 2 or 3.
Command-line arguments of the form “-something” are often called “flags”, and
provide the means for varying the way the program runs, or varying the form of
the output. (“-“ by itself denotes stdin.)
The final command-line argument is the name of the input file, and this name
will not begin with a “-“ unless it is “-“ by itself.
As in pa02, the “-V” flag denotes that IntVec should be used for lists and
stacks.
The new command-line flag “-u” instructs the program to build an undirected
graph from the input. That is, if the input contains “3 5” on a line, enter 5
as an adjacency of 3 and enter 3 as an adjacency of 5. Do not worry about
duplicate edges.
DFS Trace will expect the graph not to be weighted. Therefore weights in the
input should be parsed if they are present, but they do not become part of the
data structure for the graph.
In pa03 IntList will not be used (although intList.h and intList.c are still
required to be submitted and working). Therefore if a flag “-L” is present on
the command line, that is an error, and should be treated as specified in the
first paragraph of this subsection..
The flags -u and -V may be in either order before the file name. The -V is
required for compatibility; -u is optional.
When running the program on a large input file remember to use > to
redirect the stdout to a file. Do not submit very large test files or their
outputs. We will supply some large files.
Example command lines for doing SCCs:
scc03
(user wants usage message.)
scc03 -V -
(user wants type in the file, directed.)
scc03 -V test1.in
(test1.in is treated as directed.)
scc03 -u -V test2.in
(test2.in is treated as undirected.)
Input format
This is the same as pa01 and pa02, repeated for self-containment.
Input consists of a sequence of lines read from a file that was given as the
LAST command-line argument. The string “-“ as a filename stands for standard
input, as usual. We will use stdin to denote either case.
End-of-file signals the end of input, and is typed on the keyboard as cntl-D
in Unix (maybe cntl-Z in DOS, Windows, etc.).
Lines will have the format expected by graph01.c with or without without
weights.
One int on the first line to tell us the value of “n”. Two ints per line for
each edge after that, or two ints and a double per line if the graph is
weighted. For pa03, weights are parsed but ignored, even if they are present
in the input.
Print an informative error message if the input contains a bad vertex number,
outside 1,…,n, or has the wrong number of words on a line. This is for your
own protection. It is not a grading issue and submitting tests to check bad
input is not asked and will not count as testing credit.
Example 1 input, unweighted
1 4
5 4
1 3
2 3
3 3
5 6
6 5
4 3
1 2
Remember that graphs want to start on index 1, not index 0. So allocate 1
extra space in the array and start loading at 1.
Example 2, with weights:
1 4 2.7
5 4 -3
1 3 0.0
Undirected input
Whether the input is treated as undirected or directed depends on a command-
line argument “-u”, as described before. If the graph is considered
undirected, create an edge in each direction from one edge in the input file.
In the above example, when “-u” is specified, “1 4 2.7” should result in edges
(1,4) and (4,1). If “-w” was also specified, both edges have weight 2.7.
Do not worry if edges are not unique. The algorithms will work anyway.
OUTPUT
Print information on stdout. You should know how to structure your unix
command line to redirect stdout to a file or another process, so your program
is not concerned about these details.
For a preliminary version, print the input graph as in pa01, ignoring edge
weights even if “-w” was specified.
Example 2 would look something like this:
1 [3, 4]
2 []
3 []
4 []
5 [4]
6 []
Using “[]” instead of “null” for an empty list is preferred. Details like
punctuation may vary but the numbers should be in the order shown.
It would be quite complicated to try to show that structure of the DFS forest
graphically, so for phase 1, write a procedure that just prints a table of 5
columns for vertex, color, dtime, ftime, and parent. In that order (spacing is
flexible). Do not use numbers for colors! Include column titles (exact
spelling not required) and print an empty line after the table.
Use “-1” for the parent if the vertex is the root of a DFS tree.
This first table should present the arrays filled by dfsTrace1. Also print the
arrays filled by dfsTrace1 to show whether the graph is being visited
correctly.
Example 2 after dfsTrace1 is finished would look something like this:
V color dTime fTime parent
1 B 1 6 -1
2 B 7 8 -1
3 B 2 3 1
4 B 4 5 1
5 B 9 10 -1
6 B 11 12 -1
Color should be one of W,G,B and other table entries are ints.
The reason for making this a procedure is so you can call it at any time (in
gdb, most likely, or in debugging code that you remove later).
If you call this print function BEFORE dfsTrace1 is finished, every vertex
with color W should show 0 for the last 3 columns, and every vertex with color
G should show 0 for fTime. This might be helpful for debugging and for midterm
studying, but should not occur in the submitted program.
After the table for dfsTrace1, print finishStk1 ON A SINGLE LINE with the
bottom element to the left, top to the right.
E.g.,
FSTK: 3 4 1 2 5 6
There should not be any other numbers on this line. The title and spacing are
flexible, but don’t make the mistake of using “FSTK1”.
Print the transpose graph in the same format as the original graph. The same
print function should work for both (the title can be printed before calling
the function or passed as a parameter).
The last part of the output shows the result of dfsTrace2. This shows values
for the tranpose graph. Write a separate procedure for this.
Example 2 after dfsTrace2 is finished would look something like this:
V color2 dTime2 fTime2 parent2 dfstRoot2
1 B 7 8 -1 1
2 B 5 6 -1 2
3 B 2 3 -1 3
4 B 9 10 -1 4
5 B 3 4 -1 5
6 B 1 2 -1 6
This is a pretty boring example, and just shows the format, not an interesting
test. Every dfs tree has one vertex and no edges. Every SCC has one vertex and
is its own dfsRoot.
How to preceed
Make a new directory to work in. Do this first.
If you wrote a weighted edge ADT for pa01, save it for last. (It was not
assigned in pa01.)
You need to use the standard names given in this section so your ADTs can
interface with other students’ clients and vice versa.
The function names in the intList ADT must be as given in the intList.h
starter file for pa01 and pa02. The function names in the intVec ADT must be
as given in the intVec.h starter file for pa02.
These names must be spelled and capitalized as shown in that file.
For this program, loadGraph.c should be a separate file, although that was not
required in pa01. loadGraph.h will provide the interface. Functions in
loadGraph.c that are only called within loadGraph.c should not appear in
loadGraph.h.
loadGraph is not required to be an ADT, so the functions and prototypes do not
need to agree with other students. Similarly, dfsTrace1 and dfsTrace2 are not
ADTs.
dfsTrace1 needs to build a finishing-time stack, call it finishStk1. Starting
with an empty stack at the beginning of dfsTrace1(), simply push v (the vertex
whose visit is finishing) on to the stack at its finishing time, as explained
in Section 7.5. finishStk1 should be implemented as an IntVec with the new
constructor intMakeEmptyVecN(). What should the parameter be for this
constructor so you never need to do a realloc on it?
NEW FUNCTION: transposeGraph()
Write a function to transpose a graph, after it is built. Make your function
as simple as you can to be sure it is correct. There is a fast way to do this,
but if you do not see it, think of a simpler, possibly slower, way.
For C the function prototype is
IntVec* transposeGraph(IntVec* origGraph, int n);
—|—
It may be implemented in scc03.c; a separate file is unnecessary.
The transpose graph has edges in the opposite direction of the original graph,
in one-to-one correspondence. Suppose the original graph prints like this
1 [ 3, 2 ]
2 [ 3, 4 ]
3 [ ]
4 [ 1 ]
The transpose graph should have edges (2,1), (3,1), (4,2), (3,2), (1,4), and
print accordingly. Most likely it would appear as
1 [ 4 ]
2 [ 1 ]
3 [ 2, 1 ]
4 [ 1 ]
but other orders are possible. See the text for more details. if needed.
NEW C FILE: dfsPhase2.c
dfsPhase2() in dfsPhase2.c will implement phase 2 of the SCC algorithm, and
also will compute discoverTime2, finishTime2 for insurance, although the SCC
algorithm does not need them.
After you get dfsTrace1.c working, you should be able to use almost all the
code here, with some name modifications.
Keep in mind that dfsPhase2() uses finishStk1 for dfsSweepT() and operates on
the transpose graph. The recursive function is named something like dfsT() or
dfsTrace2(). Read the text for details.
An additional array, dfstRoot2, will be filled to keep track of the separate
DFS trees in a second dfs. Some function prototypes will be altered to pass
this value down from dfsTsweep() through dfsTrace2() calls.
The purpose of dfstRoot2 is to tell every vertex who is its SCC leader.
dfsSweepT() passes the number of the root into the recursive function dfsT.
(Where does dfsSweepT get this number from?) Then dfsT(v, …) puts this number
into dfstRoot[v] and passes this number down into its own recursive calls of
dfsT().
Write dfsTrace1.h and dfsPhase2.h to declare the function prototypes in the
respective C files, and state the pre- and post-conditions.
