Line data Source code
1 : /**
2 : * @file ADTGraph.cpp
3 : * @author Pheadon Seitanidis
4 : * @brief
5 : * @version 0.1
6 : * @date 2023-11-01
7 : *
8 : * @copyright Copyright (c) 2023
9 : *
10 : */
11 :
12 : #include "cppdescent/ADTGraph.hpp"
13 : #include <gsl/gsl_blas.h>
14 : #include <gsl/gsl_vector.h>
15 : #include <climits>
16 : #include <iostream>
17 : #include "cppdescent/cppdescent.hpp"
18 :
19 5126 : int compareVertices(Pointer vertex1, Pointer vertex2) {
20 5126 : GraphVertex* v1 = (GraphVertex*)vertex1;
21 5126 : GraphVertex* v2 = (GraphVertex*)vertex2;
22 :
23 5126 : if (gsl_vector_equal((gsl_vector*)v1->getData(), (gsl_vector*)v2->getData()))
24 220 : return 0;
25 : else
26 4906 : return 1;
27 : }
28 :
29 1226 : int compareNeighbors(Pointer neighbor1, Pointer neighbor2) {
30 1226 : GraphVertexPair* pair1 = (GraphVertexPair*)neighbor1;
31 1226 : GraphVertexPair* pair2 = (GraphVertexPair*)neighbor2;
32 :
33 : float first =
34 1226 : cppdescent::euclideanDistance(pair1->getVertex1(), pair1->getVertex2());
35 : float second =
36 1226 : cppdescent::euclideanDistance(pair2->getVertex1(), pair2->getVertex2());
37 :
38 1226 : float result = first - second;
39 :
40 1226 : if (result < 0)
41 668 : return -1;
42 : else
43 558 : return 1;
44 : }
45 :
46 902 : void destroyVertex(GraphVertex* vertex) {
47 902 : gsl_vector_free((gsl_vector*)vertex->getData());
48 :
49 902 : delete vertex;
50 902 : }
51 :
52 : // Graph //
53 :
54 126 : Graph::Graph(CompareFunc compare_data, DestroyFunc destroy_data)
55 126 : : size(0), compare_data(compare_data), destroy_data(destroy_data) {
56 126 : this->vec = new Vector(0, (DestroyFunc)destroyVertex);
57 :
58 126 : this->compare_vertices = compareVertices;
59 126 : }
60 :
61 1240 : int Graph::getSize() {
62 1240 : return this->size;
63 : }
64 :
65 : /**
66 : * @brief Insert a vertex to the graph (if it doesn't already exist).
67 : *
68 : * @param vertex A Pointer to the vertex to be unserted.
69 : */
70 1032 : void Graph::insertVertex(Pointer vertex) {
71 1032 : GraphVertex* gvertex = new GraphVertex(vertex, this);
72 1032 : gsl_vector* x = (gsl_vector*)vertex;
73 :
74 1032 : if (this->vec->find(gvertex, this->compare_vertices) != nullptr) {
75 20 : delete gvertex;
76 20 : return;
77 : }
78 :
79 1012 : this->vec->insertLast(gvertex);
80 1012 : this->size++;
81 : double norm;
82 1012 : gsl_blas_ddot(x, x, &norm);
83 1012 : gvertex->setNorm(norm);
84 1012 : gvertex->setPos(this->size - 1);
85 : }
86 :
87 61 : Vector* Graph::getVerticesV() {
88 61 : return this->vec;
89 : }
90 :
91 200 : void Graph::removeVertex(Pointer vertex) {
92 200 : GraphVertex* gvertex = new GraphVertex(vertex, this);
93 200 : int i = this->vec->findPos(gvertex, this->compare_vertices);
94 :
95 : // LCOV_EXCL_START
96 : if (i == -1) {
97 : std::cerr << "removeVertex: given vertex not found. Exiting...\n";
98 : return;
99 : }
100 : // LCOV_EXCL_STOP
101 :
102 200 : this->vec->swap(i, this->size - 1);
103 200 : this->vec->removeLast();
104 :
105 200 : this->size--;
106 :
107 200 : delete gvertex;
108 : }
109 :
110 903 : void Graph::insertEdge(Pointer data1, Pointer data2) {
111 903 : GraphVertex* gvertex1 = (GraphVertex*)data1;
112 903 : GraphVertex* gvertex2 = (GraphVertex*)data2;
113 :
114 903 : GraphVertexPair* pair = new GraphVertexPair(this, gvertex1, gvertex2);
115 :
116 903 : if (gvertex1->getNeighbors()->find(
117 903 : pair, (CompareFunc)cppdescent::compareGraphVertexPairs) != -1) {
118 91 : delete pair;
119 91 : return;
120 : }
121 :
122 812 : gvertex1->addNeighbor(pair);
123 812 : gvertex2->addReverse(pair);
124 : }
125 :
126 153 : void Graph::removeEdge(Pointer data1, Pointer data2) {
127 153 : GraphVertex* vertex1 = (GraphVertex*)data1;
128 153 : GraphVertex* vertex2 = (GraphVertex*)data2;
129 :
130 153 : GraphVertexPair* pair = new GraphVertexPair(this, vertex1, vertex2);
131 :
132 153 : vertex1->removeNeighbor(pair,
133 : (CompareFunc)cppdescent::compareGraphVertexPairs);
134 153 : vertex2->removeReverse(pair,
135 : (CompareFunc)cppdescent::compareGraphVertexPairs);
136 :
137 153 : delete pair;
138 153 : }
139 :
140 40 : Vector* Graph::getAdjacentV(Pointer vertex) {
141 40 : GraphVertex* gvertex = (GraphVertex*)vertex;
142 :
143 40 : PQueue* pqueue = gvertex->getNeighbors();
144 :
145 40 : return pqueue->toVector();
146 : }
147 :
148 179 : Vector* Graph::getReverseAdjacentV(Pointer vertex) {
149 179 : GraphVertex* gvertex = (GraphVertex*)vertex;
150 :
151 179 : PQueue* pqueue = gvertex->getReverse();
152 :
153 179 : return pqueue->toVector();
154 : }
155 :
156 774 : void destroyEdgePair(GraphVertexPair* pair) {
157 774 : delete pair;
158 774 : }
159 :
160 : /**
161 : * @brief Returns a vector where the K first elements are the direct neighbors
162 : * of the vertex and the rest are the reverse ones.
163 : *
164 : * @param vertex
165 : * @return Vector*
166 : */
167 20 : Vector* Graph::getGeneralNeighborsV(Pointer vertex) {
168 20 : Vector* direct = getAdjacentV(vertex);
169 20 : Vector* reverse = getReverseAdjacentV(vertex);
170 :
171 20 : Vector* neighbors = new Vector(0, nullptr);
172 :
173 176 : for (int i = 0; i < direct->getSize(); i++) {
174 156 : GraphVertexPair* pair = (GraphVertexPair*)direct->getAt(i);
175 156 : neighbors->insertLast(pair);
176 : }
177 200 : for (int i = 0; i < reverse->getSize(); i++) {
178 180 : GraphVertexPair* pair = (GraphVertexPair*)reverse->getAt(i);
179 180 : neighbors->insertLast(pair);
180 : }
181 :
182 20 : return neighbors;
183 : }
184 :
185 859 : bool Graph::isNeighborVertex(Pointer v1, Pointer v2) {
186 859 : GraphVertex* gvertex1 = (GraphVertex*)v1;
187 859 : GraphVertex* gvertex2 = (GraphVertex*)v2;
188 :
189 859 : bool alreadyMember = false;
190 :
191 859 : GraphVertexPair* pair = new GraphVertexPair(this, gvertex1, gvertex2);
192 :
193 859 : if (gvertex1->getNeighbors()->toVector()->find(
194 859 : pair, (CompareFunc)cppdescent::compareGraphVertexPairs) != nullptr)
195 706 : alreadyMember = true;
196 :
197 859 : delete pair;
198 :
199 859 : return alreadyMember;
200 : }
201 :
202 115 : Graph::~Graph() {
203 115 : delete this->vec;
204 115 : }
205 :
206 : // GraphVertex
207 :
208 1628 : GraphVertex::GraphVertex(Pointer data, Graph* owner)
209 1628 : : data(data), owner(owner), hasBeenChecked(false) {
210 1628 : neighbors = new PQueue(compareNeighbors, nullptr, nullptr);
211 1628 : reverse = new PQueue(compareNeighbors, (DestroyFunc)destroyEdgePair, nullptr);
212 1628 : }
213 :
214 1402 : GraphVertex::~GraphVertex() {
215 1402 : delete neighbors;
216 1402 : delete reverse;
217 1402 : }
|
