그래프 직렬화

Question

유향 그래프를 '직렬화'하는 간단한 알고리즘을 찾고 있습니다.특히 실행 순서에 상호 의존성이 있는 파일 세트가 있는데 컴파일 타임에 올바른 순서를 찾고 싶습니다.나는 그것이 매우 일반적인 일임에 틀림없다는 것을 알고 있습니다. 컴파일러는 항상 그것을 합니다. 그러나 오늘 내 google-fu는 약했습니다.이에 대한 '이동' 알고리즘은 무엇입니까?

Answer 1

토폴로지 정렬 (위키피디아에서):

그래프 이론에서, 지시 된 acyclic 그래프 (DAG)의 토폴로지 정렬 또는 토폴로지 순서는 각 노드가 아웃 바운드 가장자리를 갖는 모든 노드 앞에 오는 노드의 선형 순서입니다.모든 DAG에는 하나 이상의 토폴로지 종류가 있습니다.

의사 코드:

L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
    remove a node n from Q
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into Q
if graph has edges then
    output error message (graph has a cycle)
else 
    output message (proposed topologically sorted order: L)

Answer 2

이것이 필요한 도구는 단순히 깊이 우선 방식으로 트리를 탐색하고 리프에 도달하면 처리하기만 하면 됩니다(예:컴파일) 그래프에서 제거합니다(또는 처리된 것으로 표시하고 모든 리프가 리프로 처리된 노드를 처리합니다).

DAG라면 이 간단한 스택 기반 탐색은 사소한 일입니다.

Answer 3

그래프에 주기가 포함되어 있으면 파일에 허용되는 실행 순서가 어떻게 존재할 수 있습니까?그래프에 사이클이 포함되어 있으면 해결책이 없으며 위의 알고리즘에 의해 올바르게보고됩니다.

Answer 4

나는 상당히 순진한 재귀 알고리즘(의사 코드)을 생각해냈습니다.

Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list

function resolve(a):
    if (dest.contains(a)) return;
    foreach (b in source[a]):
        resolve(b);
    dest.add(a);

foreach (a in source):
    resolve(a);

이것의 가장 큰 문제는 순환 종속성을 감지하는 능력이 없다는 것입니다. 무한 재귀(예: 스택 오버플로 ;-p)가 발생할 수 있습니다.내가 볼 수 있는 유일한 방법은 재귀 알고리즘을 수동 스택이 있는 대화형 알고리즘으로 전환하고 스택에서 반복되는 요소가 있는지 수동으로 확인하는 것입니다.

누구든지 더 나은 것이 있습니까?