Data Structures Term Project (Critical Path)

Ding Zhiyu 202331060205 [TOC]

Problem Requirements

1. Drawing an Activity-On-Edge (AOE) Network: Based on the given film production process, draw an AOE network reflecting each activity and its time requirements. This graph will serve as the basis for determining the project timeline and critical path.

2. Critical Path Analysis: By analyzing the AOE network, identify the critical path that determines the minimum project completion time. The critical path is the sequence of activities that cannot be delayed in the project, and its total duration determines the shortest completion time for the entire project.

3. Algorithm Implementation and Output: Implement an algorithm to calculate the minimum time from project launch to the start of shooting. Additionally, the algorithm should output the specific activities on the critical path.

4. Efficiency Analysis: Analyze the time complexity and space complexity of the implemented algorithm.

Implementation

Drawing the AOE Network

graph LR;
    A[Project Launch] -->|1| B[Confirm Director]
    B -->|2| C[Finalize Details]
    C -->|2| F[Start Shooting]
    A -->|3| D[Confirm Actors]
    B -->|1| D
    D -->|2| F
    A -->|5| E[Complete Locations]
    D -->|1| E
    E -->|1| C
    E -->|2| F

Analyzing the Critical Path

• 0 (Project Launch)
• 1 (Confirm Director)
• 2 (Finalize Details)
• 3 (Confirm Actors)
• 4 (Complete Locations)
• 5 (Start Shooting)

Based on edge definitions and weights, calculate the following paths:

• 0 -> 1 -> 2 -> 5
• 0 -> 3 -> 5
• 0 -> 4 -> 2 -> 5
• 0 -> 4 -> 5

Calculate the total duration of each path to determine which is the critical path.

Calculation

• Path 0 -> 1 -> 2 -> 5: Time = 1 + 2 + 2 = 5
• Path 0 -> 3 -> 5: Time = 3 + 2 = 5
• Path 0 -> 4 -> 2 -> 5: Time = 5 + 1 + 2 = 8 (longest path)
• Path 0 -> 4 -> 5: Time = 5 + 2 = 7

Path 0 -> 4 -> 2 -> 5 is the critical path because it has the longest duration of 8 time units. Any delay on this path will directly affect the entire project's completion time.

Conclusion

"Project Launch -> Complete Locations -> Finalize Details -> Start Shooting" is the critical path.

Code Implementation

1. Build the graph data structure - Use an adjacency list to represent the graph.
2. Topological Sort - To determine the order of activities.
3. Critical Path Method - Calculate the minimum completion time.

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 6 // Define maximum number of nodes

int indegree[MAX_NODES] = {0}; // Store indegree of each node
int earliest[MAX_NODES] = {0}; // Store earliest start time of each node
int latest[MAX_NODES] = {0};   // Store latest start time of each node

// Define node structure
typedef struct Node
{
    int vertex;        // Adjacent vertex number
    int weight;        // Edge weight
    struct Node *next; // Pointer to the next adjacent vertex
} Node;

Node *graph[MAX_NODES] = {NULL}; // Adjacency list representation of the graph

// Add an edge to the graph
void addEdge(int start, int end, int weight)
{
    Node *newNode = (Node *)malloc(sizeof(Node)); // Dynamically allocate node memory
    newNode->vertex = end;                        // Set adjacent vertex number
    newNode->weight = weight;                     // Set weight
    newNode->next = graph[start];                 // Insert new node into the linked list
    graph[start] = newNode;
    indegree[end]++; // Increase indegree of the end vertex
}

// Convert node numbers to specific event names
const char *translateEvent(int vertex);

// Topological sort
void topologicalSort(int *sorted)
{
    int queue[MAX_NODES], front = 0, rear = 0; // Use a queue for topological sort
    for (int i = 0; i < MAX_NODES; i++)
    {
        if (indegree[i] == 0)
        {
            queue[rear++] = i; // Enqueue nodes with indegree 0
        }
    }

    int index = 0;
    while (front < rear)
    {
        int u = queue[front++]; // Dequeue a node
        sorted[index++] = u;    // Store the sort result
        for (Node *v = graph[u]; v != NULL; v = v->next)
        {
            if (--indegree[v->vertex] == 0)
            {
                queue[rear++] = v->vertex; // If indegree becomes 0 after decrement, enqueue
            }
        }
    }
}

// Calculate critical path
void criticalPath(int *sorted)
{
    for (int i = 0; i < MAX_NODES; i++)
    {
        int u = sorted[i];
        for (Node *v = graph[u]; v != NULL; v = v->next)
        {
            if (earliest[v->vertex] < earliest[u] + v->weight)
            {
                earliest[v->vertex] = earliest[u] + v->weight; // Calculate earliest time
            }
        }
    }

    for (int i = 0; i < MAX_NODES; i++)
    {
        latest[i] = earliest[MAX_NODES - 1]; // Initialize latest time
    }

    for (int i = MAX_NODES - 1; i >= 0; i--)
    {
        int u = sorted[i];
        for (Node *v = graph[u]; v != NULL; v = v->next)
        {
            if (latest[u] > latest[v->vertex] - v->weight)
            {
                latest[u] = latest[v->vertex] - v->weight; // Calculate latest time
            }
        }
    }

    printf("Minimum time to start shooting is %d time units.\n", earliest[MAX_NODES - 1]);
    printf("Critical path includes:\n\n ");
    for (int i = 0; i < MAX_NODES; i++)
    {
        int u = sorted[i];
        for (Node *v = graph[u]; v != NULL; v = v->next)
        {
            if (earliest[u] + v->weight == latest[v->vertex] && earliest[u] == latest[u])
            {
                printf("%s --> %s\n", translateEvent(u), translateEvent(v->vertex)); // Output critical path using event names
            }
        }
    }
}

// Convert node numbers to specific event names
const char *translateEvent(int vertex)
{
    switch (vertex)
    {
    case 0:
        return "Project Start";
    case 1:
        return "Confirm Director";
    case 2:
        return "Finalize Details";
    case 3:
        return "Confirm Actors";
    case 4:
        return "Complete Locations";
    case 5:
        return "Start Shooting";
    default:
        return "Unknown";
    }
}

int main()
{
    addEdge(0, 1, 1);
    addEdge(1, 2, 2);
    addEdge(2, 5, 2);
    addEdge(0, 3, 3);
    addEdge(1, 3, 1);
    addEdge(3, 5, 2);
    addEdge(0, 4, 5);
    addEdge(3, 4, 1);
    addEdge(4, 2, 1);
    addEdge(4, 5, 2);

    int sorted[MAX_NODES];
    topologicalSort(sorted);
    criticalPath(sorted);
    return 0;
}

Code Screenshot

Output Screenshot

Efficiency Analysis

Time Complexity

1. Edge Addition Operation (addEdge): Each call to the addEdge function has a time complexity of O(1), as it only involves a few basic operations such as memory allocation and updating the adjacency list.

2. Topological Sort (topologicalSort): In topological sort, each node is enqueued once, dequeued once, and each edge is checked once. If there are V vertices and E edges, the time complexity of topological sort is O(V + E).

3. Critical Path Calculation (criticalPath): This part involves two traversals of all edges and nodes: one for calculating the earliest start times and one for calculating the latest start times. Therefore, the time complexity of this part is also O(V + E).

Overall, the time complexity of the entire algorithm is O(V + E).

Space Complexity

1. Adjacency List: Using an adjacency list to store the graph structure, each vertex has a linked list to store connected edges. Therefore, the space complexity is related to the number of vertices and edges, which is O(V + E).

2. Auxiliary Arrays: Such as indegree, earliest, latest, and sorted, each occupying O(V) space.

3. Queue: The queue used in topological sort can contain all nodes in the graph in the worst case, requiring O(V) space.

Therefore, the space complexity of the entire algorithm is mainly composed of the adjacency list and auxiliary data structures, which is O(V + E) overall.