The graph representation in JUNG

1. Network and graph data sets have often been described mathematically as matrices which are commonly implemented as 2D arrays. The represantation facilitates fast retrieval of the edges, which operations is called findEdge in JUNG.
However, this representation is generally not feasible for large-scale networks. First, it requires O(|V|2) space. Second, existing algorithms for network analysis, which involve matrix multiplication or matrix inversion, generally require O(|V|3) time on 2D arrays. Third, this representation is problematic for dynamic networks(those whose vertex set may grow larger or smaller) and for networks with parallel edges. Finally, large-scale networks are almost invariably very sparse, so almost all the the space in a 2D array representing such a network is wasted on representing absent links.
2. A common alternative representation for sparse graphs and networks is the adjacency list representation, in which each vertex maintains a list of incident edges (or adjacent vertices); this requires O(|V|+|E|) space. This representation does NOT permit an efficient implementation of findEdge.
3. Most of the current JUNG vertex implementations employ a variant of the adjacency list representation, which is termed as adjacency map representation: each vertex maintains a map from each adjacent vertex to the connecting edge(or connecting edge set, in the case of graphs that permit parallel edges). ( Separate maps are maintained, if appropriate, for incoming directed edges, outgoing directed edges, and undirected edges.) This uses slightly more memory than the adjacency list representation, but makes findEdge approximately as fast as the corresponding operation on the 2D array representation.