🔓알고리즘/그래프

네트워크 유량 알고리즘 Network flow [ C++20 / Algorithm ]

Mawile 2021. 6. 19.

개발환경 >> 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;
}

와우~~~~~ 끝!!!

'🔓알고리즘 > 그래프' 카테고리의 다른 글

최단거리 경로탐색 프로그램 다운로드및 설명 (0)	2021.08.05

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

네트워크 유량 알고리즘 Network flow [ C++20 / Algorithm ]

개발환경 >> Visual Studio 2022

언어 >> C++20

운영체제 >> Windows10

[ 참고자료 ]

'A'에서 'H'로 가는데 최대한으로 보낼수있는 유량은 몇일까요?

(그림에서 빠뜨렸는데, B -> C로 가는 용량은 4입니다.)

와우~~~~~ 끝!!!

'🔓알고리즘 > 그래프' 카테고리의 다른 글

댓글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역