🔓알고리즘/그래프
네트워크 유량 알고리즘 Network flow [ C++20 / Algorithm ]
728x90
개발환경 >> Visual Studio 2022
언어 >> C++20
운영체제 >> Windows10
[ 참고자료 ]
안녕하세요!!!
이번에는 네트워크 유량에 관한 알고리즘을 객체화해보았습니다.'
바로 시작하겠습니다!
[ 네트워크유량 알고리즘 network flow algorithm ]
우선은 네트워크유량 알고리즘이란?
각각의 변(edge)에 정해진 용량(capacity)보다 작은 흐름(flow)이 주어진 방향 그래프
라고 합니다!!
다음과 같은 그래프가있을때..!
'A'에서 'H'로 가는데 최대한으로 보낼수있는 유량은 몇일까요?
(그림에서 빠뜨렸는데, B -> C로 가는 용량은 4입니다.)
다음에서 나와있는 숫자는 그 간선으로 데이터를 보낼수있는 총 용량 이며,
용량이상으로는 유량의 데이터를 보내지못합니다!
네, 15입니다.
G->H : 5
F->H : 4
E->H : 6
5 + 4 + 6 = 15
그렇다면, 이 알고리즘은 실제로 어떻게 구현될까요?
알고리즘에 관한 참고자료는 위에, 링크로 걸어두었습니다.
추가 설명을 듣고싶으신분은 링크로 들어가서 추가설명을 들어주세요!
[ 네트워크 유량 알고리즘 객체화하여 구현 ] ( C++20 / 위에서만 작동 )
#include <iostream> // C++표준입출력
#include <algorithm> // 알고리즘
#include <vector> // 벡터
#include <queue> // 큐
// 무한대수 정의
constinit int Infinity = (987654321);
// char이나 int만 올수있는 템플릿 정의
template<class OnlybeCharOrInt>
concept CharOrIntIt = requires(OnlybeCharOrInt _OnlybeCharOrInt) {
{ _OnlybeCharOrInt } -> std::convertible_to<int>;
{ _OnlybeCharOrInt } -> std::convertible_to<char>;
};
// 네트워크 유량의 시작점과 끝점을 저장하는 구조체 정의
template<CharOrIntIt _CharOrIntIt>
struct dist {
_CharOrIntIt start, end;
dist(_CharOrIntIt start, _CharOrIntIt end) : start(start), end(end) { }
};
// 네트워크유량 알고리즘을 객체화한 클래스
template<CharOrIntIt _CharOrIntIt>
class NetworkFlow {
private:
int _Executed = 0; // Execute함수 재사용시 내용물 초기화할지 정하는 함수
int DotIt, ResultOf; // 정점의 갯수, 결과값
std::vector<dist<_CharOrIntIt>> _Costs; // 네트워크유량을 저장
std::vector<std::vector<int>> _Cc, _Ff; // 용량, 유량
public:
int Value() { return (this->ResultOf); } // 결과값 반환하는 함수
void Execute(_CharOrIntIt _StartOf, _CharOrIntIt _EndOf) { // 네트워크유량 알고리즘 함수
if (_Executed++) Clear();
// 이 부분은 클래스의 유연성을 늘리고, 메모리를 아끼기 위한 부분중 하나로,
// char자료형의 데이터를 모두 int로 바꿔줍니다.
if (std::_Is_character<_CharOrIntIt>::value) {
if (65 <= _StartOf && _StartOf <= 90) _StartOf -= 64;
if (65 <= _EndOf && _EndOf <= 90) _EndOf -= 64;
if (97 <= _StartOf && _StartOf <= 122) _StartOf -= 96;
if (97 <= _EndOf && _EndOf <= 122) _EndOf -= 96;
}
while (true) {
std::vector<int> _Visited(this->DotIt + 1, -1); // 해당 정점 방문여부
std::queue<int> _Queue; // 큐
_Queue.push(_StartOf);
while (!_Queue.empty()) {
int x = _Queue.front(); // 차례대로 정점의 시작점을 뺀다.
_Queue.pop();
for (size_t i = 0; i < _Costs.size(); ++i) {
if (_Costs[i].start == x) { // 그 정점의 시작점에서 이어지는 도착점들을 순회
const int y = _Costs[i].end; // 그 정점의 도착점
if (_Cc[x][y] - _Ff[x][y] > 0 && _Visited[y] == -1) {
//만약 (용량 - 유량)이 양수인 동시에 방문안한 정점일시
_Queue.push(y);
_Visited[y] = x;
if (y == _EndOf) break;
}
}
}
}
if (_Visited[_EndOf] == -1) break; // 도착지점에 왔을경우 종료
int flow = Infinity; // 유량의 최솟값을 찾기위해, 초기값을 무한대수로 정의
for (int i = _EndOf; i != _StartOf; i = _Visited[i]) // 각 정점에 대한 (용량-유량)의 최솟값구하기
flow = std::min(flow, _Cc[_Visited[i]][i] - _Ff[_Visited[i]][i]);
for (int i = _EndOf; i != _StartOf; i = _Visited[i]) {
_Ff[_Visited[i]][i] += flow; // 구한최솟값을 기준으로 정점을 거꾸로 거슬러가며
_Ff[i][_Visited[i]] -= flow; // 시작지점까지 갈때까지 흐를수있는 유량계산
}
this->ResultOf += flow;
}
}
void Add(_CharOrIntIt start, _CharOrIntIt end, int cost) { //각 정점에 대한 비용을 저장할 함수
if (std::_Is_character<_CharOrIntIt>::value) { // (위에서 설명했으므로 생략)
if (65 <= start && start <= 90) start -= 64;
if (65 <= end && end <= 90) end -= 64;
if (97 <= start && start <= 122) start -= 96;
if (97 <= end && end <= 122) end -= 96;
}
_Costs.push_back(dist(start, end));
_Costs.push_back(dist(end, start));
_Cc[start][end] = cost;
}
constexpr void SetN(int DotIt) { // 총 정점의 객수를 입력하는 함수
this->DotIt = DotIt;
_Cc.clear();
_Ff.clear();
_Costs.clear();
this->ResultOf = 0;
_Cc.resize(this->DotIt + 1);
_Ff.resize(this->DotIt + 1);
for (int i = 0; i < this->DotIt + 1; ++i) {
_Cc[i].resize(this->DotIt + 1);
_Ff[i].resize(this->DotIt + 1);
std::fill(_Cc[i].begin(), _Cc[i].end(), 0);
std::fill(_Ff[i].begin(), _Ff[i].end(), 0);
}
}
constexpr void Clear() { // 내용초기화함수
_Ff.clear();
this->ResultOf = 0;
_Ff.resize(this->DotIt + 1);
for (int i = 0; i < this->DotIt + 1; ++i) {
_Ff[i].resize(this->DotIt + 1);
std::fill(_Ff[i].begin(), _Ff[i].end(), 0);
}
}
NetworkFlow() noexcept = default;
explicit(true) NetworkFlow(int N) noexcept { SetN(N); }
~NetworkFlow() noexcept { }
};
자,, 그러면!!!
테스트를 해보겠습니다!!
예시 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <conio.h>
constinit int Infinity = (987654321);
template<class OnlybeCharOrInt>
concept CharOrIntIt = requires(OnlybeCharOrInt _OnlybeCharOrInt) {
{ _OnlybeCharOrInt } -> std::convertible_to<int>;
{ _OnlybeCharOrInt } -> std::convertible_to<char>;
};
template<CharOrIntIt _CharOrIntIt>
struct dist {
_CharOrIntIt start, end;
dist(_CharOrIntIt start, _CharOrIntIt end) : start(start), end(end) { }
};
template<CharOrIntIt _CharOrIntIt>
class NetworkFlow {
private:
int DotIt, ResultOf;
std::vector<dist<_CharOrIntIt>> _Costs;
std::vector<std::vector<int>> _Cc, _Ff;
public:
int Value() { return (this->ResultOf); }
void Execute(_CharOrIntIt _StartOf, _CharOrIntIt _EndOf) {
if (std::_Is_character<_CharOrIntIt>::value) {
if (65 <= _StartOf && _StartOf <= 90) _StartOf -= 64;
if (65 <= _EndOf && _EndOf <= 90) _EndOf -= 64;
if (97 <= _StartOf && _StartOf <= 122) _StartOf -= 96;
if (97 <= _EndOf && _EndOf <= 122) _EndOf -= 96;
}
while (true) {
std::vector<int> _Visited(this->DotIt + 1, -1);
std::queue<int> _Queue;
_Queue.push(_StartOf);
while (!_Queue.empty()) {
int x = _Queue.front();
_Queue.pop();
for (size_t i = 0; i < _Costs.size(); ++i) {
if (_Costs[i].start == x) {
const int y = _Costs[i].end;
if (_Cc[x][y] - _Ff[x][y] > 0 && _Visited[y] == -1) {
_Queue.push(y);
_Visited[y] = x;
if (y == _EndOf) break;
}
}
}
}
if (_Visited[_EndOf] == -1) break;
int flow = Infinity;
for (int i = _EndOf; i != _StartOf; i = _Visited[i])
flow = std::min(flow, _Cc[_Visited[i]][i] - _Ff[_Visited[i]][i]);
for (int i = _EndOf; i != _StartOf; i = _Visited[i]) {
_Ff[_Visited[i]][i] += flow;
_Ff[i][_Visited[i]] -= flow;
}
this->ResultOf += flow;
}
}
void Add(_CharOrIntIt start, _CharOrIntIt end, int cost) {
if (std::_Is_character<_CharOrIntIt>::value) {
if (65 <= start && start <= 90) start -= 64;
if (65 <= end && end <= 90) end -= 64;
if (97 <= start && start <= 122) start -= 96;
if (97 <= end && end <= 122) end -= 96;
}
_Costs.push_back(dist(start, end));
_Costs.push_back(dist(end, start));
_Cc[start][end] = cost;
}
constexpr void SetN(int DotIt) {
this->DotIt = DotIt;
_Cc.clear();
_Ff.clear();
_Costs.clear();
this->ResultOf = 0;
_Cc.resize(this->DotIt + 1);
_Ff.resize(this->DotIt + 1);
for (int i = 0; i < this->DotIt + 1; ++i) {
_Cc[i].resize(this->DotIt + 1);
_Ff[i].resize(this->DotIt + 1);
std::fill(_Cc[i].begin(), _Cc[i].end(), 0);
std::fill(_Ff[i].begin(), _Ff[i].end(), 0);
}
}
NetworkFlow() noexcept = default;
explicit(true) NetworkFlow(int N) noexcept { SetN(N); }
~NetworkFlow() noexcept { }
};
void NetworkFlowFunc() {
NetworkFlow<char> nf;
nf.SetN(8);
nf.Add('A', 'B', 16);
nf.Add('A', 'C', 9);
nf.Add('A', 'D', 17);
nf.Add('B', 'G', 5);
nf.Add('B', 'C', 4);
nf.Add('C', 'F', 9);
nf.Add('D', 'C', 6);
nf.Add('D', 'E', 7);
nf.Add('E', 'F', 3);
nf.Add('E', 'H', 6);
nf.Add('F', 'H', 4);
nf.Add('G', 'H', 7);
nf.Execute('A', 'H');
std::cout << "결과값 : " << nf.Value() << std::endl;
}
이런식으로 사용하셔도됩니다!!
void NetworkFlowFunc() {
NetworkFlow<char> nf;
nf.SetN(8);
nf.Add('A', 'B', 16);
nf.Add('A', 'C', 9);
nf.Add('A', 'D', 17);
nf.Add('B', 'G', 5);
nf.Add('B', 'C', 4);
nf.Add('C', 'F', 9);
nf.Add('D', 'C', 6);
nf.Add('D', 'E', 7);
nf.Add('E', 'F', 3);
nf.Add('E', 'H', 6);
nf.Add('F', 'H', 4);
nf.Add('G', 'H', 7);
nf.Execute('A', 'H');
std::cout << "결과값1 : " << nf.Value() << std::endl;
NetworkFlow<int> nff;
nff.SetN(8);
nff.Add(1, 2, 16);
nff.Add(1, 3, 9);
nff.Add(1, 4, 17);
nff.Add(2, 7, 5);
nff.Add(2, 3, 4);
nff.Add(3, 6, 9);
nff.Add(4, 3, 6);
nff.Add(4, 5, 7);
nff.Add(5, 6, 3);
nff.Add(5, 8, 6);
nff.Add(6, 8, 4);
nff.Add(7, 8, 7);
nff.Execute(1, 8);
std::cout << "결과값2 : " << nff.Value() << std::endl;
}
와우~~~~~ 끝!!!
728x90
'🔓알고리즘 > 그래프' 카테고리의 다른 글
| 최단거리 경로탐색 프로그램 다운로드및 설명 (0) | 2021.08.05 |
|---|
댓글