Topological sorting and graphical display of critical path

Resource download address ：https://download.csdn.net/download/sheziqiong/85883662
Resource download address ：https://download.csdn.net/download/sheziqiong/85883662

Algorithm implementation design description

subject

Given a directed graph , complete ：

1. Establish and display its adjacent linked list ;
2. Sort the graph topologically , Display the results of topology sorting , And display the entry field at any time The change of ;
3. Give its critical path （ requirement ： It shows that Ve,Vl,E,L,L-E Result ）.

software function

First , The primary function of software is to accept the input of a directed graph , After that, the functions of adjacency list display, topology sorting and critical path display can be carried out .

As shown in the figure , The program can input nodes first , Then input a directed graph in the form of edges .

after , The adjacency list can be displayed in the form of animation , The general implementation method is to traverse the adjacent linked list , And the information of corresponding nodes and edges is stored in the graphic display configuration item [1] among , Display .

secondly , The program can carry out topological sorting according to the given adjacent linked list , And the topological sorting process can be displayed in the form of animation . The specific implementation method is to load the sorting results of each round into the animation display configuration item while sorting the topology , And then display it , In the middle of each round of sorting, a delay is set , Make sure you can animate , The delay of animation can be determined by external input .

Last , The program can also display the critical path of the input graph , And display the Ve,Vl And all sides （ Activities ） Of L and E Value . The specific implementation method is also to implement the critical path algorithm for the input adjacency matrix , Calculate the earliest start time and the latest start time of each vertex , Then calculate the earliest and latest start time on each side , And calculate the critical path , And the relevant information is stored in the configuration item of image display , So as to complete the display of the critical path .

design idea

The whole algorithm implementation problem is actually a relatively complete implementation idea according to the order of the problem .

The first is to read the adjacency list , Determine the number and name of nodes according to the given node information , Open up storage space . Then read the information of the side , For each given edge , Find its source , Add corresponding meeting points and edge weights to the subsequent chain structure , Complete the construction of adjacency list .

The process of topological sorting , The first is to create an array that stores the in degrees of each node , And initialize its depth to 0. Then traverse the entire adjacency table , For the meeting point appearing on each side , All of them should be put into the degree accordingly +1, Get the penetration of each node . Traverse the entry table , Find all the entrances for 0 The node of , Add the node name to the stack .

Because topological sorting will remove a node from the original graph every time , Therefore, the number of complete topological sorting must be fixed , Equal to the number of nodes in the graph . When sorting topology for the first time , There should be an initial entry of 0 The node of , Then pop up the top element , However, the entry of other nodes referred to by this element is reduced by one , And monitor the change of penetration , If the penetration of this node becomes zero , Then add this node to the stack , Doing so ensures that finding other degrees of penetration is 0 The point of does not incur additional overhead . Then repeat this operation for each cycle , You can complete the whole topology sorting process . among , If you are sorting a topology , Found that the stack is empty , In the last round of sorting, there was no discrepancy of 0 The node of , It means that the graph cannot produce effective topological sorting , And then jump out of the loop , Pop up the error display box .[2]

After topological sorting , What needs to be implemented is the critical path algorithm . The critical path is simply a positive topological sort and an inverse topological sort , Calculate the earliest occurrence time of each vertex while sorting the positive topology , Then calculate the latest occurrence time of each vertex by inverse topological sorting . Then traverse the whole graph , Calculate each edge according to the node information （ Activities of the ） Earliest occurrence time and latest occurrence time , And determine whether this activity is a key activity , And the calculated information is stored in the graphic display configuration item , Display .[3]

Logical structure and physical structure

Logical structure ：

When storing graphs , The logical structure adopted is graphic structure , The graph is a directed graph , Each node may have multiple predecessor nodes and multiple successor nodes , It is a many to many graphic structure .

In topological sorting , The stack is used to store all entries as 0 The node of , The start node and the end node of the stack are unique , Each node has and has only one precursor node , There is only one successor node , It's a linear structure .

Store the degree relationship of each node in topology sorting , And the earliest and latest occurrence time of each point and each side stored in the critical path , It uses a set structure , There is no clear logical relationship between nodes , Just to reflect the relationship between each node and its corresponding value .

Physical structure ：

For the storage of adjacency matrix , First, the hash storage structure is used , The mapping from the node name to the node chain pointed to is formed . Then, all the nodes pointed to by a node use the chain storage structure , It facilitates frequent insertion and deletion .

The storage penetration is 0 Node stack , Because insertion and deletion operations occur frequently , And we only care about the tail nodes , Therefore, the chain storage structure is used to realize .

For the corresponding relationship between storage nodes and their degrees, as well as the data structure of nodes and edges and the earliest and latest occurrence time , Because we only care about the corresponding value , Therefore, the hash storage structure is used for storage .[4]

Development platform

Development platform ：

Electron 8.0.3 GitHub Released cross platform desktop application development tools , Support Web Technology development desktop

application , It is based on C++ Developed ,GUI The core comes from Chrome, and JavaScript Engine USES v8.[5]

Third party Library ：

ECharts A use JavaScript Open source visual Library of implementation , It can run smoothly in PC And mobile devices , Compatible with most current browsers （IE8/9/10/11,Chrome,Firefox,Safari etc. ）, The bottom layer relies on lightweight vector graphics library ZRender, Provide intuitive , Rich interaction , Highly customizable data visualization chart .[6]

jQuery A fast 、 concise JavaScript frame . jQuery Set package JavaScript Common function codes , Provides a simple JavaScript Design patterns , Optimize HTML The document operation 、 Event handling 、 Animation design and Ajax Interaction .[7]

The running environment of the software ：Windows10

Analysis and description of the operation results of the system

Debugging and development process ： The first is to carefully read and think about the topic , I have a general idea of the whole algorithm flow and data structure design . Then it is to search relevant databases and relevant materials , Development . Because the project is based on Electron Development , Therefore, the development process of the whole project is actually front-end development .

Debugging tools use Electron Browser like debugging console integrated in .

The running results show that ： First, you can open the program to see the input interface , You can input nodes and edges . After the program is opened, there is a default preset value , Of course, you can also re-enter and adjust by yourself .

Click on “ Adjacency list ” Button , Can display the adjacent linked list of input graphics ：

Click on “ A topological sort ” Button , You can display an animation of the topological sorting of a given graph

Click on “ critical path ” After the button , The critical path of the current graph will be displayed ：

When making wrong input , Error prompts will be displayed when performing operations such as adjacency list and topological sorting critical path

When the input graph does not meet the topological sorting conditions , That is, when it forms a loop , It will report an error and prompt that topology sorting or critical path generation cannot be performed .

Operation instructions

After opening the program , Will automatically enter the input interface , The contents that can be input mainly include the number of nodes in the graph 、 Number of each node 、 The number of sides 、 The situation of each edge and the display delay of topology sorting animation .

The input rules of each input box are as follows ：

1. The number of input nodes should be an Arabic number .

2. The number of input nodes should be consistent with the number of input nodes , Too few input nodes may cause errors , If there are too many input nodes, subsequent nodes will not be read . Each node number is separated by a space , Node numbers support arbitrary strings , Not limited to numbers .

3. The number of input edges should be an Arabic number .

4. When inputting information about edges , Input the information of one side in each line , The form of each side is as follows ：u v w,u Represents the node name of the source point ,v Represents the node name of the sink ,w Represents the weight of an edge , Three data should be separated by spaces .u v It needs to be the name that has appeared in the entered node name , The number of edges needs to be the same as the number entered above .

When you're done typing , You can click the corresponding button to display the corresponding animation .

Resource download address ：https://download.csdn.net/download/sheziqiong/85883662
Resource download address ：https://download.csdn.net/download/sheziqiong/85883662