FilesExpand file tree

master

/

graph_list.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

150 lines (136 loc) · 6.5 KB

master

/

graph_list.py

Copy path

Top

File metadata and controls

• Code
• Blame

150 lines (136 loc) · 6.5 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

#!/usr/bin/env python3

# Author: OMKAR PATHAK, Nwachukwu Chidiebere

# Use a Python dictionary to construct the graph.

from __future__ import annotations

from pprint import pformat

from typing import Generic, TypeVar

T = TypeVar("T")

class GraphAdjacencyList(Generic[T]):

"""

Adjacency List type Graph Data Structure that accounts for directed and undirected

Graphs. Initialize graph object indicating whether it's directed or undirected.

Directed graph example:

>>> d_graph = GraphAdjacencyList()

>>> print(d_graph)

{}

>>> d_graph.add_edge(0, 1)

{0: [1], 1: []}

>>> d_graph.add_edge(1, 2).add_edge(1, 4).add_edge(1, 5)

{0: [1], 1: [2, 4, 5], 2: [], 4: [], 5: []}

>>> d_graph.add_edge(2, 0).add_edge(2, 6).add_edge(2, 7)

{0: [1], 1: [2, 4, 5], 2: [0, 6, 7], 4: [], 5: [], 6: [], 7: []}

>>> d_graph

{0: [1], 1: [2, 4, 5], 2: [0, 6, 7], 4: [], 5: [], 6: [], 7: []}

>>> print(repr(d_graph))

{0: [1], 1: [2, 4, 5], 2: [0, 6, 7], 4: [], 5: [], 6: [], 7: []}

Undirected graph example:

>>> u_graph = GraphAdjacencyList(directed=False)

>>> u_graph.add_edge(0, 1)

{0: [1], 1: [0]}

>>> u_graph.add_edge(1, 2).add_edge(1, 4).add_edge(1, 5)

{0: [1], 1: [0, 2, 4, 5], 2: [1], 4: [1], 5: [1]}

>>> u_graph.add_edge(2, 0).add_edge(2, 6).add_edge(2, 7)

{0: [1, 2], 1: [0, 2, 4, 5], 2: [1, 0, 6, 7], 4: [1], 5: [1], 6: [2], 7: [2]}

>>> u_graph.add_edge(4, 5)

{0: [1, 2],

1: [0, 2, 4, 5],

2: [1, 0, 6, 7],

4: [1, 5],

5: [1, 4],

6: [2],

7: [2]}

>>> print(u_graph)

{0: [1, 2],

1: [0, 2, 4, 5],

2: [1, 0, 6, 7],

4: [1, 5],

5: [1, 4],

6: [2],

7: [2]}

>>> print(repr(u_graph))

{0: [1, 2],

1: [0, 2, 4, 5],

2: [1, 0, 6, 7],

4: [1, 5],

5: [1, 4],

6: [2],

7: [2]}

>>> char_graph = GraphAdjacencyList(directed=False)

>>> char_graph.add_edge('a', 'b')

{'a': ['b'], 'b': ['a']}

>>> char_graph.add_edge('b', 'c').add_edge('b', 'e').add_edge('b', 'f')

{'a': ['b'], 'b': ['a', 'c', 'e', 'f'], 'c': ['b'], 'e': ['b'], 'f': ['b']}

>>> char_graph

{'a': ['b'], 'b': ['a', 'c', 'e', 'f'], 'c': ['b'], 'e': ['b'], 'f': ['b']}

"""

def __init__(self, directed: bool = True) -> None:

"""

Parameters:

directed: (bool) Indicates if graph is directed or undirected. Default is True.

"""

self.adj_list: dict[T, list[T]] = {} # dictionary of lists

self.directed = directed

def add_edge(

self, source_vertex: T, destination_vertex: T

) -> GraphAdjacencyList[T]:

"""

Connects vertices together. Creates and Edge from source vertex to destination

vertex.

Vertices will be created if not found in graph

"""

if not self.directed: # For undirected graphs

# if both source vertex and destination vertex are both present in the

# adjacency list, add destination vertex to source vertex list of adjacent

# vertices and add source vertex to destination vertex list of adjacent

# vertices.

if source_vertex in self.adj_list and destination_vertex in self.adj_list:

self.adj_list[source_vertex].append(destination_vertex)

self.adj_list[destination_vertex].append(source_vertex)

# if only source vertex is present in adjacency list, add destination vertex

# to source vertex list of adjacent vertices, then create a new vertex with

# destination vertex as key and assign a list containing the source vertex

# as it's first adjacent vertex.

elif source_vertex in self.adj_list:

self.adj_list[source_vertex].append(destination_vertex)

self.adj_list[destination_vertex] = [source_vertex]

# if only destination vertex is present in adjacency list, add source vertex

# to destination vertex list of adjacent vertices, then create a new vertex

# with source vertex as key and assign a list containing the source vertex

# as it's first adjacent vertex.

elif destination_vertex in self.adj_list:

self.adj_list[destination_vertex].append(source_vertex)

self.adj_list[source_vertex] = [destination_vertex]

# if both source vertex and destination vertex are not present in adjacency

# list, create a new vertex with source vertex as key and assign a list

# containing the destination vertex as it's first adjacent vertex also

# create a new vertex with destination vertex as key and assign a list

# containing the source vertex as it's first adjacent vertex.

else:

self.adj_list[source_vertex] = [destination_vertex]

self.adj_list[destination_vertex] = [source_vertex]

else: # For directed graphs

# if both source vertex and destination vertex are present in adjacency

# list, add destination vertex to source vertex list of adjacent vertices.

if source_vertex in self.adj_list and destination_vertex in self.adj_list:

self.adj_list[source_vertex].append(destination_vertex)

# if only source vertex is present in adjacency list, add destination

# vertex to source vertex list of adjacent vertices and create a new vertex

# with destination vertex as key, which has no adjacent vertex

elif source_vertex in self.adj_list:

self.adj_list[source_vertex].append(destination_vertex)

self.adj_list[destination_vertex] = []

# if only destination vertex is present in adjacency list, create a new

# vertex with source vertex as key and assign a list containing destination

# vertex as first adjacent vertex

elif destination_vertex in self.adj_list:

self.adj_list[source_vertex] = [destination_vertex]

# if both source vertex and destination vertex are not present in adjacency

# list, create a new vertex with source vertex as key and a list containing

# destination vertex as it's first adjacent vertex. Then create a new vertex

# with destination vertex as key, which has no adjacent vertex

else:

self.adj_list[source_vertex] = [destination_vertex]

self.adj_list[destination_vertex] = []

return self

def __repr__(self) -> str:

return pformat(self.adj_list)