// adjacency_matrix_graph.tpp
#ifndef ADJACENCY_MATRIX_GRAPH_TPP
#define ADJACENCY_MATRIX_GRAPH_TPP
template<typename VertexType, typename WeightType>
AdjacencyMatrixGraph<VertexType, WeightType>::AdjacencyMatrixGraph(
GraphType type, GraphWeightType weight_type, WeightType no_edge)
: graph_type_(type), weight_type_(weight_type), no_edge_value_(no_edge),
vertex_count_(0), edge_count_(0) {
// 初始化空矩阵
matrix_ = std::vector<std::vector<WeightType>>(0, std::vector<WeightType>(0, no_edge_value_));
}
template<typename VertexType, typename WeightType>
bool AdjacencyMatrixGraph<VertexType, WeightType>::addVertex(const VertexType& vertex) {
// 检查顶点是否已存在
if (vertex_index_map_.find(vertex) != vertex_index_map_.end()) {
return false;
}
// 添加新顶点
int new_index = vertex_count_;
vertices_.push_back(vertex);
vertex_index_map_[vertex] = new_index;
vertex_count_++;
// 调整矩阵大小
resizeMatrix(vertex_count_);
return true;
}
template<typename VertexType, typename WeightType>
bool AdjacencyMatrixGraph<VertexType, WeightType>::removeVertex(const VertexType& vertex) {
// 查找顶点索引
auto it = vertex_index_map_.find(vertex);
if (it == vertex_index_map_.end()) {
return false;
}
int index_to_remove = it->second;
// 计算要删除的边数
int edges_removed = 0;
for (int i = 0; i < vertex_count_; i++) {
if (matrix_[index_to_remove][i] != no_edge_value_) {
edges_removed++;
}
if (matrix_[i][index_to_remove] != no_edge_value_) {
edges_removed++;
}
}
// 如果是无向图，每条边被计算了两次
if (graph_type_ == UNDIRECTED) {
edges_removed /= 2;
}
// 从顶点列表中移除
vertices_.erase(vertices_.begin() + index_to_remove);
vertex_index_map_.erase(vertex);
// 更新其他顶点的索引映射
for (auto& pair : vertex_index_map_) {
if (pair.second > index_to_remove) {
pair.second--;
}
}
// 从矩阵中移除对应的行和列
matrix_.erase(matrix_.begin() + index_to_remove);
for (auto& row : matrix_) {
row.erase(row.begin() + index_to_remove);
}
vertex_count_--;
edge_count_ -= edges_removed;
return true;
}
template<typename VertexType, typename WeightType>
bool AdjacencyMatrixGraph<VertexType, WeightType>::addEdge(
const VertexType& v1, const VertexType& v2, WeightType weight) {
// 查找顶点索引
auto it1 = vertex_index_map_.find(v1);
auto it2 = vertex_index_map_.find(v2);
if (it1 == vertex_index_map_.end() || it2 == vertex_index_map_.end()) {
return false;
}
int idx1 = it1->second;
int idx2 = it2->second;
// 无权图使用固定权重1
if (weight_type_ == UNWEIGHTED) {
weight = WeightType(1);
}
// 添加边
if (matrix_[idx1][idx2] == no_edge_value_) {
matrix_[idx1][idx2] = weight;
edge_count_++;
} else {
matrix_[idx1][idx2] = weight; // 更新已存在边的权重
}
// 如果是无向图，添加对称边
if (graph_type_ == UNDIRECTED && idx1 != idx2) {
if (matrix_[idx2][idx1] == no_edge_value_) {
matrix_[idx2][idx1] = weight;
} else {
matrix_[idx2][idx1] = weight;
}
}
return true;
}
template<typename VertexType, typename WeightType>
bool AdjacencyMatrixGraph<VertexType, WeightType>::removeEdge(
const VertexType& v1, const VertexType& v2) {
auto it1 = vertex_index_map_.find(v1);
auto it2 = vertex_index_map_.find(v2);
if (it1 == vertex_index_map_.end() || it2 == vertex_index_map_.end()) {
return false;
}
int idx1 = it1->second;
int idx2 = it2->second;
if (matrix_[idx1][idx2] == no_edge_value_) {
return false;
}
// 移除边
matrix_[idx1][idx2] = no_edge_value_;
edge_count_--;
// 如果是无向图，移除对称边
if (graph_type_ == UNDIRECTED) {
matrix_[idx2][idx1] = no_edge_value_;
}
return true;
}
template<typename VertexType, typename WeightType>
int AdjacencyMatrixGraph<VertexType, WeightType>::getVertexIndex(const VertexType& vertex) const {
auto it = vertex_index_map_.find(vertex);
return (it != vertex_index_map_.end()) ? it->second : -1;
}
template<typename VertexType, typename WeightType>
std::vector<VertexType> AdjacencyMatrixGraph<VertexType, WeightType>::getAdjacentVertices(
const VertexType& vertex) const {
std::vector<VertexType> adjacent;
auto it = vertex_index_map_.find(vertex);
if (it == vertex_index_map_.end()) {
return adjacent;
}
int idx = it->second;
for (int i = 0; i < vertex_count_; i++) {
if (matrix_[idx][i] != no_edge_value_) {
adjacent.push_back(vertices_[i]);
}
}
return adjacent;
}
template<typename VertexType, typename WeightType>
VertexType AdjacencyMatrixGraph<VertexType, WeightType>::getFirstAdjacentVertex(
const VertexType& vertex) const {
auto it = vertex_index_map_.find(vertex);
if (it == vertex_index_map_.end()) {
throw std::invalid_argument("Vertex not found");
}
int idx = it->second;
for (int i = 0; i < vertex_count_; i++) {
if (matrix_[idx][i] != no_edge_value_) {
return vertices_[i];
}
}
throw std::runtime_error("No adjacent vertices found");
}
template<typename VertexType, typename WeightType>
VertexType AdjacencyMatrixGraph<VertexType, WeightType>::getNextAdjacentVertex(
const VertexType& vertex, const VertexType& prev) const {
auto it_vertex = vertex_index_map_.find(vertex);
auto it_prev = vertex_index_map_.find(prev);
if (it_vertex == vertex_index_map_.end() || it_prev == vertex_index_map_.end()) {
throw std::invalid_argument("Vertex not found");
}
int idx_vertex = it_vertex->second;
int idx_prev = it_prev->second;
// 从prev的下一个位置开始查找
for (int i = idx_prev + 1; i < vertex_count_; i++) {
if (matrix_[idx_vertex][i] != no_edge_value_) {
return vertices_[i];
}
}
throw std::runtime_error("No next adjacent vertex found");
}
template<typename VertexType, typename WeightType>
bool AdjacencyMatrixGraph<VertexType, WeightType>::hasEdge(
const VertexType& v1, const VertexType& v2) const {
auto it1 = vertex_index_map_.find(v1);
auto it2 = vertex_index_map_.find(v2);
if (it1 == vertex_index_map_.end() || it2 == vertex_index_map_.end()) {
return false;
}
return matrix_[it1->second][it2->second] != no_edge_value_;
}
template<typename VertexType, typename WeightType>
WeightType AdjacencyMatrixGraph<VertexType, WeightType>::getEdgeWeight(
const VertexType& v1, const VertexType& v2) const {
auto it1 = vertex_index_map_.find(v1);
auto it2 = vertex_index_map_.find(v2);
if (it1 == vertex_index_map_.end() || it2 == vertex_index_map_.end()) {
throw std::invalid_argument("Vertex not found");
}
WeightType weight = matrix_[it1->second][it2->second];
if (weight == no_edge_value_) {
throw std::runtime_error("Edge does not exist");
}
return weight;
}
template<typename VertexType, typename WeightType>
std::vector<VertexType> AdjacencyMatrixGraph<VertexType, WeightType>::bfs(
const VertexType& start_vertex) const {
std::vector<VertexType> result;
auto it = vertex_index_map_.find(start_vertex);
if (it == vertex_index_map_.end()) {
return result;
}
int start_index = it->second;
std::vector<bool> visited(vertex_count_, false);
std::queue<int> q;
visited[start_index] = true;
q.push(start_index);
while (!q.empty()) {
int current = q.front();
q.pop();
result.push_back(vertices_[current]);
for (int i = 0; i < vertex_count_; i++) {
if (matrix_[current][i] != no_edge_value_ && !visited[i]) {
visited[i] = true;
q.push(i);
}
}
}
return result;
}
template<typename VertexType, typename WeightType>
std::vector<VertexType> AdjacencyMatrixGraph<VertexType, WeightType>::dfs(
const VertexType& start_vertex) const {
std::vector<VertexType> result;
auto it = vertex_index_map_.find(start_vertex);
if (it == vertex_index_map_.end()) {
return result;
}
std::vector<bool> visited(vertex_count_, false);
dfsUtil(it->second, visited, result);
return result;
}
template<typename VertexType, typename WeightType>
void AdjacencyMatrixGraph<VertexType, WeightType>::dfsUtil(
int vertex_index, std::vector<bool>& visited, std::vector<VertexType>& result) const {
visited[vertex_index] = true;
result.push_back(vertices_[vertex_index]);
for (int i = 0; i < vertex_count_; i++) {
if (matrix_[vertex_index][i] != no_edge_value_ && !visited[i]) {
dfsUtil(i, visited, result);
}
}
}
template<typename VertexType, typename WeightType>
void AdjacencyMatrixGraph<VertexType, WeightType>::resizeMatrix(int new_size) {
// 保存旧矩阵
auto old_matrix = matrix_;
int old_size = old_matrix.size();
// 创建新矩阵
matrix_.resize(new_size);
for (int i = 0; i < new_size; i++) {
matrix_[i].resize(new_size, no_edge_value_);
}
// 复制旧数据
for (int i = 0; i < std::min(old_size, new_size); i++) {
for (int j = 0; j < std::min(old_size, new_size); j++) {
matrix_[i][j] = old_matrix[i][j];
}
}
}
template<typename VertexType, typename WeightType>
bool AdjacencyMatrixGraph<VertexType, WeightType>::isValidVertexIndex(int index) const {
return index >= 0 && index < vertex_count_;
}
template<typename VertexType, typename WeightType>
void AdjacencyMatrixGraph<VertexType, WeightType>::printMatrix() const {
std::cout << "Adjacency Matrix:" << std::endl;
std::cout << " ";
for (int i = 0; i < vertex_count_; i++) {
std::cout << vertices_[i] << " ";
}
std::cout << std::endl;
for (int i = 0; i < vertex_count_; i++) {
std::cout << vertices_[i] << " ";
for (int j = 0; j < vertex_count_; j++) {
if (matrix_[i][j] == no_edge_value_) {
std::cout << "0 ";
} else {
std::cout << matrix_[i][j] << " ";
}
}
std::cout << std::endl;
}
}
template<typename VertexType, typename WeightType>
void AdjacencyMatrixGraph<VertexType, WeightType>::printGraph() const {
std::cout << "Graph Information:" << std::endl;
std::cout << "Type: " << (graph_type_ == UNDIRECTED ? "Undirected" : "Directed") << std::endl;
std::cout << "Weight Type: " << (weight_type_ == UNWEIGHTED ? "Unweighted" : "Weighted") << std::endl;
std::cout << "Vertices: " << vertex_count_ << std::endl;
std::cout << "Edges: " << edge_count_ << std::endl;
std::cout << "Vertices: ";
for (const auto& vertex : vertices_) {
std::cout << vertex << " ";
}
std::cout << std::endl;
std::cout << "Edges:" << std::endl;
for (int i = 0; i < vertex_count_; i++) {
for (int j = 0; j < vertex_count_; j++) {
if (matrix_[i][j] != no_edge_value_) {
if (graph_type_ == UNDIRECTED && i <= j) {
std::cout << " " << vertices_[i] << " - " << vertices_[j];
if (weight_type_ == WEIGHTED) {
std::cout << " (" << matrix_[i][j] << ")";
}
std::cout << std::endl;
} else if (graph_type_ == DIRECTED) {
std::cout << " " << vertices_[i] << " -> " << vertices_[j];
if (weight_type_ == WEIGHTED) {
std::cout << " (" << matrix_[i][j] << ")";
}
std::cout << std::endl;
}
}
}
}
}
#endif // ADJACENCY_MATRIX_GRAPH_TPP