|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
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.
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.
- Design an API for directed graphs. You will need
Edge classes. Using your API, you should
be able to:
Add convenience methods as you deem appropriate.
- Construct any graph.
- Change any graph into any other graph.
- Learn everything about the graph.
- Display (print) the graph.
- 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.
- Provide complete Javadocs and JUnit tests.
Monday, March 10, before midnight. Submit the usual way.