Graphvertexrefactor

GraphVertex Refactor

Encapsulate GraphVertex, use OverlayGraphs

This is a conversation that occurred by email. It is posted here to allow for comments and objections before implementing any of this.

AMB = andrew byrd

DT = david turner

BF = brian ferris

AMB: In class Graph we now have: HashMap<String, GraphVertex> vertices; So the collection of GraphVertex (and hence the edge lists) are keyed on vertex labels. String hashcodes are cached, so I imagine this is not a performance problem, but I find it much cleaner to just use the vertex itself as the key since it has its own unique index, and use identity equality for vertices. Is there a compelling reason to continue using the label?

DT: Well, it's kind of nice to be able to look up vertices by label. But I guess we could give that up.

AMB: It is also possible to make GraphVertex a private detail inside Graph and hide all the graphvertex-fetching details, getting straight to the edgelists, e.g.

class OverlayGraph:
public void addOutgoing(Vertex v, Edge e)
public List<Edge> getOutgoing(Vertex v)

DT: This would be great; the current code is a bit ugly.

BF: I'm +1 on using the Vertex itself as the key. I also introduced the HasEdges decorator interface to indicate that a Vertex can be examined directly for its edges, avoiding a HashMap lookup for vertices where it made sense.

AB: I propose the following compromise:

All vertices have their own edges (i.e. merge the hasedges interface into the vertex class), which are their edges in the main graph. A Graph object is then just several indexes (by label, vertexid, spatial...) into the set of vertices. Overlay graphs provide supplemental edges beyond those in the main graph, for contraction hierarchies or what we call "extra edges" which connect temporary vertices to the main graph (I think it would make more sense if these were renamed temporaryEdges in the process). Eliminate GraphVertex entirely (well, a similar private class could be used to group incoming and outgoing edge lists in OverlayGraphs). The current extraEdges map does not distinguish between incoming and outgoing edges, which leads to some backward edge traversals that are mostly harmless but nonetheless incorrect.