Skip to content

Program for selecting vertices that have a sign of implicit transition

License

Notifications You must be signed in to change notification settings

jackshendrikov/implicit-transition-graph

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Dynamic and Static Planning

Write a program that implements one of the algorithms of dynamic or static planning.

📝 Task

Develop a program for selecting vertices that have a sign of implicit transition (the number of vertices is not less than 30).

📙 Description

The source information for structural analysis is a graph of the problem, presented in a tiered-parallel form. Each vertex of the original graph after analysis is marked and assigned the sign of "transition".

General algorithm for solving this problem:

  1. Identify a critical path;
  2. Cluster implicit transition vertices. This is done in order to group implicit transition vertices and thus reduce the width of the graph, and hence the number of processors.

The following graph was used to test the program part:

Main Graph

Critical path: 0 → 2 → 5 → 8 → 11 → 14 → 16 → 21 → 22 → 26 → 28 → 30

Let's check the accuracy on a graph of lower dimension:

Test Graph

Now we choose the critical path:

Test Graph (Critical Path)

Tcr = 7 + 7 + 2 = 16

Zeroing the critical path and clusterize the vertices:

Test Graph (Сlasterisation)

Tcr = 7 + 7 + 2 = 16

After clasterisation Tcr did not increase, which confirms the correctness of the work. The program found the critical path and clustered the vertices in the same way. Screenshot of the implementation are given below.

📷 Results

Result

About

Program for selecting vertices that have a sign of implicit transition

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages