Description
prob1: linked
As you know web pages can contain links to other pages. Even if one page does not link directly
to another page, you might still get from one page to another by following links on pages in
between. For example, suppose page A links to page B and page B links to page C. You can get
from page A to page C by following a chain (path) of links, first going to B and then going to C.
You will write a program in a file called linked.c and a Makefile which creates from that source
code a program called linked, that will use a graph to create a model of linked web pages, and
answer queries about whether one page is connected to another through a chain of links.
Invocation: Your program will be invoked with an optional command-line argument:
linked [ inFile ]
“[ inFile ]” indicates an optional argument that is the name of a file.
If a command-line argument is specified, it should be the name of a readable file.
Input: If an input file has been specified via a command-line argument, your program
will take its input from this file. If no command-line argument is specified, it will read its
input from stdin.
The input will consist of a sequence of directives of the following form, one per line:
op args
where:
o op specifies an operation, and can be one of: @addPages, @addLinks, and
@isConnected; and
o args is a sequence of zero or more arguments to the operation. The number of
arguments depends on the operation (see below).
Each line mentions one or more page names according to the format described below;
you may assume that each such page name is of length at most 64 characters.
Program behavior: Your program will read in commands, one per line, and use them to
construct a representation of the pages and links and to answer queries about whether two
pages are connected by a chain of links. You will read the input until end of file is
reached, processing the commands one at a time as they are read. Note the data structure
you will be using for this program is a directed graph. You may think of the pages as the
vertices and the links as the edges.
The program behaviors for different input directives are as follows:
o @addPages Name1 Name2 . . . Namen
This the command followed by a list of n (n ≥ 0) names of pages, separated by
whitespace, to be added to the structure. A name can be any string, but you may
assume no name is longer than 64 characters. If no names are listed (n = 0), this is
a legal command but of course it does nothing. It is a non-fatal error if one or
more of the names have already been added as pages. In this case, as for all
nonfatal errors, an error message should be printed, but the other names on that
line should still be added.
o @addLinks sourcePage Page1 Page2 . . . Pagen
This is the command, followed by the name of the page containing the links, and
then a list of n (n ≥ 0) pages linked to. It is a nonfatal error if no sourcePage is
given. If the sourcePage does not exist, that is also a nonfatal error and the
command should be ignored. If a linked page does not exist, that is also a nonfatal
error, but the rest of the links should still be added.
It is NOT an error if a link already exists on the source page to some Pagei. You
may ignore the instruction to add that link a second time. It is also not an error to
include a link from a page to itself, although this also adds no information since
all pages are connected to themselves (see below).
o @isConnected Page1 Page2
This is the command followed by two page names. It asks whether there is a chain
of links connected page Page1 to page Page2. Your program should answer this
question based on the pages and links processed up to that point. (i.e. based on the
commands that came before this query, not looking yet at the commands that
come after it) It should print out a 0 if the pages are not connected and a 1 if they
are. Use something like:
printf(“%d\n”, pathExists); /* pathExists = 1 if there pages are conneced,
0 otherwise */
It is a nonFatal error if either of the pages don’t exist, or if the string
@isConnected is not followed by exactly two page names. In this case an error
message should be printed to stderr and the command ignored.
In the special case where Page1 = Page2 we will print a 1. In other words, all
pages are connected to themselves.
Blank lines (lines containing only whitespace) in the input are not errors and should be
ignored. Any line of input whose first string is something other than @addPages,
@addLinks, or @isConnected is a nonfatal error. An error message should be
printed to stderr and the line ignored.
page names are case sensitive. (This is to make the program easier to write)
Remember each command is on a separate line. One that line all the arguments are
separated by some positive number of tabs or spaces. This means you will need to read
the input in a line at a time, but then you will have to parse each line. I suggest you use
sscanf() to parse the lines, but for this assignment you may also use strtok() if you would
like to.
Error Conditions:
Non-fatal errors: more than one command-line argument specified (ignore any additional
arguments after the first one); input directives do not follow the format specified (see
descriptions above). For all nonfatal errors you should print an error message to stderr,
but then continue processing. As you know by now, if you have encountered any error
your exit status should be 1.
Fatal errors: input file does not exist or is not readable. We call an error a fatal error if it
means the program should halt when the error is encountered. In this case you print an
error message to stderr and exit immediately with a status of 1.
Data structure: The data structure you should use for this program is an adjacency list.
To implement this you will use two structs. One to represent the pages and the other to
represent the links between the pages. The pages will be organized in a linked list. Each
page will have an associated linked list of links, one for each link coming from the page.
This looks very much like the data structure for the noVowels2 program. Here, the struct
for the edges needs to contain the page being linked to, and a pointer to the next link on
the page. Students are always tempted to store the name of the page being linked to in
this struct. Don’t. It is far faster and more efficient to store a pointer to the struct
representing the page instead.
Algorithm: The simplest way to solve this problem is to use depth-first search.
Pseudocode for this algorithm is as follows.
/* dfs(fromPage, toPage) — returns true if there is a path from
fromPage to toPage.
To find whether there is a path from page A to page B:
1) mark every page as “not visited”
2) compute dfs(A, B)
*/
int dfs(fromPage, toPage) {
if (fromPage == toPage) return 1;
if (fromPage is marked “visited”) return 0;
mark fromPage as “visited”;
for each page midPage linked to by fromPage do {
if (dfs(midPage, toPage)) return 1;
}
return 0;
}
Makefile:
In addition to your source file, you should submit a make file named Makefile that
supports at least the following functionality:
make linked
Compiles the C source code to create an executable named linked. The compiler options
used should include -Wall.
Extra credit [20%]: Free up all of the memory allocated by your program before it exits. The
resulting code should (obviously) still generate the correct output and run cleanly under valgrind.
