Topological sort in OCaml

Question

ocaml에 토폴로지 정렬을 쓰려고하는데, 초보자입니다. (OCaml & 그래프 알고리즘) 나는 이것을 스스로 할 수 없습니다.

예를 들어 C++에서 토폴로지 정렬에 대해 생각하는 것이 더 쉽습니다 (인터넷에서 C++의 토폴로지 정렬에 대한 많은 예제가 있지만). 새로운 것을 배우고 싶습니다. 또한, OCaml로 작성된 토폴로지 정렬의 몇 가지 예를 발견했습니다. 솔직히 말해서 OCaml을 이해하지 못합니다.

의 내가 예를 들어, 목록 (int * int list) list 있다고 가정 해 봅시다 : 내가 필요한 것을,

myList = [(1, [2]); (5, [6; 7]); (3, [2]); (6, [3; 7]); (8, [7]); (4, [3; 1])];;

그 의미를 "할"작업 1 등 작업 3 및 1 전에 작업 2, 작업 4 전

나는이 목록이 출력해야한다, 생각 :

,293,210

또한

, 나는 위상 종류가 작동하지 않는 것을 읽었습니다 (난 그냥이 예제를 만들었 기 때문에 그러나 내가 틀렸다면 제발 수정 있도록, 확실하지 않다) 그래프에서 순환하기 때문에주기에 어떤 종류의 조건이 있어야합니다. 주어진 그래프에주기가있을 때 우리는 예외를 발생시킵니다 (좋은 생각이라고 생각합니다).

AFAIK는, 나는 (내가 주요 개념을 이해하지만, 내가 가 어떻게 작동하는지을 느끼지 않는다 OCaml의에서 구현하는 방법을 모른다 (DFS) 위상 정렬을위한 알고리즘에 DFS를 사용할 필요가 OCaml/함수 프로그래밍).

이 개념을 이해하는 데 큰 도움을 주셔서 감사합니다. 토폴로지 정렬, OCaml/함수 프로그래밍의 DFS를 의미합니다. 가능한 경우, 예제 코드를 보여 주면 코드를 읽는 것이 좋습니다. 왜냐하면 코드 읽기가 알고리즘 개념을 이해하는 가장 좋은 방법이기 때문입니다.

나는 당신이 대부분의 사람들에게 이것은 간단한 질문이지만, 나는 그것이 당신이 나를 도와주지 못하게 해주기를 바랍니다.

추신 : 저는 OCaml을 혼자서 배우고 있습니다. (나는 고등학교에 다니고 있습니다.) 그래서 OCaml이나 알고리즘에서 솔리드 이론 배경을 가지고 있지 않습니다. 재귀 컨셉을 이해하고 싶었 기 때문에 OCaml을 배우기 시작 했었습니다. 이제는 C++과 완전히 다른 언어이기 때문에이 언어가 재미있을 것 같습니다. 그래서 OCaml에서 새로운 것을 배우려고합니다.

Answer 1

[경우 당신은 내가 무슨 뜻 아래 DAG 쓰기 용어, "감독 비순환 그래프", 또는 /로부터주기가 없도록 정점을 연결 가장자리의 컬렉션을 모른다.]

이를 수행하는 한 가지 방법은 부분 순서 (DAG 구조)를 전체 순서로 확장하는 것입니다 (따라서 별개의 정점 u와 v의 모든 쌍에 대해 u는 v의 후속 또는 그 반대입니다). 그런 다음 정점을 순서대로 정렬 할 수 있습니다. v가 v의 후속이면 v가 앞에옵니다.

빈 그래프부터 시작하여 원본 DAG에서 한 번에 하나의 가장자리를 추가하여 전체 주문을 구성 할 수 있습니다. 즉, 원래 DAG의 항목 (u, [v1; v2; ...; vn])은 가장자리 (u, v1), (u, v2), ..., (u, vn)에 해당합니다. 이러한 각 모서리 (u, v)에 대해 전체 순서에서 u의 전임자 P와 v의 후속 S를 찾으십시오. 그런 다음 P U (u)의 모든 p와 S U (v)의 s에 대해 전체 순서에 (p, s)를 추가하십시오.

지금! 더 빠른 방법은 원래 DAG (즉 선행 작업이없는 정점)에서 루트를 찾고 해당 루트에서 깊이 우선 검색을 수행하여 동일한 정점을 두 번 방문하지 않도록하는 것입니다. 트래버스에서 역 추적 할 때마다 떠나는 정점을 "출력"합니다. 이렇게하면 토폴로지 종류의 DAG를 구성 할 수 있습니다. 어떤 꼭지점이 남아 있으면, 씻어 내고, 모두 끝날 때까지 반복하십시오.

Answer 2

저는 OCaml을 모르지만,에 간단한 알고리즘이 있습니다. Kahn은 제가 성공적으로 (Python으로 옮겨서) 사용했습니다. 그것은 매우 간단하여 OCaml로 변환 할 수 있습니다. 여기에 있습니다 :

Answer 3

먼저 DFS를 시도해보십시오. 더 쉽고 보람 있습니다.

Answer 4

먼저 Objective Caml은 구문상의 차이에도 불구하고 변경 가능한 데이터 구조 (참조, 배열, 해시 테이블) 및 필수 구성 (for 및 while 루프)을 통해 C++과 상당히 유사한 프로그래밍 스타일을 지원한다는 점에 유의하십시오. , 변수 할당). 나는 당신이 실제로 관용적 인 순수한 기능적 스타일로 위상 적 분류를 쓰려고한다는 것을 아래에서 추측하고 있습니다.

순수 함수 프로그래밍은 대부분 선언적입니다.이 함수는 해당 값 에 적용되며이 다른 값은입니다. 따라서 let x =의 오른쪽은 return을 사용하는 일련의 동작 대신 표현식 (값으로 평가)입니다. 물론 일련의 단계로 일반적으로 설명되는 알고리즘을 적용 할 때 문제가 발생합니다.

다행스럽게도 "X 값 변경"을 "이전 값과 동일한 새 오브젝트 반환"으로 전환하여 기능 스타일에서 명령형 알고리즘을 나타낼 수있는 패턴 (실제로는 패밀리 패턴 패밀리)이 있습니다. , X의 값은 제외. "

전통적인 DFS 알고리즘은 어떤 요소가 이미 방문했는지 (일반적으로 (한 번 이상 방문하지 않도록) 및 현재 위치로 이동하는 것을 기억하면서 그래프를 단계별로 진행 함) 사이클). 따라서 DFS 알고리즘의 명령형 상태는 현재 노드, 방문한 노드 집합 및 현재 경로에있는 노드 집합으로 구성됩니다. 이 모든 데이터는 재귀 호출에 제공되어야하며 영구적 인 변경 사항은 동일한 재귀 호출에 의해 반환되어야합니다. 두 세트리스트 표현 (가 거의 최적의 - Set 여기에 더 나은 선택이 될 것입니다)와 함께 위의 그래프 구조를 사용

, 알고리즘은 다음과 같이 다소 보일 것이다

let dfs graph start_node = 
    let rec explore path visited node = 
    if List.mem node path then raise (CycleFound path) else 
    if List.mem node visited then visited else  
     let new_path = node :: path in 
     let edges = List.assoc node graph in 
     let visited = List.fold_left (explore new_path) visited edges in 
     node :: visited 
    in explore [] [] start_node 

세 위의 중요한 세부 사항 : 첫째, DFS에 따르면 주어진 노드의 모든 하위 노드를 탐색 한 후 "현재 경로"목록에서 해당 노드를 제거하고이를 "방문한"목록에 넣어야합니다. 우리가 불변의 데이터 구조를 사용하기 때문에 첫 번째 단계는 필요하지 않습니다. 탐색의 시작시 노드의 삽입을 취소하는 것이 유일한 목적이며 에 대한 재귀 호출에 의해 목록 new_path이 수정되지 않습니다. 이것은 기능적 데이터 구조가 명령형 구조보다 작업하기에 더 편한 경우의 예입니다.

또 다른 중요한 세부 사항은 List.fold_left입니다. 상태를 명시 적으로 만들기 시작할 때 유형 -> unit의 암시 적 명령형 함수를 -> state -> .. -> state 유형의 명시 적 함수로 대체했습니다 (매개 변수로 상태를 허용하고 새 상태를 반환).그래서,이처럼 보였다 명령형 목록 탐험 :

f edge_1 ; f edge_2 ; f edge_3 

이제 다음과 같습니다

let state = f (f (f state edge_1) edge_2) edge_3) 

을 List.fold_left f state [edge_1 ; edge_2 ; edge_3]이 바로 이러한 작업을 수행하는 것입니다 어느. 나만의 경적을 울리고 있지만, 나는 a nice article about this here이있다.

목록을 사용하여 집합을 나타낼 때 "추가 할 요소 추가"작업은 element :: set으로 작성됩니다. 이는 모든 요소가 포함 된 새 집합 (목록)을 반환하는 연산이기 때문입니다. 원래 요소는 새 요소와 함께 설정됩니다. 이렇게하면 일정한 양의 메모리를 사용하면서 원본 세트가 그대로 유지됩니다 (1 단계에서 설명한 이유 때문에 유용함). 이는 셀에 대한 참조를 포함하는 간단한 머리 - 꼬리 쌍이며 집합에 대한 참조를 포함합니다) : 실행 취소 기능을 제공 할뿐만 아니라 추가 비용없이 그렇게 할 수 있습니다.

위의 알고리즘은 DFS 탐색의 잎으로 시작하여 visited에 노드를 "삽입"합니다.이 경우 노드는 마지막으로 수행해야하는 노드를 나타냅니다. 즉, 반환 된 목록은 토폴로지별로 정렬되지만 시작점이 유일한 루트 요소가 아니거나 루트 요소가 아닐 수도 있기 때문에 모든 요소가 포함되어 있지 않을 수도 있습니다. 따라서 그래프에서 다른 노드를 가져 와서 모든 그래프를 탐색 할 때까지 추가 처리 단계가 있습니다.

또는, 즉, 그래프의 모든 노드에서 새 DFS 탐사 을 시작하지만, 이전에 모든 노드를 무시가을 탐구

- 다음에 하나 개의 DFS 탐사에서 방문 요소의 목록을 유지에 해당하는 .

let dfs graph visited start_node = 
    let rec explore path visited node = 
    if List.mem node path then raise (CycleFound path) else 
    if List.mem node visited then visited else  
     let new_path = node :: path in 
     let edges = List.assoc node graph in 
     let visited = List.fold_left (explore new_path) visited edges in 
     node :: visited 
    in explore [] visited start_node 

let toposort graph = 
    List.fold_left (fun visited (node,_) -> dfs graph visited node) [] graph 

팅겨 이미 방문한 노드의 목록을 지정 dfs의 호출을 허용으로 구성되어 있습니다 : 이전 알고리즘에 작은 비틀기를 사용

,이 두 라인을합니다. 모든 노드에서 DFS를 시작하는 동안 방문한 노드 목록을 전달하는 것은 전에와 마찬가지로 List.fold_left을 사용하여 수행됩니다.

EDIT : 예외 유형을 제외하고 그래프의 요소 유형을 제한하는 요소는 여기에 없습니다. 그러나 예외는 다형성 일 수 없으므로 두 가지 가능한 솔루션이 있습니다. 첫 번째는 실제로 예외와 함께 모든 데이터를 반환 포기하는 것입니다

exception CycleFound 

... raise CycleFound ... 

이

다시 ('a * ('a list)) list -> 'a list 더 일반적인에 toposort의 유형을 되돌아갑니다.

다른 솔루션은 오히려 고급 OCaml이 있습니다 :

module type NODE = sig 
    type t 
end 

module type Topo = functor (Node:NODE) -> struct 
    exception CycleFound of Node.t list  
    let dfs ... 
    let sort ... 
end 

이 유형을 만들 것입니다 : 다음과 같이 예외 및 특정 유형의 다형성 위상 종류를 포함 모듈을해야

귀하의 질문은 다른 말로 표현 되었다면

type recipe = Eggs | Milk | Wheat | Mix | Cook | Serve 

module Node = struct 
    type t = recipe 
end 

let graph = [ Wheat, [Eggs,Milk,Mix] ; 
       Milk, [Mix] ; 
       Eggs, [Mix] ; 
       Mix, [Cook] ; 
       Cook, [Serve] ; 
       Serve, [] ] 

module RecipeTopo = Topo(Node) 

let sorted = RecipeTopo.sort graph