CIT 594 Assignment 9: Graphs Spring 2006, David Matuszek |

- To familiarize you with graphs and hypergraphs
- To give you some experience in API design

Implement a Graph API in terms of a hypergraph. You will use your API in a subsequent assignment.

A * directed graph* (

A * hypergraph* is a collection of zero or more graphs, with many
fewer restrictions. For example, an edge may point from a node on one graph
to a node on a different graph; or an edge may point to several different nodes.
There is no generally accepted definition of a hypergraph.

A ** plex** is a simple, uniform, primitive object that can be used
to build hypergraphs. Using plexes, it is simple to build structures in which:

- Nodes may reside simultaneously on many graphs, or on none at all.
- Edges may emanate from multiple nodes, or none at all.
- Edges may terminate on (point to) multiple nodes, or none at all.
- The start and end points of an edge need not be on the same graph.
- Edges may emanate from and/or point to graphs or other edges.
- Graphs may contain other graphs as nodes. Nodes may contain graphs. Even edges may contain graphs.

Graphs are formed from hypergraphs by taking the single basic element of a hypergraph, the plex, and adding restrictions to form graphs, nodes, and edges.

A plex consists of four sets:

containers:The other plexes in which this plex occurs. For example, nodes and arcs may occur in a graph.

contents:The other plexes contained in this plex. For example, a graph may contain nodes and arcs.

origins:The other plexes "from which" this plex comes. For example, an edge comes from a node.

destinations:The other plexes "to which" this plex goes. For example, an edge goes to a node.

And some simple validity rules:

- If plex X is a container of plex Y, then plex Y is a content of plex X, and vice versa.
- If plex X is a destination of plex Y, then plex Y is an origin of plex X, and vice versa.

The `containers` and `contents` sets are mutually redundant,
as are the `origins` and `destinations` sets. The redundancy
is present for reasons of efficiency.

an API for directed graphs. You will need*Design*`Graph`

,`Node`

, and`Edge`

classes. Using your API, you should be able to:- Construct any graph.
- Change any graph into any other graph.
- Learn everything about the graph.
- Display (print) the graph.

your API using plexes. A graph, a node, and an edge should each be represented by a single plex, with the following restrictions:*Implement*- A
**graph**is a plex whose`origins`,`destinations`, and`containers`sets are empty. The nodes of the graph are in the`contents`set. - A
**node**is a plex whose`contents`set is empty; whose`containers`set contains a single element, the graph that the node resides on; whose`origins`set contains the edges that point to the node; and whose`destinations`set contains the edges that come out of the node. - An
**edge**is a plex whose`contents`set is empty; whose`containers`set contains only the graph that the edge resides on; whose`origins`set contains only the one node from which the edge comes; and whose`destinations`set contains only the one node that the edge points to.

- A
- Provide complete
and**Javadocs**.**JUnit tests**

Monday, March 10, before midnight. Submit the usual way.