`graphlib` --- Chức năng hoạt động với các cấu trúc giống như đồ thị¶

class graphlib.TopologicalSorter(graph=None)¶

Cung cấp chức năng sắp xếp theo cấu trúc liên kết biểu đồ của các nút hashable.

Thứ tự tôpô là thứ tự tuyến tính của các đỉnh trong đồ thị sao cho với mọi cạnh có hướng u -> v từ đỉnh u đến đỉnh v, đỉnh u xuất hiện trước đỉnh v theo thứ tự. Ví dụ: các đỉnh của biểu đồ có thể biểu thị các nhiệm vụ cần thực hiện và các cạnh có thể biểu thị các ràng buộc mà một nhiệm vụ phải được thực hiện trước một nhiệm vụ khác; trong ví dụ này, thứ tự tôpô chỉ là một chuỗi hợp lệ cho các tác vụ. Có thể sắp xếp thứ tự tôpô hoàn chỉnh khi và chỉ khi đồ thị không có chu trình có hướng, nghĩa là nếu nó là đồ thị không có chu trình có hướng.

Nếu đối số graph tùy chọn được cung cấp thì đó phải là một từ điển biểu thị biểu đồ tuần hoàn có hướng trong đó các khóa là các nút và các giá trị là các giá trị có thể lặp lại của tất cả các nút trước của nút đó trong biểu đồ (các nút có các cạnh trỏ đến giá trị trong khóa). Các nút bổ sung có thể được thêm vào biểu đồ bằng phương pháp add().

Trong trường hợp chung, các bước cần thiết để thực hiện sắp xếp một biểu đồ đã cho như sau:

Tạo một phiên bản của TopologicalSorter với biểu đồ ban đầu tùy chọn.
Thêm các nút bổ sung vào biểu đồ.
Gọi prepare() trên đồ thị.
Trong khi is_active() là True, hãy lặp lại các nút được get_ready() trả về và xử lý chúng. Gọi done() trên mỗi nút khi nó xử lý xong.

Trong trường hợp chỉ cần sắp xếp ngay lập tức các nút trong biểu đồ và không liên quan đến tính song song, phương thức tiện lợi TopologicalSorter.static_order() có thể được sử dụng trực tiếp:

>>> đồ thị = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(đồ thị)
>>> bộ dữ liệu(ts.static_order())
('A', 'C', 'B', 'D')

Lớp này được thiết kế để dễ dàng hỗ trợ xử lý song song các nút khi chúng sẵn sàng. Ví dụ:

topological_sorter=TopologicalSorter()

các nút # Add thành 'topological_sorter'...

topo_sorter.prepare()
trong khi topological_sorter.is_active():
    cho nút trong topological_sorter.get_ready():
        các luồng hoặc quy trình # Worker yêu cầu các nút hoạt động ngoài
        # hàng đợi 'task_queue'.
        task_queue.put(nút)

    # When công việc của một nút đã hoàn tất, công nhân đã đưa nút vào
    # 'finalized_tasks_queue' để chúng tôi có thể có thêm nút để làm việc.
    Định nghĩa # The của 'is_active()' đảm bảo rằng, tại thời điểm này, tại
    # least một nút đã được đặt trên 'task_queue' nhưng vẫn chưa
    # been được chuyển tới 'done()', vì vậy việc chặn 'get()' này phải (cuối cùng)
    # succeed.  Sau khi gọi 'done()', chúng ta lặp lại để gọi 'get_ready()'
    # again, vì vậy hãy đặt các nút mới được giải phóng vào 'task_queue' ngay khi
    # logically có thể.
    nút = Finalized_tasks_queue.get()
    topo_sorter.done(nút)

add(node, *predecessors)¶

Thêm một nút mới và các nút trước đó vào biểu đồ. Cả node và tất cả các phần tử trong predecessors đều phải là hashable.

Nếu được gọi nhiều lần với cùng một đối số nút, tập hợp các phần phụ thuộc sẽ là tập hợp của tất cả các phần phụ thuộc được truyền vào.

Có thể thêm một nút không có phần phụ thuộc (predecessors không được cung cấp) hoặc cung cấp phần phụ thuộc hai lần. Nếu một nút chưa được cung cấp trước đó được bao gồm trong predecessors, nó sẽ tự động được thêm vào biểu đồ mà không có nút trước đó.

Tăng ValueError nếu được gọi sau prepare().

prepare()¶

Đánh dấu biểu đồ là đã hoàn thành và kiểm tra các chu kỳ trong biểu đồ. Nếu phát hiện bất kỳ chu kỳ nào, CycleError sẽ được tăng lên, nhưng get_ready() vẫn có thể được sử dụng để thu được càng nhiều nút càng tốt cho đến khi các chu kỳ chặn nhiều tiến trình hơn. Sau khi gọi hàm này, biểu đồ không thể được sửa đổi và do đó không thể thêm nút nào nữa bằng add().

Một ValueError sẽ được nâng lên nếu việc sắp xếp được bắt đầu bởi static_order() hoặc get_ready().

Thay đổi trong phiên bản 3.14: prepare() bây giờ có thể được gọi nhiều lần miễn là việc sắp xếp chưa bắt đầu. Trước đây điều này đã gây ra ValueError.

is_active()¶

Trả về True nếu có thể thực hiện được nhiều tiến bộ hơn và trả về False nếu ngược lại. Tiến trình có thể được thực hiện nếu các chu kỳ không chặn độ phân giải và vẫn còn các nút sẵn sàng chưa được TopologicalSorter.get_ready() trả về hoặc số nút được đánh dấu TopologicalSorter.done() ít hơn số được TopologicalSorter.get_ready() trả về.

Phương thức __bool__() của lớp này trì hoãn chức năng này, vì vậy thay vì

nếu ts.is_active():
    ...

có thể chỉ cần làm:

nếu ts:
    ...

Tăng ValueError nếu được gọi mà không gọi prepare() trước đó.

done(*nodes)¶

Đánh dấu một tập hợp các nút được TopologicalSorter.get_ready() trả về là đã được xử lý, bỏ chặn mọi nút kế thừa của mỗi nút trong nodes để được trả về trong tương lai bằng lệnh gọi tới TopologicalSorter.get_ready().

Tăng ValueError nếu bất kỳ nút nào trong nodes đã được đánh dấu là đã được xử lý bằng lệnh gọi trước đó tới phương thức này hoặc nếu một nút không được thêm vào biểu đồ bằng cách sử dụng TopologicalSorter.add(), nếu được gọi mà không gọi prepare() hoặc nếu nút chưa được get_ready() trả về.

get_ready()¶

Trả về tuple với tất cả các nút đã sẵn sàng. Ban đầu, nó trả về tất cả các nút không có nút trước đó và khi các nút đó được đánh dấu là đã xử lý bằng cách gọi TopologicalSorter.done(), các lệnh gọi tiếp theo sẽ trả về tất cả các nút mới có tất cả các nút trước đó đã được xử lý. Khi không thể thực hiện được tiến trình nào nữa, các bộ dữ liệu trống sẽ được trả về.

Tăng ValueError nếu được gọi mà không gọi prepare() trước đó.

static_order()¶

Trả về một đối tượng iterator sẽ lặp qua các nút theo thứ tự tôpô. Khi sử dụng phương pháp này, không nên gọi prepare() và done(). Phương pháp này tương đương với:

def static_order(tự):
    tự.prepare()
    trong khi self.is_active():
        node_group = self.get_ready()
        lợi nhuận từ node_group
        self.done(*node_group)

Thứ tự cụ thể được trả về có thể phụ thuộc vào thứ tự cụ thể mà các mục được chèn vào biểu đồ. Ví dụ:

>>> ts = TopologicalSorter()
>>> ts.add(3, 2, 1)
>>> ts.add(1, 0)
>>> print([*ts.static_order()])
[2, 0, 1, 3]

>>> ts2 = TopologicalSorter()
>>> ts2.add(1, 0)
>>> ts2.add(3, 2, 1)
>>> print([*ts2.static_order()])
[0, 2, 1, 3]

Điều này là do thực tế là "0" và "2" ở cùng cấp độ trong biểu đồ (chúng sẽ được trả về trong cùng một lệnh gọi tới get_ready()) và thứ tự giữa chúng được xác định theo thứ tự chèn.

Nếu phát hiện bất kỳ chu kỳ nào, CycleError sẽ được nâng lên.

Added in version 3.9.

Ngoại lệ¶

Mô-đun graphlib xác định các lớp ngoại lệ sau:

exception graphlib.CycleError¶

Lớp con của ValueError được tạo ra bởi TopologicalSorter.prepare() nếu tồn tại các chu trình trong biểu đồ đang hoạt động. Nếu có nhiều chu kỳ tồn tại, chỉ một lựa chọn không xác định trong số đó sẽ được báo cáo và đưa vào ngoại lệ.

Chu trình được phát hiện có thể được truy cập thông qua phần tử thứ hai trong thuộc tính args của phiên bản ngoại lệ và bao gồm một danh sách các nút, sao cho mỗi nút, trong biểu đồ, là tiền thân trực tiếp của nút tiếp theo trong danh sách. Trong danh sách được báo cáo, nút đầu tiên và nút cuối cùng sẽ giống nhau, để làm rõ rằng nó có tính tuần hoàn.

`graphlib` --- Chức năng hoạt động với các cấu trúc giống như đồ thị¶

Ngoại lệ¶

Table of Contents

Chủ đề trước

Chủ đề tiếp

Trang này

graphlib --- Chức năng hoạt động với các cấu trúc giống như đồ thị¶

Ngoại lệ¶

`graphlib` --- Chức năng hoạt động với các cấu trúc giống như đồ thị¶