Có một thuật toán được thiết lập để tìm các cạnh dư thừa trong biểu đồ không?Thuật toán để tìm các cạnh dư thừa trong biểu đồ hoặc cây
Ví dụ, tôi muốn để thấy rằng a-> d và a-> e là không cần thiết, và sau đó để loại bỏ chúng, như thế này:
=>
Chỉnh sửa: Strilanc đủ tốt để đọc suy nghĩ của tôi cho tôi. "Dự phòng" quá mạnh của một từ, vì trong ví dụ trên, không phải a-> b hoặc a-> c được coi là dư thừa, nhưng a-> d là.
Bạn muốn tính toán biểu đồ nhỏ nhất duy trì khả năng hiển thị đỉnh.
Đây được gọi là transitive reduction của biểu đồ. Bài viết wikipedia sẽ giúp bạn bắt đầu đi đúng con đường.
Cảm ơn, đó là chính xác những gì tôi đang tìm kiếm. Bài báo trên Wikipedia thậm chí còn đề cập đến 'tred' cho Graphviz, đặc biệt hữu ích, vì đó là những gì tôi đang làm việc. –
Nó đây rồi. Tôi có thể thấy sự đóng cửa chuyển tiếp đã gần. –
Biểu đồ con của biểu đồ nhất định không chứa "cạnh dự phòng" được gọi là 'spanning tree' của biểu đồ đó. Đối với bất kỳ biểu đồ nào, có thể có nhiều cây bao trùm.
Vì vậy, để loại bỏ các cạnh dư thừa, tất cả những gì bạn cần làm là tìm bất kỳ cây bao trùm nào trong biểu đồ của bạn. Bạn có thể sử dụng bất kỳ thuật toán depth-first-search hoặc breadth-first-search nào và tiếp tục tìm kiếm cho đến khi bạn đã truy cập mọi đỉnh trong biểu đồ.
Đó là muộn, nhưng là những gì ông mô tả thực sự là một cây bao trùm? –
Có. Anh ta muốn có một biểu đồ con chứa tất cả các đỉnh của đồ thị ban đầu chỉ với một cách để đạt được từ đỉnh này sang đỉnh khác. Đó chính xác là cái cây bao trùm. –
Không, ngay cả trong biểu đồ giảm có 2 cách để đi từ a đến d. – xuanji
Kiểm tra này: Minimum Spanning Tree
Nếu tất cả những gì anh ta cần là loại bỏ các cạnh dư thừa, anh ta không phải lo lắng về cây bao trùm _minimum_. Bất kỳ cây bao trùm ole sẽ làm. –
Cũng nên nhớ "Với đồ thị được kết nối, không bị chiếu xạ, một cây bao trùm của biểu đồ đó là một đồ thị con là một cây và kết nối tất cả các đỉnh với nhau." Tuy nhiên, đồ thị của anh ta không bị vô hướng. –
Một số cách để tấn công này, nhưng trước tiên bạn sẽ cần phải xác định vấn đề hơn một chút chính xác. Đầu tiên, đồ thị bạn có ở đây là theo chu kỳ và hướng dẫn: điều này có đúng không?
Tiếp theo, bạn cần phải xác định ý mình là "cạnh dự phòng". Trong trường hợp này, bạn bắt đầu với một đồ thị có hai đường dẫn a-> c: một đường thẳng qua b và một đường thẳng. Từ điều này tôi suy luận rằng bởi "dư thừa", bạn có nghĩa là một cái gì đó như thế này. Hãy G = < V, E> là một đồ thị, với V bộ đỉnh và E ⊆ V × V tập các cạnh. Có vẻ như bạn đang xác định tất cả các cạnh từ v i đến v j ngắn hơn cạnh dài nhất là "dự phòng". Vì vậy, điều dễ nhất là sử dụng tìm kiếm độ sâu đầu tiên, liệt kê các đường dẫn và khi bạn tìm thấy một đường dẫn mới dài hơn, hãy lưu nó làm ứng cử viên tốt nhất.
Tôi không thể tưởng tượng điều bạn muốn. Bạn có thể nói?
Tôi nghĩ rằng cách dễ nhất để làm điều đó, thực sự tưởng tượng như thế nào nó sẽ tìm trong các công việc thực tế, hãy tưởng tượng nếu bạn có khớp, Giống như
(A-> B) (B-> C) (A- > C), hãy tưởng tượng nếu khoảng cách giữa gần các đồ thị là bằng 1, vì vậy
(A-> B) = 1, (B-> C) = 1, (A-> C) = 2.
Vì vậy, bạn có thể loại bỏ khớp (A-> C).
Nói cách khác, hãy thu nhỏ.
Đây chỉ là ý tưởng của tôi làm thế nào tôi sẽ suy nghĩ về nó lúc bắt đầu. Có nhiều bài báo và nguồn khác nhau trên mạng, bạn có thể xem chúng và đi sâu hơn.
Tài nguyên, mà sẽ giúp bạn:
Algorithm for Removing Redundant Edges in the Dual Graph of a Non-Binary CSP
Graph Data Structure and Basic Graph Algorithms
Google Books, On finding minimal two connected Subgraphs
Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs
Loại giảm đồ thị này được gọi cụ thể là giảm giảm trong các thuật ngữ được đặt theo lý thuyết, bằng cách này: http://en.wikipedia.org/wiki/Transitive_reduction – Gracenotes
Vâng, nhưng bạn vẫn có thể sử dụng thuật toán từ các khu vực khác nhau để giải quyết vấn đề này vấn đề, theo nhu cầu của bạn. –
Tôi đã có một vấn đề tương tự và kết thúc giải quyết nó theo cách này:
cấu trúc dữ liệu của tôi được làm bằng dependends từ điển, từ một node id vào một danh sách các nút phụ thuộc vào nó (tức là tín đồ của nó trong. DAG). Lưu ý rằng nó chỉ hoạt động đối với một DAG - đó là đồ thị theo hướng, tuần hoàn.
Tôi chưa tính độ phức tạp chính xác của nó, nhưng nó nuốt đồ thị của tôi vài nghìn lần trong một giây.
_transitive_closure_cache = {}
def transitive_closure(self, node_id):
"""returns a set of all the nodes (ids) reachable from given node(_id)"""
global _transitive_closure_cache
if node_id in _transitive_closure_cache:
return _transitive_closure_cache[node_id]
c = set(d.id for d in dependents[node_id])
for d in dependents[node_id]:
c.update(transitive_closure(d.id)) # for the non-pythonists - update is update self to Union result
_transitive_closure_cache[node_id] = c
return c
def can_reduce(self, source_id, dest_id):
"""returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
for d in dependents[source_id]:
if d.id == dest_id:
continue
if dest_id in transitive_closure(d.id):
return True # the dest node can be reached in a less direct path, then this link is redundant
return False
# Reduce redundant edges:
for node in nodes:
dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]
chỉ muốn bình luận về các câu trả lời trước - Giảm các cạnh thừa không giống như Spanning Tree, thậm chí không giống như Spanning Tree tối thiểu. Và nếu một đường dẫn từ A đến B dài hơn một đường dẫn khác từ A đến B thì nó không có nghĩa là bất kỳ thứ gì về các cạnh (nếu có) là thừa. Trong ví dụ trên, bạn có thể xây dựng một cây bao trùm không có cạnh a-> b nhưng nó không thừa. – Iftah
Thay vào đó, chúng tôi có thể xem xét B ---> C để dự phòng không? –
Liệu dự phòng có nghĩa là "một cạnh X-> Y là dư thừa nếu có một đường dẫn không cạnh từ X đến Y" hay bạn chỉ đơn giản là tìm kiếm một cây bao trùm? –
@ Zach: Không, B-> C không thừa, vì nếu nó bị xóa, không có đường dẫn nào trong biểu đồ kết quả từ B đến C. – ShreevatsaR