DAG와 의존성 그래프 — 빌드 시스템부터 스프링 빈까지

DAG:                     DAG가 아닌 그래프 (사이클):
  A → B → D               A → B → D
  ↓   ↓                   ↓   ↓   ↑
  C → E                   C → E → F

public List<Integer> topologicalSort(int vertices, List<List<Integer>> adjList) {
    // 1. 진입 차수 계산
    int[] inDegree = new int[vertices];
    for (int u = 0; u < vertices; u++) {
        for (int v : adjList.get(u)) {
            inDegree[v]++;
        }
    }

    // 2. 진입 차수가 0인 정점을 큐에 추가
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < vertices; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }

    // 3. BFS
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order.add(u);

        for (int v : adjList.get(u)) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                queue.offer(v);
            }
        }
    }

    // 4. 사이클 감지
    if (order.size() != vertices) {
        throw new RuntimeException("사이클이 존재합니다!");
    }

    return order;
}

public List<Integer> topologicalSortDFS(int vertices, List<List<Integer>> adjList) {
    boolean[] visited = new boolean[vertices];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < vertices; i++) {
        if (!visited[i]) {
            dfs(i, adjList, visited, stack);
        }
    }

    return new ArrayList<>(stack);
}

private void dfs(int u, List<List<Integer>> adjList,
                 boolean[] visited, Deque<Integer> stack) {
    visited[u] = true;
    for (int v : adjList.get(u)) {
        if (!visited[v]) {
            dfs(v, adjList, visited, stack);
        }
    }
    stack.push(u); // 후위 순서로 스택에 추가
}

  A → B → D
  ↓   ↓
  C → E

진입 차수: A=0, B=1, C=1, D=1, E=2

순서: A → B → C → D → E (또는 A → C → B → E → D 등)

// build.gradle
task compileJava {
    // 소스 컴파일
}

task processResources {
    // 리소스 복사
}

task classes {
    dependsOn compileJava, processResources
}

task test {
    dependsOn classes
}

task jar {
    dependsOn classes
}

task build {
    dependsOn test, jar
}

compileJava ─────┐
                  ├→ classes → test ──┐
processResources ─┘            │      ├→ build
                               jar ───┘

@Service
public class OrderService {
    private final UserService userService;
    private final PaymentService paymentService;

    // OrderService → UserService, PaymentService
    public OrderService(UserService userService, PaymentService paymentService) {
        this.userService = userService;
        this.paymentService = paymentService;
    }
}

@Service
public class PaymentService {
    private final PaymentGateway gateway;

    // PaymentService → PaymentGateway
    public PaymentService(PaymentGateway gateway) {
        this.gateway = gateway;
    }
}

PaymentGateway → PaymentService
UserService ─────────────────────→ OrderService

// 순환 의존성 — 이것은 DAG가 아닙니다!
@Service
public class ServiceA {
    @Autowired private ServiceB serviceB; // A → B
}

@Service
public class ServiceB {
    @Autowired private ServiceA serviceA; // B → A → 사이클!
}

***************************
APPLICATION FAILED TO START
***************************
The dependencies of some of the beans in the application context form a cycle:
  serviceA → serviceB → serviceA

// 해결: 공통 로직을 별도 서비스로 추출
@Service
public class ServiceA {
    private final CommonService commonService;
}

@Service
public class ServiceB {
    private final CommonService commonService;
}

# Airflow DAG 예시 (Python)
from airflow import DAG
from airflow.operators.python import PythonOperator

dag = DAG('daily_etl', schedule_interval='@daily')

extract = PythonOperator(task_id='extract', python_callable=extract_data, dag=dag)
transform = PythonOperator(task_id='transform', python_callable=transform_data, dag=dag)
load = PythonOperator(task_id='load', python_callable=load_data, dag=dag)
notify = PythonOperator(task_id='notify', python_callable=send_notification, dag=dag)

extract >> transform >> load >> notify
# extract → transform → load → notify

extract → transform → load → notify

// 크리티컬 패스: DAG에서 최장 경로 (위상 정렬 + DP)
public int criticalPath(int vertices, List<List<int[]>> adjList) {
    List<Integer> order = topologicalSort(vertices, adjList);
    int[] longest = new int[vertices]; // 시작점부터의 최장 거리

    for (int u : order) {
        for (int[] edge : adjList.get(u)) {
            int v = edge[0], weight = edge[1];
            longest[v] = Math.max(longest[v], longest[u] + weight);
        }
    }

    return Arrays.stream(longest).max().orElse(0);
}

빌드(30s) → 단위 테스트(60s) → 통합 테스트(120s) → 배포(30s)
빌드(30s) → 코드 분석(45s)
빌드(30s) → Docker 이미지(20s)

크리티컬 패스: 빌드 → 단위 테스트 → 통합 테스트 → 배포 = 240초

public boolean hasCycle(int vertices, List<List<Integer>> adjList) {
    int[] state = new int[vertices]; // 0: 미방문, 1: 진행 중, 2: 완료

    for (int i = 0; i < vertices; i++) {
        if (state[i] == 0 && dfsCycle(i, adjList, state)) {
            return true;
        }
    }
    return false;
}

private boolean dfsCycle(int u, List<List<Integer>> adjList, int[] state) {
    state[u] = 1; // 진행 중

    for (int v : adjList.get(u)) {
        if (state[v] == 1) return true;  // 진행 중인 노드를 다시 방문 → 사이클!
        if (state[v] == 0 && dfsCycle(v, adjList, state)) return true;
    }

    state[u] = 2; // 완료
    return false;
}