graphlib --- قابلیت کار با ساختارهای گراف‌مانند¶

کد منبع: Lib/graphlib.py

class graphlib.TopologicalSorter(graph=None)¶

امکان مرتب‌سازی توپولوژیک گرافی از گره‌های هش‌پذیر را فراهم می‌کند.

یک ترتیب توپولوژیک، یک ترتیب خطی از رأس‌های یک گراف است، به‌گونه‌ای که برای هر یال جهت‌دار u -> v از رأس u به رأس v، رأس u در آن ترتیب پیش از رأس v می‌آید. برای نمونه، رأس‌های گراف ممکن است نشان‌دهنده‌ی وظایفی باشند که باید انجام شوند، و یال‌ها ممکن است نشان‌دهنده‌ی قیدهایی باشند که بر اساس آن‌ها یک وظیفه باید پیش از وظیفه‌ی دیگر انجام شود؛ در این مثال، یک ترتیب توپولوژیک صرفاً یک دنباله‌ی معتبر برای وظایف است. یک ترتیب توپولوژیک کامل ممکن است اگر و تنها اگر گراف هیچ دور جهت‌داری نداشته باشد، یعنی اگر آن گراف یک گراف جهت‌دار بدون دور باشد.

اگر آرگومان اختیاری graph ارائه شود، باید یک دیکشنری باشد که یک گراف جهت‌دار بدون دور را نشان می‌دهد؛ به‌طوری که کلیدها گره‌ها هستند و مقادیر، پیمایش‌پذیرهایی از تمام پیشینیان آن گره در گراف هستند (گره‌هایی که یال‌هایی دارند که به مقدار کلید اشاره می‌کنند). می‌توان گره‌های بیشتری را با استفاده از متد add() به گراف اضافه کرد.

در حالت کلی، مراحل مورد نیاز برای انجام مرتب‌سازی یک گراف داده‌شده به شرح زیر است:

• یک نمونه از TopologicalSorter با یک گراف اولیه اختیاری ایجاد کنید.

• گره‌های بیشتری به گراف اضافه کنید.

• prepare() را روی گراف فراخوانی کنید.

• تا زمانی که is_active() برابر True است، گره‌های بازگردانده‌شده توسط get_ready() را پیمایش کنید و آن‌ها را پردازش کنید. پس از پایان پردازش هر گره، done() را برای آن فراخوانی کنید.

در صورتی که تنها مرتب‌سازی فوری گره‌های گراف لازم باشد و موازی‌سازی در کار نباشد، می‌توان مستقیماً از متد کمکی TopologicalSorter.static_order() استفاده کرد:

>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')

این کلاس به‌گونه‌ای طراحی شده است که به‌راحتی از پردازش موازی گره‌ها به‌محض آماده شدن آن‌ها پشتیبانی کند. برای مثال:

topological_sorter = TopologicalSorter()

# Add nodes to 'topological_sorter'...

topological_sorter.prepare()
while topological_sorter.is_active():
    for node in topological_sorter.get_ready():
        # Worker threads or processes take nodes to work on off the
        # 'task_queue' queue.
        task_queue.put(node)

    # When the work for a node is done, workers put the node in
    # 'finalized_tasks_queue' so we can get more nodes to work on.
    # The definition of 'is_active()' guarantees that, at this point, at
    # least one node has been placed on 'task_queue' that hasn't yet
    # been passed to 'done()', so this blocking 'get()' must (eventually)
    # succeed.  After calling 'done()', we loop back to call 'get_ready()'
    # again, so put newly freed nodes on 'task_queue' as soon as
    # logically possible.
    node = finalized_tasks_queue.get()
    topological_sorter.done(node)

add(node, *predecessors)¶

یک گره جدید و پیش‌نیازهای آن را به گراف اضافه کنید. هم node و هم همه‌ی عناصر موجود در predecessors باید hashable باشند.

اگر چندین بار با همان آرگومان گره فراخوانی شود، مجموعه وابستگی‌ها اجتماع تمام وابستگی‌های ارسال‌شده خواهد بود.

می‌توانید گره‌ای بدون وابستگی اضافه کنید (وقتی predecessors ارائه نشده باشد) یا یک وابستگی را دو بار ارائه کنید. اگر گره‌ای که پیش‌تر ارائه نشده است جزو predecessors باشد، به‌طور خودکار به گراف اضافه می‌شود، بدون این‌که پیش‌نیازی از خود داشته باشد.

در صورت فراخوانی پس از prepare()، استثنای ValueError را پرتاب می‌کند.

prepare()¶

گراف را به‌عنوان پایان‌یافته علامت‌گذاری می‌کند و وجود دورها را در گراف بررسی می‌کند. اگر هرگونه دوری تشخیص داده شود، CycleError پرتاب خواهد شد، اما همچنان می‌توان از get_ready() برای دریافت تا حد ممکن از گره‌ها استفاده کرد، تا زمانی که دورها مانع پیشرفت بیشتر شوند. پس از فراخوانی این تابع، گراف قابل تغییر نیست و بنابراین دیگر نمی‌توان گره‌های بیشتری را با استفاده از add() اضافه کرد.

اگر مرتب‌سازی توسط static_order() یا get_ready() آغاز شده باشد، یک ValueError پرتاب خواهد شد.

تغییر یافته در نسخه‌ی 3.14: اکنون تا زمانی که مرتب‌سازی آغاز نشده باشد، می‌توان prepare() را بیش از یک بار فراخوانی کرد. پیش از این، این کار ValueError را پرتاب می‌کرد.

is_active()¶

در صورت امکان پیشرفت بیشتر، True و در غیر این صورت False برمی‌گرداند. پیشرفت در صورتی می‌تواند انجام شود که چرخه‌ها مانع از حل نشوند و یکی از دو شرط زیر برقرار باشد: هنوز گره‌های آماده‌ای وجود داشته باشند که TopologicalSorter.get_ready() آن‌ها را برنگردانده است، یا تعداد گره‌های علامت‌گذاری‌شده با TopologicalSorter.done() کمتر از تعداد گره‌هایی باشد که TopologicalSorter.get_ready() آن‌ها را برگردانده است.

متد __bool__() این کلاس به این تابع ارجاع می‌دهد، بنابراین به‌جای:

if ts.is_active():
    ...

می‌توانید به‌سادگی این کار را انجام دهید:

if ts:
    ...

اگر بدون فراخوانی پیشین prepare() فراخوانی شود، یک ValueError پرتاب می‌کند.

done(*nodes)¶

مجموعه‌ای از گره‌های بازگشت‌داده‌شده از TopologicalSorter.get_ready() را به‌عنوان پردازش‌شده علامت‌گذاری می‌کند و هر جانشینی از هر گره در nodes را برای بازگشت در آینده با فراخوانی TopologicalSorter.get_ready() از حالت مسدود خارج می‌کند.

اگر هر یک از گره‌های nodes از پیش با فراخوانی پیشین این متد به‌عنوان پردازش‌شده علامت‌گذاری شده باشد، یا اگر گره‌ای با استفاده از TopologicalSorter.add() به گراف اضافه نشده باشد، یا اگر این متد بدون فراخوانی prepare() فراخوانی شود، یا اگر گره هنوز توسط get_ready() برگردانده نشده باشد، ValueError پرتاب می‌شود.

get_ready()¶

یک tuple شامل همه گره‌های آماده را برمی‌گرداند. در ابتدا، همه گره‌های بدون پیش‌نیاز را برمی‌گرداند و پس از این‌که آن‌ها با فراخوانی TopologicalSorter.done() به‌عنوان پردازش‌شده علامت‌گذاری شدند، فراخوانی‌های بعدی تمام گره‌های جدیدی را برمی‌گردانند که همه پیش‌نیازهایشان از قبل پردازش شده‌اند. هنگامی که دیگر پیشرفتی امکان‌پذیر نباشد، تاپل‌های خالی برگردانده می‌شوند.

اگر بدون فراخوانی پیشین prepare() فراخوانی شود، یک ValueError پرتاب می‌کند.

static_order()¶

یک شیء پیمایش‌گر برمی‌گرداند که گره‌ها را به ترتیب توپولوژیک پیمایش می‌کند. هنگام استفاده از این متد، نباید prepare() و done() فراخوانی شوند. این متد معادل است با:

def static_order(self):
    self.prepare()
    while self.is_active():
        node_group = self.get_ready()
        yield from node_group
        self.done(*node_group)

ترتیب خاصی که برگردانده می‌شود، ممکن است به ترتیب خاصی که آیتم‌ها در گراف درج شده‌اند بستگی داشته باشد. برای مثال:

>>> 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]

این به این دلیل است که "0" و "2" در سطح یکسانی از گراف قرار دارند (آن‌ها در یک فراخوانی مشترک به get_ready() برگردانده می‌شدند) و ترتیب میان آن‌ها بر اساس ترتیب درج تعیین می‌شود.

اگر چرخه‌ای تشخیص داده شود، CycleError پرتاب خواهد شد.

اضافه شده در نسخه‌ی 3.9.