Topological sorting

What is topological sorting?

    in graph theory, topological ordering is a linear sequence of all vertices of a directed acyclic graph (to obtain a topological ordered sequence). And the sequence must meet the following two conditions:

1. Each vertex appears only once.
2. If there is A path from vertex A to vertex B, vertex A appears in front of vertex B in the sequence.

Only directed acyclic graphs (DAG) have topological sorting, and non DAG graphs have no topological sorting.

 
 

How to sort topology?

Topology sorting steps:

1. Select a vertex without a precursor in a directed graph and output it.
2. Delete the vertex and all arcs ending in it from the graph.

   repeat the above two steps until all vertices have been output, or there are no vertices without precursors in the current graph. The latter case shows that there are rings in a directed graph.

  in the figure, if V1 and V6 have no precursors, you can choose either. Suppose that V6 is output first. After deleting V6 and arc < V6, V4 >, < V6, V5 >, only vertex V1 has no precursor. Output V1 and delete V1 and arc < V1, V2 >, < V1, V3 > and < V1, V4 >, and then V3 and V4 have no precursor. And so on, you can choose one of them to continue. The whole topology sorting process is shown in the figure above.

 
 

Topology sorting implementation

  we use the adjacency table as the storage structure of the directed graph, and add an array of vertex entry degrees in the head node. The vertex with zero penetration is the vertex without precursor. The operation of deleting the vertex and the arc with its tail can be realized by subtracting 1 from the penetration of the vertex at the arc head.

Status TopologicalSort(ALGraph G){
	//Directed graph G adopts adjacency table storage structure 
	//If G has no loop, a topological sequence of vertices of G is output and returns OK, otherwise ERROR 
	FindInDegree(G, indegree);//Calculate the penetration degree of each vertex indegree[0..vernum-1] 
	InitStack(S);
	for(i=0;i<G.vexnum;i++)//Build zero degree vertex stack S 
		if(!indegree[i])//If the entry degree is 0, enter the stack 
			Push(S, i);
	count = 0;//Count output vertices 
	while(!StackEmpty(S)){
		Pop(S, i);	printf(i, G.vertices[i].data);	count++;//Output vertex i and count 
		for(p=G.vertices[i].firstarc; p; p=p->nextarc){
			k = p->adjvex;//The penetration of each adjacent point of vertex i is reduced by 1 
			if(!(--indegree[k]))//If the input degree is reduced to 0, it will be stacked 
				Push(S, k);
		}
	}
	if(count<G.vexnum)//The directed graph has a loop 
		return ERROR;
	else
		return OK;
}

   for a digraph with n vertices and e arcs, the time complexity O(e) for finding the penetration of each vertex is established; The time complexity of building zero input vertex stack is O(n); In the process of topological sorting, if the directed graph is acyclic, each vertex enters and exits the stack once. The operation of entering degree minus 1 is executed e times in the WHILE statement. Therefore, the total time complexity is O(n+e).
   when there is no ring in the directed graph, the depth first traversal can also be used for topological sorting. Because there is no ring in the graph, when the depth first search traversal starts from a point in the graph, the vertex that exits the DFS function first, that is, the vertex with zero degree, is the last vertex in the topological ordered sequence. Thus, the vertex sequence recorded in the order of exiting the DFS function (like the vertex sequence in the finished array when calculating the strongly connected component) is the reverse topological ordered sequence.
 
 

critical path

What is the critical path?

AOE network: in a weighted directed graph representing the project, the vertex represents the event (such as V1), the directed edge represents the activity (such as < V1, V2 > = A1), and the weight on the edge represents the duration of the activity. Such a directed graph is called the network of activities represented by edges.
Source point: in AOE network, vertices without edges are called source points; Such as vertex V1.
End point: in AOE network, vertices without edges are called end points; Such as vertex V9.
Nature of AOE network:

1. Only when the activities entering a vertex have ended, the event represented by the vertex occurs; For example, when a V5 event occurs, both a4 and a5 activities need to end.
2. Only after the event represented by a vertex occurs, the activities starting from the vertex begin; For example, activities a7 and a8 cannot start until the V5 event ends.
   

   in AOE network, all activities can reach the end point only after they are completed. Therefore, the time (i.e. the shortest construction period) required to complete the whole project should be the maximum path length from the source point to the end point. The path with the maximum path length is called critical path. The activities on the critical path are called critical activities.
  assuming that the starting point is V1, the longest path length from V1 to Vi is called the earliest event of event Vi. This time determines the earliest start time of all activities represented by arcs with Vi as tail. We use e(i) to represent the earliest start time of activity ai. You can also define the latest start time l(i) of an activity, which is the time when the activity ai must start at the latest without delaying the completion of the whole process. The difference l(i)-e(i) means the time margin to complete the activity ai. We call the activity of l(i)=e(i) key activity.

Ask for time from critical paths and resources from non critical paths.

1. From front to back, calculate the duration and the earliest start time of each activity;
2. From back to front, push back the latest start time of each activity.
3. Critical path: earliest start time = latest start time

 
 

How to find the critical path?

ve(j): earliest occurrence time
vl(j): latest occurrence time

1. Input e arcs < J, k > to establish the storage structure of AOE network;
2. Starting from the source point v0, let ve[0]=0, and calculate the earliest discovery time ve[i] (1 ≤ I ≤ n-1) of other vertices according to topological order. If the number of vertices in the topological ordered sequence is less than the number of vertices n in the network, it indicates that there are rings in the network, the critical path cannot be obtained, and the algorithm terminates; Otherwise, proceed to step (3).
3. Starting from the sink vn, let vl[n-1]=ve[n-1], find the latest occurrence time vl[i] (n-2 ≥ I ≥ 2) of other vertices according to the inverse topological order;
4. According to the ve and vl values of each vertex, calculate the earliest start time e(s) and the latest start time l(s) of each arc s. If an arc satisfies the condition e(s)=l(s), it is a key activity.

  
   according to the above algorithm, the ve value of each vertex is calculated in the process of topological sorting. The topological sorting algorithm needs to be modified as follows:

1. Set the initial value before topological sorting, so that ve[i]=0 (0 ≤ I ≤ n-1);
2. Add an operation to calculate the earliest occurrence time of the direct successor vk of vj: if ve [J] + DUT (< J, k >) > ve [k], then ve [k] = ve [J] + DUT (< J, k >);
3. In order to calculate the vl value of each vertex in the order of the inverse topological ordered sequence, it is necessary to record the topological ordered sequence obtained in the process of topological sorting. This requires adding a stack in the topological sorting algorithm to record the topological ordered sequence. After calculating the ve value of each vertex, the inverse topological ordered sequence will be from the top of the stack to the bottom of the stack.

 
 

Critical path implementation

Overridden topology sort code:

Status TopologicalOrder(ALGraph G, Stack &T){
	//Digraph G uses adjacency table storage structure to find the earliest occurrence time ve (global variable) of each vertex event 
	//T is the topological sequence vertex stack, and S is the zero in degree vertex stack 
	//If G has no loop, use stack T to return a topological sequence of G, and the function value is OK, otherwise ERROR 
	FindInDegree(G, indegree);//Calculate the penetration degree of each vertex indegree[0..vernum-1] 
	InitStack(S);//Build zero degree vertex stack S 
	for(i=0;i<G.vexnum;i++)//Build zero degree vertex stack S 
		if(!indegree[i])//If the entry degree is 0, enter the stack 
			Push(S, i);
	InitStack(T);	count = 0;	ve[0..G.vexnum-1] = 0;//initialization 
	while(!StackEmpty(S)){
		Pop(S, j);	Push(T, j);	count++;//j vertex into T stack and count 
		for(p=G.vertices[j].firstarc; p; p=p->nextarc){
			k = p->adjvex;//Subtract 1 from the penetration of each adjacent point of vertex j 
			if(--indegree[k] == 0)//If the input degree is reduced to 0, it will be stacked 
				Push(S, k);
			if(ve[j]+ *(p->info)>ve[k])
				ve[k] = ve[j] + *(p->info);
		}
	}
	if(count < G.vexnum)//The directed graph has a loop 
		return ERROR;
	else
		return OK;
} 

Critical path algorithm:

Status CriticalPath(ALGraph G){
	//G is a directed graph, which outputs the key activities of G 
	if(!TopologicalOrder(G, T))
		return ERROR;
	vl[0..G.vexnum-1] = ve[G.vexnum-1];//Initializes the latest occurrence of a vertex event 
	while(!StackEmpty(T)){//Find the vl value of each vertex in topological reverse order 
		for(Pop(T, j),p=G.vertices[j].firstarc; p; p=p->nextarc){
			k = p->adjvex;	dut = *(p->info);
			if(vl[k]-dut < vl[j])
				vl[j] = vl[k]-dut;
		}
	}
	for(j=0;j<G.vexnum;j++){//Seeking ee, el and key activities 
		for(p=G.vertices[j].firstarc; p; p=p->nextarc){
			k = p->adjvex;	dut = *(p->info);
			ee = ve[j];	el = vl[k]-dut;
			tag = (ee==el)?'*':'';
			printf(j, k, dut, ee, el, tag);//Output key activities 
		}
	}
} 

   the time complexity of the above two algorithms is O(n+e), and the time complexity of calculating the earliest start time and the latest start time of the arc activity is O(e), so the total time complexity of finding the critical path is O(n+e).
 
 

Example of critical path finding process

The key activities in the figure above are A1, a4, a7, a8, a10 and a11. They constitute two critical paths: (V1, V2, V5, V7, V9) and (V1, V2, V5, V8, V9).
  practice has proved that it is very useful to estimate the completion time of some projects with AOE network. It is effective to improve the speed of key activities only without changing the critical path of the network. If there are several critical paths in the network, only increasing the speed of key activities on one critical path can not shorten the construction period of the whole project, but must increase the speed of activities on several critical paths at the same time.