DAG Applications

def build_order(projects, dependencies):
    """
    Determine build order for projects with dependencies.
    dependencies: [(dependent, dependency)]
    """
    graph = {p: [] for p in projects}
    in_degree = {p: 0 for p in projects}
    
    for dep, proj in dependencies:
        graph[proj].append(dep)
        in_degree[dep] += 1
    
    queue = [p for p in projects if in_degree[p] == 0]
    build_order = []
    
    while queue:
        project = queue.pop(0)
        build_order.append(project)
        
        for dependent in graph[project]:
            in_degree[dependent] -= 1
            if in_degree[dependent] == 0:
                queue.append(dependent)
    
    return build_order if len(build_order) == len(projects) else None

def longest_path_dag(graph, weights, start):
    """
    Find longest path from start to all vertices in weighted DAG.
    Time: O(V + E)
    """
    n = len(graph)
    
    # Topological sort
    in_degree = [0] * n
    for u in range(n):
        for v, _ in graph[u]:
            in_degree[v] += 1
    
    queue = [i for i in range(n) if in_degree[i] == 0]
    topo_order = []
    
    while queue:
        u = queue.pop(0)
        topo_order.append(u)
        for v, _ in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    # Longest path calculation
    dist = [-float('inf')] * n
    dist[start] = 0
    
    for u in topo_order:
        if dist[u] != -float('inf'):
            for v, weight in graph[u]:
                if dist[v] < dist[u] + weight:
                    dist[v] = dist[u] + weight
    
    return dist

def critical_path(activities, dependencies):
    """
    Find critical path in project scheduling.
    activities: {activity: duration}
    dependencies: [(activity, prerequisite)]
    """
    # Build graph
    graph = {a: [] for a in activities}
    in_degree = {a: 0 for a in activities}
    
    for act, prereq in dependencies:
        graph[prereq].append(act)
        in_degree[act] += 1
    
    # Topological sort
    queue = [a for a in activities if in_degree[a] == 0]
    topo_order = []
    
    while queue:
        activity = queue.pop(0)
        topo_order.append(activity)
        for dep in graph[activity]:
            in_degree[dep] -= 1
            if in_degree[dep] == 0:
                queue.append(dep)
    
    # Calculate earliest start times
    earliest = {a: 0 for a in activities}
    for activity in topo_order:
        for dep in graph[activity]:
            earliest[dep] = max(earliest[dep], 
                              earliest[activity] + activities[activity])
    
    # Calculate latest start times
    latest = {a: earliest[topo_order[-1]] + activities[topo_order[-1]] 
              for a in activities}
    
    for activity in reversed(topo_order):
        for dep in graph[activity]:
            latest[activity] = min(latest[activity], 
                                 latest[dep] - activities[activity])
    
    # Find critical path
    critical = [a for a in activities 
                if earliest[a] == latest[a]]
    
    return critical, earliest, latest

def event_ordering(events, happens_before):
    """
    Order events based on happens-before relation.
    happens_before: [(event1, event2)] meaning event1 happens before event2
    """
    graph = {e: [] for e in events}
    in_degree = {e: 0 for e in events}
    
    for e1, e2 in happens_before:
        graph[e1].append(e2)
        in_degree[e2] += 1
    
    queue = [e for e in events if in_degree[e] == 0]
    order = []
    
    while queue:
        event = queue.pop(0)
        order.append(event)
        for next_event in graph[event]:
            in_degree[next_event] -= 1
            if in_degree[next_event] == 0:
                queue.append(next_event)
    
    return order