CXXGraph
v4.1.0
CXXGraph — это комплексная библиотека C++, которая управляет алгоритмами графов. Эта библиотека только для заголовков служит альтернативой библиотеке Boost Graph (BGL).
Мы ищем:
Если вам интересно, свяжитесь с нами по адресу [email protected] или внесите свой вклад в этот проект. Мы ждем вас!
| Завершенный | Описание | Дата завершения |
|---|---|---|
| ✔️ | Релиз 0.4.0 | 7 октября 2022 г. |
| ✔️ | Релиз 0.5.0 | 23 марта 2023 г. |
| ✔️ | Первый стабильный выпуск 1.0.0 | 28 марта 2023 г. |
| ✔️ | Версия 1.0.1 | 7 мая 2023 г. |
| ✔️ | Версия 1.1.0 | 8 мая 2023 г. |
| ✔️ | Стабильная версия 2.0.0 | 1 июня 2023 г. |
| ✔️ | Стабильная версия 3.0.0 | 3 ноября 2023 г. |
| ✔️ | Версия 3.1.0 | 9 января 2023 г. |
| Представляем гиперграф №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 .
GoogleТест
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После компиляции сборки запустите исполняемый файл «test_exe» в каталоге «build» с помощью следующей команды:
./test_exe
Для тестирования требуется CMake 3.9 и более поздние версии, библиотека GoogleTest и библиотека Google Benchmark .
Google Бенчмарк
# 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После компиляции сборки запустите исполняемый файл «benchmark» в каталоге «build» с помощью следующей команды:
./benchmark
Проверить результат теста можно по этой ссылке.
Чтобы создать пакет tarball, выполните следующую команду из командной строки:
# Enter Packaging Directory
$ cd packaging
# Execute the script to generate tarballs
$ ./tarballs.shЧтобы создать пакет RPM, выполните следующую команду из командной строки:
# Enter Packaging Directory
$ cd packaging/rpm
# Execute the script to generate tarballs
$ ./make_rpm.shЧтобы создать пакет deb, выполните в командной строке следующее:
# Enter Packaging Directory
$ cd packaging/deb
# Execute the script to generate tarballs
$ ./make_deb.shГраф Алгоритм кратчайшего пути Дейкстры (Dijkstra's Shortest Path) [Алгоритм Дейкстры] (https://www.interviewbit.com/blog/find-shortest-path-dijkstras-algorithm/) используется для поиска кратчайшего пути от исходного узла до все остальные достижимые узлы графа. Алгоритм изначально предполагает, что все узлы недоступны из данного исходного узла, поэтому мы отмечаем расстояния всех узлов как бесконечность. (бесконечность) от исходного узла (INF / бесконечность означает невозможность достижения).
Специализация набора алгоритма Дейкстры.
Когда веса ребер представляют собой небольшие целые числа (ограниченные параметром C ), специализированные очереди, использующие этот факт, могут использоваться для ускорения алгоритма Дейкстры. Первым алгоритмом этого типа был алгоритм Дайала (Dial 1969) для графов с положительными целочисленными весами ребер, который использует очередь сегментов для получения времени работы O(|E|+|V|C) . (источник в Википедии)
Ниже приведен полный алгоритм:
По этой ссылке вы можете найти пошаговые иллюстрации.
Алгоритм Прима Алгоритм Прима — это жадный алгоритм, который находит минимальное остовное дерево для взвешенного неориентированного графа. Это означает, что он находит подмножество ребер, образующее дерево, включающее каждую вершину, где общий вес всех ребер в дереве минимизирован. Алгоритм строит это дерево по одной вершине за раз из произвольной начальной вершины, на каждом шаге добавляя самое дешевое возможное соединение из дерева в другую вершину.
Шаги:
(Поиск в ширину) Алгоритм поиска в ширину (Поиск в ширину) Поиск в ширину , также называемый BFS , представляет собой алгоритм обхода графа. Временная сложность O(|V| + |E|), где V — количество вершин, а E — количество ребер в графе. Приложения поиска в ширину:
И есть еще много...
(Поиск в глубину) Алгоритм поиска в глубину (Поиск в глубину) Поиск в глубину , также называемый DFS , представляет собой алгоритм обхода графа. Временная сложность O(|V| + |E|), где V — количество вершин, а E — количество ребер в графе. Применение поиска в глубину:
И есть еще много...
Лучший первый поиск Лучший первый поиск — это класс поисковых алгоритмов, которые обходят граф, исследуя наиболее перспективный узел, выбранный в соответствии с функцией оценки. Временная сложность в худшем случае равна O(n * log n), где n — количество узлов в графе.
Цикл (теория графов)
Существование цикла в ориентированных и неориентированных графах можно определить по тому, находит ли поиск в глубину (DFS) ребро, указывающее на предка текущей вершины (оно содержит заднее ребро). Все задние ребра, которые пропускает DFS, являются частью циклов. В неориентированном графе ребро родительского узла не должно считаться задним ребром, но обнаружение любой другой уже посещенной вершины будет указывать на заднее ребро. В случае неориентированных графов для поиска цикла в n-вершинном графе требуется всего O(n) времени, поскольку не более n - 1 ребер могут быть ребрами дерева.
Многие алгоритмы топологической сортировки также обнаруживают циклы, поскольку они являются препятствиями для существования топологического порядка. Кроме того, если ориентированный граф разделен на сильно связные компоненты, циклы существуют только внутри компонентов, а не между ними, поскольку циклы сильно связны.
Для ориентированных графов можно использовать алгоритмы на основе распределенных сообщений. Эти алгоритмы основаны на идее, что сообщение, отправленное вершиной в цикле, вернется к самому себе. Алгоритмы обнаружения распределенных циклов полезны для обработки крупномасштабных графов с использованием системы распределенной обработки графов в компьютерном кластере (или суперкомпьютере).
Приложения обнаружения циклов включают использование графиков ожидания для обнаружения взаимоблокировок в параллельных системах.
Алгоритм Беллмана-Форда можно использовать для поиска кратчайшего расстояния между источником и целевым узлом. Временная сложность O(|V| . |E|), где V — количество вершин, а E — количество ребер в графе, что выше, чем в алгоритме кратчайшего пути Дейкстры. Временная сложность алгоритма Дейкстры равна O(|E| + |V| log |v| ). Преимущество Bellman-Ford перед Dijkstra состоит в том, что он может обрабатывать графы с отрицательными весами ребер. Кроме того, если график содержит цикл с отрицательным весом, алгоритм может обнаружить и сообщить о наличии отрицательного цикла.
В этом видео дается хороший обзор реализации алгоритма. Эта лекция Массачусетского технологического института дает доказательство правильности теории Беллмана-Форда и ее способности обнаруживать отрицательные циклы. Приложения:
Алгоритм Флойда Уоршалла
На первом этапе мы инициализируем матрицу решения так же, как матрицу входного графа. Затем мы обновляем матрицу решения, рассматривая все вершины как промежуточные вершины. Идея состоит в том, чтобы одну за другой выбирать все вершины и обновлять все кратчайшие пути, которые включают выбранную вершину в качестве промежуточной вершины в кратчайшем пути. Когда мы выбираем вершину номер k в качестве промежуточной вершины, мы уже рассматриваем вершины {0, 1, 2, .. k-1} как промежуточные вершины. Для каждой пары (i, j) исходных и целевых вершин соответственно есть два возможных случая.
Транзитивная редукция
Этот алгоритм используется для построения ориентированного графа с одинаковой достижимостью и удовлетворяет транзитивному замыканию с как можно меньшим количеством ребер. Более конкретно, он создает минимальный эквивалентный граф с как можно меньшим количеством ребер, удаляя «короткие» пути через граф.
Это делается путем перебора каждой пары узлов, проверки наличия двух ребер, выходящих из первого узла ИЛИ из последнего узла, удаления ребра пары узлов, если оно существует.
В псевдокоде: foreach x в графе.vertices foreach y в графе.vertices foreach z в графе.vertices удалить ребро xz, если ребра xy и yz существуют.
В нашей реализации есть элементы if, которые выполняют раннюю проверку ребер в нескольких местах, что обеспечивает немного более быстрое время выполнения, чем кубический псевдокод здесь.
Алгоритм Краскала можно использовать для поиска минимального остовного леса неориентированного графа, взвешенного по ребрам. Временная сложность O(E log E) = O(E log V), где V — количество вершин, а E — количество ребер в графе. Основное ограничение скорости этого алгоритма — сортировка ребер.
Для быстрого понимания процедуры алгоритма посмотрите это видео. Некоторые из реальных приложений:
Другими алгоритмами поиска минимального остовного леса являются алгоритм Прима или алгоритм Борувки.
Алгоритм Борувки — это жадный алгоритм, который можно использовать для поиска минимального остовного дерева в графе или минимального остовного леса в случае несвязного графа.
Алгоритм начинается с поиска ребра минимального веса, инцидентного каждой вершине графа, и добавления всех этих ребер в лес. Затем он повторяет аналогичный процесс поиска ребра минимального веса от каждого построенного дерева к другому дереву и добавляет все эти ребра в лес. Каждое повторение этого процесса уменьшает количество деревьев в каждом связном компоненте графа не более чем до половины этого прежнего значения, поэтому после логарифмического количества повторений процесс завершается. Когда это происходит, набор добавленных ребер образует минимальный остовный лес.
Можно показать, что алгоритм Борувки выполняет O(log V) итераций внешнего цикла до его завершения и, следовательно, работает за время O(E log V), где E — количество ребер, а V — количество вершин в G (при условии, что E ≥ V).
Математическое определение задачи: пусть G — множество узлов графа, а n — заданный узел в этом множестве. Пусть C — нестрогое подмножество G, содержащее как n, так и все узлы, достижимые из n, и пусть C’ — его дополнение. Существует третье множество M, которое является нестрогим подмножеством C, содержащим все узлы, достижимые из любого узла в C'. Задача состоит в том, чтобы найти все узлы, принадлежащие C, но не принадлежащие M.
Реализованный на данный момент алгоритм:
Приложение:
Этот алгоритм используется в системах сбора мусора, чтобы решить, какие еще объекты необходимо освободить, учитывая, что один объект вот-вот будет освобожден.
Алгоритм Форда-Фалкерсона — это жадный алгоритм поиска максимального потока в потоковой сети. Идея алгоритма заключается в следующем: пока существует путь от источника (начального узла) до приемника (конечного узла) с доступной пропускной способностью на всех ребрах пути, мы отправляем поток по одному из путей. Затем мы находим другой путь и так далее. Путь с доступной пропускной способностью называется расширяющим путем.
Алгоритм Косараджу — это алгоритм с линейным временем для поиска сильно связных компонентов ориентированного графа. Он основан на идее, что если можно достичь вершины v, начиная с вершины u, то можно достичь вершины u, начиная с вершины v, и если это так, можно сказать, что вершины u и v являются сильно связные — они находятся в сильно связном подграфе. Ниже приведен пример:
1). Создайте пустой стек «S» и выполните обход графа DFS. При обходе DFS после вызова рекурсивного DFS для соседних вершин вершины помещает вершину в стек. 2). Поменяйте направления всех дуг, чтобы получить транспонированный граф. 3). Одну за другой выталкивайте вершины из S, пока S не пусто. Пусть выскочившая вершина будет «v». Возьмите v в качестве источника и выполните DFS (вызов DFSUtil(v)). DFS, начиная с v, печатает сильно связный компонент v.
Алгоритм Кана находит топологическое упорядочение путем итеративного удаления узлов графа, у которых нет входящих ребер. Когда узел удаляется из графа, он добавляется в топологическое упорядочение, и все его ребра удаляются, позволяя выбрать следующий набор узлов без входящих ребер.
Алгоритм раскраски Уэлша Пауэлла — это жадный алгоритм раскраски вершин. Этот алгоритм также используется для определения хроматического числа графа.
Алгоритм Уэльса Пауэлла состоит из следующих шагов:
Алгоритм возвращает результат 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 ;
}Минимальная раскраска начинается с 1 вместо 0.
Алгоритм предполагает, что граф неориентированный. Все источники и вдохновения связаны в декларации алгоритма и тестовых примерах.
Разделение вершинного разреза делит ребра графа на разделы одинакового размера. Вершины, содержащие конечные точки ребра, также помещаются в тот же раздел, что и само ребро. Однако вершины не уникальны в разных разделах, и их, возможно, придется реплицировать (вырезать) из-за распределения их ребер по разным разделам.
Коэффициент репликации количественно определяет, сколько вершин реплицируется на компьютерах по сравнению с количеством вершин исходного входного графа.
Этот алгоритм представляет собой простой метод кругового разреза вершин. Он берет исходные ребра графа и присваивает их разделам, разделяя их на равные (или аналогичные) размеры. Этот алгоритм не заботится об оптимизации репликации вершин (коэффициент репликации), а только балансирует края в разделах.
Алгоритмы жадного разделения используют всю историю назначений ребер для принятия следующего решения. Алгоритм сохраняет набор разделов A(v), которым была назначена каждая уже наблюдаемая вершина v, и текущие размеры разделов. При обработке ребра e ∈ E, соединяющего вершины vi, vj ∈ V, жадный алгоритм следует этому простому набору правил:
Алгоритм высокой степени репликации первым (HDRF) представляет собой жадный алгоритм вырезания вершин, описанный в этой статье. Этот алгоритм пытается оптимизировать коэффициент репликации, используя историю назначений ребер и дополнительную степень вершины. С помощью функции, которая учитывает эти два фактора, рассчитывается лучший раздел для назначения анализируемого ребра. Создаваемые реплики основаны на степени вершин, а реплицируемые вершины, вероятно, представляют собой так называемый «концентратор-узел», который представляет собой вершины с более высокой степенью.
Эффективный и сбалансированный алгоритм вырезания вершин (EBV) — это автономный алгоритм вырезания вершин, описанный в этой статье. Этот алгоритм пытается сбалансировать разделы по количеству ребер и вершин каждого раздела и коэффициенту репликации. Он применяет формулу для оценки разделения, в котором назначается ребро, которое также учитывает общее количество ребер и вершин графа. Формула оценки следующая:
В качестве идентификатора раздела принимается наименьшее значение.
Матрица степеней — это квадратная матрица, которая дает представление о связности узлов графа. Для ориентированных графов он отражает количество входящих и исходящих ребер для каждого узла, а для неориентированных графов — количество ребер, инцидентных каждому узлу.
Матрица Лапласа — это квадратная матрица, полученная из матрицы смежности и матрицы степеней графа. Он помогает анализировать различные свойства графа, такие как связность, количество остовных деревьев и другие спектральные характеристики.
Матрица перехода обычно используется при изучении цепей Маркова и случайных процессов. В контексте графа он обозначает вероятности перехода от одного узла к другому, часто на основе весов ребер или заранее определенных критериев. Эта матрица находит применение в различных областях, таких как сетевой анализ, машинное обучение и оптимизация.
Если вы хотите оказать поддержку, вы можете создать запрос на включение или сообщить о проблеме . Если вы хотите изменить код, исправить проблему или реализовать новую функцию, прочтите наше Руководство для участников.
Если вы хотите обсудить новые функции или у вас есть какие-либо вопросы или предложения по поводу библиотеки, откройте обсуждение или просто пообщайтесь в чате.
Сайт CXXGraph
Электронная почта: [email protected].
Профиль GitHub
Чтобы поддержать меня, добавьте Звезду проекту или подпишитесь на меня.
Чтобы быть в курсе, следите за проектом
На нас ссылаются:
Спасибо сообществу TheAlgorithms за вдохновение для алгоритмов.
Спасибо GeeksForGeeks за вдохновение для алгоритмов.
Спасибо всем, кто уже внес свой вклад в CXXGraph!
Если вы используете это программное обеспечение, следуйте инструкциям CITATION. Спасибо!
Мы участвовали в Hacktoberfest 2021. Спасибо всем участникам!
Мы участвовали в Hacktoberfest 2022. Спасибо всем участникам!
Мы участвовали в Hacktoberfest 2023. Спасибо всем участникам!
Посмотреть ориентировочную стоимость проекта
@ZigRazor |
|---|
