MaximumBandwidthGraphTheory/Graph.py at main · alekhyaduba/MaximumBandwidthGraphTheory · GitHub

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
import random
# import seaborn as sn
# import pandas as pd
# import matplotlib.pyplot as plt


class Graph:

    def __init__(self, numOfVertices, edgeConnectivity, maxEdgeWeights):


        self.adjMatrix = [[0 for i in range(numOfVertices)] for j in range(numOfVertices)]
        self.maxEdgeWeight = maxEdgeWeights
        self.numVertices = numOfVertices
        self.edgeConnectivity = edgeConnectivity
        self.vertexDegree = [0 for i in range(numOfVertices)]
        self.numEdges = numOfVertices * edgeConnectivity / 2
        self.adjList = [[] for i in range(numOfVertices)]

        self.createGraph()

    #
    # def addVertices(self):
    #     """
    #     Adds the given number of vertices to the graph
    #     :param numberOfVertices: number of vertices to be added to the graph
    #     :return: none
    #     """
    #
    #     for i in range(self.numVertices):
    #         self.adjList[i] = []

    def addEdge(self, vertex1, vertex2):
        """
        Adds an undirected edge between two vertices
        :param vertex1: Vertex 1
        :param vertex2: Vertex 2
        :return: None
        """
        if self.adjMatrix[vertex1][vertex2] == 0:
            self.numEdges -= 1
            self.adjList[vertex1].append(vertex2)
            self.adjList[vertex2].append(vertex1)
            weight = random.randint(1, self.maxEdgeWeight)
            self.adjMatrix[vertex1][vertex2] = weight
            self.adjMatrix[vertex2][vertex1] = weight
            self.vertexDegree[vertex1] += 1
            self.vertexDegree[vertex2] += 1
            return True
        return False

    def printGraph(self):
        """
        Prints all the vertices and edges in the graph
        :return:
        """
        str_list = ""
        for index, val in enumerate(self.adjList):
            str_list += f"\n{index} : {val}"
        with open("graph.txt", "w") as fh:
            fh.write(str_list)
        # print(self.adjList)

    # def plot_graph(self):
    #     # array = [[33, 2, 0, 0, 0, 0, 0, 0, 0, 1, 3],
    #     #          [3, 31, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    #     #          [0, 4, 41, 0, 0, 0, 0, 0, 0, 0, 1],
    #     #          [0, 1, 0, 30, 0, 6, 0, 0, 0, 0, 1],
    #     #          [0, 0, 0, 0, 38, 10, 0, 0, 0, 0, 0],
    #     #          [0, 0, 0, 3, 1, 39, 0, 0, 0, 0, 4],
    #     #          [0, 2, 2, 0, 4, 1, 31, 0, 0, 0, 2],
    #     #          [0, 1, 0, 0, 0, 0, 0, 36, 0, 2, 0],
    #     #          [0, 0, 0, 0, 0, 0, 1, 5, 37, 5, 1],
    #     #          [3, 0, 0, 0, 0, 0, 0, 0, 0, 39, 0],
    #     #          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
    #     df_cm = pd.DataFrame(self.adjMatrix, index=[i for i in range(self.numVertices)],
    #                          columns=[i for i in range(self.numVertices)])
    #     plt.figure(figsize=(10, 10))
    #     sn.heatmap(df_cm, annot=True, cmap="OrRd")
    #     plt.savefig("plt_red.png", dpi=300)
    #     plt.show()

    def calculateAvgInDegree(self):
        """
        prints the average in degree of the vertices
        :return:
        """
        # print(self.numEdges * 2 / len(self.adjList))

    def createGraph(self):
        """
        Creates a graph pf given number of vertices and with given density/edge connectivity
        :param numVertices: Number of vertices in the graph
        :param edgeConnectivity: density of edges
        :return: graph
        """
        # Start the timer
        # start = timeit.default_timer()

        # Add vertices to the graph
        # self.addVertices()

        # Construct edges between two vertices according to the given edge density
        availableVertices = [i for i in range(0, self.numVertices)]

        # This loop ensures that the entire graph is connected
        for i in range(0, self.numVertices - 1):
            self.addEdge(i, i + 1)
        self.addEdge(self.numVertices - 1, 0)

        while self.numEdges > 0:
            # print(graph.numEdges, len(availableVertices))
            vertex1 = random.choice(availableVertices)
            vertex2 = random.choice(availableVertices)
            if vertex2 != vertex1:
                if self.addEdge(vertex1, vertex2):
                    if self.vertexDegree[vertex1] >= 1.05 * self.edgeConnectivity:
                        availableVertices.remove(vertex1)
                    if self.vertexDegree[vertex2] >= 1.05 * self.edgeConnectivity:
                        availableVertices.remove(vertex2)

        self.calculateAvgInDegree()
        # end = timeit.default_timer()
        # print((end - start))

    def getNumEdges(self):
        numEdges = 0

        for vList in self.adjList:
            for vertex in vList:
                numEdges += 1

        numEdges = int(numEdges/2)
        return numEdges

    def getEdgesListB(self):
        """
        This assumes that no self edges exists
        :return: A list with edge names as the index and [weight of edge , (u,v)]
        """
        edges_values_vertices = [[] for i in range(self.maxEdgeWeight + 1)]
        # edge_vertices = []
        for i in range(0,self.numVertices):
            for j in range(i+1, self.numVertices):
                if self.adjMatrix[i][j] != 0:
                    # edges.append([self.adjMatrix[i][j], (i, j)])
                    edges_values_vertices[self.adjMatrix[i][j]].append((i,j))
                    # edges_values_vertices.append(self.adjMatrix[i][j])
        return edges_values_vertices


    def getEdgesList(self):
        """
        This assumes that no self edges exists
        :return: A list with edge names as the index and [weight of edge , (u,v)]
        """
        edges_values = []
        edge_vertices = []
        for i in range(0,self.numVertices):
            for j in range(i+1, self.numVertices):
                if self.adjMatrix[i][j] != 0:
                    edge_vertices.append((i, j))
                    edges_values.append(self.adjMatrix[i][j])
        return edges_values, edge_vertices