Vertices that can be reached
Breadth-first search measures how far each vertex of a graph is from a starting vertex. Many questions about a graph ask for less: whether one vertex can be reached from another at all, or how many separate pieces the graph has. Depth-first search (DFS) answers such questions, and it can be written as a recursive function of a few lines. The first problem of this lesson asks only which rooms of a house can be reached:
There are rooms numbered 0 to . Room 0 is open and every other room is locked. Each room holds some keys; a key numbered opens room , and you keep every key you pick up.
rooms[i] lists the keys inside room . Return true if you can enter every room, and false otherwise.
Constraints
- Each room holds at most keys, and all rooms together hold between 1 and
- Every key is a room number from 0 to , and the keys in one room are distinct
Sample 1 · Input
rooms = [[1],[2],[3],[]]
Output
true
Sample 2 · Input
rooms = [[1,3],[3,0,1],[2],[0]]
Output
false
In the first sample room 0 holds key 1, room 1 holds key 2 and room 2 holds key 3, so we can walk through all four rooms and the answer is true. In the second sample the only key to room 2 lies in room 2 itself. We can never enter it, and the answer is false.
The house is a directed graph. Each room is a vertex, and a key to room lying in room is an edge u → v, because from room we can go on to room . The list rooms[u] is the adjacency list of . We can enter a room when a path leads to it from room 0, and such a room is called reachable from room 0. The problem asks whether every vertex is reachable from vertex 0.
A plain walk through the house, which takes the first key in each room and goes on to the room it opens, does not answer that. The walk can go in a circle: in the second sample room 0 holds a key to room 1, room 1 a key to room 3, and room 3 a key back to room 0. It also leaves keys behind: room 0 holds two keys, and the walk follows only one of them. A search has to record which rooms it has entered, and it has to come back for the keys it has not used.
Breadth-first search does both and would solve this problem, since the rooms that end with a distance are the reachable ones. Depth-first search, written as a recursive function, needs neither the queue nor the distances, so it is shorter. It also keeps the path it is on, which a later part of this lesson uses to find round trips in a graph.
The order of the search
The search walks along one path and marks each vertex it comes to, until it is at a vertex with no unmarked neighbor. Then it steps back along the path, one vertex at a time, until it is at a vertex that still has an unmarked neighbor, and walks on from there. We write this as a procedure for visiting one vertex. To visit a vertex :
- Mark as visited.
- Go through the neighbors of in the order of its adjacency list. Each time a neighbor is not marked yet, visit , which means carrying out steps 1 and 2 for to the end, and only then go on to the next neighbor of .
To search from a starting vertex, we visit it. A visit is over when its vertex has no neighbor left to try. The search is then back in the visit that started this one, and goes on with the next neighbor there.
The search on six vertices
The samples of Keys and Rooms are too small to show much of this order, so we follow the search on a larger directed graph. It has six vertices and the edges 0 → 1, 0 → 2, 1 → 3, 3 → 4, 2 → 4 and 4 → 1, and vertex 5 has no edges. As a house it is rooms = [[1, 2], [3], [4], [4], [1], []]. The note under each vertex is its place in the order of the search:
The search begins with a visit to vertex 0. Its first neighbor, vertex 1, is unmarked, so the visit to 0 waits while vertex 1 is visited. The only neighbor of 1 is vertex 3 and the only neighbor of 3 is vertex 4, and both are unmarked. The search is now four visits deep, and each of the first three is waiting for the next:
visited are highlighted. The numbers under visited are the vertices.The neighbor of 4 is vertex 1, which is marked, so the search does not go there. Without the mark it would go around 1, 3 and 4 forever. Vertex 4 has no other neighbor, so its visit is over, and the visits to 3 and to 1 end for the same reason. The search is back at vertex 0, whose second neighbor, vertex 2, is unmarked:
The neighbor of 2 is vertex 4, which was marked earlier, by way of 1 and 3. The visit to 2 ends, then the visit to 0, and with it the search. Vertex 5 is still unmarked, because no edge leads to it. In the house, room 5 cannot be entered, and the answer to Keys and Rooms is false.
The vertices were visited in the order 0, 1, 3, 4, 2. A BFS from vertex 0 takes them in the order 0, 1, 2, 3, 4, nearest first. The depth-first search left vertex 2, one edge from the start, for last, because it went as deep as it could along the path through vertex 1 first. That is where its name comes from.
The three states of a vertex
During the search every vertex is in one of three states. It is unseen until its visit starts, that is, while it is unmarked. It is active from then until its visit is over, which includes the time it waits for the visits it started. After that it is finished. The active vertices are the ones on the path in the two drawings above, and at every moment of the search they form such a path, from the start to the vertex being visited. The figure has one bar for each visit of the search:
The dashed and the dotted arrow are the two edges that led to a marked vertex. The edge 4 → 1 was read while vertex 1 was active, and the edge 2 → 4 when vertex 4 was already finished. Near the end of this lesson, this difference becomes the test for a cycle in a directed graph.
The search as a recursive function
A visit that starts other visits and waits for each of them is a function that calls itself. In the program below, visit(u) marks and then calls visit(v) for every neighbor that is not marked. The call stack, which holds every call that has started and not yet returned, keeps the waiting visits, so the program itself stores only the array visited. The program runs the search on our six rooms and then on the two samples.
def can_visit_all_rooms(rooms):
visited = [False] * len(rooms)
def visit(u):
visited[u] = True
for v in rooms[u]:
if not visited[v]:
visit(v)
visit(0)
return all(visited)
print(can_visit_all_rooms([[1, 2], [3], [4], [4], [1], []]))
print(can_visit_all_rooms([[1], [2], [3], []]))
print(can_visit_all_rooms([[1, 3], [3, 0, 1], [2], [0]]))The program prints False, True and False. The first line is for our six rooms, where room 5 cannot be entered.
The search marks every vertex that is reachable from the start and no other. It moves only along edges, so every vertex it marks is reachable. And when a visit to is over, every neighbor of is marked. At the end all visits are over, so no edge leads from a marked vertex to an unmarked one. A path from the start begins at a marked vertex, so each of its edges leads to another marked vertex, and every vertex on it is marked.
Worked example
Step through the search
The trace runs the recursive search one step at a time, first on the six vertices. It shows the state of each vertex and the call stack, which holds the active vertices in the order of the path.
The other presets are the six vertices with the neighbors of vertex 0 in the other order, 2 before 1, which the search visits in the order 0, 2, 4, 1, 3; the second sample of Keys and Rooms, in which room 2 stays unseen; and an undirected graph of four edges, each entered as two directed edges.
Enter 0, mark it active and pause earlier calls while its outgoing edges are explored.
- start
- 0
Change the example input
Current result: [0,1,3,4,2]
Cost of the search
- Time
- A visit starts only at an unmarked vertex and marks it at once, so each vertex is visited at most once, and each visit reads one adjacency list. For vertices and edges that is at most visits and list entries.
- Memory besides the graph
- One mark for each vertex, and one open call for each vertex on the path.
Keys and Rooms has at most 1,000 rooms and 3,000 keys:
A stack in place of the recursion
The recursive search has one call open for every vertex on its path, and on some graphs the path runs through every vertex. One such graph is a house in which room 0 holds only the key to room 1, room 1 only the key to room 2, and so on.
Python stops a program at about 1,000 nested calls, and on a line of 1,000 rooms, which Keys and Rooms allows, the program above ends with a RecursionError. A line of 998 rooms is the longest it handles, because the top level of the program and the call to can_visit_all_rooms already count as two. sys.setrecursionlimit raises the limit, but Building Roads, later in this lesson, has up to cities, and it is safer not to depend on the depth of the calls.
When the search only has to mark the reachable vertices, the loop of breadth-first search can replace the recursion, with a stack in place of the queue. The stack holds vertices that are marked but whose adjacency lists have not been read. The loop takes a vertex off it, reads its list, and marks and pushes every unmarked neighbor:
def can_visit_all_rooms(rooms):
visited = [False] * len(rooms)
visited[0] = True
stack = [0]
while stack:
u = stack.pop()
for v in rooms[u]:
if not visited[v]:
visited[v] = True
stack.append(v)
return all(visited)
print(can_visit_all_rooms([[1, 2], [3], [4], [4], [1], []]))
print(can_visit_all_rooms([[1], [2], [3], []]))
print(can_visit_all_rooms([[1, 3], [3, 0, 1], [2], [0]]))
line = [[room + 1] for room in range(99_999)] + [[]]
print(can_visit_all_rooms(line))The fourth line, True, is for a line of 100,000 rooms.
A vertex is marked at the moment it is pushed, so it is pushed once, and the loop takes time like the recursive function. This loop is often called an iterative DFS, but it does not keep to one path: in a triangle it marks both other vertices straight from the first, where a depth-first search reaches the third vertex from the second.
It marks the same vertices as the recursive function, though, and takes our six off the stack in the order 0, 2, 4, 1, 3, because a stack returns the vertex pushed last. The next two parts need only the marks and use this loop; finding a cycle needs the path of the search, which this stack does not hold.
Connected components
So far a search has started at one vertex and marked what is reachable from it. The next question is about a whole graph, and the graph is undirected. In an undirected graph, reaching works both ways: a path from to , walked backwards, is a path from to . And reaching can be chained: if reaches and reaches , the first path followed by the second takes to . So the vertices fall into groups in which any two vertices are joined by a path, and no edge joins two different groups. These groups are the connected components of the graph. Here is a problem about them:
A country has cities numbered 1 to and two-way roads. Build as few new roads as possible so that every city can reach every other city, and say which roads to build.
The first line holds and , and each of the next lines holds the two cities of a road. Print the number of new roads, then one new road per line. Any valid set of roads is accepted.
Constraints
- A road joins two different cities, and no two roads join the same pair
Sample · Input
4 2 1 2 3 4
Output
1 2 3
In the sample, cities 1 and 2 are one component and cities 3 and 4 are another. One new road between the two, such as the road from 2 to 3 in the sample output, connects all four cities.
A search from a vertex marks the vertices it can reach, which in an undirected graph are exactly the vertices of its component. To find all the components we go through the vertices in order and start a search at every vertex that is still unmarked, with one array visited for all the searches. Each search marks one whole component, so the number of searches is the number of components. On the sample there are two:
visited after each search, with the entries that search marked highlighted. City 2 is marked when the scan comes to it, so the second search starts at city 3.Say the map has components. A new road joins at most two of them into one, so each road lowers the number of components by at most 1, and going from components to one takes at least roads. That many are enough: we keep the city at which each search started, one per component, and build a road from each of these cities to the next one.
Count the searches and join their starting cities
The program reads each road into the adjacency lists of both its cities. The search inside the scan is the loop from the previous part.
def building_roads(n, graph):
visited = [False] * (n + 1)
starts = []
for city in range(1, n + 1):
if visited[city]:
continue
starts.append(city) # a search starts here: a new component
visited[city] = True
stack = [city]
while stack:
u = stack.pop()
for v in graph[u]:
if not visited[v]:
visited[v] = True
stack.append(v)
return [(starts[i], starts[i + 1]) for i in range(len(starts) - 1)]
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
graph = [[] for _ in range(n + 1)]
for i in range(m):
a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
graph[a].append(b)
graph[b].append(a)
roads = building_roads(n, graph)
print(len(roads))
for a, b in roads:
print(a, b)On the sample the searches start at cities 1 and 3, so the program prints 1 and then the road 1 3, where the sample output has 2 3. The judge accepts any correct set of roads.
The scan adds little work. No city is marked twice, since visited is never cleared, and each road is read twice, once from each of its ends. For the largest input that is
When a problem asks which component each vertex is in, the search can write the number of its component into an array in place of the mark. Two vertices are connected when they have the same number.
The scan finds components only because reaching works both ways. In a directed graph, what a search marks depends on where it starts: on our six vertices a search from vertex 0 marks vertices 0 to 4, and a search from vertex 4 marks only 4, 1 and 3. So the number of searches a scan starts depends on the order in which it takes the vertices: scanning our six vertices from 0 up to 5 starts two searches, and scanning them from 5 down to 0 starts four.
Coloring a graph with two colors
A search can also give each vertex a value that depends on the vertex it was reached from. One example is splitting the vertices of an undirected graph into two groups so that every edge runs from one group to the other. A graph that can be split like this is called bipartite. It is easier to think of the groups as two colors: each vertex gets color 0 or color 1, and the two ends of an edge must have different colors.
You get an undirected graph with vertices numbered 0 to as adjacency lists: graph[u] lists the neighbors of . Return true if the graph is bipartite, which means that its vertices can be split into two groups so that every edge joins a vertex of one group to a vertex of the other.
Constraints
- No vertex is its own neighbor, and no neighbor is listed twice
- If
graph[u]contains , thengraph[v]contains - The graph need not be connected
Sample 1 · Input
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output
false
Sample 2 · Input
graph = [[1,3],[0,2],[1,3],[0,2]]
Output
true
In the second sample the four vertices form a ring, and the colors 0, 1, 0, 1 around the ring satisfy every edge. In the first sample vertices 0, 1 and 2 form a triangle. Vertices 1 and 2 both need the color that vertex 0 does not have, and there is an edge between them, so no coloring works.
In the triangle, the color of vertex 0 decided the colors of its neighbors. The same holds in any graph: once a vertex has a color, each of its neighbors must get the other one. So we give the starting vertex color 0 and let the search hand the colors on. When it reads an edge from to a neighbor that has no color, it gives the color that does not have. When has a color already, it compares the two colors, and if they are equal the graph is not bipartite. If the search ends without finding such an edge, the coloring is valid.
When a comparison fails, no other coloring would have worked, because the search had no choice anywhere. Within a component, the color of the start forces every other color, one edge at a time, and starting with color 1 would only swap the two colors on every vertex. A graph that contains a ring with an odd number of vertices, like the triangle, cannot pass: around a ring the colors must alternate, and after an odd number of edges the walk is back at its first vertex with the wrong color.
The loop with a color for each vertex
The graph can have several components, so the program starts a search at every vertex that has no color, as the scan for components did. The array color holds for a vertex without a color, which makes it the mark as well.
def is_bipartite(graph):
color = [-1] * len(graph)
for start in range(len(graph)):
if color[start] != -1:
continue
color[start] = 0
stack = [start]
while stack:
u = stack.pop()
for v in graph[u]:
if color[v] == -1:
color[v] = 1 - color[u]
stack.append(v)
elif color[v] == color[u]:
return False
return True
print(is_bipartite([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]))
print(is_bipartite([[1, 3], [0, 2], [1, 3], [0, 2]]))The program prints False for the first sample and True for the second. 1 - color[u] is the color that does not have.
On the first sample the program colors the vertices as in the figure and takes vertex 3 off the stack first. Its neighbor 2 has color 1 as well, so the function returns false.
Finding a cycle in an undirected graph
The ring of the second two-coloring sample and the triangle of the first are examples of a cycle, a closed loop of vertices. In an undirected graph a cycle starts at a vertex, passes through at least two other vertices, all of them different, and ends with an edge back to where it started. The next problem asks for one:
A country has cities numbered 1 to and two-way roads. Find a round trip that starts in some city, passes through at least two other cities, all different, and returns to the start. Print IMPOSSIBLE if there is none.
The input is laid out as in Building Roads. Print the number of cities on the trip, counting the start at both ends, then the cities in order. Any valid trip is accepted.
Constraints
- A road joins two different cities, and no two roads join the same pair
Sample · Input
5 6 1 3 1 2 5 3 1 5 2 4 4 5
Output
4 3 5 1 3
In the sample, roads join cities 1 and 3, cities 3 and 5, and cities 5 and 1, so 1, 3, 5, 1 is a round trip. The sample output is the same trip, started at city 3.
In a tree, a search that skips the node it came from never meets a marked node: the search has already reached that node along one path, and meeting it from another node would give it a second path, which a tree does not have. A graph with a cycle has such second paths, and that is how the search finds a cycle.
The vertex from which the search entered is the parent of , and the search passes over the parent in the adjacency list of , since that entry is the edge it has just walked along, read from the other end. If any other neighbor of is already marked, the graph has a cycle.
In a search that follows one path, like the recursive one, is active at that moment, so it lies on the path from the start to . The Deeper read at the end of this part shows why it cannot be finished. The part of the path from to , closed by the edge from back to , is the cycle, and it has at least three vertices because is not the parent of . Following parents from until we reach lists its vertices.
On the sample the search starts at city 1, goes to city 3, the first city in the list of 1, and from there to city 5:
parent are the cities, and the highlighted entries are the parents of cities 3 and 5. A 0 means no parent: city 1 is the start, and cities 2 and 4 have not been entered.The list of city 5 is 3, 1, 4. City 3 is the parent of 5 and is passed over. City 1 is marked and is not the parent of 5, so there is a cycle. Following parents from 5 gives 5, 3, 1, and with city 5 added at the end the round trip is 5, 3, 1, 5.
Deeper read: why the marked neighbor is on the path
Take a search that follows one path, as the recursive one does. It is in the visit to and reads a neighbor that is marked and is not the parent of . The search stops the first time this happens, so it has not happened before. We show that cannot be finished.
Suppose it were. A finished visit to has read every entry in the list of , including the entry for , and when it read that entry, was either unseen or marked. If was unseen, the visit to entered , which would make the parent of . But is not the parent of .
If was marked, the visit to met a marked neighbor, and the search went on, so must have been the parent of . Then the search entered by reading the entry for in the list of . Round Trip has no two roads between the same pair of cities, so the list of has one entry for , and the search reads each entry once. It read that entry when it entered , so it cannot be reading it now. Both cases are impossible, so cannot be finished, and since it is marked, it is active.
A search that keeps its path
The program for Round Trip has to follow parents along the path of the search. The stack of the earlier loop is no help, because the vertices on it are waiting to be read and are not a path. A recursive function is risky as well: Round Trip allows a line of cities, which the search follows visits deep.
That is 100 times the number of nested calls that Python allows by default.
So the program keeps the path itself, as the call stack did. The list path holds the active vertices, and position[u] counts the entries of the adjacency list of that have been read. A waiting call keeps the same count as its place in its loop over the neighbors.
Each turn of the loop works on the vertex at the end of the path. If has an entry left, the loop reads it and then enters the neighbor, passes over the parent, or reports the cycle. If not, is finished and comes off the path. The outer loop starts a search at every city that is not marked, since the map can have several components.
def round_trip(n, graph):
visited = [False] * (n + 1)
parent = [0] * (n + 1)
position = [0] * (n + 1) # entries of graph[u] that have been read
for start in range(1, n + 1):
if visited[start]:
continue
visited[start] = True
path = [start]
while path:
u = path[-1]
if position[u] == len(graph[u]):
path.pop() # u is finished
continue
v = graph[u][position[u]]
position[u] += 1
if not visited[v]:
visited[v] = True
parent[v] = u
path.append(v)
elif v != parent[u]: # marked, and not where we came from
trip = [u]
while trip[-1] != v:
trip.append(parent[trip[-1]])
trip.append(u)
return trip
return []
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
graph = [[] for _ in range(n + 1)]
for i in range(m):
a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
graph[a].append(b)
graph[b].append(a)
trip = round_trip(n, graph)
if trip:
print(len(trip))
print(*trip)
else:
print("IMPOSSIBLE")On the sample the program prints 4 and then 5 3 1 5, the trip we found by hand.
When a problem only asks whether a cycle exists, counting can answer it. A component with vertices and no cycle is a tree, which has exactly edges, one from each vertex other than the root to its parent. So a component with or more edges contains a cycle. A component with edges has none. If it had a cycle, removing one edge of the cycle would leave it connected with edges, but connecting vertices takes at least edges, since each edge joins at most two pieces into one. The number of edges of a component is half the total length of its adjacency lists.
Cycles in directed graphs
In a directed graph a marked neighbor that is not the parent does not prove a cycle. On our six vertices the edge 2 → 4 led to such a neighbor, and no cycle passes through vertex 2, because no path leads back to it. Vertex 4 was finished when that edge was read. The edge 4 → 1 did close a cycle, 1 → 3 → 4 → 1, and vertex 1 was active when it was read.
So a directed graph needs another test: it has a cycle exactly when the search, started from every unmarked vertex in turn as in the scan for components, reads an edge to an active vertex. An edge like that always closes a cycle, because the active vertices form the path of the search. When the visit to reads an edge u → v and is active, lies on the path that leads to , and the edge leads from back to .
That every cycle is caught this way is proved on the Cycle detection page of the Topological sort lesson. Find Eventual Safe States, the last problem in this lesson's list, needs that test and is best tried after that page.
DFS or BFS
Reachability, components and two-coloring come out the same with either search. When a problem asks for the fewest steps, only BFS is right, because a depth-first search reaches a vertex along whichever path it happens to be on: on our six vertices it reached vertex 4 along three edges, and the path through vertex 2 has two. Depth-first search is needed when the answer depends on the path the search is on, as it does in Round Trip.
Common mistakes in depth-first search
Marking a vertex after the loop over its neighbors.
- Where it breaks
- In the second sample of Keys and Rooms the search goes from room 0 to room 1 to room 3, and room 3 holds a key to room 0. Room 0 is still unmarked, so it is visited again, and the calls go around the three rooms until the program is stopped, with a
RecursionErrorin Python and a crash in C++. - The fix
- Mark the vertex first, before any of its neighbors is read.
Searching from vertex 0 only, on a graph that can have several components.
- Where it breaks
- For the graph
[[1], [0], [3, 4], [2, 4], [2, 3]], two-coloring from vertex 0 colors vertices 0 and 1 and stops. Vertices 2, 3 and 4 form a triangle that is never read, and the function returns true where the answer is false. - The fix
- Start a search at every vertex that is still unmarked, as the scan for components does.
Counting the edge back to the parent as a cycle.
- Where it breaks
- On a map of two cities joined by one road, the search goes from city 1 to city 2, reads city 1 in the list of city 2, and reports the trip
2 1 2. The right answer isIMPOSSIBLE. - The fix
- Record the parent of each vertex and pass over that one entry of its list.
Recall An undirected graph has the edges 1-2, 1-3, 2-3 and 3-4, given in that order. The round-trip program starts its search at vertex 1. Which vertices does it enter, and what trip does it report?
The adjacency list of vertex 1 is 2, 3. The list of vertex 2 is 1, 3, the list of vertex 3 is 1, 2, 4, and the list of vertex 4 is 3. The search enters 1, then 2, then 3. The first entry in the list of 3 is vertex 1, which is marked and is not the parent of 3, so the search stops there. Following parents from 3 gives 3, 2, 1, and the trip is 3, 2, 1, 3. Vertex 4 is never entered, because the cycle is found before the search reads that far in the list of 3.
Further reading
- USACO Guide, SilverGraph Traversal(opens in a new tab)
Building Roads and a two-coloring problem solved with DFS and again with BFS, a section on deep recursion, and practice problems for both.
- Antti Laaksonen (PDF)Competitive Programmer’s Handbook(opens in a new tab)
Chapter 12 searches one graph step by step, then uses DFS to test connectivity, find cycles and check bipartiteness in undirected graphs.
- cp-algorithmsDepth First Search(opens in a new tab)
Entry and exit times, white, grey and black vertices, and the classification of edges into tree, back, forward and cross edges, with a list of applications.
- cp-algorithmsChecking a graph for acyclicity and finding a cycle in O(M)(opens in a new tab)
Three colors find a directed cycle and parent pointers print it; the undirected version skips the edge back to the parent, as Round Trip does.
- MIT 6.006 lecture notes, Spring 2020Lecture 10: Depth-First Search(opens in a new tab)
Proves DFS correct and linear, then restarts it from every vertex for connectivity, topological sort and cycle detection.
- OI Wiki, in ChineseDFS(图论)(opens in a new tab)
Stack and recursive implementations, the DFS order and the bracket sequence of entry and exit events.
- Jeff Erickson (PDF)Algorithms, Chapter 6: Depth-first search(opens in a new tab)
Numbers each vertex when its call starts and ends, sorts the edges of a directed graph by the states of their ends, tests for a cycle by looking for an edge to an active vertex, and reverses the finishing order to sort a directed acyclic graph topologically. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
- Pat MorinOpen Data Structures, Chapter 12: Graphs(opens in a new tab)
Section 12.3 describes depth-first search as breadth-first search with a stack in place of the queue, colors the vertices white, grey and black, and uses the colors to find a cycle. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code.