getEdges and getNeighbors methods need to run in constant time (or at least amortized-constant)

Presently, both methods require a full O(n) linear search of the graph's edge 
set each execution, which--while enabling in its architectural simplicity--has 
become increasingly problematic for the design of functions, especially those 
already computationally expensive (e.g. connectivity testing, path-finding 
algorithms, Floyd-Warshall's algorithm).  There needs to be a core change to 
the software architecture to enable roughly constant time neighbor-vertex and 
coincident-edge lookup.

Ideally, though the raw vertex and edge sets should still be available, edge 
creation and deletion should be handled by the Graph class--not by an 
ObservableList property of a Graph.  This way, edge creation, validation, and 
deletion can also be executed in constant time in a more consistent manner.  
Unfortunately, the only way to do both would be to convert the edges 
ObservableList (if not also the vertexes ObservableList) to some sort of 
ObservableReadOnlyList that is only editable by the Graph.  This can be 
accomplished by explicitly stating a private backing list for all such 
read-only lists, and exposing them through a wrapper that merely entails 
iteration, indexing, and reading.  In pseudo-code:

public class Graph
{
     public ObservableReadOnlyList<Vertex> vertexes;
     public ObservableReadOnlyList<Edge>   edges;

     private List<Vertex> vertexList;
     private List<Edge>   edgeList;

     public Graph( ... )
     {
          vertexList = new List<Vertex>();
          vertexes = new ObservableReadOnlyList<Vertex>(vertexList);

          edgeList = new List<Edge>();
          edges = new ObservableReadOnlyListn<Edge>(edgeList);

          ...
     }

     // Vertex and edge creation/deletion methods go here

     ...
}

public class ObservableReadOnlyList<T> implements Iterable<T>
{
     List<T> backing;

     public ObservableReadOnlyList( List<T> backing )
     {
          this.backing = backing;
     }

     public T get(int index)
     {
          return backing.get(index);
     }

     // Inherited Iterable<T> methods go here

     ...
}

It is also perhaps possible that using this architecture, the read-only lists 
would not have to be observable anymore (now handled by the graph) and they 
could be implemented as indexable-sets (i.e. effectively lists disallowing 
duplicate items).  Either way, this will be a major change and will certainly 
break present compatibilities with all generators and many functions.

Original issue reported on code.google.com by 0x24a53...@gmail.com on 16 Dec 2010 at 1:33

WmHHooper / visigraph

getEdges and getNeighbors methods need to run in constant time (or at least amortized-constant) #95