Edges that point one way
A graph can be a map, with places as vertices and ways to move between them as edges. An edge can also record a relation that holds in one direction only: a course has to be passed before a later course can be taken, a file has to be compiled before the program that uses it, and one person can trust another who does not trust them back. A graph of such relations is a directed graph: every edge has a direction, from to , and it does not lead from back to .
Our example, here and in the topological sort and cycle detection that follow, is a set of four courses, numbered 0 to 3, with four rules:
- course 0 must be taken before course 1
- course 0 must be taken before course 2
- course 1 must be taken before course 3
- course 2 must be taken before course 3
The four courses as a graph
We make each course a vertex, and we draw each rule as an edge from the course that comes first to the course that has to wait for it:
We store the graph in adjacency lists: graph[u] is the list of the vertices that has an edge to.
graph[0] = [1, 2]graph[1] = [3]graph[2] = [3]graph[3] = []An undirected edge goes into two lists, one at each of its ends. A directed edge goes into one, the list of the vertex it starts at. So graph[0] shows at once which courses wait for course 0, but nothing stored at course 3 says which courses it is waiting for. To find that out from these lists we would have to read all of them.
Indegree and outdegree
For many questions we do not need to know which edges enter a vertex, only how many do. The indegree of a vertex is the number of edges that end at it, and its outdegree is the number of edges that start at it. Course 3 has indegree 2, because the edges from courses 1 and 2 end at it, and outdegree 0, because no edge starts at it. Here are both numbers for all four courses:
For the courses, the indegree counts the courses that must be taken directly before this one, and the outdegree counts the courses that wait directly for it. Course 0 has indegree 0, so nothing has to come before it. Course 3 has outdegree 0, so nothing waits for it. Only the rules themselves are counted, and not what follows from them. Course 3 cannot be taken before course 0 either, but there is no edge , so course 0 does not count towards the indegree of course 3.
Both rows add up to 4, the number of edges. This is true of every directed graph. Each edge starts at exactly one vertex and ends at exactly one vertex, so it adds 1 to one outdegree and 1 to one indegree.
The outdegree of is the length of graph[u]. The indegrees are not stored anywhere, so we count them while we read the edges:
def degrees(n, edges):
graph = [[] for _ in range(n)]
indegree = [0] * n
for u, v in edges:
graph[u].append(v) # the edge u -> v goes into the list of u only
indegree[v] += 1
outdegree = [len(graph[u]) for u in range(n)]
return indegree, outdegree
indegree, outdegree = degrees(4, [(0, 1), (0, 2), (1, 3), (2, 3)])
print(*indegree)
print(*outdegree)The program prints the two rows of cells shown above. It does a fixed amount of work for each vertex and for each edge.
Find a vertex by its degrees
Some problems can be answered from the two degrees alone, without any search of the graph. Here is one:
A town has people labeled to . Each pair [a, b] in trust says that person a trusts person b. The town judge trusts nobody, and everybody else trusts the judge.
Return the judge's label, or -1 if nobody fits.
Constraints
- At most pairs, all different, with
Sample 1 · Input
n = 2, trust = [[1,2]]
Output
2
Sample 2 · Input
n = 3, trust = [[1,3],[2,3]]
Output
3
Sample 3 · Input
n = 3, trust = [[1,3],[2,3],[3,1]]
Output
-1
We make each person a vertex and each pair [a, b] an edge , which reads " trusts ". The two conditions on the judge then become conditions on the degrees of one vertex:
- The judge trusts nobody, so no edge starts at the judge. The judge has outdegree 0.
- Everybody else trusts the judge, so an edge from each of the other people ends at the judge. The judge has indegree .
In the third sample the edges are , and , which give these degrees:
Person 3 has indegree , but also outdegree 1 because of the edge , so person 3 is not the judge. Nobody else has indegree 2, and the answer is .
Two people cannot both pass the test. If and both did, then would trust , because everybody other than trusts , and the outdegree of would not be 0. So the function can return the first person who passes. A town of one person needs no special case: there are no pairs, the one person has indegree and outdegree 0, and the answer is 1.
def find_judge(n, trust):
indegree = [0] * (n + 1) # people are numbered from 1
outdegree = [0] * (n + 1)
for a, b in trust: # a trusts b: the edge a -> b
outdegree[a] += 1
indegree[b] += 1
for person in range(1, n + 1):
if indegree[person] == n - 1 and outdegree[person] == 0:
return person
return -1
print(find_judge(2, [[1, 2]]))
print(find_judge(3, [[1, 3], [2, 3]]))
print(find_judge(3, [[1, 3], [2, 3], [3, 1]]))The last three lines run the samples.
The graph is never built. The function reads each pair once and then each person once.
Cost of storing a graph and counting degrees
- Adjacency lists
time and memory - One list per vertex and one entry per edge, for vertices and edges.
- Indegrees and outdegrees
time - One addition per edge while the edges are read, and one list length per vertex.
- Find the Town Judge
time for pairs - One pass over the pairs and one over the people, at most steps at this problem's limits.
Vertices with indegree 0
The indegrees also tell us where to begin when we want to take the four courses one at a time without breaking a rule. Course 0 has indegree 0, so it can be taken first. Once it is done, its two edges no longer hold anything back, and courses 1 and 2 are waiting for nothing.
The widget shows the four courses and calls them tasks. The badge on a task counts the edges into it from tasks that are not finished yet, so every badge starts at the indegree. Finish all four tasks in an order the widget accepts, and watch which badges drop after each one. Then press Add the edge 3 → 0 and start again. Now every task has an edge into it, and none of them can go first.
Finishing a task whose badge shows 0, again and again until every task is done, puts the tasks in an order that breaks no rule. Finding such an order is called topological sorting, and this way of finding it is called Kahn's algorithm. The run with the edge 3 → 0 shows that it can get stuck, when tasks wait for each other in a circle, called a cycle.
Common mistakes with directed edges
Adding a directed edge to both adjacency lists, as for an undirected graph.
- Where it breaks
- For the four courses,
graph[3]becomes[1, 2]. Course 3 then appears to have outdegree 2, and courses 1 and 2 appear to wait for it. Its outdegree is 0. - The fix
- For an edge , append to
graph[u]and nothing else.
Reading a pair in the wrong direction.
- Where it breaks
- In Find the Town Judge with
n = 3, trust = [[1,3],[2,3]], counting each pair[a, b]as an edge gives person 3 outdegree 2 and indegree 0, and the function returns-1. The answer is3. - The fix
- Before writing the loop, write down in words what an edge means, here " trusts ", and check the first sample against it.
Checking only the judge's indegree.
- Where it breaks
- In the third sample,
n = 3, trust = [[1,3],[2,3],[3,1]], person 3 is trusted by both others, so a check of the indegree alone returns3. Person 3 trusts person 1, and the answer is-1. - The fix
- Require outdegree 0 as well as indegree .
Recall A directed graph has five vertices with outdegrees 2, 0, 1, 3 and 1. How many edges does it have, and what do its indegrees add up to?
It has edges, because every edge starts at exactly one vertex and is counted once in that vertex's outdegree. The indegrees add up to 7 as well, because every edge also ends at exactly one vertex.