Code for advanced algorithm lecture Prof. Wonjun Kim
Last Revision Date: July 21, 2022
- The error of the critical activity function was corrected
Revision Date: May 26, 2022
- Creates a function BFS_adjmatrix_path that uses BFS method to create a path from the beginning to the end of a graph.
- Creates a function Maximum_flow that takes capacity as input and finds the maximum value that can flow to the Sink.
Revision Date: May 21, 2022
- The print_adjmatrix function was changed in a way suitable for outputting a three-digit weight.
- Create a function critical_activity that takes network as input and finds the maximum time and deadline for the task and then finds the critical task.
Revision Date: May 17, 2022
- A variable to contain outdegree information was added to the network structure.
- The set_topology function now updates the outdegrees information as well.
- Creates a DFS_revtopsort function that searches the graph in the outdegree direction.
- Creates a function strong_recur that detects the part of the graph that creates the cycle.
Revision Date: May 14, 2022
- Create a function floyd that updates reachability considering weight.
- The dijkstra function was modified not to change the contents of the graph.
- A structure network was created to store the topology of the graph.
- Creates a function set_indegree that updates the preceding conditions in the net structure.
- Create a function set_topology that updates the net structure by receiving information from the graph.
- Create a function DFS_toport that explores graphs containing prerequisites in a DFS manner.
Revision Date: May 5, 2022
- Created an Input function for directed graph.
- DFS and BFS search functions were upgraded to update parent.
- DFS and BFS search functions for directed graphs were added.
- Created a warshall function for add an direct edge between reachable nodes.
- The print score function was modified to properly detect ROOT. Discussion: Can warshall function really consider all reachable nodes?
Revision Date: May 2, 2022
- Added the shortest_adjlist function to find the minimum path of the graph expressed as a list.
- Added the dijkstra function to find the minimum path of the graph expressed as a matrix.
- Renamed node header to queue header.
- Now in the check array, 0 means the root node.
- A kruskal function that performs PFS SEARCH around the edge was added.
- Find_set and union_set functions were added to assist the kruskal function
- The pq_update function was renamed to the heap_update function and moved to the heap header.
Revision Date: April 19, 2022
- Modified the data type of Parent.
- Modified the data type of GL.
- Modified the parameter data type of input_adjlist and print_adjlist.
- A function to output a score based on the search path was added. Discussion: Articulation points are likely to be related to finding the shortest path.
Revision Date: April 13, 2022
- input_adjlist now accepts input as a file.
- Node structures now have weights as variables.
- print_adjlist now outputs weights as well.
- The heap now sets the maximum value based on the weight.
- A heap sort function adjust_heap was added.
- A function pq_update was added to update weights and heaps.
- A function pis_adjlist that searches for NODE through the PFS algorithm was added.
- The print_heap function outputs weights and outputs characters instead of integers.
- Added a variable 'parent' that stores the node that called itself.
- Added a function print_tree that outputs the tree structure.
Revision Date: April 11, 2022
- Recursion project integrated.
- Separate into header and source for code brevity of graph search project.
- Add codes related to heap (note that they are implemented differently from the class)