CIT 594 Assignment 9: Graphs
Spring 2006, David Matuszek

Purposes:

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:

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:

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: 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:
  3. Provide complete Javadocs and JUnit tests.

Provided code:

Plex.java, PlexTest.java

Due date:

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