On this page:
1 Report on Integration
2 Implement a Graph Service
3 Project Plan
6.0.0.1

Project 3: 9/15

This project is due on 9/15 at midnight.

Submission Directory: project03 in your pair’s GitHub repository. Failure to follow the submission instructions means your project will not be graded.

1 Report on Integration

Your task is to evaluate the effort of integrating the graph library that you received in the exchange directory back with your graph server. For each test case in<N>.xml found in this repository, use one of the following options:
  • The graph server/library combination passes the test case by producing the same output at out<N>.xml. You may indicate this case with the single word "passes."

  • The test case is ill-formulated according to projects 1 or 2. Explain whether the test case violates the requirement description of project 1 or the graph server specification of project 2.

  • The fault is in your graph server component. Explain how your graph server violates the specification. If you found the problem, point to specific files/statements.

  • The fault is in the graph library constructed elsewhere. Explain how the delivered graph library violates the specification you wrote. If applicable, you may add the error message from the parser or a run-time error message.

  • The fault is in the interface that you wrote. Explain how your interface violates the requirement description from project 1.

At the beginning of the file, describe the effort required to get the system running to the point that you could try it on test cases. Explain whether the problems you encountered were due to the server, the client, or the interface.

Your explanations for each test case may use at most three lines. A line may consist of at most 80 ASCII characters. Use complete sentences for your explanation. Deliver the write-up in 1.txt in your folder for project 3.

2 Implement a Graph Service

Your task is to implement a graph service, as described in project 2, in the programming language in which you wish to develop your Acquire project.

The primary deliverable for this task is an executable called graph-service in your folder for project 3 that starts up at the command line like this:

$ ./graph-service &

It doesn’t matter how you generate this executable, but it must run on the departmental Linux servers.

It then listens on port 5432 for TCP connections and responds to XML requests on these connections. The secondary deliverable is a subfolder, graph-service-tests, with three test cases specified as a pair of file: inN.xml and outN.xml for N = 1, 2, and 3. Each test case that exposes a flaw in some other code base gets you a bonus point. In addition, you should have a directory for the source code of your service, including a README.txt.

Your server must respond to multiple connections in sequence, but you do not need to handle multiple concurrent connections. Your server must respond with error messages for all grammatically correct inputs—crashing is never the correct behavior.

Here is the basic interaction diagram:

SERVICE | | CLIENT1 | | | new | a client requests the |<------------------------| creation of a graph | graph/e | |========================>| | | | add | a client can add an edge |<------------------------| to a graph | graph/e | |========================>| | | | join | or join two graphs |<------------------------| | graph/e | |========================>| | | it can inspect the nodes | nodes | |<------------------------| | nodes/e | |========================>| | | and the edges of a graph | edges | |<------------------------| | edges/e | |========================>| | | and get its cost, too | path | |<------------------------| | path/e | |========================>| | |

The following table specifies the five kinds of requests that your server must process and the four kinds of responses that are expected. The third section of the table specifies data common to the requests and responses.

new = <new low=Cost high=Cost /> creates a new graph from a cost interval add = <add from=NN to=NN cost=Cost> Graph </add> adds the (from,cost,to) edge to Graph if the edge preserves the triangle inequality join = <join>Graph Graph </join> adds the edges of the second Graph to the first Graph nodes = <nodes> Graph </nodes> extracts the set of nodes of the given Graph edges = <edges> Graph </edges> extracts the set of edges of the given Graph path = <path from=NN to=NN> Graph </path> determines whether there is a sequence of edges in the given Graph that connect from with to if so: computes the cost and responds with a path/e if not: it responds with <false />

requests

graph/e = Graph | Error a complete Graph, optionally an error nodes/e = <nodes> Node ... </nodes> | Error a sequence of Nodes, optionally an error edges/e = <edges> Edge ... </edges> | Error a sequence of Edges, optionally an error path/e = <path cost=Cost> Edge ... </path> | <false /> | Error a path: a cost plus a sequence of Edges, optionally an error

responses

Graph = <graph low=Cost high=Cost> EdgeDescription ... </graph> Node = <node name=NN /> Edge = <edge from=NN to=NN cost=Cost /> Boolean = <true /> | <false /> NN = String, at most 20 ASCII chars Cost = String, a positive real number in school book decimal notation, e.g., "-2.593", ".5", "0.00" Error = <error msg=String />

common kinds of data

Note that (a) graphs now have a cost interval bounded both above and below and (b) you must produce a list of edges in the result of a path query. Also note that this is a more complex protocol than you implemented last week. You will likely have to substantially revise all of the code you wrote or integrated last week.

3 Project Plan

Your company has decided to launch Acquire.com, a subsidiary that offers a unique service to the world of bored programmers. Management wishes to run a permanent, web-based programmer competition. To this end, the company will provide an Acquire game server that coordinates distributed Acquire games. Every programmer wishing to prove his or her worth will develop an Acquire player and plug it into the on-line services interface of Acquire.com. Your company’s service will run many rounds of Acquire with all these players and publish the vital statistics about these games.

Draft a memo that describes a development plan. The memo should describe up to five development stages. The objective of each stage is to deliver a running product, with all stages as of the second one extending the previous stage. In addition, the memo may list up to 10 questions concerning the rules of Acquire or the eventual goal of management.

Physical specs: The memo is not to exceed a single page (letter format, 11pt font, 16pt base line, 1.5in margin all around), including the memo header. Your grade will depend on the memo format, its English correctness (style, grammar, organization), and the content.