Làm cách nào để sắp xếp biểu đồ tuyến tính mà không chồng chéo?

Question

Tôi đang cố gắng viết một plugin cho Blender tự động sắp xếp một nút cây gọn gàng, không có chồng chéo hoặc các kết nối chảy sang trái. Tôi có quyền truy cập vào danh sách các nút, vị trí của chúng, kích thước của chúng và danh sách các kết nối/liên kết. Biểu đồ chạy từ trái sang phải và có thể có nhiều nút bắt đầu và kết thúc. Sản lượng của một node không thể kết nối với đầu vào của một nút trước đó, hoặc đó là đầu vào của riêng

Có ai biết của một bài báo hoặc bài viết tập trung vào mã hóa một cái gì đó mà có thể tắt chức năng này (không phụ thuộc cyclic.):

?

Phương pháp tôi đã tạo ban đầu là: Đối với tất cả các nút không có kết nối đầu vào, hãy xếp hàng chúng ở bên trái. Đối với tất cả các nút được kết nối với các nút bắt đầu này, đặt chúng ở bên phải của nút bắt đầu kết nối. Lặp lại điều này cho mỗi nút cho đến khi kết thúc. Nếu một nút chồng lên nhau, di chuyển nó và chuỗi các nút sang phải, xuống.

này làm việc tuyệt vời cho mỗi chuỗi bị cô lập, nhưng khi một nút của một chuỗi kết nối với một nút của người khác (một chi nhánh kết nối trở lại thân cây chẳng hạn), nó sẽ thường có một kết nối ngược:

Phương pháp này tôi đã đưa ra có vẻ khá ... thô. Tôi đã đọc một chút về bố cục Spring Force-Directed, nhưng chúng dường như nhiều hơn cho các đồ thị chảy theo bất kỳ/tất cả các hướng nào và tôi không hoàn toàn chắc chắn cách tôi thực hiện thủ công ở đây dù sao, vì tôi ' m hạn chế sử dụng toán học lõi một mình mà không có thư viện bên ngoài khác.

Nó không chính xác là một vấn đề phổ biến, nhưng tôi là người đầu tiên cố gắng tìm ra nó. Tôi không yêu cầu mã ví dụ chính xác, chỉ cần một cái gì đó để xem xét để giúp tôi làm việc ra một thuật toán phong nha.

Answer 1

Thay vì cố gắng tạo ra hệ thống hoàn hảo, tôi quyết định bắt buộc phải vẽ đồ thị gọn gàng bằng cách tự sửa từng vấn đề, thay vì ngăn chặn nguyên nhân. Đó là thô, đó là chậm và đó là xa lý tưởng, nhưng nó hoạt động:

tôi sẽ phát hành nó dưới dạng GNU khi nó hoàn thiện hơn, nhưng bây giờ đây là cốt lõi của nó: http://www.pasteall.org/43213/python

EDIT: Đã phát hành: http://wiki.blender.org/index.php/Extensions:2.6/Py/Scripts/Nodes/Node_Wrangler

Answer 2

A topological sort các nút, nếu nút đó tồn tại, sẽ cung cấp cho bạn thứ tự các nút chính xác để hiển thị. Nếu hai nút không liên quan nhưng được sắp xếp liền kề, chúng có thể được đặt ở cùng một tọa độ X nếu bạn muốn.

Nói chung, vẽ cây với khoảng cách thích hợp là NP-hoàn thành [xem tài liệu tham khảo tại Drawing Presentable Trees, bởi Bill Mill] và vẽ đồ thị không dễ dàng hơn.

Answer 3

tôi sẽ sử dụng GraphViz cho việc này: http://www.graphviz.org/

1. đọc đồ thị Máy xay sinh tố của bạn vào bộ nhớ
2. Viết ra cùng một đồ thị trong định dạng GraphViz đồ thị tập tin
3. Chạy một trong những thực thi GraphViz (Tôi sẽ đề xuất dot (link))
4. Đọc biểu đồ tương đương nhưng có vị trí nút được tạo bởi GraphViz
5. Viết biểu đồ Máy xay sinh tố của bạn, với các vị trí được sửa đổi dựa trên kết quả của GraphViz

Trừ khi bạn muốn vì lý do học tập, không phát minh lại bánh xe. Cách tiếp cận này nên dễ thực hiện, và nó sẽ không yêu cầu thiết kế một thuật toán bố cục đồ thị phức tạp.