קראתי היום פוסט שכתבתי לפני כמה ימים על מימוש אלגוריתם BFS ב Python וגיליתי באג שלא שמתי לב אליו בכתיבה הראשונה של הקוד, אבל שמאפיין לא מעט מהבעיות בתכנות מונחה עצמים.

אני מזכיר שהקוד למימוש BFS שכתבתי נראה במקור כך (זה הקוד עם הבאג):

def bfs(q, callback):
    while len(q) > 0:
        node = q.popleft()

        # Skip this node, we've already visited it
        if hasattr(node, 'visited') and node.visited is True: continue

        # Now we can start processing the node:
        # 1. Let's notify outside code that we found a new node
        callback(node)

        # 2. Let's mark it as visited so we won't have to
        #    process it again
        node.visited = True

        # 3. Let's add all of its neighbors to the queue
        #    so we'll be able to process them too
        for friend in node.neighbours:
            q.append(friend)

זיהיתם את הבאג? אם לא, קחו כמה דקות לקרוא את זה שוב.

הבעיה היא המנגנון ששומר האם כבר ביקרנו ב Node מסוים או לא: המנגנון מסמן את ה Node בתור כזה שביקרנו בו כדי שלא נחזור לאותו Node פעמיים, אבל מה קורה אם נרצה להפעיל את bfs פעם שניה על אותו עץ?

במצב כזה כל הצמתים כבר מסומנים בתור כאלה שביקרנו בהם ולכן הריצה השניה תחזור מיד.

זו בעיה אופיינית לתכנות מונחה עצמים מאחר וכשהאוביקטים עצמם שומרים את המידע, והמידע מפוזר על פני אוביקטים רבים בתוכנית, זו אחריות שלנו לזכור לאפס את המידע כשסיימנו איתו - אחריות שקל לשכוח ממנה.

פיתרון אחד קל לבעיה עבור מנגנון ה bfs יהיה להשתמש במבנה נתונים חיצוני ולשמור בו את כל הצמתים בהם ביקרנו. כך נראה הקוד עם קבוצה:

def bfs(q, callback):
    visited_nodes = set()
    while len(q) > 0:
        node = q.popleft()

        # Skip this node, we've already visited it
        if node in visited_nodes: continue

        # Now we can start processing the node:
        # 1. Let's notify outside code that we found a new node
        callback(node)

        # 2. Let's mark it as visited so we won't have to
        #    process it again
        visited_nodes.add(node)

        # 3. Let's add all of its neighbors to the queue
        #    so we'll be able to process them too
        for friend in node.neighbours:
            q.append(friend)

זה גם הפיתרון שעכשיו מופיע בפוסט המקורי כדי לא להשאיר שם טעויות.

פיתרון שני שמעניין לראות עושה שימוש ב ExitStack כדי להוסיף קוד ניקוי אחרי כל שינוי, זה נראה כך:

from contextlib import ExitStack
def bfs(q, callback):
    with ExitStack() as stack:
        while len(q) > 0:
            node = q.popleft()

            # Skip this node, we've already visited it
            if hasattr(node, 'visited') and node.visited is True: continue

            # Now we can start processing the node:
            # 1. Let's notify outside code that we found a new node
            callback(node)

            # 2. Let's mark it as visited so we won't have to
            #    process it again
            node.visited = True
            stack.callback(node.reset_visited)

            # 3. Let's add all of its neighbors to the queue
            #    so we'll be able to process them too
            for friend in node.neighbours:
                q.append(friend)

פיתרון זה יותר גנרי ויותר אופייני לגישה מונחית עצמים כיוון שאפשר להוסיף כל Callback Function שרוצים ל Exit Stack, ובסוף בלוק ה with באופן אוטומטי פייתון יריץ את כל קודי הניקוי שלנו. הוא גם יותר מתאים לגישת ה Object Oriented כיוון שכל אוביקט Node אחראי על קוד הניקוי שלו.