Suppose you’ve been developing programs for a while, and you keep finding yourself building graphs – the node and edge kind – over and over. So, you’ve built a graph class, which you move from one project to the next, improving it as you go.

You’ve heard of frameworks, and you think your graph might make a good mini-framework.

A framework has a scope of application – it can’t be all things to everybody. What applications might use your graph framework?

• web site manager

• traffic simulator

• object modeling tool

Web Site Manager

You’d like a tool to help maintain your web site. You can treat the web as a graph: each page is a node, and links between pages are edges.

This tool might analyze your site:

• Are any pages unreachable? Any have no exit?

• Which pages have high in-counts? They may be landmarks.

• Which pages have high out-counts? They may be index pages.

• What’s the readability of a page?

• Is each page valid HTML?

Traffic Simulator

You might need to simulate traffic in a city, to decide where new streets should be placed. You can treat intersections as nodes, and streets as edges; each edge might have a weight indicating its capacity. (Or maybe it’s better to treat intersections as edges and streets as nodes.)

You’d build a model of the street, and simulate traffic. Perhaps you assign a set of probabilities for each intersection, indicating where traffic might go. Then you run your simulation with various changes.

Object Modeling Tool

We want a tool to represent the object model of our program, as a UML diagram. Classes will be nodes, and relationships between classes will be edges.

Both nodes and edges may have a lot of information attached.

Common Characteristics

The graphs in these applications share a number of characteristics:

• They have a moderate number of nodes (hundreds, possibly thousands, but not millions).

• There is information attached to nodes, edges, or both.

• The edges are directed (and the direction is important).

• There may be constraints on the graph. (For example, in the modeling tool, a class may refer to itself, but may not inherit from itself.)

• The applications could benefit from a generic graph.

Approach

· Original package

· Seek the model

· Be ruthlessly consistent

· Choose names carefully

· Keep the secret

· Document!

· Define what happens

· Keep independent features separate

Our Existing Class

We want to grow our existing graph class into a framework.

In this chapter, we’ll improve the class on its own (in terms of good class design). In the next chapter, we’ll mold it into more of a framework. Along the way, we’ll acquire a number of guidelines that can improve classes or frameworks.

Without further ado, here is our graph:

// v0.1

public class Node {

// How to use: subclass Node and add any

// fields you need for your information.

public String name; // The name of the node

public Vector edges = new Vector();

public Node(String name) { this.name = name;}

public void addNode(Node n) { edges.addElement(n);}

public void removeEdge(Node n) { edges.removeElement(n);}

public Node[] getNodes() {

Node[] result = new Node[edges.size()];

for (int i = 0; i < result.length; i++) {

result[i] = edges.elementAt(i);

}

return result;

}

public Enumeration pathTo (Node goal) {

Vector path = new Vector(this);

if (this == goal) return path.elements;

Vector queue = new Vector();

queue.addElement(path);

while (queue.size() != 0) { // Breadth-first search

Vector path = (Vector) queue.firstElement();

queue.removeElementAt(0);

Node n = (Node)path.lastElement();

for (int i = 0; i < n.edges.size(); i++) {

Node child = (Node)n.edges.elementAt(i);

if (child == goal) {

path.addElement(child);

return path.elements();

} else if (!path.contains(child)) {

Vector cloned = path.clone();

cloned.addElement(child);

queue.addElement(cloned);

} else { // child was in path already

// loop – ignore path

}

} // end for

} // end while

return null; // all paths exhausted

}

This is not a perfect class by any stretch. Perhaps it’s not terrible, but it definitely has flaws. How can we make it better?

These are the rules we’ll apply:

[TBD]

Seek the model.

For many frameworks, it can be tricky or difficult to find the model behind the framework. For graphs, we’re lucky: graph theory is a well-known part of mathematics.

From http://www.astro.virginia.edu/~ewwlen/math: *****

“Graph. A mathematical object composed of points known as Vertices or Nodes, and lines connecting some (possibly empty) subset of them, known as Edges.

Edge (Graph). For an undirected Graph, an unordered pair of nodes which specify the line connecting them. For a directed graph, the edge is an ordered pair of nodes.

Digraph. A Graph in which each Edge is replaced by a directed Edge.”

We can phrase this in a more set-like way:

G = <N, E> A graph has nodes and edges

N & E = 0 Nodes and edges are separate things

E <= N x N An edge is an ordered pair of nodes

We often visualize a graph using bubbles and arrows:

Where’s the graph?!

We spoke of our class as representing graphs, but when we compare it to the mathematical definition, we can see that it represents the Node, while Graph and Edge are implicit!

Should we represent Graph and Edge explicitly?

For explicit representation: The graph as a whole is maintained by the clients of node; centralizing it will let us track the graph as an explicit entity. For Edge – we have applications that attach information to edges. If they’re not explicit, where can we attach the information?

Against explicit representation: The implicit representation saves space: we don’t have to create Edge objects when they have no separate attributes. Plus the class has worked pretty well so far without them.

Decision: We will explicitly represent Graph and Edge.

We’ll keep the cost of an explicit edge in mind though.

Result:

public class Graph { …}

public class Node { …}

public class Edge { …}

like this:

// v0.2

public class Graph {

public Enumeration getNodes();

public Enumeration getEdges();

}

public class Node {

public String name;

private Vector edges;

public Node (String name) { …}

public void addEdge(Edge e) { …} // was addNode()

public Edge[] getEdges() { …}

public Node[] getNodes() { …} // still wanted?

public void removeEdge(Edge e) { …}

public Enumeration pathTo(Node n) { …}

}

public class Edge {

public Edge(Node fromNode, Node toNode) { …}

public Node getFromNode() { …}

public Node getToNode() { …}

}

Be ruthlessly consistent.

Keep an eye out for places where you have been inconsistent. This can be small things, like using the same abbreviation everywhere (not “Num” in one place and “No” in another), or larger things, like consistent method or class names.

Consistency pays off in the future: when you examine code, it works the same as other code you’ve already seen. When you decide to merge classes, you’ll have fewer style clashes.

In the graph class, the most obvious inconsistency is that we return arrays some times, and Enumerations others.

Arrays or Enumerations?

For arrays: Arrays tell exactly what the type is – they don’t require casts. (So, “Edge[]” contains edges, enforced by the language. “Enumeration” could be anything, enforced only by convention.)

For enumerations: The whole collection need not be generated all at once – access is controlled rather than arbitrary. An enumeration can be generated from many sorts of collections, while an array has a fixed form. If we return arrays, and the internal format is not an array, it implies a copy must be made.

Decision: We will use Enumerations. (The argument about not forcing a particular internal representation is the deciding factor.) It’s a close call; in some circumstances you might prefer arrays.

***** TBD – collections

Thus, we’ll make a couple changes in Node:

public Enumeration getEdges();

public Enumeration getNodes();

The other names and types are pretty consistent; we’ll live with them for now.

Emerson: “A foolish consistency is the hobgoblin of little minds.”

Choose names carefully.

One rule people often use is to make class names be nouns or noun phrases (such as Container or JInternalFrame), methods be verbs (e.g., paint()), and attributes be nouns (e.g., getIcon() or getText()). (See http://java.sun.com/docs/codeConv/html).

For interfaces, you’ll often see either a noun phrase (such as TreeCellEditor), or a verb + “able” when it’s an interface to mix in features (e.g., Linkable, Undoable).

You want concise, consistent names. When you have pairs, you want names that go together, e.g., insertElementAt(), removeElementAt().

For our Graph classes, the names of the Edge methods getFromNode() and getToNode() are weak. It took a while to recall a better name pair: “source” and “sink” or perhaps “source” and “target”.

Rename the methods to use “source” and “sink.”

public Node getSource() { …}

public Node getSink() { …}

A dictionary and a thesaurus can be very helpful in choosing just the right name.

The Magician’s Rule: Keep the secret.

A class should encapsulate some secret. For example, the representation of an object should be hidden, so clients depend on the interface alone. This way, a change in the implementation requires no changes in the clients.

What about our class? Can we tell how it’s represented?

Don’t expose attributes in public.

Using attributes couples clients to a decision subject to change. The day will come when you change your mind: you want to count accesses, store the attribute somewhere else, etc. If everybody who uses the class accesses it directly, you have no freedom to change the attributes.

Don’t build “data bags.”

Moving to getter and setter methods, as in the previous rule, are often an improvement but still not enough. Try to go even further – what’s the use of the attribute going to do with the information? Can you do it for them? If all you’re doing is making a C-style “struct”, the object is not very object-oriented.

Wrap the name attribute.

The name attribute is currently declared public. We’ll hide it behind methods:

public void setName (String name) { …}

public String getName () { …}

Can we tell how the graph is implemented?

Much of the representation is hidden. We can’t tell whether the node is an array, vector, or some other structure, or if the edge is stored with the graph object, the node, or somewhere else entirely.

There is a place where we can hide representations better, though. Recall how we introduced explicit Edge objects in order to reflect the full model. A node must be able to report its edges, which implies Edge objects must exist somewhere.

But must they be permanent? We can introduce a test for equality:

public boolean equals (Edge e) { …}

This way, when a node reports an edge object, it has the freedom to create one on the spot (rather than requiring it to have “independent” existence).

We’re not forbidding edges to exist. Most implementations might well create explit edges; they would just define equals() to be “==”. By not requiring edges, we allow for a natural case: when edges have no data of their own, and most traversal is from node to node, our graph can use the original representation of storing a Vector of Nodes rather than Edges.

What about node equality? A similar argument applies.

Test nodes and edges for equality using equals(). *

* By Java conventions, we also redefine hashCode(), to ensure that two equal components have equal hash codes.

Finally, how are Graphs and Nodes created? We’ve defined a constructor for Node, but how does a graph find out which nodes it contains?

Our Graph has accessor methods, but no modifying methods – it has no way to be told what’s in the graph!

One way to handle this problem would be to add a method:

public void add (Node n) { …} // but…

Then we could create a node, and add it to the graph:

Graph g = new Graph();

Node n = new Node(“test”);

g.add(n); // but…

We let Graph track Nodes, and Nodes track Edges. (But wait: Graph can tell us what the Edges are – it must go to the Nodes to get them. Is that OK?)

There is an alternative, known as a Factory Method. (We’ll discuss this more in the chapter on patterns. TBD) A factory method is a method that creates another object. The constructor of the other object is usually made unavailable after that.

In class Graph, add these methods:

public void makeNode (String name) { …}

public void makeEdge (Node n1, Node n2) { …}

Hide the Node constructor, and move responsibility for Edges into the Graph.

Graph now owns responsibility for creating nodes and edges. Since Graph creates node and edges, we’ll make it responsible for deleting them as well.

Make Graph use a Factory Method for Nodes and Edges.

What’s our code now?

public class Graph {

public Graph() { …}

public Node makeNode (String name) { …}

public Edge makeEdge (Node n1, Node n2) { …}

public Enumeration getNodes() { …}

public Enumeration getEdges() { …}

public void remove (Node n) { …}

public void remove (Edge e) { …}

}

public class Node {

public String getName() { …}

public void setName (String name) { …}

public Enumeration getEdges() { …}

public Enumeration getNodes() { …}

public Enumeration pathTo (Node n) { …}

public boolean equals (Object n) { …}

public int hashCode() { …}

}

public class Edge {

public Node getSource() { …}

public Node getSink() { …}

public boolean equals(Object e) { …}

public int hashCode() { …}

}

[TBD – summarize]

Document! Document! Document!

As you move your framework from being a private entity to becoming a public one, you must improve the documentation so other people can use it. (For one thing – they’re not experts in your subject – that’s why they want a framework in the first place!) In The Mythical Man-Month, Brooks says that a public documented product will take about 9 times the effort to produce.

Where do we stand?

Well, the 2-line comment: “How to use: subclass Node, and add any fields you need for your information” is not universally regarded as adequate documentation for a framework.

What is needed? I’d suggest at least three things: javadoc comments in the code (so a reference manual can be automatically generated), a framework user’s guide, and a test gauge. The javadoc should explain each public or protected class and method. The user’s guide should contain an overview, to explain the overall philosophy, and a set of task-oriented examples. The test gauge helps demonstrate that the framework is working.

For the graph class, a minimal user guide would include:

Overview: What is a Graph?

How to create a graph

How to make nodes contain special information

How to make edges contain special information

How to define a graph algorithm

Index

Provide concrete source code for complete, runnable applications. This lets people move from a working example to the application they want to build. You’ll rarely hear a complaint “Too many examples.”

Define what happens.

Bertrand Meyer, the inventor of Eiffel, defines contracts in terms of pre-conditions and post-conditions:

Pre-condition: If you do this…

Post-condition: This will happen.

Under this regimen, it’s the caller’s responsibility to ensure that preconditions are met, and the callee’s responsibility to fulfill the contract. (Meyer also defines a class invariant that will be true for the class at (almost) all times.)

***** Expand to two separate topics.

You may not want to develop these contracts completely, but users need to know what is legal for each argument. For each return value, you need to tell what values are possible.


Numeric (short, int, etc.)	Can it be negative? 0? positive? Is there a lower limit? upper limit?
Character	Is 0 allowed? Any restrictions (e.g., ASCII only)?
String	Null allowed? 0-length string? Character restrictions?
Object	Null allowed? Type restrictions?
Array	Null allowed? 0-length array? Min/max size?
Enumeration	Null allowed? What types are returned?

There’s nothing wrong with restricting values – not documenting the restrictions is a problem.

For example, in our code we do not want to allow edges to have one of their nodes be null. (We never expect getSource() or getSink() to return null either.) This is a reasonable restriction.

If you don’t tell people what’s legal, they only have one way to find out: try it and see what happens. That’s no good though, because it only tells them about today. If you haven’t said what’s right, they can’t trust it tomorrow.

Keep independent features separate.

If one feature can change independently of another, don’t provide an interface that couples them.

The graph classes are pretty good on this front (most methods have zero or one argument). So, we’ll make up an example. Suppose you create a document class and have a method:

public void setStyle (Font f, int mods, int size)

[TBD – Regard a style as being…]

Can we conceive of changing the size without changing the font? Of course. So we end up with client code like this:

setStyle (getFont(), getModifiers(), newSize);

We’ve had to fetch the old font and modifiers just to pass them in again – wasted work!

It can be even worse. Suppose we don’t have getFont() or getModifiers() methods; instead we have a getStyle() method that returns them. Then we have to call getStyle(), save the result, pull the pieces out, and pass them to setStyle(). (Odds are good that would require another class to hold the style information.)

Or, worst of all, suppose that the class doesn’t provide any method to access the current style. Then you have to track it through variables external to the class.

The “compound” setStyle() method is really only acceptable as a convenience method: if all three attributes are often set together, and the individual “set” methods are available, then we can define

public void setStyle (Font f, int modifiers, int size) {

setFont(f); setModifiers(modifiers); setSize(size);

}

You usually become aware of the need for these convenience methods after you’ve been using the class for a while, and usage patterns recur.

Be suspicious of methods with a lot of parameters. Try to keep independent features separate.

***** Decision – what can change, what won’t?

Summary

? Questions

· Where’s the graph?

· No modifiers?

–^– Decisions

· Graph and edge explicit? Explicit.

· Arrays or enumerations? Enumerations.

· Rename? Source and sink.

· Wrap the name attribute.

· Test using eqals()

· Factory method

TODO

· Keep in mind the cost of an explicit edge.

Starting from the original package, we developed these rules:

· Seek the model

· Be ruthlessly consistent

· Choose names carefully

· Keep the secret

· Document!

· Define what happens

· Keep independent features separate

We made these decisions:

We have these open issues:

CHAPTER 4: … To Framework

In the last chapter, we discussed our class as a class. In this chapter, we want to turn the graph into more of a framework.

We’ll follow several guidelines:

· Use Java interfaces.

· Steal good ideas.

· Omit needless features.

· Add features for completeness.

· Packages are the unit of release.

· White box vs. Black box frameworks.

· Hollywood principle.

· Comb through and fix the details.

[TBD]

Use Java interfaces.

Java provides “interface” classes. These classes define the methods that must be present, but no implementations. This provides a strong barrier between interface and implementation. Using an interface lets us commit to the interface alone without committing to the implementation.

By defining your framework in terms of interfaces, you will give yourself freedom to develop a minimalist/naive implementation during the early stages. If the interface changes, it will be easier to change a simple implementation. As the framework becomes more stable, you can invest more in a high-quality implementation.

Make our classes into interfaces.

Our previous implementation still provides a useful group of classes. We’ll rename them to SimpleGraph etc. and make those classes implement our interfaces.

Retain our original classes as a sample implementation. Make them implement the interfaces.

public interface Graph {

public Node makeNode (String name);

public Enumeration getNodes();

public void removeNode (Node n);

public Edge makeEdge (Node n1, Node n2);

public Enumeration getEdges();

public void removeEdge (Edge e);

}

public interface Node {

public String getName();

public void setName (String name);

public Enumeration getEdges();

public Enumeration getNodes();

public Enumeration pathTo (Node n);

public boolean equals (Object node);

public int hashCode();

}

public interface Edge {

public Node getSource();

public Node getSink();

public boolean equals (Object edge);

public int hashCode();

}

public class SimpleGraph implements Graph { …}

etc.

Steal good ideas.

We talked earlier about using a model to drive the design. But there are other good ideas that can be used as well.

Quote: “Newton said he stood on the shoulders of giants. In computer science, we often stand on their toes.” ??

Find similar classes, and see if you can learn anything from their approach. For the Graph class, we might look at the Swing tree package (since a tree is a kind of graph), at the JDK 1.2 collection classes (since a graph is a collection of nodes and edges), and at the C++ Standard Template Library (STL) (more collections).

***** Also Rogers etc – some real graph class.

From Swing trees, we can see:

· distinction between mutable and immutable nodes

· a userObject rather than “name”

· use of interfaces, abstract classes, and concrete classes

From collections, we see:

· mutable vs. immutable managed by exceptions

· notification as an issue

From STL:

· radical separation of algorithm from implementation (generic algorithms across interfaces)

· use of iterators and adapters

In this section, we’ll discuss mutability, adapters, and notification. In the next section, we’ll discuss algorithms. In the discussion of black box vs. white box, we’ll consider the userObject field.

Mutability

Mutability is an important distinction: can the graph be changed while in use? Some applications have dynamic graphs, but a number of others build the graph once, and work from the static graph.

One approach to this problem is to make a distinction at the class (or interface) level. In our case, we could define interfaces Graph (for read-only graphs) and MutableGraph (for modifiable graphs), with MutableGraph an extension of Graph.

A second approach is used in the JDK 1.2 collection classes. Here, some operations are permitted to throw an UnsupportedOperationException. (As an exception, it needn’t be declared in the throws clause. Instead, it is noted by a comment in the class description.)

Enforce mutability by class or by operation?

By class: This is an important distinction, worth reflecting in the class hierarchy. Our classes will be more readily substitutable if we don’t have “vetoable” operations.

By operation: We can let a particular graph decide its own constraints without increasing the number of classes. (For example, one graph might not allow any changes, while another might permit edges to be added but not nodes.)

Decision: [This is a tough call, but…] We’ll support mutability on a by-operation basis. We’ll mark some methods “optional,” and they will throw an UnsupportedOperationException if they don’t support the operation.

We may want some support classes. For example, there is a Collections class with methods that wrap a collection so that all optional operations throw the exception. This turns any collection into a read-only collection.

Consider mutability adapter classes.

Notification

Next, we’d like to consider notification. What happens when the graph changes? In the current implementation there’s no easy way to discover this has happened.

The applications we described could make use of change notification: the traffic simulator could simulate the impact of streets opening and closing; the object tool could revise the visible graph when the underlying information changes.

Add notification support to graph.

Note: This is another big decision that affects the fundamental nature of our framework.

To fit with the JDK 1.1. event model, we’ll do something like this:

public class GraphEvent {

public final static int GRAPH_CHANGED=1;

public final static int NODE_ADDED=2,

NODE_CHANGED=3, NODE_REMOVED=4;

public final static int EDGE_ADDED=5,

EDGE_CHANGED=6, EDGE_REMOVED=7;

public GraphEvent (Graph g, int id) { …}

public GraphEvent (Graph g, int id, Node n) { …}

public GraphEvent (Graph g, int id, Edge e) { …}

public Graph getGraph() { return (Graph)getSource();}

public Node getNode() {…}

public Edge getEdge() {…}

}

public interface GraphListener {

by event or just one method?? [TBD]

}

public interface Graph {

public void addGraphListener (GraphListener gl) { …}

public void removeGraphListener (GraphListener gl) { …}

}

And (!) define which methods cause what notifications.

Omit needless features.

Classes and frameworks have a way of picking up “burrs” – methods or fields that serve a particular use, but are not good for the framework overall. We must lightly sand these away.

In our case, three features of Node stand out: the getPathTo() method, the name field, and the getNodes() method.

Paths

Is the getPathTo() method generally useful? Sometimes yes, sometimes no. Many applications are not searching for paths; for them it’s extra baggage. Furthermore, the implementation we have is awkward: breadth-first search of all connected nodes. (An application in which paths are important might use a more optimized approach.)

Remove the getPathTo() method.

We don’t have to get rid of it completely – we could take the STL approach and have a separate algorithms class. But, for the framework, we’ll eliminate it.

Names

Next, the name field (realized by getName() and setName()): Is it generally useful? Yes, many applications will want to attach name or other information to a node.

Don’t make subclasses pay for weight they don’t need.

Not every class needs a name string, though. (Recall our original comment: “subclass and add your information to the node.”) Should subclasses pay for a string they don’t need? No!

[TBD – Pay as you go – Algol]

Remove “name” from Node.

Node and Edge are lighter now. A Node has information about its edges. An Edge has information about its two ends. A subclass can add in information as it needs it.

Nodes

What about the getNodes() method? We can easily implement it by taking the result of getEdges(), and seeing what sink is at the end of each.

Remove the getNodes() method.

Note: This is not so straightforward as it sounds: using the result of getEdges() requires instantiating each edge. In a “mostly edge-free” implementation, this could be fairly expensive. (Our original nodes had an array of node pointers; deleting this method means there’s no particular advantage to that implementation.)

Add features for completeness.

You will usually have no problem finding methods you could add to your class. How do you decide which features you should add?

Try this rule of thumb:

Add methods to support useful features that would be difficult or impossible to provide using existing methods.

The getPathTo() and getNodes() methods failed that test: they can be defined in terms of the other access methods. (Again, if path-finding is crucial, our breadth-first method might be too slow; then we might change our mind.)

For the graph package, the notable missing feature is: given a node, which edges go into it? (We already have a mechanism to locate outgoing edges.)

With the current interface, the only approach is to enumerate all edges, and see which ones point to our node. It’s clear the graph package could do this better if it knows that incoming edges are needed – it could maintain two lists of Edges per node, one for incoming and one for outgoing.

Track incoming edges?

Yes: Many applications will want this information. It’s hard to derive using existing methods.

No: This adds weight to our graph. Now Node (or Graph) will have to track both in- and out-edges.

Decision: We’ll allow it, but not require it.

Add a method to Graph:

public boolean isLinkReversible();

which returns true if the incoming edges are tracked.

Add a method to Node:

public Enumeration getInEdges();

If graph.isLinkReversible() is false, we have to decide what to do. One approach would be to return an empty (not null!) Enumeration. Another approach would be to say that the items in the Enumeration are a subset of the true set of incoming edges. (This latter form looks to its use in a web application: it’s possible to know some but not all incoming links.)

You may decide to reject this sort of reasoning in favor of keeping the definition more simple. When you move down this path, you find that since you guarantee so little, you may end up with algorithms that are not guaranteed to accomplish anything.

Packages are the unit of release.

***** [TBD] Martin? Booch?

We’ve talked about our graph framework, but how is it delivered?

[TBD – UML]

One good way is to use packages as the unit of release. In our case, we could put them in a package com.xxx.graph. This package will contain Graph, Node, Edge, GraphEvent, GraphListener.

Actual implementations can go in a related package such as com.yyy.graph.sample. Notice that they don’t go in the graph package itself – we want to freeze that package. Once frozen, we can trust it. Every time a package or class is changed, there’s a new opportunity to introduce errors, so we want to minimize changes. Notice that the implementation package needs to have no particular relationship to the graph package (here, we even have it coming from a different company).

When we use the graph, we can import the interface package and an implementation:

import com.xxx.graph;

import com.yyy.graph.sample;

Ideally, you have very few places aware of the second import; most methods should work with Graph, not SampleGraph. In the best case, you have something like:

Graph graph = new SampleGraph (parameters);

and from then on, nothing is aware that the actual class is SampleGraph.

White box vs. Black Box Frameworks

The graph framework is white-box: use of it requires some understanding of the internals; extension is by inheritance. As the package evolves, we may find ways to make it more flexible by emphasizing composition over inheritance (black-box).

Composition is more flexible: in most object-oriented systems, the class inheritance is fixed, but the composition can vary.

In our graph framework, we can eliminate some inheritance by using a technique from the Swing tree classes: define a “userObject” field to contain node- or edge-specific information.

public Object getObject();

public void setObject() (Object o);

(added to both nodes and edges).

This will eliminate the need to subclass Node and Edge; we can put our information in the userObject rather than putting it in the subclass.

But didn’t we just get “name” out of the Node class? Yes, for good reason: we had subclasses that didn’t need a name field, and eliminated it out of the “pay for what you get” principle. But we anticipate most uses needing to attach some information. This does add some indirection cost (traversing from the Node to the userObject, and casting to the desired information), but we hope the extra generality makes it worthwhile.

The Hollywood Principle: Don’t call us, we’ll call you.

One common aspects of frameworks is the issue of who’s in charge. In a non-framework program, you write your code that controls the main event loop, etc. In a framework, the framework usually owns the main event loop.

You can think of the spectrum from class library to framework. This lack tends to show our graph package as being more on the library end of things. [TBD – ??]

We do have some aspects of this principle embodied in the GraphListener facility. Programs can register as a GraphListener, and then they’re notified when the graph changes.

Frameworks are often structured so you just register code fragments, and then the framework takes resonsibility for calling the code when it needs to.

We’ll see more of this in later examples.

Comb through – fix the details.

***** TBD

• Multiple occurrences of edges?

• Constraints on graphs?

• Auto-links (to self)?

Summary

Key ideas

· Use Java interfaces.

· Steal good ideas.

· Omit needless features.

· Add features for completeness.

· Packages are the unit of release.

· White box vs. Black box frameworks.

· Hollywood principle.

· Comb through and fix the details.

Decisions

· Use interfaces

· Retain simple implementation

· Mutability? By operation.

· Notification.

· Remove getPathTo().

· Remove name.

· Remove getNodes().

· Track incoming edges? Allowed but not required.

Todo

· Mutability adapter classes.