DFS algorithm implementation in Python with classes

Question

I am trying to implement DFS that will return a graph with all the nodes containing their predecessor, while having the color attribute to identify a cycle in the graph (there is a cycle iff (u,v) is a back edge iff v is gray and v.discovery < u.discovery).

The code:

# A class to represent a vertex object
class Vertex:
    def __init__(self, val, color="white", d_time=-1, f_time=-1, pred=None):
        self.val = val
        self.color = color
        self.d_time = d_time
        self.f_time = f_time
        self.pred = pred

# A class to represent a graph object
class Graph:
    def __init__(self, adjDict):
        self.vertexes = dict()
        for vertex in adjDict:
            self.vertexes[Vertex(vertex)] = [Vertex(neighbor) for neighbor in adjDict[vertex]]#problematic


def dfs(g):
    for vertex in g.vertexes:
        if vertex.color == "white":
            dfs_vist(g, vertex)
    return g


def dfs_vist(g, v, time=0):
    time += 1
    v.d_time = time
    v.color = "gray"
    for neighbor in g.vertexes[v]:
        if neighbor.color == "white":
            neighbor.pred = v
            dfs_vist(g, neighbor, time)
    v.color = "black"
    time += 1
    v.f_time = time

if __name__ == '__main__':
    graph = {
        0: [2, 4],
        1: [],
        2: [1, 5],
        3: [8],
        4: [7],
        5: [4],
        6: [3],
        7: [1],
        8: []
    }
    g = dfs(Graph(graph))
    print(g)

I am trying to initialize the graph when the graph is represented as dictionary with list of neighbors. The error is in the initializing phase: the same vertex gets created twice, once as a neighbor and once as a key, and then the object is different and the g.vertexes[v] result in a key error. I want to keep my dfs and dfs_visit functions the same, is it possible to initialize it so that they remain the same?

why are you storing your object references in a dictionary? Just store them in a list you can access them directly. And store the "value" information in the Vertex class itself — Jean-François Fabre
– Jean-François Fabre ♦, Commented Jan 1, 2023 at 9:23
after fixing the issue with the constructor you still will have an issue in your dfs_visit function. You will eventually get the 2: [1, 5], and then once you iterate through the neighbors to 5 it will throw another key error because g.vertexes[5] doesn't exist — Alexander
– Alexander, Commented Jan 1, 2023 at 9:43
@Jean-FrançoisFabre Could you please write what you mean about the object references? And I am already storing the value in the Vertex class aren't I? — Kahalon
– Kahalon, Commented Jan 1, 2023 at 9:50

Alexander · Accepted Answer · 2023-01-01 09:58:01Z

1

Try doing this in your graph constructor:

class Graph:
    def __init__(self, adjDict):
        self.vertexes = dict()
        temp = {v: Vertex(v) for v in adjDict.keys()}
        for vertex, neighbors in adjDict.items():
            self.vertexes[temp[vertex]] = [temp[neighbor] for neighbor in neighbors]

If you create all of the vertexes prior to constructing the graph and then plugging them into their respective locations you avoid recreating the same vertex repeatedly.

This should solve your issue with creating duplicate vertexes, but I think your algorithm might still need a bit of tuning as well.

answered Jan 1, 2023 at 9:58

Alexander

17.5k5 gold badges15 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

DFS algorithm implementation in Python with classes

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related