Concept

An AdjacencyGraph is a graph which is concerned only with the vertices and not with the edges. There are no explicit edge objects, adjacent vertices are simply accessed as AdjacencyGraph.neighbors(). For many use cases this is sufficient.

Complexity

• AdjacencyGraph.neighbors() is required to be constant time; iterating over the iterable is required to be linear in the number of neighbors
• AdjacencyGraph.degreeOf() is required to be at most linear in the number of neighbors
• AdjacencyGraph.containsEdge() is required to be at most linear in the number of neighbors

Infinite Graphs

The number of vertices may be infinite in which case the user has to take care not to call methods which will not return (this is similar to an Iterable which may contain an infinite number of elements).

The same applies for the number of neighbors of a vertex.

Design Notes

Think about making Vertex (and, in subclasses, Edge) member classes! cf. Graph example here

A generic edge between two vertices of type Vertex.

ImplicitEdgeWeights gives a mapping from vertex pairs to weights and a zero element to make Weight a monoid.

A graph with explicit edges.

The number of vertices and edges may be infinite in which case the user has to take care not to call methods which will not return (this is similar to an Iterable which may contain an infinite number of elements).

The same applies for the neighbors or adjacent edges of a vertex.

A SimpleGraph contains at most one undirected or two directed (but opposite) edges between any two vertices.

A Graph with efficient access to all vertices.

Complexity

• VertexList.vertices is required to be constant time; iterating over the iterable is required to be linear in the number of vertices

A Walk is a possibly empty sequence of edges connecting two vertices.

Weights gives a mapping from edges to weights and a zero element to make Weight a monoid.

Hops assigns an edge the weight of 1 and can therefore be used to count the number of edges, or 'hops' between two vertices.