Một số kỹ thuật tối thiểu hóa chồng chéo cạnh khi đặt ra biểu đồ là gì? (Tốt nhất là liên quan đến GraphViz) Ngoài ra có bất kỳ phần mềm hiện có nào có thể bố trí một đồ thị theo kiểu phẳng không?Sơ đồ khối phẳng Planar
Current Layout - http://www.evecakes.com/doodles/master.gif
Phần màu hồng ở góc trên bên trái có vẻ tốt đẹp trong khi phần ánh sáng màu xanh có một số lợi thế cạnh tránh chồng chéo.
Đối với đồ thị chung, vấn đề xác định bố cục phẳng của biểu đồ có ít cạnh nhất (Crossing Number) là NP-hard. Vì vậy, một số phương pháp heuristic được sử dụng (như các thuật toán Force based layout).
Trang dưới đây mô tả ngắn gọn thuật toán graphviz và đề xuất một số cách để sử dụng chúng cho lợi ích. Nó cũng có các liên kết đến các file PDF mà nên chứa thêm thông tin về thuật toán:
http://rss.acs.unt.edu/Rdoc/library/Rgraphviz/html/GraphvizLayouts.html
Hy vọng rằng sẽ giúp.
Liên kết bị hỏng. –
Nếu đồ thị là phẳng thì bạn có thể tạo một đường nhúng với các cạnh ngang không (vì đó là định nghĩa biểu đồ phẳng) - xác định xem biểu đồ có thể đạt được trong thời gian 'O (N) 'tuyến tính [1] hay không (https://archive.org/details/PlanarityTestingByPathAddition) [2] (https://dl.acm.org/citation.cfm?id=321852)] và nó là một nhỏ (và cũng 'O (N)') để tạo một nhúng. Đối với đồ thị không phẳng thì có, đó là NP-khó để tạo ra một nhúng với giao cắt cạnh tối thiểu nhưng nó không thể là một dàn/bố trí phẳng. – MT0
Thư viện Java nguồn mở sau đây có một vài thuật toán có thể giúp đặt ra đồ thị phẳng. http://open.trickl.com/trickl-graph/index.html
Đặc biệt, các lớp sau đây cung cấp các giải pháp phân tích để các vấn đề:
ChrobakPayneLayout (dựa trên Boost C++ thực hiện bởi Aaron Windsor) http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html
FoldFreeLayout (dựa trên Neo Bản địa hóa phân phối miễn phí trong Mạng cảm biến * Nissanka B. Priyantha, Hari Balakrishnan, Erik Demaine và Seth Teller)
Những gì bạn có thể muốn làm là sử dụng một cái gì đó như thế này như là "nỗ lực" đầu tiên đảm bảo không có chồng chéo, mặc dù có thể không nhìn tuyệt vời. Sau đó, bạn có thể áp dụng một thuật toán lực-đạo để không gian ra các nút công bằng hơn.
Thật không may, thư viện vừa mới được phát hành nên không có tài liệu. Tuy nhiên nó có thể hữu ích bằng cách cung cấp một số mã thực tế thay vì chỉ là lý thuyết.
Bạn có muốn biết cách tối ưu hóa đầu ra của graphviz hay cách thực hiện tối ưu hóa chồng chéo cạnh nhau không? –
Chủ yếu là các cựu nhưng tôi quan tâm đến sau này quá. – jameszhao00
Tôi đã nghiên cứu thêm và đối với biểu đồ có kích thước của tôi, bố cục đa tỷ lệ là tùy chọn duy nhất. Vì vậy, tại thời điểm này tôi đang xem SFDP. Một thuộc tính SFDP quan trọng là cấp, trong đó xác định số lượng cân bạn muốn. – jameszhao00