Input

Output

Input Description: A graph \(G\).
Problem: Give an efficient, flexible data structure to represent \(G\).

Excerpt from The Algorithm Design Manual: While there are several possible variations, the two basic data structures for graphs are adjacency matrices and adjacency lists.

• How big will your graph be? How many vertices will it have, both typically and in the worse case? Ditto for the number of edges? If your graph has 100 vertices, your adjacency matrix contains 10,000 entries. If your graph has 1,000 vertices, your adjacency matrix contains 1,000,000 entries. If your graph has 10,000 vertices, your adjacency matrix contains 100,000,000 entries -- so forget about it. Adjacency matrices work only for small or very dense graphs.
• How dense will your graph be? If the graph is very dense, meaning that a large fraction of the vertex pairs define edges, there is probably no compelling reason to use adjacency lists, since you will be doomed to using Theta(n²) space, anyway.
• Which algorithms will you be implementing? Certain algorithms are easier on adjacency matrices (such as all-pairs shortest path) and others on adjacency lists (such as most DFS-based algorithms). Adjacency matrices win for algorithms that repeatedly ask, ``Is (i,j) in G?'' However, most graph algorithms can be modified to eliminate such queries.
• Will you be modifying the graph over the course of your application, and if so, how? Repeated edge insertions and (particularly) deletions argue for adjacency matrices, or perhaps for fancier versions of adjacency lists such as binary search trees. However, more likely than modifying the topology of graph is modifying the attributes of a vertex or edge of the graph, such as size, weight, or color. Attributes are best handled as extra fields in the vertex or edge records of adjacency lists.

  Building a good general-purpose graph type is surprisingly tricky and difficult. For this reason, we suggest that you check out existing implementations (particularly LEDA) before hacking up your own. Note that it costs only time linear in the size of the larger data structure to convert between adjacency matrices and adjacency lists. This conversion is unlikely to be the bottleneck in any application, if you decide you want to use both data structures and have the space to store them. This usually isn't necessary but might prove simplest if you are confused about the alternatives.

Implementations

Guava (rating 10)	C++ Boost Graph Library (rating 10)
LEDA (rating 10)	Boost Graph Library (rating 9)
JUNG (rating 9)	gonum (rating 8)
JGraphT (rating 8)	JDSL (rating 8)
networkx (rating 7)	Stanford Graphbase (rating 0)

Recommended Books

Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica by S. Pemmaraju and S. Skiena	Combinatorial Algorithms for Integrated Circuit Layout by T. Lengauer	Handbook of Theoretical Computer Science : Algorithms and Complexity by J. Van Leeuwen
Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein	Data Structures and Network Algorithms by R. Tarjan	Data Structures and Algorithms by A. Aho and J. Hopcroft and J. Ullman

Related Problems

Graph Partition

Set Data Structures