Topological Sorting

Page 164

Define Topological Sorting: Explain the process of linearly ordering the vertices of a directed acyclic graph (DAG).

Define Topological Order: Describe the resulting sequence of vertices from a topological sort.

Topological sorting is a problem for directed graphs that involves arranging their vertices in a linear order. The goal is to list the vertices in such a way that for every directed edge (u, v) in the graph, the vertex 'u' appears before the vertex 'v' in the sorted list.

State the minimum condition for a valid topological sort: The graph must be a Directed Acyclic Graph (DAG).

The minimum condition for a valid topological sort is that the graph must be a Directed Acyclic Graph (DAG). Meaning it contains no directed cycles. If a graph has a directed cycle, a topological sorting cannot be performed.

• Directed Acyclic Graph (DAG): A DAG is a directed graph that contains no directed cycles. This means that it is impossible to start at a vertex and follow a sequence of directed edges to return to the same vertex.

• Sufficiency of DAG: Conversely, if a directed graph has no directed cycles (i.e., it is a DAG), a solution to the topological sorting problem is guaranteed to exist.

---

This problem is particularly useful for tasks with prerequisite restrictions, such as sequencing courses in an academic program or scheduling tasks in a project.

For example, in a scenario involving academic courses, if a student can only study "Design and Analysis of Algorithms (DAA)" after completing "Data Structures (DS)" and "Discrete Mathematics (DM)", and "Data Base Management System (DBMS)" and DAA are prerequisites for "Data Analytics (DA)", a topological order would sequence these courses appropriately.

Two main efficient algorithms are used to solve the topological sorting problem:

DFS-based Algorithm (Depth-First Search):

• Process: This method involves performing a Depth-First Search (DFS) traversal on the directed graph. During the traversal, the algorithm keeps track of the order in which vertices finish (i.e., become "dead-ends" or are "popped off the traversal stack").

• Ordering: The solution is obtained by reversing the order in which vertices are popped off the DFS stack.

• Cycle Detection: If a back edge is encountered during the DFS traversal, it indicates the presence of a directed cycle, meaning the graph is not a DAG, and topological sorting is impossible.

• Why it works: When a vertex v is popped off the stack, no vertex u with an edge from u to v can still be on the stack or have been popped off before v (otherwise, (u,v) would be a back edge, indicating a cycle). This ensures that any u that points to v will appear after v in the popped-off order, and thus before v in the reversed (topologically sorted) list.

• Efficiency: The time efficiency for the DFS-based algorithm is Θ(|V|²) when the graph is represented by an adjacency matrix, and Θ(|V| + |E|) when represented by adjacency lists, where |V| is the number of vertices and |E| is the number of edges.

Source-Removal Algorithm:

• Process: This algorithm directly implements the decrease-by-one technique. A source is defined as a vertex with no incoming edges. It repeatedly identifies and removes a source from the remaining digraph.

• Steps:

  1. Find all sources in the current graph.
  2. Select one source (arbitrarily if there are multiple).
  3. Delete this source vertex along with all edges originating from it (outgoing edges).
  4. Record the deleted vertex in the topological order.
  5. Repeat until no more vertices remain.

• Ordering: The order in which the vertices are deleted from the graph constitutes a valid topological sort.

• Cycle Detection: If at any point there are no sources in a non-empty graph, it indicates the presence of a cycle, and topological sorting is impossible. A non-empty DAG must have at least one source.

• Efficiency: An efficient implementation of this algorithm for a digraph represented by its adjacency lists can achieve a running time of O(|V| + |E|).

It is important to note that a given DAG may have several alternative topological sorting solutions.

Generating Combinatorial Objects

Page 170

Discuss the Minimal Change Method and Johnson-Trotter Algorithm for generating permutaions with examples.

Both the bottom-up minimal-change approach and the Johnson-Trotter algorithm generate permutations in a "minimal-change" fashion, where each new permutation is derived from its predecessor by swapping two adjacent elements.

Minimal Change Method for Generating Permutations

The minimal change method is an approach to generating combinatorial objects, such as permutations, by exploiting the decrease-by-one technique. The core idea is that a solution for an instance of size 'n' can be derived from the solution of a smaller instance of size 'n-1'.

• Process: To generate all 'n!' permutations of a set of 'n' elements (e.g., {1, ..., n}), the method assumes that all (n-1)! permutations of the smaller set {1, ..., n-1} have already been generated. To obtain the permutations for 'n' elements, 'n' is inserted into each of the 'n' possible positions within every permutation of 'n-1' elements. All permutations generated this way are distinct, and their total number will be 'n * (n-1)! = n!'.

• Direction of Insertion: Start by inserting 'n' into the base permutation from right to left, and then switch direction (left to right, then right to left) each time a new permutation of {1, ..., n-1} is processed.

• Example for n=3, for generating permutations of {1, 2, 3}:

  • Start: Permutation of {1} is 1.
  • Insert 2 into 1 (right to left): 12, 21.
  • Insert 3 into 12 (right to left): 123, 132, 312.
  • Insert 3 into 21 (left to right): 321, 231, 213.
  • The sequence of permutations generated for n=3 is: 123, 132, 312, 321, 231, 213.

• Minimal Change Requirement: Each new permutation can be obtained from its immediate predecessor by exchanging just two elements, which are always adjacent to each other in this method.

In problems like the Traveling Salesman Problem, if permutations are generated by a minimal-change algorithm, the length of a new tour can be computed from its predecessor's length in constant time, rather than linear time.

Johnson-Trotter Algorithm

The Johnson-Trotter algorithm is another efficient method for generating permutations that also adheres to the minimal-change requirement, but it does so directly without explicitly generating permutations of smaller sets. It relies on the concept of "mobile elements" within a permutation.

• Mobile Element: In an arrow-marked permutation, an element 'k' is considered mobile if its associated arrow points to a smaller adjacent number.
• For example, in 3→ 2← 4→ 1←, elements 3 and 4 are mobile, while 2 and 1 are not.

Algorithm Steps:

1. Initialization: Start with the first permutation by initializing all elements (1, ..., n) with left-pointing arrows (e.g., 1← 2← ... n←).

2. Iteration: Continue as long as the current permutation contains a mobile element.

3. Find Largest Mobile Element: Identify the largest mobile element, say 'k'.

4. Swap: Swap 'k' with the adjacent element that its arrow points to.

5. Reverse Directions: Reverse the direction of all elements that are larger than 'k'.

6. Add to List: Add the newly generated permutation to the list.

Johnson-Trotter Algorithm Pseudocode:

ALGORITHM JohnsonTrotter(n)
// Implements Johnson-Trotter algorithm for generating permutations
// Input: A positive integer n
// Output: A list of all permutations of {1, ..., n}

initialize the first permutation with 1← 2← ... n←

while the last permutation has a mobile element do
	find its largest mobile element k
	swap k with the adjacent element k’s arrow points to
	reverse the direction of all the elements that are larger than k
	add the new permutation to the list

Example for n=3:

1. Start: 1← 2← 3←
2. Largest mobile: 3 (points left to 2). Swap 3 and 2. Reverse direction of elements larger than 3 (none). Result: 1← 3← 2←
3. Largest mobile: 3 (points left to 1). Swap 3 and 1. Reverse direction of elements larger than 3 (none). Result: 3← 1← 2←
4. Largest mobile: 2 (points left to 1). Swap 2 and 1. Reverse direction of elements larger than 2 (3 becomes 3→). Result: 3→ 2← 1←
5. Largest mobile: 2 (points right to 3). Swap 2 and 3. Reverse direction of elements larger than 2 (none). Result: 2← 3→ 1←
6. Largest mobile: 3 (points right to 2). Swap 3 and 2. Reverse direction of elements larger than 3 (none). Result: 2← 1← 3→

The sequence of permutations generated for n=3 is: 123, 132, 312, 321, 231, 213.

Efficiency: This algorithm is one of the most efficient for generating permutations, running in time proportional to the number of permutations, i.e., in Θ(n!).

However, despite its efficiency for generation, it is still "horribly slow for all but very small values of n" due to the inherently large number of permutations.