Types of Graphs

Acyclic Graph

An Acyclic Graph is a graph with no cycles. This means there is no path that starts and ends at the same vertex.


class AcyclicGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, vertex1, vertex2):
        self.add_vertex(vertex1)
        self.add_vertex(vertex2)
        self.adjacency_list[vertex1].append(vertex2)

    def is_acyclic(self):
        visited = set()
        stack = set()

        def dfs(vertex):
            visited.add(vertex)
            stack.add(vertex)

            for neighbor in self.adjacency_list[vertex]:
                if neighbor not in visited:
                    if not dfs(neighbor):
                        return False
                elif neighbor in stack:
                    return False

            stack.remove(vertex)
            return True

        for vertex in self.adjacency_list:
            if vertex not in visited:
                if not dfs(vertex):
                    return False
        return True

    def display(self):
        return '\n'.join(f"{vertex} -> {', '.join(neighbors)}" for vertex, neighbors in self.adjacency_list.items())

# Example Usage
graph = AcyclicGraph()
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')
graph.add_edge('A', 'C')
print(graph.display())
print("Is Acyclic:", graph.is_acyclic())

Cyclic Graph

A Cyclic Graph is a graph that contains at least one cycle. A cycle is a path of edges and vertices wherein a vertex is reachable from itself.


class CyclicGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, vertex1, vertex2):
        self.add_vertex(vertex1)
        self.add_vertex(vertex2)
        self.adjacency_list[vertex1].append(vertex2)
        self.adjacency_list[vertex2].append(vertex1)

    def is_cyclic(self):
        visited = set()

        def dfs(vertex, parent):
            visited.add(vertex)

            for neighbor in self.adjacency_list[vertex]:
                if neighbor not in visited:
                    if dfs(neighbor, vertex):
                        return True
                elif parent != neighbor:
                    return True
            return False

        for vertex in self.adjacency_list:
            if vertex not in visited:
                if dfs(vertex, None):
                    return True
        return False

    def display(self):
        return '\n'.join(f"{vertex} -> {', '.join(neighbors)}" for vertex, neighbors in self.adjacency_list.items())

# Example Usage
graph = CyclicGraph()
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')
graph.add_edge('C', 'A')
print(graph.display())
print("Is Cyclic:", graph.is_cyclic())

Directed Graph

A Directed Graph is a graph in which edges have orientations. That is, each edge is directed from one vertex to another.


class DirectedGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, start_vertex, end_vertex):
        self.add_vertex(start_vertex)
        self.add_vertex(end_vertex)
        self.adjacency_list[start_vertex].append(end_vertex)

    def display(self):
        return '\n'.join(f"{vertex} -> {', '.join(neighbors)}" for vertex, neighbors in self.adjacency_list.items())

# Example Usage
graph = DirectedGraph()
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')
print(graph.display())

Directed Weighted Graph

A Directed Weighted Graph is a directed graph in which edges have weights. This type of graph is useful for modeling various real-world systems like networks.


class DirectedWeightedGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, start_vertex, end_vertex, weight):
        self.add_vertex(start_vertex)
        self.add_vertex(end_vertex)
        self.adjacency_list[start_vertex].append((end_vertex, weight))

    def display(self):
        return '\n'.join(f"{vertex} -> {', '.join(f'{neighbor}({weight})' for neighbor, weight in neighbors)}" for vertex, neighbors in self.adjacency_list.items())

# Example Usage
graph = DirectedWeightedGraph()
graph.add_edge('A', 'B', 5)
graph.add_edge('B', 'C', 3)
print(graph.display())

Undirected Graph

An Undirected Graph is a graph in which edges have no orientation. The edge (A, B) is identical to the edge (B, A).


class UndirectedGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, vertex1, vertex2):
        self.add_vertex(vertex1)
        self.add_vertex(vertex2)
        self.adjacency_list[vertex1].append(vertex2)
        self.adjacency_list[vertex2].append(vertex1)

    def display(self):
        return '\n'.join(f"{vertex} -> {', '.join(neighbors)}" for vertex, neighbors in self.adjacency_list.items())

# Example Usage
graph = UndirectedGraph()
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')
print(graph.display())

Undirected Weighted Graph

An Undirected Weighted Graph is a graph in which edges have weights, and there is no orientation.


class UndirectedWeightedGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, vertex1, vertex2, weight):
        self.add_vertex(vertex1)
        self.add_vertex(vertex2)
        self.adjacency_list[vertex1].append((vertex2, weight))
        self.adjacency_list[vertex2].append((vertex1, weight))

    def display(self):
        return '\n'.join(f"{vertex} -> {', '.join(f'{neighbor}({weight})' for neighbor, weight in neighbors)}" for vertex, neighbors in self.adjacency_list.items())

# Example Usage
graph = UndirectedWeightedGraph()
graph.add_edge('A', 'B', 5)
graph.add_edge('B', 'C', 3)
print(graph.display())

Unweighted Graph

An Unweighted Graph is a graph in which edges do not have weights. This is useful for simple connections where distance or weight is not a factor.


class UnweightedGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, vertex1, vertex2):
        self.add_vertex(vertex1)
        self.add_vertex(vertex2)
        self.adjacency_list[vertex1].append(vertex2)
        self.adjacency_list[vertex2].append(vertex1)

    def remove_edge(self, vertex1, vertex2):
        if vertex1 in self.adjacency_list and vertex2 in self.adjacency_list:
            self.adjacency_list[vertex1].remove(vertex2)
            self.adjacency_list[vertex2].remove(vertex1)

    def remove_vertex(self, vertex):
        if vertex in self.adjacency_list:
            for neighbor in list(self.adjacency_list[vertex]):
                self.remove_edge(vertex, neighbor)
            del self.adjacency_list[vertex]

    def display(self):
        return '\n'.join(f"{vertex} -> {', '.join(neighbors)}" for vertex, neighbors in self.adjacency_list.items())

# Example Usage
graph = UnweightedGraph()
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')
print(graph.display())

Weighted Graph

A Weighted Graph is a graph in which each edge is assigned a weight. This can be useful in cases such as finding the shortest path or the longest path.


class WeightedGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, vertex1, vertex2, weight):
        self.add_vertex(vertex1)
        self.add_vertex(vertex2)
        self.adjacency_list[vertex1].append((vertex2, weight))
        self.adjacency_list[vertex2].append((vertex1, weight))

    def display(self):
        return '\n'.join(f"{vertex} -> {', '.join(f'{neighbor}({weight})' for neighbor, weight in neighbors)}" for vertex, neighbors in self.adjacency_list.items())

# Example Usage
graph = WeightedGraph()
graph.add_edge('A', 'B', 5)
graph.add_edge('B', 'C', 3)
print(graph.display())