Topological sort

[darwinrlo]

Repl

When there is a partial ordering, topological sort is likely the way to go.

Create a list of the vertices such that vertices do not appear before their ancestors.

Can we make progress on the problem by repeatedly removing the leaf vertices?

[darwinrlo]

Version v0.1

• Create an instance of a doubly-linked list. Call it X.
• Visit the graph in breadth-first order, adding each node to the front of X.
• Iterate through X, marking each node as added. If during the traversal we encounter a node that has already been added, remove that instance from X.

[darwinrlo]

During a traversal of a graph, when you encounter a node again it doesn't necessarily mean there's a cycle. Perhaps it is a descendant of two different nodes.

[darwinrlo]

Setup

• Create an instance of a queue (implemented using a deque). Call it sources.
• Create a hash table for storing vertices and their in-degrees. Call it inDegree.
• Create a hash table for storing adjacency lists. Call it graph.
• Iterate through the vertices, for each one creating an entry in inDegree (with value set to 0) and graph (with the value set to an empty list).
• Iterate through the edges, inserting head vertices into the adjacency lists for the tail vertices and incrementing the in-degree of head vertices in inDegree.

[darwinrlo]

Processing a Source Vertex

• Repeat until the source vertex queue is empty:
  • Remove a source vertex from the queue.
  • Remove the vertex and outgoing edges from the graph. This means deleting the entries for the vertex from graph and inDegree.
  • For the head vertex of each outgoing edge, decrease the in-degree in inDegree. Attribute this work to the outgoing edge as opposed to, say, the source vertex or the head vertex.

[darwinrlo]

Cycles

If there's a cycle, it means that there are vertices whose in-degrees will never reach 0. Hence, they will not be added to the sources queue, and hence, these vertices are never added to the result. So we can check the result list to see if it's smaller than the number of vertices.

[darwinrlo]

Time Complexity

• During setup, the algorithm iterates over the edges and vertices to build the adjacency lists and in-degree table. An entry in both these tables are created for each vertex, and there is O(1) worth of updates to these tables for each edge. In total, this represents O(V + E) work.
• Each vertex is added to the queue at most once. It is removed from the queue and processed at most once. Processing entails adding the vertex to the result. It also entails decrementing in-degrees of vertices and possibly adding other vertices to the queue, but we'll attribute this work to the edges as opposed to the vertices. What's left over is O(1) work per vertex.
• For each edge, the in-degree of the head is decremented at most once. Possibly, the head is added to. These represent O(1) work, so there is O(1) work per edge.
• So the total running time is O(V + E).

Space Complexity

• inDegree takes O(V) space.
• sources takes O(V) space.
• graph takes O(V + E) space.
• The total space complexity is O(V + E).

[darwinrlo]

Test Cases

Edge Cases

• No vertices
• One vertex, no edges

Non-Edge

• No vertices without incoming edges (the whole thing is a cycle)
• Two sources with an edge between them
• There is a vertex without incoming edges that can be used as a source vertex, but the graph has a cycle.

[darwinrlo]

This problem could be presented in two different ways: (u, v) could imply u must come before v or it could imply that v must come before u.

[darwinrlo]

O(V + E). It's linear in the number of vertices and edges. Usually, you can't do better than linear on a graph problem like this, especially one that involves touching each edge and vertex once.

Note that, at minimum, each vertex must be added to the result list. So it is impossible to do better than O(V).

[darwinrlo]

All Topological Orderings

Time Complexity

• Vertices from the same level in the dag can go into the ordering in any order w.r.t. each other.

• It doesn't matter in what order vertices from the same level are added to the ordering, and vertices can be added to the ordering level-by-level. But there are more possible ways to construct orderings.

  • Vertices in outer levels may appear before vertices in inner levels as long as they are not descendants. This includes vertices that are descendants of sibling vertices, that is, vertices on the same level.
  • Vertices in inner levels may appear after vertices in outer levels if they are ancestors of the outer vertices.

• It is possible that the best we can do is say that this takes O(V!) time and O(V!) space.

• In the generation of a single ordering, each vertex is inserted into the queue exactly once and each edge is processed exactly once (as part of processing its source vertex). There are V! possible orderings -- admittedly not all of which are going to be valid orderings. Nonetheless, the worst-case time complexity is O(V! x E).

Space Complexity

• There is only one list for the ordering. It is shared by each root-leaf path of the call tree. It never gets bigger than V.
• Each recursive call adds one vertex to the ordering. Hence, the recursion depth does not exceed V.
• A copy of the queue is created for each recursive call. On each path through the call tree, each vertex is added to the queue once. Hence, the queue never gets bigger than V.
• So the queue and ordering require O(V) space.
• To store the input into an adjacency-list graph, it takes O(V + E).
• It takes O(V!) space to store the different orderings. So you could say the total space complexity is O(V! + E).

[darwinrlo]

Alien Dictionary

Building the graph

• Iterate through the list of words, which is in dictionary (lexicographic) order. For each word, compare it with the next word. The first position in which the characters in the two words are different -- which could simply be the first character -- gives a rule: The character in the earlier word must appear before the character in the later word.

Complexity

• A rule is an ordering on characters. Characters are represented by vertices. Rules are represented by edges.
• Each pair of adjacent words contributes at most one rule. If N is the number of vertices, then the number of edges is O(N).
• So the time and space complexity is O(V + E), or just a bit better, O(V + N).

[darwinrlo]

Sequence Reconstruction

LeetCode

• Each pair of adjacent numbers in a subsequence gives rise to a rule, which is represented as an edge.
• After constructing the directed graph, return false if at any point there is more than one source vertex. When there is more than one source vertex, either of these may be added to the result without violating an ordering relationship. This was the key insight and I was able to get it pretty quickly.

[darwinrlo]

Minimum Height Tree

The height of a tree is dominated by the maximum root-leaf path length. So we have to focus on making the maximum root-leaf path length as small as possible.

There might be several, but consider the case in which there is only one path through the graph with the maximum length. If we choose a vertex not on the path to be the tree root, then the path will be present in the tree in its entirety ー along with some additional vertices, which would most certainly make the root-leaf path longer than it can be. So we have to choose a vertex on the longest path to be the root.

Choosing a vertex on the longest path will break up the path into two root-leaf paths. To get two root-leaf paths that are as short as possible, we need to choose the middle vertex, or if the path is of even length, one of the two middle vertices.

In regard to graphs in which more than one path has the maximum length, I will make the following claim: If there are two paths through the graph with the maximum length, then they have the same middle vertex, or if the length is even, two middle vertices. If two paths have the same length and have a different middle vertex, or if the path is even, two middle vertices, then these paths do not have the maximum length. This will be expanded upon in a future draft.

Implementation

A leaf vertex is most definitely not going to be the tree root of a minimum height tree. If you simply select its adjacent vertex as a tree root, you've already reduced the tree height by 1. So remove leaf vertices from the graph. Once you do that, you'll have new leaf vertices and the same reasoning applies. Remove leaf vertices repeatedly until there is one vertex or two vertices with one edge between them.

Keep a count of the vertices remaining in the graph. Every time a vertex is "removed" from the graph, decrement this count. Once the number of vertices drops below 2, instead of proceeding to process the leaf vertices in the queue, just go ahead and return the remaining vertex or vertices.