WriteNow@Š@@ @0@`x@3@T`?4@s~ AAHHdRdd@YY@YY>HHH@  >HHH@   @0@>@@X>@x@@$HH@R(,, `,-^&'$ @DHLPTX\T@8X0~~$4 ~HHH@0~$4 ~HHH@0~$4 ~HHH@0@~$4 ~HHH@PP$ PP$ 0~H$4 ~ Table Style4Geneva2Chapter 2. Graph: From Class... HHH@8 GRAPH: FROM CLASS... Suppose you've been developing programs, 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 regard the web as a graph: each page is a node, and links between pages are edges. This tool might analyze our local web: * 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? 1 D 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). 4* 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, a class may refer to itself, but may not inherit from itself.) * The applications could benefit from a generic graph. 2 OUR EXISTING CLASS We want to grow our existing Graph class into a framework. In this chapter, we'll improve it on its own (in terms of good class design). In the next chapter, we'll mold it into being 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++) { HHH@`8 result[i] = edges.elementAt(i); } return result; E } 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 }  HHH@8 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?  [KEY] Seek the model. HHH@8  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 = 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: [1] -------> [2] \_______> [3] -------> [4] iVV [?] 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! HHH@8  < [-^-] 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. [TODO] We'll keep the cost of an explicit edge in mind though. HHH@8  !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() {...} } _$W [KEY] Be ruthlessly consistent. HHH@8  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. '9 [-^-] 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. HHH@8   *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. +  [KEY] Choose names carefully. HHH@8  ,One rule people often use is to make classes 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 Edge names "getFromNode" and "getToNode" are weak. It took a while before I came across some better name pairs: "source" and "sink" or perhaps "source" and "target". HHH@ [/$HHH@8VV [DECISION] Rename the methods to use "source" and "sink."   public Node getSource() {...} public Node getSink() {...}  HHH@8  c0A dictionary and a thesaurus can be very helpful in choosing just the right name. 1TJ [KEY] The Magician's Code: Keep the Secret. HHH@8  (2 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? 3Hjff [DECISION] 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 () {...}  HHH@8  4 4ff [KEY] 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. HHH@8  +6Can we tell how the graph is implemented? Much of the representation is hidden. We can't tell is 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. 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 unique? We can introduce a test for equality: 8  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 them to have "independent" existence). We're not requiring  that edges not 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 use is from node to node, our graph can use the original representation of storing a Vector of Nodes rather than Edges. G; What about node equality? A similar argument applies. ;  [DECISION] Test nodes and edges for equality using  equals() . * HHH@8  )<* 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? = && [OOPS!] Our Graph has accessor methods, but no modifying methods - it has no way to be told what's in the graph! HHH@8  ? 2One way to handle this problem is to add a method:   public void add (Node n) {...} // but... Then we can 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.) The factory method is responsible for creating another object. (The constructor of the other object is then often not made available.) qA 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. C/p  [DECISION] Make Graph use a Factory Method for Nodes and Edges. HHH@8  DWhat'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() {...} } +FHHH@ G)HHH@8 [KEY] Document! Document! Document!  GHHH@8As 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, a 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. J What is  needed? I'd suggest at least two things: javadoc in the code (so a reference manual can be automatically generated), and a framework user's guide. 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. L 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." M0HHH@8   [KEY] Define what happens. HHH@8  hNBertrand 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.) 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. XQ5l66 [KEY] `Numeric (short, int, etc.) Char String Object Array Enumeration 6 Can it be negative? 0? positive? Is there a lower limit? upper limit? 0 allowed? Restrictions (e.g., ASCII only)? Null allowed? 0-length string? Character restrictions? Null allowed? Type restrictions? Null allowed? 0-length array? Min/max size? Null allowed? What types are returned `  4SHHH@8There'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. =UHHH@8  U [KEY] Keep independent features separate.  XVHHH@8If you could change one feature independently of another, don't provide an interface that couples them. The graph classes are pretty good on this front (most methods have 0 or 1 argument). Instead, we'll make up an example. Suppose you have a method: public void setStyle (Font f, int mods, int size) 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! 2Y 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. 9[6 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. K]o CHAPTER 4: ... To Framework In the last chapter, we discussed our class as a class. In this chapter, we want to make it become more of a framework. We'll follow several guidelines: * Use Java interfaces * Steal good ideas * Omit needless features * Use packages * White box vs black box * Inversion of control ^[KEY] 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. It lets us to commit to the interface alone. 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. [DECISION] Make our classes into interfaces. Our original implementation is still a useful group of classes. We'll rename it to SimpleGraph etc. and make it implement our interfaces. [DECISION] 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); =b 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. Ud[KEY] 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). wgC From Swing trees, we can see: * distinction between mutable and immutable nodes * a userObject rather than "name" * provision of interface, abstract class, 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. i1 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. The 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.) l4 --- [DECISION] 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.) nhv Decision: [This is a tough call, but...] We'll support mutability on a by-operation basis. Methods marked "optional" 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. [TODO] Consider mutability adapter classes. 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. py 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 graph changes. [DECISION] 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: r 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. u[KEY] 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. In our case, three features of Node stand out: the pathTo() method, the name field, and the getNodes() method. Is the getPathTo() method generally useful? Sometimes yes, sometimes no. Many applications are not searching for paths; for them it's extra baggage. Furthermorel, the implementation we have is awkward: breadth-first search of all connected nodes. (An application in which paths are important might use an entirely different approach.) x, [DECISION] Remove the getPathTo() method. We don't have to get rid of it completely - we might take the STL approach and have a separate algorithms class. But, for the framework, we'll eliminate it. 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. [Key] Don't make subclasses pay for weight they don't need. /y Not every class needs a name string. (Recall our original comment: "subclass and add your information to the node.") Why should subclasses pay for the string if the don't need it? They shouldn't! [DECISION] Remove "name" from Node. Node and Edge are looking lighter now. A Node has information about its edges. An Edge has information about its two ends. 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. [DECISION] Remove the getNodes() method. m|"[Key] 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: [KEY] Add methods to support useful features that would be difficult or impossible to provide using existing methods. So, 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. --- [DECISION] Track incoming edges? Yes: Many applications will want this information. It's hard to define from 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, this will return an empty Enumeration (not null!).) Ji[Key] Packages are the unit of release. [TBD] Martin? Booch? We've talked about our graph framwework, but how is it delivered? 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 class. 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. Za[Key] White box vs. Black Box 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 it 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 (going from the Node to the userObject, cast to the desired information), but we hope the extra generality makes it worthwhile.  [Key] 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. We do have some of this 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. [Key] Comb through - fix the details. * Multiple occurrences of edges? * Constraints on graphs? * Auto-links (to self)? P q tGeneva"xCourierp]#~d2` ` 1` @4pt2dPu &@`e ife <@!u $W_@&@e '9@* pu +6D,e /[f@0c u 1T&@2 (`e 3Hv@4e 4v@6+`8@;G e ;6`<)`e =F`? @Aqe C/6@DTF+e G)&dG`JP@Lu M6@Nhe Q5XFDS4tU=e U&DVX`Y2@[69P]oKP^@b=PdU@gCw@i@l@nh@p@rPu@x,@y/p|m@~ppiJ@PaZ`PP@@]p@0@`x@3@T` P@saXaTaPaLaHaDa@Lja0~J !dTAAHHdRdAAd@xH@xHe3 lChapter 2. Graph: From Class... HHH@8 GRAPH: FROM CLASS... Suppose you've been developing programs, 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?  jHHH@ Frameworks Copyright 1998, William C. Wake 8-24-98  r kS 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, a class may refer to itself, but may not inherit from itself.) * The applications could benefit from a generic graph.  YP OUR EXISTING CLASS We want to grow our existing Graph class into a framework. In this chapter, we'll improve it on its own (in terms of good class design). In the next chapter, we'll mold it into being 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++) { HHH@`8 result[i] = edges.elementAt(i); } return result; B Y } 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 }  HHH@8 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? / Y [KEY] Seek the model. HHH@8  i ZUVV [?] 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! HHH@8  <P Zs [-^-] 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. [TODO] We'll keep the cost of an explicit edge in mind though. HHH@8  _ Z [KEY] Be ruthlessly consistent. HHH@8  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.  [ [-^-] 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. HHH@8  l [`  [KEY] Choose names carefully. HHH@8  - [wOne rule people often use is to make classes 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 Edge names "getFromNode" and "getToNode" are weak. It took a while before I came across some better name pairs: "source" and "sink" or perhaps "source" and "target". HHH@ [; [HHH@8VV [DECISION] Rename the methods to use "source" and "sink."   public Node getSource() {...} public Node getSink() {...}  HHH@8   [ [KEY] The Magician's Code: Keep the Secret. HHH@8  b [ff [DECISION] 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 () {...}  HHH@8   \ff [KEY] 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. HHH@8   \z  [DECISION] Test nodes and edges for equality using  equals() . * HHH@8   \ && [OOPS!] Our Graph has accessor methods, but no modifying methods - it has no way to be told what's in the graph! HHH@8   ]   [DECISION] Make Graph use a Factory Method for Nodes and Edges. HHH@8  + ]]HHH@  ]eHHH@8 [KEY] Document! Document! Document!   ]zHHH@8As 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, a 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. V ]HHH@8   [KEY] Define what happens. HHH@8  X> ^66 [KEY] `Numeric (short, int, etc.) Char String Object Array Enumeration 6 Can it be negative? 0? positive? Is there a lower limit? upper limit? 0 allowed? Restrictions (e.g., ASCII only)? Null allowed? 0-length string? Character restrictions? Null allowed? Type restrictions? Null allowed? 0-length array? Min/max size? Null allowed? What types are returned `  4– ^HHH@8There'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. = ^HHH@8   ^ [KEY] Keep independent features separate.  Xŵ ^HHH@8If you could change one feature independently of another, don't provide an interface that couples them. The graph classes are pretty good on this front (most methods have 0 or 1 argument). Instead, we'll make up an example. Suppose you have a method: public void setStyle (Font f, int mods, int size) 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!  WaHH@R(,, `,-^&'dpȝ CYd3` ` 1`r0tdBPu /&@`e ife P<@!u _@&@e @* pu l6D-e ;[f@0c u &@2 (`e bv@4e v@6+`8@;G e 6`<)`e F`? @Aqe 6@DT+e &d`JP@Lu V6@Nhe >XFD–4t=e &DŵX`Y2@[69P]oKP^@b=PdU@gCw@i@l@nh@p@rPu@x,@y/p|m@~ppiJ@PaZ`PP@ C[@>@@X>@d@M C]x] W@ @$@@ȝp@ @@M`]x@3@T` P@saaaaa aah<ja ~J4  .dAAvHHdRdAAd@YH]@YH]5ϿϿϿUO'HHH@`Chapter 2. Graph: From Class... HHH@`  Suppose you've been developing programs, 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? nR( Frameworks Copyright 1998, William C. Wake 8-24-98  bR'" web site manager traffic simulator object modeling tool HHH@` Web Site Manager HHH@` You'd like a tool to help maintain your web site. You can regard the web as a graph: each page is a node, and links between pages are edges. This tool might analyze our local web: 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? uT'\ HHH@` Traffic Simulator HHH@` 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. WY'[ HHH@` Object Modeling Tool HHH@` 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. HHH@` Common Characteristics HHH@` 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, a class may refer to itself, but may not inherit from itself.) The applications could benefit from a generic graph. (Z' HHH@` Our Existing Class HHH@`  We want to grow our existing graph class into a framework. In this chapter, we'll improve it 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: lHl @0P // v0.1 public class Node { ]Z // 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; _#' } 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 } HHH@`  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? %c'HHH@8 **H @     Seek the model. HHH@`  d;'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 = 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: HHH@`  Qge h !h '  hA'HHH@8jjH @     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! HHH@8  j'>>H @     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. HHH@8  m'HHH@` Result: lHl @0P public class Graph {...} public class Node {...} public class Edge {...} HHH@`  like this: lHl @0P // 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() {...} } HHH@`  HHH@8  q'**H @     Be ruthlessly consistent. HHH@8  HHH@` 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. t~'HHH@`  In the graph class, the most obvious inconsistency is that we return arrays some times, and Enumerations others. HHH@8  u_'ZZH @     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 HHH@8  y2'HHH@` Thus, we'll make a couple changes in Node: lHl @0P public Enumeration getEdges(); public Enumeration getNodes(); HHH@8  HHH@` 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." ,{'HHH@8  **H @     Choose names carefully. HHH@`  a|4'HHH@` One rule people often use is to make classes 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 Edge names  getFromNode()  and  getToNode()  are weak. It took a while to recall a better name pair: "source" and "sink" or perhaps "source" and "target".  q'HHH@8^^H @    Rename the methods to use "source" and "sink." lHl @0P public Node getSource() {...} public Node getSink() {...} H @  HHH@`  ?'HHH@` A dictionary and a thesaurus can be very helpful in choosing just the right name. 9'HHH@8 **H @     The Magician's Rule: Keep the secret. HHH@`   'HHH@` 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? HHH@8  #'H @     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. HHH@`  'HHH@8 rrH @     Wrap the name attribute. The name attribute is currently declared public. We'll hide it behind methods: lHl @0P public void setName (String name) {...} public String getName () {...} HHH@`  e'HHH@` 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. 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: ' lHl @0P public boolean equals (Edge e) {...} HHH@` 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. c' HHH@8 **H @     Test nodes and edges for equality using  equals() . * HHH@8  [w'HHH@` * 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? }'HHH@8  ::H @     Our Graph has accessor methods, but no modifying methods - it has no way to be told what's in the graph! HHH@`  zO'HHH@` One way to handle this problem would be to add a method: lHl @0P public void add (Node n) {...} // but... HHH@` Then we could create a node, and add it to the graph: lHl @0P Graph g = new Graph(); Node n = new Node("test"); g.add(n); // but... HHH@`  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.) A factory method is a method that creates another object. (The constructor of the other object is then often not made available.)  'HHH@`  In class Graph, add these methods: lHl @0P public void makeNode (String name) {...} public void makeEdge (Node n1, Node n2) {...} HHH@` 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. u'HHH@`  HHH@8 **H @     Make Graph use a Factory Method for Nodes and Edges. HHH@8  J'HHH@` What's our code now? lHl @0P 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() {...} } HHH@`  C'HHH@`  'HHH@8 **H @     Document! Document! Document!  #'HHH@` 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, a 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. 'HHH@`  What is needed? I'd suggest at least two things:  javadoc  comments in the code (so a reference manual can be automatically generated), and a framework user's guide. 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. 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." )l'HHH@8  **H @     Define what happens. HHH@`  'HHH@` 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. U'HHH@8 H @     H`Numeric (short, int, etc.) Char String Object Array Enumeration H @ Can it be negative? 0? positive? Is there a lower limit? upper limit? Is 0 allowed? Any restrictions (e.g., ASCII only)? Null allowed? 0-length string? Character restrictions? Null allowed? Type restrictions? Null allowed? 0-length array? Min/max size? Null allowed? What types are returned HHH@`  2'HHH@` 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.  7'HHH@8 **H @     Keep independent features separate. HHH@`  i'HHH@` 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). Instead, we'll make up an example. Suppose you create a document class and have a method: lHl @0P  public void setStyle (Font f, int mods, int size) HHH@`  Can we conceive of changing the size without changing the font? Of course. So we end up with client code like this: lHl @0P setStyle (getFont(), getModifiers(), newSize); HHH@` We've had to fetch the old font and modifiers just to pass them in again - wasted work! l' 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 lHl @0P public void setStyle (Font f, int modifiers, int size) { setFont(f); setModifiers(modifiers); setSize(size); } HHH@` 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? ' HHH@` Summary HHH@`  We developed these rules: We made these decisions: We have these open issues: 'HHH@` CHAPTER 4: ... To Framework HHH@`  In the last chapter, we discussed our class as a class. In this chapter, we want to make our graph be more of a framework. We'll follow several guidelines: Use Java interfaces Steal good ideas Omit needless features Use packages White box vs black box Inversion of control HHH@`  .'HHH@` **H @     Use Java interfaces. HHH@`  5HJava provides "interface" classes. These classes define the methods that must be present, but no implementations. This provides a strong barrier between interface and implementation. It lets us commit to the interface alone. 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. f  '**H @     Make our classes into interfaces. HHH@`  ժOur original implementation is still a useful group of classes. We'll rename it to SimpleGraph etc. and make it implement our interfaces. C'::H @     Retain our original classes as a sample implementation. Make them implement the interfaces. HHH@`  (' lHl @0P 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. HHH@`   $'**H @      Steal good ideas. HHH@`  <-@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). i@ ***** Also Rogers etc - some real graph class. From Swing trees, we can see: * distinction between mutable and immutable nodes * a userObject rather than "name" * provision of interface, abstract class, 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. @' HHH@` Mutability HHH@` 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. The 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.) P a'  H @     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. HHH@`  pWe 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.  '**H @     Consider mutability adapter classes. HHH@`   'HHH@` Notification HHH@` 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 graph changes. d'0ZZH @    ! Add notification support to graph. Note: This is another big decision that affects the fundamental nature of our framework. HHH@`  G'1To fit with the JDK 1.1. event model, we'll do something like this: lHl @0P 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) {...} } HHH@`  And (!) define which methods cause what notifications. (**H @    " Omit needless features. HHH@`  1(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. In our case, three features of Node stand out: the  getPathTo()  method, the name field, and the  getNodes()  method. HHH@` Paths HHH@` 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 an entirely different approach.) "( &3(**H @    # Remove the  getPathTo()  method. HHH@`  Y( 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. HHH@` Names HHH@` 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. V(z**H @    $ Don't make subclasses pay for weight they don't need. HHH@`  s(Not every class needs a name string. (Recall our original comment: "subclass and add your information to the node.") Why should subclasses pay for the string if they don't need it? They shouldn't! I(**H @    % Remove "name" from Node. HHH@`  I(Node and Edge are lighter now. A Node has information about its edges. An Edge has information about its two ends. HHH@` Nodes HHH@` 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. ( H @    % 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. HHH@`  (  (**H @    & Add features for completeness. HHH@`  (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: WM(::H @    & Add methods to support useful features that would be difficult or impossible to provide using existing methods. HHH@`  ('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. (H @    ' 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. HHH@`  (Add a method to Graph: lHl @0P public boolean isLinkReversible(); HHH@` which returns true if the incoming edges are tracked. Add a method to Node: lHl @0P public Enumeration getInEdges(); HHH@`  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.)  (A 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.  (**H @    ( Packages are the unit of release. HHH@`  I'j***** [TBD] Martin? Booch? We've talked about our graph framwework, but how is it delivered? 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: lHl @0P import com.xxx.graph; import com.yyy.graph.sample; HHH@`  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: lHl @0P Graph graph = new SampleGraph (parameters); HHH@` and from then on, nothing is aware that the actual class is SampleGraph. x'p**H @    ) White box vs. Black Box HHH@`  Xw'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. 5'I lHl @0P public Object getObject(); public void setObject() (Object o); HHH@` (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. 'y**H @    * The Hollywood Principle: Don't call us, we'll call you. HHH@`  #'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. We do have some of this 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. (#**H @    + Comb through - fix the details. HHH@`  q '$***** TBD Multiple occurrences of edges? Constraints on graphs? Auto-links (to self)? |(" HHH@` Summary HHH@`  Key ideas Decisions Todo F ( HHH@` F Z(HHH@`  2 wa@  HH 3bP  HH3h8( @ 00 D( : ea("h h h # Q# X    #,  Helvetica .* 1  h QNj"  X QIMei# X Q8# X#"M#"67#"/ #" J#"M#"JN###"/#"/   ")2   #)3  . #)42 ga  HH 3bP  HH4e\;W( @ 88008p2>fa|  HH 3bP  HH3f8( @ > < 2phat  HH   HHpC&( @ @@ 0P2l>a  HH 3bP  HH3h8( @ 00 D( 2na  HH 3bP  HH3f8( @ > < 2rCaX  HH 3bP  HH3h8( @ 00 D( 28ya  HH 3bP  HH3f8( @ > < 2j a@  HH 3bP  HH3h8( @ 00 D( 2Sa\  HH 3bP  HH3h8( @ 00 D( 2Ea  HH 3bP  HH3f8( @ > < 254a  HH 3bP  HH3f8( @ > < 225a   HH 3bP  HH4e\;W( @ 88008p2d[aP  HH 3bP  HH3f8( @ > < 2za  HH 3bP  HH3h8( @ 00 D( 21VaX  HH 3bP  HH3h8( @ 00 D( 2 Lmap  HH 3bP  HH3h8( @ 00 D( 2",aL  HH 3bP  HH3h8( @ 00 D( 2#^۪a   HH 3bP  HH3h8( @ 00 D( 2$]aL  HH 3bP  HH3f8( @ > < 2%ma<  HH 3bP  HH3f8( @ > < 2&wa  HH 3bP  HH3h8( @ 00 D( 2(&a  HH 3bP  HH3f8( @ > < 2)Xna  HH   HHZe( @ @@ 0P2*a   HH 3bP  HH3f8( @ > < 2+a  HH 3bP  HH3h8( @ 00 D( 2,a  HH 3bP  HH3f8( @ > < 2. (sa  HH 3bP  HH3h8( @ 00 D( 2/R( a  HH 3bP  HH3f8( @ > < 20(a  HH 3bP  HH3h8( @ 00 D( 21(&a  HH 3bP  HH3f8( @ > < 22'&ah  HH 3bP  HH3h8( @ 00 D( 24'aT  HH 3bP  HH3h8( @ 00 D( 25L'a  HH 3bP  HH3h8( @ 00 D( 26~'#at  HH 3bP  HH3h8( @ 00 D( 7( . HLPTX\`dh Chili Pepper`8( pl |؀Ѐ0~~$4 ~"HHH@`0~$4~j"HHH@`*0~$4 ~j"HHH@`*0@~$4 ~j"HHH@`*PP$ PP$ 0~$0@ Table Style ~jH @`0 ~@~$0@ Sub-Subhead ~j"HHH@`0@~$,<Subhead~j"HHH@`*0~~$,<Code@ b ~&lHl @0P $,Code@ b ~ $(URL ~P<kdϿUnd҂bdudYPt(@d#u %:d;pAQm` !e Aze Ndu d~@e _jd2xu ,Jd4a`e qnd?0u 9:d pe #e d ed @;G e cJdw[`e }ZdOzd e uJdJhtCe :d#d!0u %l)Jd& e )Ud,2P.e .7:d0i`3ld5t8t9u ;.:@<5@?e ? :@@0e @CJdA(u E$ :@F-<@Hi@dK@@NPe Na@Q@e R :dS e UdjdWGu Z:d[1@_"e _3&:d`Ye bV:@cs@e dI:deIpe g@iu i:@jPe kMWJ`le odq@t pu u :`vIdyu |x:`}wXd5u :@#0u :@ qt|r@C8mdFXdZF@`n@(Cx(,@ @$@2@:@ 2@>2@p2@2@2@2@82@j2@2@2@2@22@d2@2@2@2@,2@^2@2@2@2@&2@X2@2@2@2@ 2@R2@2@2@2@2@L2@~2Š@@P@8@@M`x(@@`` P@saaaaaaa<ja~J4 d[AYHHdRdAYd@eIh@eIhwNJNJNJ