diva.graph: Design review, September 4th, 1998

Preliminary notes

Review called by John Reekie and Michael Shilman for the Diva Graph package. Eager to stabilize API as soon as possible.

Review Materials

http://ptolemy.eecs.berkeley.edu/~johnr/diva/api/diva/graph/package-summary.html

diva.graph.Edge
diva.graph.EdgeSet
diva.graph.Graph
diva.graph.GraphEvent
diva.graph.GraphListener
diva.graph.GraphModel
diva.graph.Node
diva.graph.SubGraphModel
diva.graph.CompoundNode

http://ptolemy.eecs.berkeley.edu/~johnr/diva/api/diva/util/package-summary.html

diva.util.PropertyIndexSet
diva.util.PropertyContainer

Participants

Review started:1.30 PM
Review ended: 3.00 PM

Identified defects

Author's Response

This design review was extremely useful to me. I didn't agree with all the points that were raised, but the general message that I took away from the meeting was that the facade pattern of the GraphModel class was not completely understood, and this was due to ambiguity in the fact that Nodes/Edges/Graphs were given a full and self-consistent interface. It occurred to me that if it all topology-editing operations were done through the GraphModel interface and that the only low-level operations were "read" operations and "userObject/property" calls, then nearly all of the problems and ambiguities brought up in the design review would be fixed. I am writing a new version of the overview document which will discuss this in more detail.

Overview Document

  1. Diagram: Graph not necessarily have GraphModel

    Fixed.

  2. Diagram: GraphModel has multiple GraphListeners

    Fixed.

  3. Overview: remove summary of classes

    Shortened and integrated into overview section.

  4. GraphModel: doesn't send event on Node/Edge actions: seems dangerous

    Redesigned. In the new design, low-level "write" operations are only possible through the GraphModel interface. For efficiency it is possible to turn off notifications on the GraphModel. However, when the notifications are turned back on after an algorithm has completed, it will dispatch a STRUCTURE_CHANGED event to cause clients to refresh their views.

  5. Better support for hyper-edges? (NodeSet)

    Though this graph package is general, its primary goal is as a data structure for a graph visualization system. Because decisions made at this level must be supported by visualization front-ends, it is easier to make the graph interface as minimal as possible, and since hyper-edges can be simulated using specially-tagged nodes, this is probably the easiest for front-ends to deal with.

  6. Directedness: where implemented: property container or fundamental?

    Neither. I was going to implement directedness and other "common properties" as properties, and store their property names in some globally-available place so that all graph algorithms could share them. However, this is almost the same thing as making them fundamental. So my compromise is to define another set of interfaces RawEdge/RawNode/RawGraph which implement the "raw" graph containment and connectivity, and then make Edge/Node/Graph extend these and extend PropertyContainer/UserObjectContainer and add these "almost fundamental" properties of nodes and edges.

  7. If [PropertyIndexSet/PropertyContainer] designed for efficiency [versus Hashtable], then where are benchmarks?

    Preliminary benchmarks show a 1-4x performance improvement over Hashtable using an assortment of graph sizes and numbers of properties. It also occurred to me that PropertyIndexSet has an implicit "garbage collection" which Hashtables lack. See the documentation for more details. I believe that this optimization is justified; applications are slow enough as it is.

  8. getPropertyIndexSet: Integer array indexing is dangerous. Is there a better way?

Benchmarks should show the improvement over hashtables. If this is the case, then there is no better way that I can think of.

Edge

  1. Attach: should this throw an exception, instead of detaching automatically first? Reexamine: should edges attach() or should graphs attach()

    No longer a consideration under the new interface design.

  2. attach/detach: name? suggest: connect/disconnect

    No longer a consideration under the new interface design, but fixed in the actual underlying implementation.

  3. getHead(): Add "Return null if not exist" to Documentation

    Fixed.

  4. Concurrency between threads: setHead/setTail requires to calls before edge is consistent

    It has been decided that the graph package will not support concurrency. It is up to the user to provide concurrency support. This is a common practice in the recent Java code.

  5. attach/detach: redundant with setHead, setTail? Should this be in interface

    No longer a consideration under the new interface design.

  6. Why is this an interface and not a class? (i.e. is more than one class actually going to implement this)

    No longer a consideration under the new interface design. The interfaces for graphs/nodes/edges are now read-only.

  7. What happens on setHead(Null)?

    No longer a consideration under the new interface design.

  8. Is it the responsibility of the low-level API to ensure consistency.

    No. The low- and high-level APIs are more distinct in the new interface design, and in fact it is now encouraged to always use the high-level APIs in all common package usage..

  9. Is clear() doing too much work?

    No longer relevant in new interface design.

  10. Further document what interface does in strange and possibly inconsistent calls

No longer a consideration under the new interface design.

EdgeSet

  1. add: edge is not checked for uniqueness

    No longer relevant in new interface design.

  2. Should this be an interface or a class?

    No longer relevant in new interface design.

  3. Implement better policy in interface instead of relying on comments

    Greatly improved in new interface design. GraphModel implements a tight policy.

  4. getParent: no setParent... better name, add setParent?

    getParent() removed..

  5. getParent: probably not needed

    getParent() removed..

  6. In and Out sets can get corrupted using Node/Edge interface: consistency checks? Exceptions? At least in class implementation?

    No longer visible to the user in the new API.

  7. What if edge is not in Set?

    Don't understand...

  8. CONSISTENCY CHECKS?????? Manual check? is this redundant? Leave Hooks?

GraphModel implementations can provide graph-checking routines, since it knows the underlying structure of the graph.

Graph

  1. add: spec seems over-complex. Should it simply require that the node be removed first? Advocate: consistency checks

    Under consideration...

  2. Should there be sub objects and strict hierarchy? answer:CompoundNode.

    Don't understand...

  3. delete: see add.

    Don't understand...

  4. delete: name? Suggest: remove

    Fixed.

  5. clear: clarify, and see add

    Fixed.

  6. getNodeCount: should there be getEdgeCount? Edges don't seem to be fundamental to a graph? Can there be a symmetry between edges and nodes?

In a typical graph package there is no need for edges that cut across arbitrary graphs so it is easier to create a symmetry between edges and nodes. However, in this graph package "containment" and "connectivity" are more or less orthogonal, with nodes as the common point. So because an edge doesn't "belong" to a graph per se, I don't think that a symmetry is possible, nor am I convinced that it's particularly useful.

Node

  1. setParent():seems suspicious is this something that you really want to allow?

No longer visible to the user in the new API.

GraphModel

  1. Add(2),add(3) -> addNode and addEdge

    Fixed.

  2. addNode should default to the default graph?

    Added extra addNode() method that does this.

  3. addSubModel/removeSubModel: Clarify description and improve name. Maybe some more description of how SubGraphModel works. @seealso

    There is no longer a SubModel interface. GraphModel now contains a method getRoot() that returns the root model. Implementations can choose how this is implemented. In BasicGraphModel, there are two constructors, one for the top-most model and one for a sub-model; that's all the user needs to know.

  4. addSubModel expects implementation of GraphSubModel class

    GraphSubModel has been removed. Now GraphModel knows about hierarchy. The root GraphModel has a null root reference.

  5. delete->removeNode, removeEdge

    Fixed.

  6. What are the canonical events that get generated? i.e. if node removed, then not only issue nodeRemoved, but also all the edgeRemoved.

    I have chosen the following set of events: { edge_head_changed, edge_tail_changed, edge_data_changed, node_added, node_deleted, node_data_changed, structure_changed }. Though the edge_head_changed and edge_tail_changed might allow listeners to get into strange states, they are the minimal events necessary to implement a listener that can mirror the original graph. It is assumed that the end-user code that generated these events will either be through a "safe" API (a la GraphModel) or that it will be written with care. It is also not out of the question to write listeners which are careful about the events they receive.

    Alternately, I could have "edge_added" and "edge_deleted" methods, but this might initiate more work than is necessary on any particular

  7. should get*PropertyIndexSet be in GraphModel or in graph? more description of propertyindexset or a @seealso

    Should be in GraphModel. If it's in Graph, it's too fine-grained and algorithms cannot leverage the hash-once efficiency.

  8. getRoot: more information or @seealso.

    Don't understand.

  9. getRoot: does this return root graph or root GraphModel? Or does this not really return a root and all and this should be called getGraph?

    Fixed. getRoot() now returns a pointer to the root GraphModel. getGraph() returns the model's graph.

  10. @SEEALSO!!

    Don't understand.

  11. setProperty->setEdgeProperty, setNodeProperty, setGraphProperty as well?

    Fixed.

  12. setUserObject->setEdgeUserObject,setNodeUserObject

    Fixed.

  13. SetUserObject: multiple users(algorithms)? I guess you can't.

No, and it doesn't make sense either. The UserObject semantics has been moved to a separate interface, where it explains in detail the semantics of the user object and why this doesn't make sense. Use the property mechanism for annotating the node with algorithm annotation..

Related issues

none

Concluding notes

There were more reviewers than customary because a number of people were new to design reviews. (In general, three to five reviewers is optimum.) This is the first review with significant participation by both the Newton and Lee research groups! It was great. One of the Ptolemy reviewers said that he was surprised and pleased at the different perspective he got from the reviewers from the Newton group. -- johnr

Comments to:

michaels@eecs.berkeley.edu