알고리즘...109

에지 삽입, 삭제 구현

Graph_AdjacencyMatrix.h

#pragma once
#include "Graph.h"
#include <algorithm>

/// <summary>
/// 그래프의 구성 요소 테스트를 위한 베이스 클래스
/// </summary>
class Graph_AdjacencyMatrix : public Graph
{
public:
	Graph_AdjacencyMatrix(GraphOption graphOption = GraphOption::Undirected, size_t size = 10);

	virtual bool AddNode(string name);
	virtual void AddEdge(string from, string to, int weight = 1);
	virtual bool RemoveNode(string name);
	virtual void RemoveEdge(string from, string to);
	virtual void Clear();

	virtual void PrintGraph(GraphTraversal graphTraversal = GraphTraversal::BFS, string graphName = "Graph_AdjacencyMatrix");

private:
	void Resize();

protected:
	size_t GetNodeCapacity() { return m_capacity; }

private:
	int** m_matrix;
	size_t m_capacity;
};

 

Graph_AdjacencyMatrix.cpp

#include "Graph_AdjacencyMatrix.h"

#pragma region Public Functions
/// <summary>
/// 그래프 옵션을 결정하고 그래프의 최초 크기를 설정한다.
/// </summary>
/// <param name="graphOption">그래프 옵션</param>
/// <param name="size">그래프 크기</param>
Graph_AdjacencyMatrix::Graph_AdjacencyMatrix(GraphOption graphOption, size_t size)
	: Graph(graphOption)
{
	m_capacity = size;
	
	m_matrix = new int* [size];
	for (size_t i = 0; i < size; i++)
	{
		m_matrix[i] = new int[size];
		std::fill_n(m_matrix[i], size, 0);
	}
}

/// <summary>
/// 그래프에 노드를 추가한다.
/// </summary>
/// <param name="name">추가할 노드 이름</param>
/// <returns>성공 여부</returns>
bool Graph_AdjacencyMatrix::AddNode(string name)
{
	if (!Graph::AddNode(name))
	{
		return false;
	}

	if (GetNodeCount() >= m_capacity)
	{
		Resize();
	}

	return true;
}

/// <summary>
/// 그래프에 에지를 추가한다.
/// </summary>
/// <param name="from">시작 노드</param>
/// <param name="to">끝 노드</param>
/// <param name="weight">가중치(기본: 1)</param>
void Graph_AdjacencyMatrix::AddEdge(string from, string to, int weight)
{
	size_t fromIdx{ GetNodeIndex(from) }, toIdx{ GetNodeIndex(to) };

	if (fromIdx != -1 && toIdx != -1)
	{
		m_matrix[fromIdx][toIdx] = weight;

		if (CurrentGraphOption() == GraphOption::Undirected)
		{
			m_matrix[toIdx][fromIdx] = weight;
		}
	}
}

/// <summary>
/// 그래프에서 노드를 제거한다.
/// </summary>
/// <param name="name">제거할 노드 이름</param>
/// <returns>성공 여부</returns>
bool Graph_AdjacencyMatrix::RemoveNode(string name)
{
	size_t idx{ GetNodeIndex(name) };

	if (!Graph::RemoveNode(name))
	{
		return false;
	}

	for (size_t i = 0; i < m_capacity; i++)
	{
		m_matrix[idx][i] = 0;
		m_matrix[i][idx] = 0;
	}

	return true;
}

/// <summary>
/// 그래프에서 에지를 제거한다.
/// </summary>
/// <param name="from">시작 노드</param>
/// <param name="to">끝 노드</param>
void Graph_AdjacencyMatrix::RemoveEdge(string from, string to)
{
	size_t fromIdx{ GetNodeIndex(from) }, toIdx{ GetNodeIndex(to) };

	if (fromIdx != -1 && toIdx != -1)
	{
		m_matrix[fromIdx][toIdx] = 0;

		if (CurrentGraphOption() == GraphOption::Undirected)
		{
			m_matrix[toIdx][fromIdx] = 0;
		}
	}
}

/// <summary>
/// 그래프를 초기화한다.
/// </summary>
void Graph_AdjacencyMatrix::Clear()
{
	Graph::Clear();

	for (size_t i = 0; i < m_capacity; i++)
	{
		std::fill_n(m_matrix[i], m_capacity, 0);
	}
}

/// <summary>
/// 해시 테이블의 현 상태를 출력한다.
/// </summary>
void Graph_AdjacencyMatrix::PrintGraph(GraphTraversal graphTraversal, string graphName)
{
	Graph::PrintGraph(graphTraversal, graphName);

	// GraphTraversal 에 따라 두 가지 버전 추가 필요
}
#pragma endregion

#pragma region Private Functions
/// <summary>
/// 그래프의 크기를 두배로 늘린다.
/// </summary>
void Graph_AdjacencyMatrix::Resize()
{
	size_t tempCapacity{ m_capacity * 2 };
	int** tempMatrix{ new int* [tempCapacity] };
	for (size_t i = 0; i < tempCapacity; i++)
	{
		tempMatrix[i] = new int[tempCapacity];
		std::fill_n(tempMatrix[i], tempCapacity, 0);
	}

	for (size_t i = 0; i < m_capacity; i++)
	{
		std::copy_n(m_matrix[i], m_capacity, tempMatrix[i]);
		delete[] m_matrix[i];
	}
	delete[] m_matrix;

	m_capacity = tempCapacity;
	m_matrix = tempMatrix;
}
#pragma endregion