Mẫu hoặc thuật toán hợp nhất các nhánh trong cấu trúc cây?

Question

Tôi đang cố gắng ánh xạ DAG (Đồ thị tuần hoàn hướng) vào cấu trúc tôi hiển thị bên dưới.

Dưới đây là một ví dụ về DAG tôi bắt đầu từ

nơi cung luôn đi từ trái sang phải.

sau đó tôi trở lại đồ thị và span nó vào một cái cây với các nút lặp đi lặp lại như thế này:

Những gì tôi đang tìm kiếm một số thuật toán hoặc mẫu để đạt được cơ cấu sáp nhập sau đây là. (Lưu ý nó được quay trở lại)

Mục đích là để tạo ra một XML như thế này:

<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> 

Tôi không nghĩ rằng nó có liên quan nhưng tôi phân tích cú pháp JSON để viết một XML với JAVA 7. Các hộp là các dịch vụ web và các mũi tên đại diện cho các tham số đầu vào và đầu ra, ví dụ, Mô-đun 5 được gọi là Mô-đun 1,2,3 và 4 đã hoàn thành và đầu ra của chúng là đầu vào của nó.

EDIT: Ok, đây là một ví dụ khác với mười nút. Tôi hy vọng điều này sẽ mang lại cho bạn một sự đánh giá cao hơn khi các nút của tôi được hợp nhất.

Để trả lời @blubb, trong ví dụ này chúng ta có thể xem như thế nào "dịch vụ" 8 & 9 cũng đã được sáp nhập. Nếu không, tất cả các dịch vụ mà họ cần để làm việc (1,2,3,4,5 và 6) sẽ được gọi hai lần mà không cần. Nhánh giữa trong bản phác thảo cuối cùng sẽ được thực hiện hai lần: một lần cho 8 và một lần cho 9.

Answer 1

Cuối cùng, tôi đã tìm thấy một thuật toán đã làm công việc. Ở đây, tất cả các bạn đã cố gắng giúp tôi:

Trước hết tôi xây dựng một cây bao trùm ngược từ DAG trong phác thảo 1. Vì vậy, tôi bắt đầu từ mô-đun 7 và 8, xây dựng cây ngược và nơi mô-đun được nhân đôi.

Sau đó tôi tạo các nút ảo có tên FLOW và SEQUENCE và giới thiệu chúng trong cây sao cho mỗi nút MODULE là nút con của nút SEQUENCE. Các nhánh mở rộng là các nút SEQUENCE là các nút con của các nút FLOW. Tôi nghĩ rằng đây là bước đủ trực quan nhưng ý tưởng quan trọng là phải hiểu rằng chúng ta cần các nút ảo để chúng ta có thể đóng các nút FLOW, là các nút tách ra từ một nút đến nhiều nút.

Sau đó, tôi đi qua độ sâu cây đầu tiên, và cho mỗi mô-đun (chúng tôi sẽ gọi nó là trình điều khiển) tôi so sánh con của nó với con của anh chị em của người lái xe. Nếu họ không phù hợp với tôi tiếp tục đi xuống với các cháu của anh chị em của lái xe, do đó, tất cả các chi nhánh ra khỏi anh chị em của người lái xe phải đi qua các nút tương tự như người lái xe. Đồ họa này có nghĩa là tại một số điểm, cả hai nút cần cùng một mô-đun chính xác.

Nếu chúng khớp với nhau, tôi làm sạch các nhánh ghép từ các nút trùng khớp xuống dưới, điều này có nghĩa là tôi cắt chúng ra khỏi bố mẹ. Từ đó trở đi nó đi vào một nút SEQUENCE mới cùng với nút SEQUENCE của trình điều khiển, vào cùng một nút FLOW.

Sau khi đi qua toàn bộ cây, miễn là hợp nhất đã được thực hiện, chúng tôi đi qua cây một lần nữa, lần này với một mối quan hệ lớn hơn. Điều này có nghĩa là thay vì so sánh trẻ em của lái xe, chúng tôi so sánh những đứa trẻ tuyệt vời của tài xế.

Bước cuối cùng rõ ràng là hoàn nguyên lại cây.

Có một số khái niệm tôi đã bỏ sang một bên vì sự phức tạp của chương trình của các nút ảo này hàm ý.Chủ yếu là do tất cả các mối quan hệ cha-con-anh chị em bị mất một khi các nút ảo đã được giới thiệu. Nhưng tôi hy vọng ý tưởng chung đã được hiểu.

Answer 2

Tôi không biết nhiều về cấu trúc dữ liệu cây, mà tôi tưởng tượng có thể là nhà ở tốt cho kết quả, và tôi ' m không quá am hiểu về việc chuyển đổi sang XML, nhưng nếu tôi đã đưa ra dữ liệu với các tuyến đường vạch ra, ví dụ,

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

sau đó có một cách để kết hợp các nút có thể là:

Take increasingly larger chunks from the end of each line and examine the 
first cell to the left of them. Nodes are merged if matching right-side 
chunks flow to the same aggregated first cells on the left. Remove duplicate 
paths. 

Giải thích/ví dụ:

Đầu tiên vượt qua (lấy tế bào kết thúc, so sánh với các tế bào đầu tiên tổng hợp để bên trái của họ):

4 <- 7 
    5,6 <- 8 
    5,6 <- 9 
    2,5 <- 10 

Các nút duy nhất có thể được sáp nhập là 8 và 9 vì cả hai dòng chảy cho cùng một ô tổng hợp (5,6).

Kết quả đầu tiên vượt qua:

1 4 7 
1 2 5 (8,9) -- merged 
1 3 5 (8,9) 
1 4 5 (8,9) 
1 3 6 (8,9) 
1 2 5 (8,9) 
1 3 5 (8,9) 
1 4 5 (8,9) 
1 3 6 (8,9) 
1 2 10 
1 2 5 10 
1 3 5 10 
1 4 5 10 

Thứ hai vượt qua (lấy tế bào cuối + 1 tế bào, so sánh với các tế bào đầu tiên tổng hợp để bên trái):

1  <- 4 7 
    2,3,4 <- 5 (8,9) 
    3  <- 6 (8,9) 
    1  <- 2 10 
    2,3,4 <- 5 10 

Không có thể được hợp nhất vì không có đường dẫn bên phải nào phù hợp với cùng một ô được tổng hợp đầu tiên ở bên trái của chúng.

Thứ ba đường chuyền (lấy tế bào cuối + 2 tế bào, so sánh với các tế bào đầu tiên tổng hợp để bên trái):

N/A <- 1 4 7 
    1  <- 2 5 (8,9) 
    1  <- 3 5 (8,9) 
    1  <- 4 5 (8,9) 
    1  <- 3 6 (8,9) 
    N/A <- 1 2 10 
    1  <- 2 5 10 
    1  <- 3 5 10 
    1  <- 4 5 10 

Hai hòa trộn là có thể. Thứ nhất: [2 5 (8,9)], [3 5 (8,9)] và [4 5 (8,9)] tất cả lưu lượng đến 1. Thứ hai: [2 5 10], [3 5 10] và [4 5 10] tất cả các dòng chảy để 1.

kết quả vượt qua thứ ba:

1 4 7 
1 (2,3,4) 5 (8,9) 
1 3 6 (8,9) 
1 2 10 
1 (2,3,4) 5 10 

Trông rất giống kết quả yêu cầu đối với tôi. (Các ô trùng lặp ở hai đầu có thể được hợp nhất thành các nút đơn, ví dụ, 1 ở bên trái, và (8,9) và 10 ở bên phải, như trong bản phác thảo cuối cùng của eskalera.)