4. Types of edges in graph using DFS

Types of edges in DFS | Edge classification¶

• Tree Edge:
  • Member of DFS Traversal
• Back Edge:
  • E(x, y) where y appears after x and there is a path from x to y
• Forward Edge:
  • E(x, y) where y appears before x and there is a path from y to x
• Cross Edge:
  • E(x, y) where there is no path between x and y

References:¶

1. https://www.youtube.com/watch?v=wm6qRWGjvkA&list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU&index=83&ab_channel=Jenny%27slecturesCS%2FITNET%26JRF
2. https://www.geeksforgeeks.org/tree-back-edge-and-cross-edges-in-dfs-of-graph/

In [1]:

from utils.graph import GraphAdjList as Graph
from utils.graph_properties import GraphPropertiesAdjList as gp
from utils.graph_traversal import GraphTraversal as gt

from utils.graph import GraphAdjList as Graph from utils.graph_properties import GraphPropertiesAdjList as gp from utils.graph_traversal import GraphTraversal as gt

In [2]:

# # graph with #vertices = 4, #edges = 6
# g = Graph()
# g.insert_node(0, 1)
# g.insert_node(0, 2)
# g.insert_node(1, 2)
# g.insert_node(2, 0)
# g.insert_node(2, 3)
# g.insert_node(3, 3)

# # graph with #vertices = 4, #edges = 6 # g = Graph() # g.insert_node(0, 1) # g.insert_node(0, 2) # g.insert_node(1, 2) # g.insert_node(2, 0) # g.insert_node(2, 3) # g.insert_node(3, 3)

In [3]:

# # graph with #vertices = 4, #edges = 6
# disconnected_graph = Graph()
# #disconnected_graph.insert_node(0, 1)
# disconnected_graph.insert_node(0, 2)
# disconnected_graph.insert_node(1, 2)
# disconnected_graph.insert_node(2, 0)
# disconnected_graph.insert_node(2, 3)
# disconnected_graph.insert_node(3, 3)

# # graph with #vertices = 4, #edges = 6 # disconnected_graph = Graph() # #disconnected_graph.insert_node(0, 1) # disconnected_graph.insert_node(0, 2) # disconnected_graph.insert_node(1, 2) # disconnected_graph.insert_node(2, 0) # disconnected_graph.insert_node(2, 3) # disconnected_graph.insert_node(3, 3)

In [4]:

g = Graph()
g.insert_node(1, 2)
g.insert_node(1, 4)
g.insert_node(2, 1)
g.insert_node(2, 4)
g.insert_node(2, 5)
g.insert_node(2, 3)
g.insert_node(3, 1)
g.insert_node(3, 4)
g.insert_node(4, 2)
g.insert_node(4, 3)
g.insert_node(5, 4)

g = Graph() g.insert_node(1, 2) g.insert_node(1, 4) g.insert_node(2, 1) g.insert_node(2, 4) g.insert_node(2, 5) g.insert_node(2, 3) g.insert_node(3, 1) g.insert_node(3, 4) g.insert_node(4, 2) g.insert_node(4, 3) g.insert_node(5, 4)

In [5]:

class classifyEdges:
    def __init__(self, graph):
        self.graph = graph
        self.visited = set()
        self.traversal_list = []
        self.num_vertices = gp.num_vertices(self.graph)
        self.time = 0
        self.start_time = [0] * self.num_vertices
        self.end_time = [0] * self.num_vertices
        self.tree_edge = []
        self.cross_edge = []
        self.forward_edge = []
        self.backward_edge = []

    def DFS_traversal_disconnected_graph(self):

        for vertex in self.graph:
            if vertex not in self.visited:
                self.DFS_classify_edges(vertex)

    def DFS_classify_edges(self, vertex):

        self.traversal_list.append(vertex)
        self.visited.add(vertex)
        self.start_time[vertex] = self.time
        self.time += 1

        for neighbour in self.graph[vertex]:
            if neighbour not in self.visited:
                self.tree_edge.append((vertex, neighbour))
                self.DFS_classify_edges(neighbour)
            else:
                if (
                    self.start_time[vertex] > self.start_time[neighbour]
                    and self.end_time[vertex] < self.end_time[neighbour]
                ):
                    self.backward_edge.append((vertex, neighbour))
                elif (
                    self.start_time[vertex] < self.start_time[neighbour]
                    and self.end_time[vertex] > self.end_time[neighbour]
                ):
                    self.forward_edge.append(vertex, neighbour)
                elif (
                    self.start_time[vertex] > self.start_time[neighbour]
                    and self.end_time[vertex] > self.end_time[neighbour]
                ):
                    self.cross_edge.append((vertex, neighbour))

            self.end_time[neighbour] = self.time
            self.time += 1

class classifyEdges: def __init__(self, graph): self.graph = graph self.visited = set() self.traversal_list = [] self.num_vertices = gp.num_vertices(self.graph) self.time = 0 self.start_time = [0] * self.num_vertices self.end_time = [0] * self.num_vertices self.tree_edge = [] self.cross_edge = [] self.forward_edge = [] self.backward_edge = [] def DFS_traversal_disconnected_graph(self): for vertex in self.graph: if vertex not in self.visited: self.DFS_classify_edges(vertex) def DFS_classify_edges(self, vertex): self.traversal_list.append(vertex) self.visited.add(vertex) self.start_time[vertex] = self.time self.time += 1 for neighbour in self.graph[vertex]: if neighbour not in self.visited: self.tree_edge.append((vertex, neighbour)) self.DFS_classify_edges(neighbour) else: if ( self.start_time[vertex] > self.start_time[neighbour] and self.end_time[vertex] < self.end_time[neighbour] ): self.backward_edge.append((vertex, neighbour)) elif ( self.start_time[vertex] < self.start_time[neighbour] and self.end_time[vertex] > self.end_time[neighbour] ): self.forward_edge.append(vertex, neighbour) elif ( self.start_time[vertex] > self.start_time[neighbour] and self.end_time[vertex] > self.end_time[neighbour] ): self.cross_edge.append((vertex, neighbour)) self.end_time[neighbour] = self.time self.time += 1

In [6]:

test = classifyEdges(g.graph)

test = classifyEdges(g.graph)

In [7]:

test.DFS_traversal_disconnected_graph()

test.DFS_traversal_disconnected_graph()

In [8]:

test.traversal_list

test.traversal_list

Out[8]:

[1, 2, 4, 3, 5]

In [9]:

test.backward_edge

test.backward_edge

Out[9]:

[(3, 1), (5, 4)]

In [10]:

test.forward_edge

test.forward_edge

Out[10]:

[]

In [11]:

test.cross_edge

test.cross_edge

Out[11]:

[]

In [12]:

test.tree_edge

test.tree_edge

Out[12]:

[(1, 2), (2, 4), (4, 3), (2, 5)]

In [ ]: