A Directed Acyclic Graph (DAG) is a finite directed graph containing no directed cycles. This structure is particularly useful for modeling mathematical expressions and scheduling dependencies.

Expression Representation via DAGs

Mathematical or logical expressions can be efficiently represented using DAGs to minimize redundant computations. The construction follows a deterministic procedure:

1. List all unique operands without duplication.
2. Determine the execution precedence of operators, allowing flexibility among operators of equal precedence.
3. Place operators hierarchically based on data dependencies. An operator requiring the output of a previous computation resides at a higher level.
4. Scan from the bottom up to merge identical operations occurring at the same dependency level. The resulting graph contains the minimum number of vertices required to represent the expression, as duplicate operand nodes are eliminated by design.

AOV Networks and Topological Sorting Fundamentals

An Activity On Vertex (AOV) network models project schedules where vertices represent tasks and directed edges denote precedence constraints. If an edge points from $V_i$ to $V_j$, task $V_i$ must complete before $V_j$ begins. These relationships are transitive, and cycles are strictly prohibited in valid scheduling models.

Topological sorting produces a linear sequence of vertices from a DAG where every directed edge $(u, v)$ implies $u$ precedes $v$ in the ordering. The sequence satisfies:

• Every vertex appears exactly once.
• No vertex appears after any of its predecessors in the dependency chain. Vertices with an in-degree of zero naturally occupy the initial positions in the sequence.

Algorithm Implementation: Kahn's Method

The standard iterative approach, often attributed to Kahn, processes vertices by repeatedly removing nodes with no incoming dependencies.

1. Identify all vertices with zero in-degree and place them in a working collection.
2. Extract a vertex, append it to the result sequence, and remove its outgoing edges.
3. If edge removal reduces a neighbor's in-degree to zero, add that neighbor to the collection.
4. Repeat until the collection is empty. If the output sequence length is less than the vertex count, a cycle exists.

Data Structure Definition:

#define MAX_NODES 1005

typedef struct EdgeNode {
    int target_vertex;
    struct EdgeNode* next_edge;
} EdgeNode;

typedef struct Vertex {
    int id;
    EdgeNode* edge_list_head;
} Vertex;

typedef struct {
    Vertex adj_array[MAX_NODES];
    int vertex_count;
    int edge_count;
} AdjGraph;

Initialization & Edge Insertion:

void InitializeGraph(AdjGraph* g, int v_count) {
    g->vertex_count = v_count;
    g->edge_count = 0;
    for (int i = 1; i <= v_count; ++i) {
        g->adj_array[i].id = i;
        g->adj_array[i].edge_list_head = NULL;
    }
}

void AddDirectedEdge(AdjGraph* g, int src, int dest) {
    EdgeNode* new_edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    new_edge->target_vertex = dest;
    new_edge->next_edge = g->adj_array[src].edge_list_head;
    g->adj_array[src].edge_list_head = new_edge;
    g->edge_count++;
}

Topological Sort Execution (Stack-based):

bool ExecuteTopoSort(AdjGraph g, int* indegree, int* result_seq) {
    int stack[MAX_NODES], stack_top = 0;
    int processed_count = 0;

    for (int v = 1; v <= g.vertex_count; ++v) {
        if (indegree[v] == 0) {
            stack[stack_top++] = v;
        }
    }

    while (stack_top > 0) {
        int current = stack[--stack_top];
        result_seq[processed_count++] = current;

        EdgeNode* temp = g.adj_array[current].edge_list_head;
        while (temp != NULL) {
            int neighbor = temp->target_vertex;
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                stack[stack_top++] = neighbor;
            }
            temp = temp->next_edge;
        }
    }
    return processed_count == g.vertex_count;
}

Using an adjacency list yields a time complexity of $O(|V| + |E|)$, while an adjacency matrix requires $O(|V|^2)$ due to row scanning for outgoing edges.

Depth-First Search Approach

DFS can also derive a topological ordering by leveraging post-order traversal timestamps. In a DAG, if $u$ is an ancestor of $v$, the DFS completion time for $u$ will strictly exceed that of $v$. Sorting vertices by descending finish times yields a valid sequence.

DFS Traversal & Finish Time Tracking:

int global_timer = 0;
bool is_visited[MAX_NODES];
int completion_time[MAX_NODES];

void RunDFSTraversal(AdjGraph g) {
    memset(is_visited, 0, sizeof(is_visited));
    memset(completion_time, 0, sizeof(completion_time));
    global_timer = 0;
    for (int i = 1; i <= g.vertex_count; ++i) {
        if (!is_visited[i]) {
            DFS_Visit(g, i);
        }
    }
}

void DFS_Visit(AdjGraph g, int start_node) {
    is_visited[start_node] = true;
    EdgeNode* ptr = g.adj_array[start_node].edge_list_head;
    while (ptr != NULL) {
        int neighbor = ptr->target_vertex;
        if (!is_visited[neighbor]) {
            DFS_Visit(g, neighbor);
        }
        ptr = ptr->next_edge;
    }
    completion_time[start_node] = ++global_timer;
}

To obtain the topological order, sort the vertex indices based on completion_time in descending order. If inverse topological sorting is required, vertices can be output directly upon DFS completion instead of recording timestamps.

Reverse Topological Sorting

The inverse process targets vertices with zero out-degree instead of zero in-degree.

1. Locate vertices lacking outgoing edges.
2. Output the vertex and remove all incoming edges connected to it.
3. Repeat until exhausted or stuck (indicating a cycle).

When using an adjacency list, finding incoming edges efficiently requires scanning the entire structure, degrading performance. An adjacency matrix or a dedicated inverse adjacency list mitigates this bottleneck.

Matrix-Based Implementation:

bool ComputeReverseTopo(int n, int** matrix, int* out_degree, int* sequence) {
    int stack[MAX_NODES], top_idx = 0, seq_len = 0;

    for (int v = 1; v <= n; ++v) {
        if (out_degree[v] == 0) stack[top_idx++] = v;
    }

    while (top_idx > 0) {
        int curr = stack[--top_idx];
        sequence[seq_len++] = curr;

        for (int r = 1; r <= n; ++r) {
            if (matrix[r][curr]) {
                matrix[r][curr] = 0;
                out_degree[r]--;
                if (out_degree[r] == 0) {
                    stack[top_idx++] = r;
                }
            }
        }
    }
    return seq_len == n;
}

Key characteristics of topological sequences:

• Multiple valid orderings often exist when nodes share the same dependency level or have no direct precedence constraints.
• If the DAG forms a strict linear chain, the topological sequence becomes unique.
• Reordering vertices according to their topological rank can transform the adjacency matrix into an upper-triangular form. Conversely, a triangular adjacency matrix guarantees acyclicity, though acyclic graphs do not always naturally present a triangular matrix without reordering.