1//! @file graph.hpp
2//! @author ryftchen
3//! @brief The declarations (graph) in the data structure module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2026 ryftchen. All rights reserved.
6
7#pragma once
8
9#include <functional>
10
11//! @brief The data structure module.
12namespace data_structure // NOLINT(modernize-concat-nested-namespaces)
13{
14//! @brief Graph-related functions in the data structure module.
15namespace graph
16{
17//! @brief Brief function description.
18//! @return function description (module_function)
19inline static const char* description() noexcept
20{
21 return "DS_GRAPH";
22}
23extern const char* version() noexcept;
24
25//! @brief The undirected graph structure.
26namespace undirected
27{
28//! @brief The maximum number of vertices in the graph.
29constexpr int maxVertexNum = 256;
30#ifdef __cplusplus
31extern "C"
32{
33#endif
34 //! @brief Alias for the compare function type.
35 typedef int (*Compare)(const void* const, const void* const);
36
37#pragma pack(push, 8)
38 //! @brief The edge structure in the graph.
39 struct EdgeNode
40 {
41 //! @brief The one endpoint vertex index in the edge.
42 int iVex;
43 //! @brief The other endpoint vertex index in the edge.
44 int jVex;
45 //! @brief Pointer to the next edge in the adjacency list of the one endpoint vertex.
46 struct EdgeNode* iLink;
47 //! @brief Pointer to the next edge in the adjacency list of the other endpoint vertex.
48 struct EdgeNode* jLink;
49 };
50
51 //! @brief The vertex structure in the graph.
52 struct VertexNode
53 {
54 //! @brief Pointer to the first incident edge in the adjacency list.
55 struct EdgeNode* firstEdge;
56 //! @brief Vertex data.
57 void* data;
58 };
59
60 //! @brief The undirected graph structure using an adjacency multi-list.
61 struct AMLGraph
62 {
63 //! @brief Number of vertices.
64 int vexNum;
65 //! @brief Number of edges.
66 int edgeNum;
67 //! @brief Vertex list in the adjacency multi-list representation.
68 struct VertexNode adjMultiList[maxVertexNum];
69 //! @brief The data's compare function.
70 Compare compare;
71 };
72#pragma pack(pop)
73#ifdef __cplusplus
74}
75#endif
76
77extern AMLGraph* create(const Compare cmp);
78extern void destroy(AMLGraph* graph);
79extern bool addVertex(AMLGraph* const graph, const void* const vert);
80extern bool addEdge(AMLGraph* const graph, const void* const vert1, const void* const vert2);
81extern bool deleteVertex(AMLGraph* const graph, const void* const vert);
82extern bool deleteEdge(AMLGraph* const graph, const void* const vert1, const void* const vert2);
83
84//! @brief Do traversing.
85class Traverse
86{
87public:
88 //! @brief Construct a new Traverse object.
89 //! @param graph - graph structure to be traversed
90 explicit Traverse(const AMLGraph* const graph) : graph{graph} {}
91
92 //! @brief Alias for the operation when traversing.
93 using Operation = std::function<void(const void* const)>;
94 //! @brief Perform a breadth-first search (BFS) traversal starting from a given vertex.
95 //! @param vert - starting vertex
96 //! @param op - operation on each vertex
97 void dfs(const void* const vert, const Operation& op) const;
98 //! @brief Perform a depth-first search (DFS) traversal starting from a given vertex.
99 //! @param vert - starting vertex
100 //! @param op - operation on each vertex
101 void bfs(const void* const vert, const Operation& op) const;
102
103private:
104 //! @brief The graph structure to be traversed.
105 const AMLGraph* const graph{nullptr};
106 //! @brief Perform a depth-first search (DFS) traversal recursively.
107 //! @param index - index of the starting vertex
108 //! @param visited - track visited vertices
109 //! @param op - operation on each vertex
110 void dfsRecursive(const int index, std::array<bool, maxVertexNum>& visited, const Operation& op) const;
111 //! @brief Sort the neighbors of a vertex based on their data in ascending order.
112 //! @param neighbors - neighbor indices
113 //! @param size - number of neighbors
114 void sortNeighbors(std::array<int, maxVertexNum>& neighbors, const int size) const;
115};
116} // namespace undirected
117
118//! @brief The directed graph structure.
119namespace directed
120{
121//! @brief The maximum number of vertices in the graph.
122constexpr int maxVertexNum = 256;
123#ifdef __cplusplus
124extern "C"
125{
126#endif
127 //! @brief Alias for the compare function type.
128 typedef int (*Compare)(const void* const, const void* const);
129
130#pragma pack(push, 8)
131 //! @brief The arc structure in the graph.
132 struct ArcNode
133 {
134 //! @brief The head vertex index of the arc.
135 int headVex;
136 //! @brief The tail vertex index of the arc.
137 int tailVex;
138 //! @brief Pointer to the next arc in the incoming arcs list.
139 struct ArcNode* headLink;
140 //! @brief Pointer to the next arc in the outgoing arcs list.
141 struct ArcNode* tailLink;
142 };
143
144 //! @brief The vertex structure in the graph.
145 struct VertexNode
146 {
147 //! @brief Pointer to the first incoming arc.
148 struct ArcNode* firstIn;
149 //! @brief Pointer to the first outgoing arc.
150 struct ArcNode* firstOut;
151 //! @brief Vertex data.
152 void* data;
153 };
154
155 //! @brief The directed graph structure using an orthogonal linked list.
156 struct OLGraph
157 {
158 //! @brief Number of vertices.
159 int vexNum;
160 //! @brief Number of arcs.
161 int arcNum;
162 //! @brief Vertex list in the orthogonal linked list representation.
163 struct VertexNode xList[maxVertexNum];
164 //! @brief The data's compare function.
165 Compare compare;
166 };
167#pragma pack(pop)
168#ifdef __cplusplus
169}
170#endif
171
172extern OLGraph* create(const Compare cmp);
173extern void destroy(OLGraph* graph);
174extern bool addVertex(OLGraph* const graph, const void* const vert);
175extern bool addArc(OLGraph* const graph, const void* const vert1, const void* const vert2);
176extern bool deleteVertex(OLGraph* const graph, const void* const vert);
177extern bool deleteArc(OLGraph* const graph, const void* const vert1, const void* const vert2);
178
179//! @brief Do traversing.
180class Traverse
181{
182public:
183 //! @brief Construct a new Traverse object.
184 //! @param graph - graph structure to be traversed
185 explicit Traverse(const OLGraph* const graph) : graph{graph} {}
186
187 //! @brief Alias for the operation when traversing.
188 using Operation = std::function<void(const void* const)>;
189 //! @brief Perform a breadth-first search (BFS) traversal starting from a given vertex.
190 //! @param vert - starting vertex
191 //! @param op - operation on each vertex
192 void dfs(const void* const vert, const Operation& op) const;
193 //! @brief Perform a depth-first search (DFS) traversal starting from a given vertex.
194 //! @param vert - starting vertex
195 //! @param op - operation on each vertex
196 void bfs(const void* const vert, const Operation& op) const;
197
198private:
199 //! @brief The graph structure to be traversed.
200 const OLGraph* const graph{nullptr};
201 //! @brief Perform a depth-first search (DFS) traversal recursively.
202 //! @param index - index of the starting vertex
203 //! @param visited - track visited vertices
204 //! @param op - operation on each vertex
205 void dfsRecursive(const int index, std::array<bool, maxVertexNum>& visited, const Operation& op) const;
206 //! @brief Sort the neighbors of a vertex based on their data in ascending order.
207 //! @param neighbors - neighbor indices
208 //! @param size - number of neighbors
209 void sortNeighbors(std::array<int, maxVertexNum>& neighbors, const int size) const;
210};
211} // namespace directed
212} // namespace graph
213} // namespace data_structure
214