부분 순서 표현을위한 C/C++ 그래프 인터페이스

Question

내 코드에서 나는 지시 된 비순환 그래프를 나타내는 클래스를 사용한다. 코드를 직접 작성 했으므로 어렵지 않았습니다. 그러나 나중에 내 앱이 더 많은 요구 사항을 갖고 있다는 것을 깨달았습니다. 그래프는 전이가 감소되어야합니다. 즉 부분적으로 주문자를 고유하게 표현해야합니다. 사용자가 그래프의 시각적 GUI 표현을 드래그 앤 드롭하거나 잘라 내기/복사/붙여 넣기를 수행 할 때마다 유효성을 검사하고이 요구 사항에 맞춰야합니다. 이제 상황이 더욱 복잡해집니다. 따라서 모든 그래프 작업을 안전하게 수행하는 방법을 계획했지만 코드에 실제로 들어가기 전에 다음을 알고 싶습니다.

부분 순서에 대해 알려진 C/C++ 인터페이스가 있습니까? (가급적이면 C++)

그래프에 대한 라이브러리가 많이 있지만, 이미 간단한 acyclic digraph 코드가 있습니다. 나는 transitively-reduced 그래프를 특별히 다루는 것을 찾을 수 없었다. (나는 인접한 행렬을 필요로하지 않는다. 데이터는 사용자로부터 나오므로 여기서는 비효율적이다 ... 그것은 사용자 데이터를위한 작은 그래프이다. 수학적 사용)

불필요한 연결을 자동으로 감지하여 제거하는 인터페이스를 찾고 있는데, 노드 복사/이동 작업이 부분 순서와 관련하여 유효한지, 즉 부분의 속성을 유지하는지 테스트합니다. 주문 등.

Answer 1

제가 알고있는 한, 일반적으로 프로그램은 비 수학적 목적으로 사용될 때 자체 그래프 클래스를 가지고 있습니다. 이것은 그래프가 STL 컨테이너 (벡터,리스트 등)와 같은 선형 컨테이너보다 훨씬 복잡 할 수 있기 때문에 발생합니다.

수학이나 알고리즘 분야의 특별한 요구 사항이 없으므로 (경우에 따라 검색 알고리즘이 단순한 루프가됩니다. 대부분의 경우 검색 알고리즘은 그 이상을 필요로하지 않으며 (조기) 최적화의 경우). 만약 당신이, 당신은 boost :: graph,하지만 나는 그것이 당신을 돕는 것보다 더 복잡한 것 같아요.

그래, 좋은 그래프/노드 클래스를 작성하고, 그것이 충분히 유용하고 범용 목적으로 작성 되었다면, 우리는 그것으로부터 모두 이익을 얻을 수있다. 아무도 귀하의 요구에 맞는 기존의 공개 코드가 없기 때문에 질문에 답하고있는 사람이 없습니다. 좋은 libre 코드를 한 번 작성하면 모든 곳에서 사용할 수 있습니다. 행운을 빕니다.

P.S 자신의 검색 알고리즘은 범용 그래프 라이브러리 용으로 작성된 알고리즘보다 훨씬 빠릅니다. boost :: graph를 사용하면 특정 그래프의 알려진 제한 및 규칙을 활용할 수 있으므로 seraches가 훨씬 빨라집니다. 예를 들어 전환 감소 그래프에서 A가 B의 부모 인 경우 A는 b가 아닌 자녀 양육자 (예 : 그랜드 자식)가 될 수 없으므로이 지식을 사용하여 검색을 최적화 할 수 있습니다. 당신이 지불하는 대가는 그래프를 변경할 때 많은 테스트를하고 있지만 검색/스캔이 훨씬 빨라질 수 있기 때문에 많은 돈을 벌 수 있습니다.

Answer 2

부분 주문 유효성 검사 방법을 추가하는 것이 좋습니다. 편집이 이루어질 때 전체 그래프의 사본을 하나의 사본에 적용한 다음 유효성을 검사합니다. 통과하면 수정 된 복사본을 보관하십시오. 통과하지 못하면 저장된 사본으로 되돌립니다.

아마도 유효성 검사기는 모든 하위 노드를 찾을 수 있습니다. 각 하위 노드는 상위 항목 (또는 하위 항목)을 호출하고 중복 항목을 확인합니다. 작은 그래프 만 기대한다면 탐색을위한 재귀로 돌아갈 것입니다.