CXXGraph
v4.1.0
CXXGraph 는 그래프 알고리즘을 관리하는 포괄적인 C++ 라이브러리입니다. 이 헤더 전용 라이브러리는 Boost Graph Library(BGL)의 대안으로 사용됩니다.
우리는 다음을 찾고 있습니다:
관심이 있으시면 [email protected]으로 연락하시거나 이 프로젝트에 참여해 주시기 바랍니다. 우리는 당신을 기다리고 있습니다!
| 완전한 | 설명 | 완료 날짜 |
|---|---|---|
| ✔️ | 릴리스 0.4.0 | 2022년 10월 7일 |
| ✔️ | 릴리스 0.5.0 | 2023년 3월 23일 |
| ✔️ | 첫 번째 안정 릴리스 1.0.0 | 2023년 3월 28일 |
| ✔️ | 릴리스 1.0.1 | 2023년 5월 7일 |
| ✔️ | 릴리스 1.1.0 | 2023년 5월 8일 |
| ✔️ | 안정 릴리스 2.0.0 | 2023년 6월 1일 |
| ✔️ | 안정 릴리스 3.0.0 | 2023년 11월 3일 |
| ✔️ | 릴리스 3.1.0 | 2023년 1월 9일 |
| 하이퍼그래프 #122 소개 | 미정 | |
| 안정 릴리스 4.0.0 | 미정 |
Unix/Linux 시스템에 설치하려면 명령줄에서 다음을 실행합니다.
$ sudo tar xjf CXXGraph-{version}.tar.bz2
제거하려면:
$ sudo rm -f /usr/include/Graph.hpp /usr/include/CXXGraph*
Fedora/CentOS/RedHat 시스템에 설치하려면 명령줄에서 다음을 실행합니다.
$ sudo rpm -ivh CXXGraph-{version}.noarch.rpm
제거하려면:
$ sudo rpm -e CXXGraph-{version}
Debian/Ubuntu 시스템에 설치하려면 명령줄에서 다음을 실행하세요.
$ sudo dpkg -i CXXGraph_{version}.deb
제거하려면:
$ sudo apt-get remove CXXGraph
CMake를 사용하여 자체 컴파일된 설치의 경우 컴파일이 완료되면 명령줄에서 다음을 실행합니다.
$ sudo make install
클래스 설명은 Doxygen 문서의 클래스 섹션에서 찾을 수 있습니다.
라이브러리를 사용하려면 필요한 곳에 헤더 파일을 넣기만 하면 됩니다. 정말 쉽습니다!
진행 중인 작업
단위 테스트에는 CMake 3.9 이상과 GoogleTest 라이브러리가 필요합니다.
구글테스트
git clone https://github.com/google/googletest.git
cd googletest # Main directory of the cloned repository
mkdir -p build # Create a directory to hold the build output
cd build
cmake .. # Generate native build scripts for GoogleTest
make # Compile
sudo make install # Install in /usr/local/ by default기본 디렉터리에서:
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DTEST=ON .. # Generate native build scripts for GoogleTest,
make # Compile빌드가 컴파일된 후 다음 명령을 사용하여 "build" 디렉터리에서 "test_exe" 실행 파일을 실행합니다.
./test_exe
벤치마크에는 CMake 3.9 이상, GoogleTest 라이브러리 및 Google Benchmark 라이브러리가 필요합니다.
구글 벤치마크
# Check out the library
$ git clone https://github.com/google/benchmark.git
# Google Benchmark requires GoogleTest as a dependency. Add the source tree as a subdirectory
$ git clone https://github.com/google/googletest.git benchmark/googletest
# Go to the library's root directory
$ cd benchmark
# Make a build directory to place the build output
$ cmake -E make_directory " build "
# Generate the build system files with CMake
$ cmake -E chdir " build " cmake -DCMAKE_BUILD_TYPE=Release ../
# If starting with CMake 3.13, you can use the following:
# cmake -DCMAKE_BUILD_TYPE=Release -S . -B "build"
# Build the library
$ cmake --build " build " --config Release
# Install the library
$ sudo cmake --build " build " --config Release --target install기본 디렉터리에서:
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DBENCHMARK=ON .. # Generate native build scripts for Google Benchmark
make # Compile빌드가 컴파일된 후 다음 명령을 사용하여 "build" 디렉터리에서 "benchmark" 실행 파일을 실행합니다.
./benchmark
해당 링크를 통해 벤치마크 결과를 확인하실 수 있습니다.
tarball 패키지를 생성하려면 명령줄에서 다음을 실행하십시오:
# Enter Packaging Directory
$ cd packaging
# Execute the script to generate tarballs
$ ./tarballs.shRPM 패키지를 생성하려면 명령줄에서 다음을 실행하세요.
# Enter Packaging Directory
$ cd packaging/rpm
# Execute the script to generate tarballs
$ ./make_rpm.shdeb 패키지를 생성하려면 명령줄에서 다음을 실행합니다.
# Enter Packaging Directory
$ cd packaging/deb
# Execute the script to generate tarballs
$ ./make_deb.sh그래프 Dijkstras 최단 경로 알고리즘(Dijkstra's Shortest Path) [Dijkstra's Algorithm] (https://www.interviewbit.com/blog/find-shortest-path-dijkstras-algorithm/)은 소스 노드에서 소스 노드까지의 최단 경로를 찾는 데 사용됩니다. 그래프의 다른 모든 도달 가능한 노드. 알고리즘은 처음에 주어진 소스 노드에서 모든 노드에 도달할 수 없다고 가정하므로 모든 노드의 거리를 무한대로 표시합니다. (무한대) 소스 노드에서 (INF / 무한대는 도달할 수 없음을 나타냄)
dijkstra 알고리즘의 다이얼 전문화.
간선 가중치가 작은 정수(매개변수 C 로 제한됨)인 경우 이 사실을 활용하는 특수 대기열을 사용하여 Dijkstra 알고리즘의 속도를 높일 수 있습니다. 이 유형의 첫 번째 알고리즘은 양의 정수 간선 가중치를 갖는 그래프에 대한 Dial의 알고리즘(Dial 1969)으로, 버킷 큐를 사용하여 실행 시간 O(|E|+|V|C) 을 얻습니다.(출처 wikipedia)
다음은 완전한 알고리즘입니다.
이 링크에서 단계별 그림을 볼 수 있습니다.
프림 알고리즘(Prim's Algorithm) 프림 알고리즘은 가중치가 부여된 무방향 그래프에 대한 최소 스패닝 트리를 찾는 그리디 알고리즘입니다. 즉, 모든 정점을 포함하는 트리를 형성하는 가장자리의 하위 집합을 찾고, 트리에 있는 모든 가장자리의 총 가중치가 최소화됩니다. 알고리즘은 임의의 시작 정점에서 한 번에 한 정점씩 이 트리를 구축하고 각 단계에서 트리에서 다른 정점으로 가능한 가장 저렴한 연결을 추가하는 방식으로 작동합니다.
단계:
(너비 우선 검색) 너비 우선 검색 알고리즘(Breadth First Search) 너비 우선 검색(Breadth First Search )은 BFS 라고도 불리는 그래프 순회 알고리즘입니다. 시간 복잡도 O(|V| + |E|) 여기서 V는 정점 수이고 E는 그래프의 간선 수입니다. 너비 우선 검색의 응용 프로그램은 다음과 같습니다.
그리고 더 많은 것이 있습니다 ...
(깊이 우선 탐색) 깊이 우선 탐색 알고리즘(Depth First Search) 깊이 우선 탐색 ( DFS )은 그래프 순회 알고리즘(Graph Traversal Algorithm)입니다. 시간 복잡도 O(|V| + |E|) 여기서 V는 정점 수이고 E는 그래프의 가장자리 수입니다. 깊이 우선 검색의 적용은 다음과 같습니다.
그리고 더 많은 것들이 있습니다...
Best First Search Best First Search는 평가 함수에 따라 선택된 가장 유망한 노드를 탐색하여 그래프를 탐색하는 검색 알고리즘 클래스입니다. 최악의 경우 시간 복잡도는 O(n * log n)입니다. 여기서 n은 그래프의 노드 수입니다.
순환(그래프 이론)
유향 그래프와 무향 그래프에서 순환의 존재는 깊이 우선 탐색(DFS)이 현재 꼭짓점의 조상을 가리키는 간선(뒤쪽 간선을 포함함)을 찾는지 여부에 따라 결정될 수 있습니다. DFS가 건너뛰는 모든 뒤쪽 가장자리는 주기의 일부입니다. 무방향 그래프에서 노드의 부모에 대한 가장자리는 뒤쪽 가장자리로 계산되어서는 안 되지만 이미 방문한 다른 정점을 찾는 것은 뒤쪽 가장자리를 나타냅니다. 무방향 그래프의 경우 n-정점 그래프에서 순환을 찾는 데 O(n) 시간만 필요합니다. 최대 n − 1 개의 간선이 트리 간선이 될 수 있기 때문입니다.
많은 토폴로지 정렬 알고리즘은 토폴로지 순서가 존재하는 데 장애물이 되기 때문에 사이클도 감지합니다. 또한 유향 그래프를 강하게 연결된 구성 요소로 나눈 경우 순환은 강하게 연결되어 있기 때문에 구성 요소 내부에만 존재하고 구성 요소 사이에는 순환이 존재하지 않습니다.
방향성 그래프의 경우 분산 메시지 기반 알고리즘을 사용할 수 있습니다. 이러한 알고리즘은 한 정점에서 보낸 메시지가 한 주기로 다시 자신에게 돌아올 것이라는 생각에 의존합니다. 분산주기 탐지 알고리즘은 컴퓨터 클러스터(또는 슈퍼컴퓨터)에서 분산 그래프 처리 시스템을 사용하여 대규모 그래프를 처리하는 데 유용합니다.
주기 감지의 적용에는 동시 시스템의 교착 상태를 감지하기 위한 대기 그래프 사용이 포함됩니다.
벨만-포드 알고리즘(Bellman-Ford Algorithm)은 소스 노드와 타겟 노드 사이의 최단 거리를 찾는 데 사용될 수 있습니다. 시간 복잡도 O(|V| . |E|) 여기서 V는 정점 수이고 E는 그래프의 간선 수이며 Dijkstra의 최단 경로 알고리즘보다 높습니다. Dijkstra 알고리즘의 시간 복잡도는 O(|E| + |V| log |v| )입니다. dijkstra에 비해 bellman-ford의 장점은 음수 간선 가중치를 갖는 그래프를 처리할 수 있다는 것입니다. 또한 그래프에 음의 가중치 주기가 포함된 경우 알고리즘은 음의 주기 존재를 감지하고 보고할 수 있습니다.
이 비디오는 알고리즘 구현에 대한 훌륭한 개요를 제공합니다. 이 MIT 강의는 Bellman-Ford의 정확성과 음의 순환을 감지하는 능력에 대한 증거를 제공합니다. 신청:
플로이드 워샬 알고리즘
첫 번째 단계로 입력 그래프 행렬과 동일한 해 행렬을 초기화합니다. 그런 다음 모든 정점을 중간 정점으로 간주하여 솔루션 행렬을 업데이트합니다. 아이디어는 모든 정점을 하나씩 선택하고 최단 경로의 중간 정점으로 선택한 정점을 포함하는 모든 최단 경로를 업데이트하는 것입니다. 정점 번호 k를 중간 정점으로 선택할 때 이미 정점 {0, 1, 2, .. k-1}을 중간 정점으로 간주했습니다. 소스 정점과 대상 정점의 모든 쌍(i, j)에 대해 두 가지 가능한 경우가 있습니다.
전이적 축소
이 알고리즘은 도달 가능성이 동일하고 가능한 적은 수의 간선을 사용하여 전이적 폐쇄를 충족하는 방향성 그래프를 구성하는 데 사용됩니다. 보다 구체적으로, 그래프를 통해 "단락" 경로를 제거하여 가능한 한 적은 수의 간선으로 최소 등가 그래프를 생성합니다.
이는 각 노드 쌍을 반복하여 첫 번째 노드 또는 마지막 노드에서 나오는 두 개의 에지가 있는지 확인하고 노드 쌍 에지가 있는 경우 제거함으로써 수행됩니다.
의사 코드: foreach x in graph.vertices foreach y in graph.vertices foreach z in graph.vertices 가장자리 xy 및 yz가 존재하는 경우 가장자리 xz 삭제
우리의 구현에는 여러 위치에서 가장자리를 조기에 검사하는 if 게이트가 있으며, 이는 여기의 3차 의사 코드보다 약간 더 빠른 런타임을 제공합니다.
크루스칼 알고리즘(Kruskal Algorithm)은 무방향 간선 가중치 그래프의 최소 스패닝 포레스트(Minimum Spanning Forest)를 찾는 데 사용될 수 있습니다. 시간 복잡도 O(E log E) = O(E log V) 여기서 V는 정점 수이고 E는 그래프의 가장자리 수입니다. 이 알고리즘의 주요 속도 제한은 가장자리를 정렬하는 것입니다.
알고리즘 절차를 빠르게 이해하려면 이 비디오를 확인하세요. 실제 응용 프로그램 중 일부는 다음과 같습니다.
최소 스패닝 포리스트를 찾는 다른 알고리즘은 Prim의 알고리즘 또는 Borůvka의 알고리즘입니다.
Borůvka 알고리즘은 그래프에서 최소 스패닝 트리를 찾는 데 사용할 수 있는 그리디 알고리즘이며, 연결되지 않은 그래프의 경우 최소 스패닝 포레스트를 찾는 데 사용할 수 있습니다.
알고리즘은 그래프의 각 정점에 입사하는 최소 가중치 가장자리를 찾고 해당 가장자리를 모두 포리스트에 추가하는 것으로 시작됩니다. 그런 다음 지금까지 구성된 각 트리에서 다른 트리에 최소 가중치 가장자리를 찾고 해당 가장자리를 모두 포리스트에 추가하는 유사한 프로세스를 반복합니다. 이 프로세스를 반복할 때마다 그래프의 연결된 각 구성 요소 내의 트리 수가 이전 값의 최대 절반으로 줄어들므로 대수적으로 여러 번 반복한 후에 프로세스가 완료됩니다. 그렇게 되면 추가된 가장자리 세트가 최소 스패닝 포리스트를 형성합니다.
Borůvka의 알고리즘은 외부 루프가 종료될 때까지 O(log V) 반복을 수행하므로 O(E log V) 시간 내에 실행되는 것으로 표시될 수 있습니다. 여기서 E는 모서리 수이고 V는 정점 수입니다. G(E ≥ V로 가정).
문제의 수학적 정의: G를 그래프의 노드 집합으로 설정하고 n을 해당 집합의 노드로 설정합니다. C를 n과 n에서 도달할 수 있는 모든 노드를 모두 포함하는 G의 비엄격 하위 집합으로 두고 C'를 그 보수로 둡니다. C'의 모든 노드에서 도달할 수 있는 모든 노드를 포함하는 C의 비엄격한 하위 집합인 세 번째 집합 M이 있습니다. 문제는 C에는 속하지만 M에는 속하지 않는 모든 노드를 찾는 것입니다.
현재 구현된 알고리즘:
애플리케이션:
이 알고리즘은 가비지 수집 시스템에서 한 개체가 곧 해제될 경우 어떤 개체를 해제해야 하는지 결정하는 데 사용됩니다.
Ford-Fulkerson 알고리즘은 흐름 네트워크에서 최대 흐름을 찾는 그리디 알고리즘입니다. 알고리즘의 기본 아이디어는 다음과 같습니다. 소스(시작 노드)에서 싱크(끝 노드)까지의 경로가 있고 경로의 모든 가장자리에 사용 가능한 용량이 있는 한 경로 중 하나를 따라 흐름을 보냅니다. 그런 다음 다른 경로 등을 찾습니다. 사용 가능한 용량이 있는 경로를 증강 경로라고 합니다.
Kosaraju의 알고리즘은 유향 그래프의 강하게 연결된 구성 요소를 찾는 선형 시간 알고리즘입니다. 이는 정점 u에서 시작하여 정점 v에 도달할 수 있다면 정점 v에서 시작하여 정점 u에 도달할 수 있어야 하며, 그렇다면 정점 u와 v는 다음과 같다고 말할 수 있다는 아이디어에 기초합니다. 강하게 연결됨 - 강하게 연결된 하위 그래프에 있습니다. 다음은 예입니다.
1). 빈 스택 'S'를 만들고 그래프의 DFS 순회를 수행합니다. DFS 순회에서는 정점의 인접한 정점에 대해 재귀 DFS를 호출한 후 정점을 스택으로 푸시합니다. 2). 전치 그래프를 얻기 위해 모든 호의 방향을 반대로 합니다. 3). S가 비어 있지 않은 동안 S에서 정점을 하나씩 팝합니다. 팝된 정점을 'v'로 둡니다. v를 소스로 취하고 DFS를 수행합니다(DFSUtil(v) 호출). v에서 시작하는 DFS는 v의 강하게 연결된 구성 요소를 인쇄합니다.
Kahn의 알고리즘은 들어오는 간선이 없는 그래프에서 노드를 반복적으로 제거하여 위상적 순서를 찾습니다. 그래프에서 노드가 제거되면 토폴로지 순서에 추가되고 해당 가장자리가 모두 제거되어 들어오는 가장자리가 없는 다음 노드 집합이 선택될 수 있습니다.
Welsh Powell 착색 알고리즘은 그리디 정점 착색 알고리즘입니다. 이 알고리즘은 그래프의 색수를 찾는 데에도 사용됩니다.
Welsh Powell 알고리즘은 다음 단계로 구성됩니다.
알고리즘은 각 노드를 정수로 정렬된 색상에 할당하는 std::map<Node, int> 결과를 반환합니다. 사용자는 결과 맵에서 가장 높은 값을 쿼리하여 그래프의 최소 색채 순서를 쿼리할 수도 있습니다.
std::map<Node, int > result = graph.welshPowellColoring();
auto chromatic_color = std::max_element(result.begin(), result.end(),
[]( const auto & lhs, const auto & rhs) {
return lhs. second < rhs. second ;
}최소 색상은 0이 아닌 1부터 시작됩니다.
알고리즘은 그래프의 방향이 지정되지 않은 것으로 가정합니다. 모든 소스와 영감은 알고리즘 선언과 테스트 케이스에 연결되어 있습니다.
정점 절단 분할은 그래프의 가장자리를 동일한 크기의 분할로 나눕니다. 가장자리의 끝점을 보유하는 정점도 가장자리 자체와 동일한 파티션에 배치됩니다. 그러나 꼭짓점은 파티션 전체에서 고유하지 않으며 여러 파티션에 걸쳐 가장자리가 분산되어 있기 때문에 복제(잘라내기)해야 할 수도 있습니다.
복제 인자는 원래 입력 그래프의 정점 수와 비교하여 컴퓨터를 통해 복제되는 정점 수를 수량화합니다.
이 알고리즘은 라운드 로빈 방식의 간단한 정점 절단입니다. 원본 그래프 가장자리를 가져와서 파티션에 할당하고 동일한(또는 유사한) 크기로 나눕니다. 이 알고리즘은 정점 복제(복제 요소)의 최적화를 처리하지 않고 파티션의 가장자리 균형만 조정합니다.
그리디 파티셔닝 알고리즘은 에지 할당의 전체 기록을 사용하여 다음 결정을 내립니다. 알고리즘은 이미 관찰된 각 정점 v가 할당된 파티션 집합 A(v)와 현재 파티션 크기를 저장합니다. 정점 vi, vj ∈ V를 연결하는 가장자리 e ∈ E를 처리할 때 그리디 알고리즘은 다음과 같은 간단한 규칙 집합을 따릅니다.
HDRF(High Degree (are) Replicated First) 알고리즘은 이 논문에서 설명하는 그리디 정점 절단 알고리즘입니다. 이 알고리즘은 에지 할당 기록과 증분 정점 각도를 사용하여 복제 요소를 최적화하려고 시도합니다. 이 두 가지 요소를 고려한 기능을 사용하여 분석된 에지를 할당하기 위한 최상의 파티션을 계산합니다. 생성된 복제본은 정점의 차수를 기반으로 하며 복제된 정점은 아마도 더 높은 차수를 갖는 정점인 소위 "허브 노드"일 것입니다.
Efficient and Balanced Vertex-cut(EBV)은 본 논문에서 설명하는 오프라인 정점 절단 알고리즘입니다. 이 알고리즘은 각 파티션의 모서리 및 정점 수와 복제 요소를 기준으로 파티션의 균형을 맞추려고 합니다. 그래프의 총 모서리와 꼭지점 수를 고려하여 모서리를 할당하는 파티션을 평가하는 공식을 적용합니다. 평가식은 다음과 같습니다.
가장 낮은 값이 파티션 ID로 사용됩니다.
차수 행렬은 그래프의 노드 연결에 대한 통찰력을 제공하는 정사각형 행렬입니다. 유향 그래프의 경우 각 노드에 대해 들어오고 나가는 간선의 수를 반영하고, 무방향 그래프의 경우 각 노드에 입사하는 간선의 수를 나타냅니다.
라플라시안 행렬(Laplacian Matrix)은 그래프의 인접 행렬과 차수 행렬로부터 파생된 정사각 행렬입니다. 이는 연결성, 스패닝 트리 수 및 기타 스펙트럼 특성과 같은 그래프의 다양한 속성을 분석하는 데 중요한 역할을 합니다.
전환 매트릭스는 마르코프 체인 및 확률론적 프로세스 연구에 일반적으로 사용됩니다. 그래프의 맥락에서 이는 종종 간선 가중치 또는 미리 결정된 기준을 기반으로 한 노드에서 다른 노드로 전환할 확률을 나타냅니다. 이 매트릭스는 네트워크 분석, 기계 학습, 최적화 등 다양한 분야의 응용 분야를 찾습니다.
지원을 제공하고 싶다면 끌어오기 요청을 생성하거나 문제 를 보고할 수 있습니다. 코드를 변경하거나, 문제를 수정하거나, 새로운 기능을 구현하려면 기여 가이드를 읽어보세요.
새로운 기능에 대해 논의하고 싶거나 라이브러리에 대한 질문이나 제안 사항이 있는 경우 토론을 열거나 간단히 채팅하십시오.
CXX그래프 사이트
이메일 : [email protected]
GitHub 프로필
나를 지원하려면 프로젝트에 별표 를 추가하거나 나를 팔로우하세요.
최신 소식을 확인하려면 프로젝트를 시청하세요 .
우리는 다음을 참조합니다:
알고리즘에 영감을 준 TheAlgorithms 커뮤니티에 감사드립니다.
알고리즘에 영감을 준 GeeksForGeeks에게 감사드립니다.
이미 CXXGraph에 기여해 주신 모든 분들께 감사드립니다!
이 소프트웨어를 사용하는 경우 CITATION 지침을 따르십시오. 감사합니다!
Hacktoberfest 2021에 참가했습니다. 모든 기여자분들께 감사드립니다!
Hacktoberfest 2022에 참가했습니다. 모든 기여자분들께 감사드립니다!
Hacktoberfest 2023에 참가했습니다. 모든 기여자분들께 감사드립니다!
프로젝트의 예상 가치 보기
@지그레이저 |
|---|
