1//! @file graph.cpp
2//! @author ryftchen
3//! @brief The definitions (graph) in the data structure module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2025 ryftchen. All rights reserved.
6
7#include "graph.hpp"
8
9#include <cstring>
10
11namespace data_structure::graph
12{
13//! @brief Function version number.
14//! @return version number (major.minor.patch)
15const char* version() noexcept
16{
17 static const char* const ver = "0.1.0";
18 return ver;
19}
20
21// NOLINTBEGIN(cppcoreguidelines-owning-memory, cppcoreguidelines-pro-type-const-cast)
22namespace undirected
23{
24//! @brief Locate the index of a vertex in the undirected graph.
25//! @param graph - graph to search in
26//! @param vert - vertex to locate
27//! @return index of the vertex if found, otherwise -1
28static int locateVertex(const AMLGraph* const graph, const void* const vert)
29{
30 if (!graph || !vert)
31 {
32 return -1;
33 }
34
35 for (int i = 0; i < graph->vexNum; ++i)
36 {
37 if (graph->compare(graph->adjMultiList[i].data, vert) == 0)
38 {
39 return i;
40 }
41 }
42 return -1;
43}
44
45//! @brief Get the next edge from the given edge node at the given vertex index.
46//! @param eNode - current edge node
47//! @param index - index of the vertex
48static EdgeNode* getNextEdge(const EdgeNode* const eNode, const int index)
49{
50 if (!eNode)
51 {
52 return nullptr;
53 }
54 return (eNode->iVex == index) ? eNode->iLink : eNode->jLink;
55}
56
57//! @brief Remove the given edge from a vertex's adjacency list in the undirected graph.
58//! @param vNode - vertex node whose adjacency list will be modified
59//! @param index - index of the vertex
60//! @param eNode - edge node to be removed
61static void removeEdgeFromList(VertexNode* const vNode, const int index, const EdgeNode* const eNode)
62{
63 if (!vNode || !eNode)
64 {
65 return;
66 }
67
68 EdgeNode* curr = vNode->firstEdge;
69 EdgeNode* prev = nullptr;
70 while (curr)
71 {
72 if (curr != eNode)
73 {
74 prev = curr;
75 curr = getNextEdge(eNode: curr, index);
76 continue;
77 }
78
79 if (!prev)
80 {
81 vNode->firstEdge = getNextEdge(eNode: curr, index);
82 }
83 else
84 {
85 (prev->iVex == index) ? prev->iLink = getNextEdge(eNode: curr, index) : prev->jLink = getNextEdge(eNode: curr, index);
86 }
87 break;
88 }
89}
90
91//! @brief Create the undirected graph.
92//! @param cmp - compare function to compare data
93//! @return new undirected graph
94AMLGraph* create(const Compare cmp)
95{
96 if (!cmp)
97 {
98 return nullptr;
99 }
100
101 auto* const graph = ::new (std::nothrow) AMLGraph;
102 if (!graph)
103 {
104 return nullptr;
105 }
106
107 graph->vexNum = 0;
108 graph->edgeNum = 0;
109 std::memset(s: graph->adjMultiList, c: 0, n: sizeof(graph->adjMultiList));
110 graph->compare = cmp;
111 return graph;
112}
113
114//! @brief Destroy the undirected graph.
115//! @param graph - graph to destroy
116void destroy(AMLGraph* graph)
117{
118 if (!graph)
119 {
120 return;
121 }
122
123 const EdgeNode* curr = nullptr;
124 const EdgeNode* del = nullptr;
125 for (int i = 0; i < graph->vexNum; ++i)
126 {
127 curr = graph->adjMultiList[i].firstEdge;
128 while (curr)
129 {
130 del = curr;
131 curr = (curr->iVex == i) ? curr->iLink : curr->jLink;
132 deleteEdge(graph, vert1: graph->adjMultiList[del->iVex].data, vert2: graph->adjMultiList[del->jVex].data);
133 }
134 }
135
136 ::delete graph;
137 graph = nullptr;
138}
139
140//! @brief Add a vertex into the undirected graph.
141//! @param graph - graph to add into
142//! @param vert - vert to add
143//! @return success or failure
144bool addVertex(AMLGraph* const graph, const void* const vert)
145{
146 if (!graph || !vert || (graph->vexNum >= maxVertexNum) || (locateVertex(graph, vert) >= 0))
147 {
148 return false;
149 }
150
151 graph->adjMultiList[graph->vexNum].firstEdge = nullptr;
152 graph->adjMultiList[graph->vexNum].data = const_cast<void*>(vert);
153 ++graph->vexNum;
154 return true;
155}
156
157//! @brief Add an edge between two vertices into the undirected graph.
158//! @param graph - graph to add into
159//! @param vert1 - vertex at the one endpoint of the edge
160//! @param vert2 - vertex at the other endpoint of the edge
161//! @return success or failure
162bool addEdge(AMLGraph* const graph, const void* const vert1, const void* const vert2)
163{
164 if (!graph || !vert1 || !vert2)
165 {
166 return false;
167 }
168
169 const int index1 = locateVertex(graph, vert: vert1);
170 const int index2 = locateVertex(graph, vert: vert2);
171 if ((index1 < 0) || (index2 < 0))
172 {
173 return false;
174 }
175
176 const EdgeNode* curr = graph->adjMultiList[index1].firstEdge;
177 while (curr)
178 {
179 if (((curr->iVex == index1) && (curr->jVex == index2)) || ((curr->iVex == index2) && (curr->jVex == index1)))
180 {
181 return false;
182 }
183 curr = (curr->iVex == index1) ? curr->iLink : curr->jLink;
184 }
185
186 auto* const newNode = ::new (std::nothrow) EdgeNode;
187 if (!newNode)
188 {
189 return false;
190 }
191
192 newNode->iVex = index1;
193 newNode->jVex = index2;
194 newNode->iLink = graph->adjMultiList[index1].firstEdge;
195 graph->adjMultiList[index1].firstEdge = newNode;
196 newNode->jLink = graph->adjMultiList[index2].firstEdge;
197 graph->adjMultiList[index2].firstEdge = newNode;
198 ++graph->edgeNum;
199 return true;
200}
201
202//! @brief Delete a vertex from the undirected graph.
203//! @param graph - graph to delete from
204//! @param vert - vert to delete
205//! @return success or failure
206bool deleteVertex(AMLGraph* const graph, const void* const vert)
207{
208 if (!graph || !vert)
209 {
210 return false;
211 }
212
213 const int index = locateVertex(graph, vert);
214 if (index < 0)
215 {
216 return false;
217 }
218
219 const EdgeNode* curr = graph->adjMultiList[index].firstEdge;
220 while (curr)
221 {
222 const void* const other =
223 (curr->iVex == index) ? graph->adjMultiList[curr->jVex].data : graph->adjMultiList[curr->iVex].data;
224 deleteEdge(graph, vert1: vert, vert2: other);
225 curr = graph->adjMultiList[index].firstEdge;
226 }
227
228 if (index == (graph->vexNum - 1))
229 {
230 --graph->vexNum;
231 return true;
232 }
233
234 graph->adjMultiList[index] = graph->adjMultiList[graph->vexNum - 1];
235 for (int i = 0; i < graph->vexNum; ++i)
236 {
237 EdgeNode* adj = graph->adjMultiList[i].firstEdge;
238 while (adj)
239 {
240 if (adj->iVex == (graph->vexNum - 1))
241 {
242 adj->iVex = index;
243 }
244 if (adj->jVex == (graph->vexNum - 1))
245 {
246 adj->jVex = index;
247 }
248 adj = (adj->iVex == i) ? adj->iLink : adj->jLink;
249 }
250 }
251 --graph->vexNum;
252 return true;
253}
254
255//! @brief Delete an edge between two vertices from the undirected graph.
256//! @param graph - graph to delete from
257//! @param vert1 - vertex at the one endpoint of the edge
258//! @param vert2 - vertex at the other endpoint of the edge
259//! @return success or failure
260bool deleteEdge(AMLGraph* const graph, const void* const vert1, const void* const vert2)
261{
262 if (!graph || !vert1 || !vert2)
263 {
264 return false;
265 }
266
267 const int index1 = locateVertex(graph, vert: vert1);
268 const int index2 = locateVertex(graph, vert: vert2);
269 if ((index1 < 0) || (index2 < 0))
270 {
271 return false;
272 }
273
274 const EdgeNode* curr = graph->adjMultiList[index1].firstEdge;
275 while (curr)
276 {
277 if (((curr->iVex == index1) && (curr->jVex == index2)) || ((curr->iVex == index2) && (curr->jVex == index1)))
278 {
279 break;
280 }
281 curr = (curr->iVex == index1) ? curr->iLink : curr->jLink;
282 }
283
284 if (!curr)
285 {
286 return false;
287 }
288
289 removeEdgeFromList(vNode: &graph->adjMultiList[index1], index: index1, eNode: curr);
290 removeEdgeFromList(vNode: &graph->adjMultiList[index2], index: index2, eNode: curr);
291
292 ::delete curr;
293 curr = nullptr;
294 --graph->edgeNum;
295 return true;
296}
297
298void Traverse::dfs(const void* const vert, const Operation& op) const
299{
300 if (!graph || !vert || !op)
301 {
302 return;
303 }
304
305 const int start = locateVertex(graph, vert);
306 if (start < 0)
307 {
308 return;
309 }
310
311 bool visited[maxVertexNum] = {};
312 dfsRecursive(index: start, visited, op);
313}
314
315void Traverse::dfsRecursive(const int index, bool visited[], const Operation& op) const
316{
317 if (index < 0)
318 {
319 return;
320 }
321
322 visited[index] = true;
323 op(graph->adjMultiList[index].data);
324
325 int neighbors[maxVertexNum] = {};
326 int counter = 0;
327 const EdgeNode* curr = graph->adjMultiList[index].firstEdge;
328 while (curr)
329 {
330 const int nbrIdx = (curr->iVex == index) ? curr->jVex : curr->iVex;
331 if (!visited[nbrIdx])
332 {
333 neighbors[counter++] = nbrIdx;
334 }
335 curr = (curr->iVex == index) ? curr->iLink : curr->jLink;
336 }
337
338 sortNeighbors(neighbors, size: counter);
339 for (int i = 0; i < counter; ++i)
340 {
341 if (!visited[neighbors[i]])
342 {
343 dfsRecursive(index: neighbors[i], visited, op);
344 }
345 }
346}
347
348void Traverse::bfs(const void* const vert, const Operation& op) const
349{
350 if (!graph || !vert || !op)
351 {
352 return;
353 }
354
355 const int start = locateVertex(graph, vert);
356 if (start < 0)
357 {
358 return;
359 }
360
361 bool visited[maxVertexNum] = {};
362 visited[start] = true;
363 op(graph->adjMultiList[start].data);
364
365 int queue[maxVertexNum] = {};
366 int front = 0;
367 int rear = 0;
368 queue[rear++] = start;
369 while (front < rear)
370 {
371 const int q = queue[front++];
372 int neighbors[maxVertexNum] = {};
373 int counter = 0;
374 const EdgeNode* curr = graph->adjMultiList[q].firstEdge;
375 while (curr)
376 {
377 const int nbrIdx = (curr->iVex == q) ? curr->jVex : curr->iVex;
378 if (!visited[nbrIdx])
379 {
380 neighbors[counter++] = nbrIdx;
381 }
382 curr = (curr->iVex == q) ? curr->iLink : curr->jLink;
383 }
384
385 sortNeighbors(neighbors, size: counter);
386 for (int i = 0; i < counter; ++i)
387 {
388 if (!visited[neighbors[i]])
389 {
390 visited[neighbors[i]] = true;
391 op(graph->adjMultiList[neighbors[i]].data);
392 queue[rear++] = neighbors[i];
393 }
394 }
395 }
396}
397
398void Traverse::sortNeighbors(int neighbors[], const int size) const
399{
400 for (int i = 1; i < size; ++i)
401 {
402 const int temp = neighbors[i];
403 int j = i - 1;
404 while ((j >= 0) && (graph->compare(graph->adjMultiList[neighbors[j]].data, graph->adjMultiList[temp].data) > 0))
405 {
406 neighbors[j + 1] = neighbors[j];
407 --j;
408 }
409 neighbors[j + 1] = temp;
410 }
411}
412} // namespace undirected
413
414namespace directed
415{
416//! @brief Locate the index of a vertex in the directed graph.
417//! @param graph - graph to search in
418//! @param vert - vertex to locate
419//! @return index of the vertex if found, otherwise -1
420static int locateVertex(const OLGraph* const graph, const void* const vert)
421{
422 if (!graph || !vert)
423 {
424 return -1;
425 }
426
427 for (int i = 0; i < graph->vexNum; ++i)
428 {
429 if (graph->compare(graph->xList[i].data, vert) == 0)
430 {
431 return i;
432 }
433 }
434 return -1;
435}
436
437//! @brief Delete all outgoing arcs from a vertex in the directed graph.
438//! @param graph - graph to delete from
439//! @param index - index of the vertex
440static void deleteOutgoingArcs(OLGraph* const graph, const int index)
441{
442 if (!graph || (index < 0))
443 {
444 return;
445 }
446
447 const ArcNode* curr = graph->xList[index].firstOut;
448 const ArcNode* del = nullptr;
449 while (curr)
450 {
451 del = curr;
452 curr = curr->tailLink;
453 ::delete del;
454 del = nullptr;
455
456 --graph->arcNum;
457 }
458 graph->xList[index].firstOut = nullptr;
459}
460
461//! @brief Delete all incoming arcs from a vertex in the directed graph.
462//! @param graph - graph to delete from
463//! @param index - index of the vertex
464static void deleteIncomingArcs(OLGraph* const graph, const int index)
465{
466 if (!graph || (index < 0))
467 {
468 return;
469 }
470
471 for (int i = 0; i < graph->vexNum; ++i)
472 {
473 ArcNode* curr = graph->xList[i].firstOut;
474 ArcNode* prev = nullptr;
475 while (curr)
476 {
477 if (curr->headVex != index)
478 {
479 prev = curr;
480 curr = curr->tailLink;
481 continue;
482 }
483
484 prev ? prev->tailLink = curr->tailLink : graph->xList[i].firstOut = curr->tailLink;
485 ::delete curr;
486 curr = nullptr;
487
488 --graph->arcNum;
489 curr = prev ? prev->tailLink : graph->xList[i].firstOut;
490 }
491 }
492}
493
494//! @brief Create the directed graph.
495//! @param cmp - compare function to compare data
496//! @return new directed graph
497OLGraph* create(const Compare cmp)
498{
499 if (!cmp)
500 {
501 return nullptr;
502 }
503
504 auto* const graph = ::new (std::nothrow) OLGraph;
505 if (!graph)
506 {
507 return nullptr;
508 }
509
510 graph->vexNum = 0;
511 graph->arcNum = 0;
512 std::memset(s: graph->xList, c: 0, n: sizeof(graph->xList));
513 graph->compare = cmp;
514 return graph;
515}
516
517//! @brief Destroy the directed graph.
518//! @param graph - graph to destroy
519void destroy(OLGraph* graph)
520{
521 if (!graph)
522 {
523 return;
524 }
525
526 const ArcNode* curr = nullptr;
527 const ArcNode* del = nullptr;
528 for (int i = 0; i < graph->vexNum; ++i)
529 {
530 curr = graph->xList[i].firstOut;
531 while (curr)
532 {
533 del = curr;
534 curr = curr->tailLink;
535 ::delete del;
536 del = nullptr;
537 }
538 graph->xList[i].firstIn = nullptr;
539 graph->xList[i].firstOut = nullptr;
540 }
541
542 ::delete graph;
543 graph = nullptr;
544}
545
546//! @brief Add a vertex into the directed graph.
547//! @param graph - graph to add into
548//! @param vert - vert to add
549//! @return success or failure
550bool addVertex(OLGraph* const graph, const void* const vert)
551{
552 if (!graph || !vert || (graph->vexNum >= maxVertexNum) || (locateVertex(graph, vert) >= 0))
553 {
554 return false;
555 }
556
557 graph->xList[graph->vexNum].firstIn = nullptr;
558 graph->xList[graph->vexNum].firstOut = nullptr;
559 graph->xList[graph->vexNum].data = const_cast<void*>(vert);
560 ++graph->vexNum;
561 return true;
562}
563
564//! @brief Add an arc between two vertices into the directed graph.
565//! @param graph - graph to add into
566//! @param vert1 - vertex at the tail (source) of the arc
567//! @param vert2 - vertex at the head (destination) of the arc
568//! @return success or failure
569bool addArc(OLGraph* const graph, const void* const vert1, const void* const vert2)
570{
571 if (!graph || !vert1 || !vert2)
572 {
573 return false;
574 }
575
576 const int index1 = locateVertex(graph, vert: vert1);
577 const int index2 = locateVertex(graph, vert: vert2);
578 if ((index1 < 0) || (index2 < 0))
579 {
580 return false;
581 }
582
583 const ArcNode* curr = graph->xList[index1].firstOut;
584 while (curr)
585 {
586 if (curr->headVex == index2)
587 {
588 return false;
589 }
590 curr = curr->tailLink;
591 }
592
593 auto* const newNode = ::new (std::nothrow) ArcNode;
594 if (!newNode)
595 {
596 return false;
597 }
598
599 newNode->headVex = index2;
600 newNode->tailVex = index1;
601 newNode->headLink = graph->xList[index2].firstIn;
602 newNode->tailLink = graph->xList[index1].firstOut;
603 graph->xList[index2].firstIn = graph->xList[index1].firstOut = newNode;
604 ++graph->arcNum;
605 return true;
606}
607
608//! @brief Delete a vertex from the directed graph.
609//! @param graph - graph to delete from
610//! @param vert - vert to delete
611//! @return success or failure
612bool deleteVertex(OLGraph* const graph, const void* const vert)
613{
614 if (!graph || !vert)
615 {
616 return false;
617 }
618
619 const int index = locateVertex(graph, vert);
620 if (index < 0)
621 {
622 return false;
623 }
624
625 deleteOutgoingArcs(graph, index);
626 deleteIncomingArcs(graph, index);
627
628 for (int i = index; i < (graph->vexNum - 1); ++i)
629 {
630 graph->xList[i] = graph->xList[i + 1];
631 }
632 --graph->vexNum;
633
634 for (int i = 0; i < graph->vexNum; ++i)
635 {
636 ArcNode* curr = graph->xList[i].firstOut;
637 while (curr)
638 {
639 if (curr->tailVex > index)
640 {
641 --curr->tailVex;
642 }
643 if (curr->headVex > index)
644 {
645 --curr->headVex;
646 }
647 curr = curr->tailLink;
648 }
649 }
650 return true;
651}
652
653//! @brief Delete an arc between two vertices from the directed graph.
654//! @param graph - graph to delete from
655//! @param vert1 - vertex at the tail (source) of the arc
656//! @param vert2 - vertex at the head (destination) of the arc
657//! @return success or failure
658bool deleteArc(OLGraph* const graph, const void* const vert1, const void* const vert2)
659{
660 if (!graph || !vert1 || !vert2)
661 {
662 return false;
663 }
664
665 const int index1 = locateVertex(graph, vert: vert1);
666 const int index2 = locateVertex(graph, vert: vert2);
667 if ((index1 < 0) || (index2 < 0))
668 {
669 return false;
670 }
671
672 ArcNode* curr = graph->xList[index1].firstOut;
673 ArcNode* prev = nullptr;
674 while (curr)
675 {
676 if (curr->headVex != index2)
677 {
678 prev = curr;
679 curr = curr->tailLink;
680 continue;
681 }
682
683 prev ? prev->tailLink = curr->tailLink : graph->xList[index1].firstOut = curr->tailLink;
684 ::delete curr;
685 curr = nullptr;
686
687 --graph->arcNum;
688 return true;
689 }
690 return false;
691}
692
693void Traverse::dfs(const void* const vert, const Operation& op) const
694{
695 if (!graph || !vert || !op)
696 {
697 return;
698 }
699
700 const int start = locateVertex(graph, vert);
701 if (start < 0)
702 {
703 return;
704 }
705
706 bool visited[maxVertexNum] = {};
707 dfsRecursive(index: start, visited, op);
708}
709
710void Traverse::dfsRecursive(const int index, bool visited[], const Operation& op) const
711{
712 if (index < 0)
713 {
714 return;
715 }
716
717 visited[index] = true;
718 op(graph->xList[index].data);
719
720 int neighbors[maxVertexNum];
721 int counter = 0;
722 const ArcNode* curr = graph->xList[index].firstOut;
723 while (curr)
724 {
725 neighbors[counter++] = curr->headVex;
726 curr = curr->tailLink;
727 }
728
729 sortNeighbors(neighbors, size: counter);
730 for (int i = 0; i < counter; ++i)
731 {
732 if (!visited[neighbors[i]])
733 {
734 dfsRecursive(index: neighbors[i], visited, op);
735 }
736 }
737}
738
739void Traverse::bfs(const void* const vert, const Operation& op) const
740{
741 if (!graph || !vert || !op)
742 {
743 return;
744 }
745
746 const int start = locateVertex(graph, vert);
747 if (start < 0)
748 {
749 return;
750 }
751
752 bool visited[maxVertexNum] = {};
753 visited[start] = true;
754 op(graph->xList[start].data);
755
756 int queue[maxVertexNum] = {};
757 int front = 0;
758 int rear = 0;
759 queue[rear++] = start;
760 while (front < rear)
761 {
762 const int q = queue[front++];
763 int neighbors[maxVertexNum];
764 int counter = 0;
765 const ArcNode* curr = graph->xList[q].firstOut;
766 while (curr)
767 {
768 neighbors[counter++] = curr->headVex;
769 curr = curr->tailLink;
770 }
771
772 sortNeighbors(neighbors, size: counter);
773 for (int i = 0; i < counter; ++i)
774 {
775 if (!visited[neighbors[i]])
776 {
777 visited[neighbors[i]] = true;
778 op(graph->xList[neighbors[i]].data);
779 queue[rear++] = neighbors[i];
780 }
781 }
782 }
783}
784
785void Traverse::sortNeighbors(int neighbors[], const int size) const
786{
787 for (int i = 1; i < size; ++i)
788 {
789 const int temp = neighbors[i];
790 int j = i - 1;
791 while ((j >= 0) && (graph->compare(graph->xList[neighbors[j]].data, graph->xList[temp].data) > 0))
792 {
793 neighbors[j + 1] = neighbors[j];
794 --j;
795 }
796 neighbors[j + 1] = temp;
797 }
798}
799} // namespace directed
800// NOLINTEND(cppcoreguidelines-owning-memory, cppcoreguidelines-pro-type-const-cast)
801} // namespace data_structure::graph
802