Graph: adjacency list and matrix
In short: A graph is a set of vertices and edges; in a program it is stored as an adjacency list using O(V + E) memory or as an adjacency matrix using O(V²).
Problem
The table that does not fit
A courier company keeps the street network of the city in a table: a row and a column for every crossroad, and the cell holds 1 if there is a street between the two. When the company worked in one district with 300 crossroads, the table had 90,000 cells and nobody complained.
Then the company covered the whole city: 40,000 crossroads. The table became 40,000 × 40,000 = 1.6 billion cells. Even at one byte per cell that is 1.6 GB, and the server started to crash every time it loaded the map.
The most annoying part is that almost everything in the table is 0. Three or four streets leave a crossroad, not 40,000. How do you keep only the streets that exist?
The idea
Stops and streets: a graph
The delivery map is described by two things: stops (crossroads, warehouses, addresses) and the streets between them. Such a thing is called a graph. The stops are its vertices, and the streets are its edges. The number of vertices is written V, and the number of edges E.
- Undirected graph: the street goes both ways. If there is a way from Station to Square, there is one back.
- Directed graph: one-way streets. An edge Station → Square gives no way Square → Station.
- Weighted graph: every edge carries a number: length in metres, minutes, a price in €.
Here is our city: 8 stops and 9 two-way streets. The river splits it in two parts, joined by two bridges. This is how the graph comes from the company's system: a list of the stops and a list of the streets (a pair of names per row).
String[] stops = { "Depot", "Station", "Market", "Square", "Park", "Cinema", "Hospital", "Stadium",};String[][] streets = { {"Depot", "Station"}, {"Depot", "Market"}, {"Station", "Square"}, {"Market", "Square"}, {"Market", "Park"}, {"Square", "Cinema"}, {"Cinema", "Hospital"}, {"Park", "Stadium"}, {"Hospital", "Stadium"},};You will need the same city through the whole module: for the shortest route, for the islands after a closed bridge, and later for Dijkstra.
The idea
Two ways to keep it
Adjacency matrix. You number the stops from 0 to V − 1. The table is V × V, and the cell [i][j] says whether there is a street from i to j. This is the table from the problem.
Adjacency list. For every stop you keep a list of its neighbours only. In code this is a dictionary from a name to a list: Map<String, List<String>>. There are no empty places: a street that does not exist takes nothing.
Both are built from the same list of streets, in the same loop.
See it
One street, two entries
Map<String, List<String>> graph = new HashMap<>();Map<String, Integer> index = new HashMap<>();for (int i = 0; i < stops.length; i++) { graph.put(stops[i], new ArrayList<>()); index.put(stops[i], i);}int n = stops.length;boolean[][] matrix = new boolean[n][n];for (String[] street : streets) { String a = street[0], b = street[1]; graph.get(a).add(b); graph.get(b).add(a); int i = index.get(a), j = index.get(b); matrix[i][j] = matrix[j][i] = true;}Step by step, in words
- Eight stops, no streets yet. Every stop gets an empty list and a number: its row and column in the 8 × 8 matrix, all zeros.
- The first street, Depot – Station: Station goes into the list of Depot, and Depot into the list of Station. In the matrix two cells become 1: [0][1] and [1][0].
- Depot – Market: Market goes after Station in the list of Depot. The order in a list is the order of the streets.
- A two-way street is written twice: in both lists and in both cells. That is why the matrix is symmetric about its diagonal.
- Market – Park and Square – Cinema cross the river. Market and Square now have three neighbours each; the others have two.
- The last streets on the other bank. Every list grows only by its real streets.
- 9 streets: 18 entries in the lists, 64 cells in the matrix, 46 of them zero. With 40 000 crossroads that is about 120 000 entries against 1.6 billion cells.
The whole program prints the lists and the matrix:
for (String stop : stops) { System.out.println(stop + ": " + String.join(", ", graph.get(stop)));}for (boolean[] row : matrix) { StringBuilder line = new StringBuilder(); for (boolean cell : row) line.append(cell ? "1 " : "0 "); System.out.println(line.toString().trim());}Depot: Station, MarketStation: Depot, SquareMarket: Depot, Square, ParkSquare: Station, Market, CinemaPark: Market, StadiumCinema: Square, HospitalHospital: Cinema, StadiumStadium: Park, Hospital0 1 1 0 0 0 0 01 0 0 1 0 0 0 01 0 0 1 1 0 0 00 1 1 0 0 1 0 00 0 1 0 0 0 0 10 0 0 1 0 0 1 00 0 0 0 0 1 0 10 0 0 0 1 0 1 0The list of each stop is in the order in which the streets came. The matrix is symmetric: row 2 and column 2 are the same, because every street goes both ways.
Try it
Predict the output
Three streets around Square, in a different order. What does the program print?
String[][] streets = { {"Market", "Square"}, {"Square", "Cinema"}, {"Station", "Square"},};Map<String, List<String>> graph = new HashMap<>();for (String stop : stops) graph.put(stop, new ArrayList<>());for (String[] street : streets) { graph.get(street[0]).add(street[1]); graph.get(street[1]).add(street[0]);}System.out.println(String.join(", ", graph.get("Square")));Try it
Fill in
A two-way street has to be written into both cells:
for (String[] street : streets) {
int i = index.get(street[0]), j = index.get(street[1]);
matrix[i][j] = = true;
}The cell [i][j] is the street from i to j, and [j][i] is the same street back. In an undirected graph the two are always equal.
The idea
What it costs
The three questions that the courier app asks all the time cost different amounts:
| matrix | adjacency list | |
|---|---|---|
| memory | V² cells | V lists and 2E entries: O(V + E) |
| is there a street between a and b? | one cell: O(1) | a look over the neighbours of a: O(neighbours) |
| who are the neighbours of a? | the whole row: O(V) | only the neighbours: O(neighbours) |
The program goes over the neighbours of every stop in both ways and counts every look: in the matrix every cell, in the list every stop and every entry.
int matrixLooks = 0, matrixFound = 0;for (int i = 0; i < stops.length; i++) { for (int j = 0; j < stops.length; j++) { matrixLooks++; if (matrix[i][j]) matrixFound++; }}int listLooks = 0, listFound = 0;for (String stop : stops) { listLooks++; for (String next : graph.get(stop)) { listLooks++; listFound++; }}System.out.println("Matrix: " + matrixLooks + " looks, " + matrixFound + " neighbours");System.out.println("List: " + listLooks + " looks, " + listFound + " neighbours");boolean inMatrix = matrix[index.get("Market")][index.get("Park")];boolean inList = graph.get("Market").contains("Park");System.out.println("Is there a street Market - Park? " + inMatrix + " " + inList);Matrix: 64 looks, 18 neighboursList: 26 looks, 18 neighboursIs there a street Market - Park? true trueWith 8 stops the difference is small. Run the same on a grid city of n crossroads, each one joined to its right and its lower neighbour:
- Matrix: the whole row of every crossroad
O(n²) - Adjacency list: only the real streets
O(n)
| Algorithm | n = 10 | n = 1,000 | n = 5,000 | n = 100,000 |
|---|---|---|---|---|
| Matrix: the whole row of every crossroad | 100 | 1,000,000 | 25,000,000 | ≈ 10,000,000,000 |
| Adjacency list: only the real streets | 36 | 4,872 | 24,716 | 498,734 |
int matrixLooks = 0, matrixFound = 0;for (int i = 0; i < stops.length; i++) { for (int j = 0; j < stops.length; j++) { matrixLooks++; if (matrix[i][j]) matrixFound++; }}int listLooks = 0, listFound = 0;for (String stop : stops) { listLooks++; for (String next : graph.get(stop)) { listLooks++; listFound++; }}System.out.println("Matrix: " + matrixLooks + " looks, " + matrixFound + " neighbours");System.out.println("List: " + listLooks + " looks, " + listFound + " neighbours");boolean inMatrix = matrix[index.get("Market")][index.get("Park")];boolean inList = graph.get("Market").contains("Park");System.out.println("Is there a street Market - Park? " + inMatrix + " " + inList);At 1000 crossroads the matrix makes 1,000,000 looks, and the list 4,872. At 5000 the matrix is already at 25,000,000, the list at 24,716. These numbers are also the memory: the matrix holds n² cells, the list as many entries as it makes looks.
That is why city maps, social networks and dependencies between packages are kept as adjacency lists. They are sparse graphs: E is of the order of V, not of V².
More precisely, if you are curious
The matrix wins when the graph is dense: almost everyone is connected to almost everyone, for example a table of distances between 50 warehouses. Then V² cells are not a waste, and "is there an edge" is one cell. There is also a middle way: an adjacency list with a set (Set) instead of a list answers "is there a street" in O(1) on average, at the price of more memory per entry.
The idea
Direction and length
In the real system a street comes with a length, and some streets are one-way. The adjacency list then keeps a pair: where to and how many metres. The system sends them as text, one street per row: "from to metres".
record Street(String to, int meters) {}
String[] lines = { "Depot Station 400", "Depot Market 300", "Station Square 500", // …};Map<String, List<Street>> graph = new HashMap<>();for (String stop : stops) graph.put(stop, new ArrayList<>());for (String line : lines) { String[] part = line.split(" "); int meters = Integer.parseInt(part[2]); graph.get(part[0]).add(new Street(part[1], meters)); graph.get(part[1]).add(new Street(part[0], meters));}record Street is the neighbour together with the length. The row is split with split, and the metres become a number with Integer.parseInt.String text = graph.get("Market").stream() .map(s -> s.to() + " " + s.meters() + " m") .collect(Collectors.joining(", "));System.out.println("Market" + ": " + text);Market: Depot 300 m, Square 350 m, Park 600 mA one-way street is only the first add: b goes into the list of a, not the other way round. In the matrix only [i][j] is filled, and it stops being symmetric. In a weighted matrix the cell keeps the length, and a missing street is a special value, for example infinity.
Try it
Find the bug
A colleague builds the adjacency list. The program prints:
Map<String, List<String>> graph = new HashMap<>();for (String stop : stops) graph.put(stop, new ArrayList<>());for (String[] street : streets) { String a = street[0], b = street[1]; graph.get(a).add(b); graph.get(b).add(b);}Depot: Station, MarketStation: Station, SquareMarket: Market, Square, ParkSquare: Square, Square, CinemaPark: Park, StadiumCinema: Cinema, HospitalHospital: Hospital, StadiumStadium: Stadium, StadiumStation turns out to be its own neighbour, and Depot is missing from its list. Which line has the bug?
Pick the line with the bug.
The second direction has to put a into the list of b: graph.get(b).add(a);. Now every street writes b into its own list. The way from Depot to Station is there, and the way back is not, as if all streets were one-way, plus one "street" from every stop to itself.
More precisely
How it is in the other languages
HashMapdoes not keep the order of its keys. That is why the programs go over the arraystops, not overgraph.keySet(). If you need an order, there isLinkedHashMap(insertion order) andTreeMap(sorted keys).- When the stops are not known in advance, the list is created at the first street:
graph.computeIfAbsent(a, k -> new ArrayList<>()).add(b). boolean[]takes one byte per cell.BitSetkeeps one bit, eight times less, but 1.6 billion bits are still 200 MB.
Exercise
Streets and metres
Solve the task in your editor.
The streets of a stop. The system sends the two-way streets as rows "from to metres", and the one-way streets separately:
String[] lines = { "Depot Station 400", "Depot Market 300", "Station Square 500", "Market Square 350", "Market Park 600", "Square Cinema 450", "Cinema Hospital 300", "Park Stadium 500", "Hospital Stadium 250",};String[] oneWay = { "Station Market 650", "Stadium Cinema 550",};Build the weighted graph: the two-way streets in both directions, the one-way ones only from the first stop to the second. For every stop print how many streets leave it and how many metres they are in total, and at the end the stop with the most streets (on a tie, the first in order):
Depot: 2 streets, 700 mStation: 3 streets, 1550 mMarket: 3 streets, 1250 mSquare: 3 streets, 1300 mPark: 2 streets, 1100 mCinema: 2 streets, 750 mHospital: 2 streets, 550 mStadium: 3 streets, 1300 mMost streets: Station (3)More tasks
- Dead ends. Print the stops that only one street leaves.
- Matrix with metres. Build a matrix where the cell is the length of the street, or -1 if there is no street, and print it.
- The other direction. From the graph with the one-way streets build the reverse one: every edge a → b becomes b → a. Which of the two do you need if you ask "from which stops can you reach Hospital"?
Test