그래프를 다른 구조에 매핑하는 알고리즘

Question

그래프 구조를 아래에 나와있는 구조로 매핑하려고합니다. 여기

내가 매핑해야 그래프의 형태의 일례이다

왼쪽에서 오른쪽 화살표는 항상 한 방향이

.

내가 찾던 결과가 여기에 있습니다.

<root> 
    <seq> 
     <mod1/> 
     <flow> 
      <seq> 
       <mod4/> 
       <mod7/> 
      </seq> 
      <seq> 
       <flow> 
        <seq> 
         <flow> 
          <mod4/> 
          <mod3/> 
         </flow> 
         <mod6/> 
        </seq> 
        <seq> 
         <flow> 
          <mod4/> 
          <mod3/> 
          <mod2/> 
         </flow> 
         <mod5/> 
        </seq> 
       </flow> 
       <mod8/> 
      </seq> 
     </flow> 
    </seq> 
</root> 

내가 사용할 수있는 알고리즘이 있습니까 :

목표는이 같은 XML을 생성하는 것입니다?

필자는 JSON을 구문 분석하여 Java 7로 XML을 작성하고 있습니다. 상자는 웹 서비스이고 화살표는 입력 및 출력 매개 변수를 나타냅니다. 예를 들어 모듈 5는 모듈 1, 2,3 및 4는 끝났고 출력은 입력입니다.

Answer 1

그것을 떠나, 내가하는 알고리즘을 발견 그 일을 했어. 여기 나를 돕기 위해 노력한 여러분 모두를위한 것입니다 :

우선 저는 스케치 1에서 DAG의 거꾸로 된 스패닝 트리를 만들었습니다. 그래서 모듈 7과 8에서 시작하여 트리를 거꾸로 만들고 모듈 중복됩니다.

는 그 후 나는 FLOW와 SEQUENCE라는 가상 노드를 생성하고 모든 모듈 노드가 SEQUENCE 노드의 아이가되도록 트리를 소개합니다. 스패닝 브랜치는 FLOW 노드의 하위 노드 인 SEQUENCE 노드입니다. 이 단계는 직관적이라고 생각하지만 중요한 아이디어는 가상 노드가 필요하다는 것을 이해하는 것입니다. 따라서 하나의 노드에서 둘 이상의 노드로 분할되는 FLOW 노드를 닫을 수 있습니다. 내가 처음 트리 깊이 가서, 모든 모듈에 대해 나는 운전자의 형제 자매의 자녀와 함께 아이를 비교 (우리가 드라이버를 호출 것이다) 그 후

. 일치하지 않으면 나는 운전자 형제 자매의 손자와 계속 추종합니다. 그래서 운전자 형제에게서 나오는 모든 가지는 운전자와 같은 노드를 통과해야합니다. 그래픽 적으로 이는 어떤 시점에서 두 노드가 완전히 동일한 모듈을 필요로한다는 것을 의미합니다.

그들은 내가 그들의 부모를 차단하는 것을 의미, 아래로 일치 노드에서 병합 가지를 정리 일치합니다. 그곳에서 위쪽으로 동일한 SEQUENCE 노드와 함께 새로운 SEQUENCE 노드가 동일한 FLOW 노드로 이동합니다.

는 전체 트리에 걸쳐 진행 한 후, 한 병합이 이루어지고있다, 우리는 다시 나무를 통해 더 큰 관계로이 시간을 이동합니다. 즉, 운전자의 자녀를 비교하는 대신 운전자의 훌륭한 자녀를 비교합니다.

마지막 단계는 분명히 다시 트리를 되돌리는 것입니다.

내가 때문에 이러한 가상 노드의 프로그래밍 의미 복잡한의 곁에 남아있는 몇 가지 개념이있다. 주로 가상 노드가 도입되면 모든 부모 - 자식 - 형제 관계가 손실되기 때문입니다. 그러나 일반적인 생각이 이해되기를 바랍니다.

Answer 2

경로가 지정된 경우 여러 경로에 해당하는 리프 노드를 복제하여 동일한 트리 구조가 형성됩니다. 구조체가 지시 된 경로를 가지고 있지 않다면, 나는 일반적인 경우에 대응하는 트리 구조가 없다고 믿는다.

이, 해당 트리 구조가 방향성 그래프되는 새로운 정보에 비추어 EDIT

:

1 
    2 
    5 
     8 
    3 
    5 
     8 
    6 
     8 
    4 
    6 
     8 
    7 

이것을 도출하는 알고리즘의 중위 순회이고 그래프, 나가는 경로가 없을 때 각 다리에서 멈 춥니 다.

Answer 3

위의 그래프는주기가 있으므로 결코 트리로 표시 될 수 없습니다. 일반적으로 트리는 사이클이없는 연결된 그래프로 정의됩니다. 따라서 일반 그래프를 트리로 변환하는 유일한 방법은 사이클을 제거하고 필요한 경우 연결하는 것입니다.

편집 : 그래프가 조정되어 다시 DAG이 되겠지 만 다시 트리가 아니지만 몇 가지 흥미로운 속성이 있습니다.

Answer 4

는 문제는 여전히하지만 난 당신이 그래프 직렬화, 또는 위상 정렬 그래프의을 수행해야하는 느낌을 받고 있어요, 조금 불분명 남아있다. 사이클이 종속성 주기로 해석 될 수 있기 때문에 DAG에만 적용 할 수 있습니다.

Answer 5

(안 대답,하지만 내 제안 편집이 가짜 이유로 거부되었다.)

공식 문제 재 작성,이 질문에 대한 의견과 다른 하나

에 기반 입력은 입니다 ≤ _X (유한 집합 X), 꼭지점 X가있는 비순환 방향 그래프로 지정됩니다.출력은 일련의 한 요소 부분 주문 병렬 구성에 의해 특정 된 유한 집합 Y, 및지도 F에 series-parallel partial order ≤ _Y이다 명시 적으로 지정 Y → X, 예컨대, 그 때마다의 최대 체인 X < _x & hellip; < _{X X} N (= 입력 그래프 transitive reduction의 소스 - 싱크 경로) 정확히 하나 개의 최대 체인 Y에게 존재 _{1 < Y} 중 & hellip; < _Y Y ∈ 모든 J에 대한 F (Y _J) = J X _{와 N} {1, hellip ;, & N}. 우리는 | Y | 가능한 한 작아야한다.

Answer 6

당신이 보여주는 그림은 그 접근법이 끝에서부터 작동해야한다는 것을 암시합니다. 먼저, 자식이없는 노드 (이 경우에는 8과 7)를 찾습니다. 트리의 "이중 트렁크"를 형성합니다. 그런 다음 8과 7의 부모를 모두 찾으십시오. 부모가없는 모듈을 찾으십시오.이 경우 1. 이것을 조상이라고 부릅니다. 그것은 "끝점"입니다. 마지막으로 공통 노드 집합마다 "패밀리"를 선언합니다. 공통 노드를 가진 노드는 같은 노드가 둘 이상의 패밀리에 속할 수있는 경우에도 패밀리입니다. 부모가 하나 뿐인 노드는 해당 부모의 가족 중 일부입니다.

8를 들어, 당신은 찾을 수 5, 6 가족 A.

7의 경우, 4 가족 B. 7 단 하나의 부모가, 그래서 우리는 가족 B.

전화의 네 부분으로 전화를 찾을 수

이 "세대 2".

2 세대의 경우 부모를 찾습니다.

패밀리 A : 5 -> 2,3,4. 가족 C 6 -> 3,4. 패밀리 D

패밀리 B : 4 -> 1 - 확장 된 패밀리가 조상에 이릅니다. 이 경로는 이제 완료되었습니다. > 1 - 2 : 5 (가족 C)의

: 우리는 1-4-7 엔드 (모든 "가족 B")

이제 3 세대의 부모를 보면 하나 개의 경로를 캡처 할 수 있습니다 3 -> 1 4 -> 1 같은 부모의 같은 가족 구성원은 '가까운 형제 자매'이고 위와 아래의 <flow>이됩니다. 6 (가족 D)의

: 3 -> 1 4 -> 1 또 다른 가까운 가족

그리고이 가족 모두가 조상을 가리키는 결국 때문에, 우리가 서로를해야합니다

.

따라서 우리는 설명 된 모든 프로세스의 완전한 조상을 가지고 있습니다. 이제 위의 "패밀리"를 사용하여 플로우 맵으로 변환합니다.

Your desired XML - annotated with the families. You can see how this works 

<root> 
    <seq> 
     <mod1/> // the ancestor 
     <flow> 
      <seq> // family B - straight through. 
       <mod4/> 
       <mod7/> 
      </seq> 
      <seq> 
       <flow> 
        <seq> 
         <flow> // close family D 
          <mod4/> 
          <mod3/> 
         </flow> 
         <mod6/> // child of D 
        </seq> 
        <seq> 
         <flow> // close family C 
          <mod4/> 
          <mod3/> 
          <mod2/> 
         </flow> 
         <mod5/> // child of C 
        </seq> 
       </flow> 
       <mod8/> 
      </seq> 
     </flow> 
    </seq> 
</root> 

이 도움이 되었습니까, 아니면 완전히 해제 되었습니까?

편집 : "중간에 폐쇄 흐름"의 주제에, 다음과 같은 생각 :

가족이 다른 가족과 같은 (그랜드) 아이가, 그들은 같은 (그랜드) 부모가있는 경우

, 그들의 흐름은 그 수준에서 결합 될 수 있습니다. 이를 발견하려면 각 가족과 함께 "직계"목록을 유지해야하며이 목록을 반복적으로 검색하여 모든 가족이 공통 (웅대 한) 부모와 공통 (웅대 한) 자녀가있는 경우를 찾아야합니다. 일반적인 방법으로이를 통해 작업하기 내가 오늘 밤에 투입 할 수있는 것보다 조금 더 많은 노력을 할 것이다, 당신은 당신이 솔루션에 가까운 표시했기 때문에 내가 마지막으로 ... 여기