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 ", 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.

Example:

If the input looks like:

@addPages myPage UofA csDept localTheater

@addLinks myPage UofA

@addLinks UofA csDept

@addLinks csDept localTheater

@isConnected myPage localTheater

@addPages TucsonHome ComicsStore

@isConnected myPage ComicsStore

@addLinks TucsonHome localTheater UofA

@isConnected TucsonHome csDept

@addLinks UofA myPage localTheater TucsonHome ComicsStore

@isConnected UofA TucsonHome

then the output should be:

1

0

1

1

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.