Vẽ đồ thị với các cạnh có trọng số

Question

Tôi đang tìm cách xây dựng một thuật toán (hoặc sử dụng lại một) để tổ chức các nút và cạnh trên canvas 2 chiều, trong đó các cạnh có thể có các trọng số tương ứng.

Bất kỳ tài liệu bắt đầu và thông tin nào đều hữu ích.

Answer 1

Trọng lượng sẽ ảnh hưởng đến vị trí của chúng trên canvas của bạn là bao nhiêu?

Điều đó đang được nói, bạn có thể muốn xem xét graphviz và cụ thể hơn là ngôn ngữ DOT, tổ chức các nút trên canvas.

Nhiều khung hình trực quan hóa đồ thị sử dụng mô phỏng dựa trên lực, trong đó tất cả các nút tạo lực đẩy với nhau (với khối lượng của chúng là kích thước của chúng) và các cạnh gây căng thẳng trên các nút mà chúng kết nối. Điều này tạo ra các hình ảnh đồ thị được sắp xếp theo thẩm mỹ.

Mặc dù một lần nữa, tôi không chắc chắn nơi bạn muốn nút "trọng số" đi vào chơi. Bạn có muốn các nút có trọng số cao hơn ở trung tâm không? Để lớn hơn? Xa hơn?

Answer 2

Nhiều thuật toán bố cục đồ thị/mạng hoàn toàn có khả năng xử lý các mạng có trọng số, nhưng bạn có thể cần thực hiện một số xử lý trước và chỉnh sửa để triển khai để làm cho nó hoạt động. Thông thường bước đầu tiên là xác định xem trọng số của bạn đại diện cho "điểm tương đồng" (thường được hiểu là có nghĩa là trọng số mạnh hơn nên đặt nút gần nhau hơn) hay "khác nhau" (trọng lượng mạnh hơn = cha cách nhau). Trường hợp phổ biến nhất là trường hợp cũ, vì vậy bạn sẽ cần dịch chúng sang các điểm khác nhau, thường được thực hiện bằng cách trừ đi từng giá trị cạnh từ giá trị cạnh được quan sát tối đa trong mạng. Ma trận của các giá trị khác nhau cho mỗi cạnh có thể được đưa vào thuật toán và được hiểu là khoảng cách mong muốn trong không gian bố trí cho mỗi cạnh (tức là "độ dài mùa xuân") - thường sau khi nhân với một số hằng số để chuyển đổi sang đơn vị hiển thị (pixel) .

Nếu bạn cho tôi biết bạn đang sử dụng ngôn ngữ nào, tôi có thể chỉ cho bạn một số ví dụ về mã.