혼합 비순환 그래프가 방향성 및 비 방향성 에지로 구성된 경우이 그래프를 체인 구성 요소의 유향 그래프로 분해하려고합니다 (체인 구성 요소 내의 각 노드는 무 디렉션으로 만 서로 연결됩니다. 가장자리) 및 순서.혼합 그래프에서 체인 구성 요소 추출
방향 지정 가장자리를 먼저 위상 적으로 정렬해야하는지, 그리고 방향이 지정되지 않은 가장자리를 체인 구성 요소로 사냥해야하는지 혼란 스럽거나 모든 방향이 지정되지 않은 가장자리를 찾아 그룹 ID를 부여한 다음 해당 구성 요소 .
그래프가 비순환 적이므로 낮은 숫자의 구성 요소에서 높은 번호의 구성 요소로 순서를 지정할 수는 있지만 확실한 대답은 얻을 수 없습니다.
두 방법 모두 잘 작동한다고 생각합니다.
내 마음에는 두 번째 방법이 더 자연스럽게 보입니다. 내가 networkx에서이 일을 한 경우
나는하여 두 번째 방법을 구현하는 것이 :
만 방향성 가장자리를 포함하는 새로운 그래프 H를 만듭니다.
H의 connected_components을 호출하여 체인 구성 요소를 추출하고 각 구성 요소에 다른 그룹 ID를 할당하십시오.
각 그룹 id마다 1 개의 노드가있는 새 그래프 F를 만듭니다. 원래 그래프의 지시 된 가장자리를 기반으로 방향이 지정된 가장자리로 F 그룹을 연결하십시오.
F의 topological_sort을 호출하여 그룹 ID의 순서를 계산하십시오.
여러분이 묘사 한 혼합 그래프는 다시 한 가지 직접 그래프입니다. 각각의 방향이 지정되지 않은 가장자리를 반대 방향을 가리키는 2 개의 지시 된 것과 바꿉니다.
또한 비 방향 그래프를 가질 수 없습니다. 최소한 길이 2의주기가 항상 존재하므로, 이것이 무엇을 의미하는지 확신 할 수 없습니다.
이 그래프에서 강력하게 연결된 구성 요소를 찾고있는 것 같아서 Tarjan's algorith을 찾는 것이 좋습니다.