146 lines
4.8 KiB
C++
146 lines
4.8 KiB
C++
#ifndef MATRIXGRAPH_H
|
|
#define MATRIXGRAPH_H
|
|
|
|
#include "DynamicArray.h"
|
|
#include "Exception.h"
|
|
#include "Graph.h"
|
|
|
|
namespace Kylin {
|
|
|
|
/**
|
|
* MatrixGraph row即为起始点Vertex的index,col即为终止点的index
|
|
*/
|
|
template <int N, typename VertexType, typename EdgeType>
|
|
class MatrixGraph : public Graph<VertexType, EdgeType> {
|
|
public:
|
|
VertexType vertex(size_t index) const final {
|
|
if (index >= vertexCount()) THROW_EXCEPTION(IndexOutOfBoundsException, "Index is out of bounds.");
|
|
if (m_vetexes[index] != nullptr) {
|
|
return *(m_vetexes[index]);
|
|
} else {
|
|
THROW_EXCEPTION(InvalidOperationException, "No value assigned to this vertex.");
|
|
}
|
|
}
|
|
|
|
bool setVertex(size_t index, const VertexType &value) final {
|
|
bool ret = ((0 <= index) && (index < vertexCount()));
|
|
if (!ret) return false;
|
|
auto data = m_vetexes[index];
|
|
if (data == nullptr) data = new VertexType();
|
|
if (data != nullptr) {
|
|
*data = value;
|
|
m_vetexes[index] = data;
|
|
} else {
|
|
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to store new vertex value ...");
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
/**
|
|
* @brief 获取与Vertex[index]相邻接的顶点(Vertex[index]作为起始点)
|
|
*/
|
|
DynamicArray<size_t> adjacent(size_t index) const final {
|
|
if ((0 <= index) && (index < vertexCount())) {
|
|
size_t n = 0;
|
|
for (size_t j = 0; j < vertexCount(); j++) {
|
|
if (m_edges[index][j] != nullptr) {
|
|
n++;
|
|
}
|
|
}
|
|
DynamicArray<size_t> ret(n);
|
|
for (size_t j = 0, k = 0; j < vertexCount(); j++) {
|
|
if (m_edges[index][j] != nullptr) ret[k++] = j;
|
|
}
|
|
return ret;
|
|
} else {
|
|
THROW_EXCEPTION(InvalidParameterException, "Index is invalid...");
|
|
}
|
|
}
|
|
|
|
std::optional<EdgeType> edge(size_t start, size_t end) const final {
|
|
bool status = ((0 <= start) && (start < vertexCount())) && ((0 <= end) && (end < vertexCount()));
|
|
if (!status) return std::optional<EdgeType>{};
|
|
if (m_edges[start][end] != nullptr) {
|
|
return std::optional<EdgeType>{*(m_edges[start][end])};
|
|
} else {
|
|
return std::optional<EdgeType>{};
|
|
}
|
|
}
|
|
|
|
bool setEdge(size_t start, size_t end, const EdgeType &value) final {
|
|
bool ret = ((0 <= start) && (start < vertexCount())) && ((0 <= end) && (end < vertexCount()));
|
|
if (!ret) return false;
|
|
auto ne = m_edges[start][end];
|
|
if (ne == nullptr) {
|
|
ne = new EdgeType();
|
|
if (ne != nullptr) {
|
|
*ne = value;
|
|
m_edges[start][end] = ne;
|
|
m_edgeCount++;
|
|
} else {
|
|
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to store new edge value ...");
|
|
}
|
|
} else {
|
|
*ne = value;
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
bool removeEdge(size_t start, size_t end) final {
|
|
bool ret = ((0 <= start) && (start < vertexCount())) && ((0 <= end) && (end < vertexCount()));
|
|
if (!ret) return false;
|
|
auto toDel = m_edges[start][end];
|
|
m_edges[start][end] = nullptr;
|
|
if (toDel != nullptr) {
|
|
m_edgeCount--;
|
|
delete toDel;
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
size_t vertexCount() const final { return N; }
|
|
|
|
size_t edgeCount() const final { return m_edgeCount; }
|
|
|
|
size_t outDegree(size_t index) const final {
|
|
size_t ret = 0;
|
|
if ((0 <= index) && (index < vertexCount())) {
|
|
for (size_t j = 0; j < vertexCount(); j++) {
|
|
if (m_edges[index][j] != nullptr) ret++;
|
|
}
|
|
} else {
|
|
THROW_EXCEPTION(InvalidParameterException, "Index i is invalid ...");
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
size_t inDegree(size_t index) const final {
|
|
size_t ret = 0;
|
|
if ((0 <= index) && (index < vertexCount())) {
|
|
for (size_t i = 0; i < vertexCount(); i++) {
|
|
if (m_edges[i][index] != nullptr) ret++;
|
|
}
|
|
} else {
|
|
THROW_EXCEPTION(InvalidParameterException, "Index j is invalid ...");
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
~MatrixGraph() {
|
|
auto vetexes = vertexCount();
|
|
for (size_t i = 0; i < vetexes; i++) {
|
|
for (size_t j = 0; j < vetexes; j++) {
|
|
delete m_edges[i][j];
|
|
}
|
|
delete m_vetexes[i];
|
|
}
|
|
}
|
|
|
|
protected:
|
|
VertexType *m_vetexes[N] = {nullptr};
|
|
EdgeType *m_edges[N][N] = {nullptr};
|
|
size_t m_edgeCount = 0;
|
|
};
|
|
} // namespace Kylin
|
|
#endif // MATRIXGRAPH_H
|