Purposes:

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

General Idea:

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

Definitions:

A directed graph (G) consists of zero or more nodes (A, B, C, D). Each node may have zero or more arcs or edges (P, Q, R, S) going from it to some other node (or possibly to itself) on the same 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.

Plex implementation:

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.

Assignment:

1. Design an API for directed graphs. You will need 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.
   Add convenience methods as you deem appropriate.
   
   
2. Implement your API using plexes. A graph, a node, and an edge should each be represented by a single plex, with the following restrictions:
   • 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.
     
     
3. Provide complete Javadocs and JUnit tests.

Provided code:

Plex.java, PlexTest.java

Due date:

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