Topological ordering in a Graph

Graph Theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
Introduction To Graph Theory …FTC 👈 👈 😉

A topological ordering, or a topological sort, orders the vertices in a directed acyclic graph on a line, i.e. in a list, such that all directed edges go from left to right. Such an ordering cannot exist if the graph contains a directed cycle because there is no way that you can keep going right on a line and still return back to where you started from.

Formally, in a graph G = (V, E) , then a linear ordering of all its vertices is such that if G contains an edge (u, v) ∈ E from vertex u to vertex v then u precedes v in the ordering.

It is important to note that each DAG has at least one topological sort.

There are known algorithms for constructing a topological ordering of any DAG in linear time, one example is:

1. Call depth_first_search(G) to compute finishing times v.f for each vertex v
2. As each vertex is finished, insert it into the front of a linked list
3. the linked list of vertices, as it is now sorted.

A topological sort can be performed in (V + E) time, since the depth-first search algorithm takes (V + E) time and it takes Ω(1) (constant time) to insert each of |V| vertices into the front of a linked list.

Many applications use directed acyclic graphs to indicate precedences among events. We use topological sorting so that we get an ordering to process each vertex before any of its successors.

Vertices in a graph may represent tasks to be performed and the edges may represent constraints that one task must be performed before another; a topological ordering is a valid sequence to perform the tasks set of tasks described in V .

Problem instance and its solution

Let a vertice v describe a Task(hours_to_complete: int) , i. e. Task(4) describes a Task that takes 4 hours to complete, and an edge e describe a Cooldown(hours: int) such that Cooldown(3) describes a duration of time to cool down after a completed task.

Let our graph be called dag (since it is a directed acyclic graph), and let it contain 5 vertices:

A <- dag.add_vertex(Task(4));
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3));
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));

where we connect the vertices with directed edges such that the graph is acyclic,

dag.add_edge( A, B, Cooldown(2));
dag.add_edge( A, C, Cooldown(2));
dag.add_edge( B, D, Cooldown(1));
dag.add_edge( C, E, Cooldown(1));
dag.add_edge( C, D, Cooldown(1));
dag.add_edge( D, E, Cooldown(3));

then there are three possible topological orderings between A and E ,

1. A -> B -> D -> E
2. A -> C -> D -> E
3. A -> C -> E

To store a graph, two methods are common:

• Adjacency Matrix
• Adjacency List

An adjacency matrix is a square matrix used to represent a finite graph. Adjacency Matrix (Storing Graphs)  👈 👈 😉 

An Adjacency list is a collection of unordered lists used to represent a finite graph. Storing Graphs (Adjacency List)  👈 👈 😉 

---

Morae Q!

1. Convert from binary number to decimal number.
2. Swap two numbers by using division and multiplication.
3. Compute foot and inches into centimetres.
4. Concatenate Strings.
5. Convert lowercase letters to uppercase letters.
6. Compute the sum of all the digits of N.
7. Compute the area of the pentagon.
8.  Get input using scanner.
9. Find the distance between two points (x1,y1) and (x2,y2).
10. Finding patterns in a file using frep and egrep .
11. Detecting a cycle in a directed graph using Depth First Traversal.
12. Topological ordering in a Graph.
13. Storing graphs using adjacency list.
14. Introduction to graph theory.
15. Graph Adjacency Matrix pseudo code.
16. Adjacency Matrix for storing graphs.
17. Dijkstra’s shortest path algorithm .
18. Breadth first search (BFS) Algorithm.
19. Find the multiple of given number in the list of integers.
20. Finding patterns in files using grep .

---