Алгоритмы, реализованные в библиотеке AGraph

Сокращения: "Э" - используется эффективный (полиномиальной сложности) алгоритм, "НЭ" - неэффективный (экспоненциальной сложности).

Обозначения: n - количество вершин в графе, m - количество ребер.

Задача Модуль, процедура/функция или класс/метод Комментарий

поиск пути (заданного количества путей) минимальной длины (в смысле минимального количества промежуточных вершин/ребер) между заданными вершинами графа Graphs
TGraph.FindMinPathCond
TGraph.FindMinPathDirected
TGraph.FindMinPathUndirected
TGraph.FindMinPath
TGraph.FindMinPaths
TGraph.FindMinPathsDirected
TGraph.FindMinPathsUndirected
(Э); используется волновой алгоритм, называемый также поиском в ширину (BFS - breadth first search), сложность - O(n+m)

поиск цикла минимальной длины (в смысле минимального количества промежуточных ребер), проходящего через заданную вершину графа Graphs
TGraph.FindMinRingCond
TGraph.FindMinRing
(Э); волновой алгоритм

построение матрицы связности и обобщенной матрицы связности графа Graphs
TGraph.CreateConnectionMatrix
TGraph.CreateExtendedConnectionMatrix
(Э); волновой алгоритм

построение матрицы достижимости графа Graphs
TGraph.CreateReachabilityMatrix
(Э)

построение матрицы расстояний графа (вес любого ребра считается равным единице) Graphs
TGraph.CreateDistanceMatrix
(Э)

проверка совпадения графов при заданном отображении вершин Graphs
TGraph.EqualToGraph
(Э)

поиск максимальных независимых множеств вершин графа Graphs
TGraph.FindMaxIndependentVertexSets
(НЭ); для данной задачи заведомо не существует эффективного алгоритма, т.к. количество максимальных независимых множеств вершин достигает 3^n/3

поиск системы независимых минимальных колец графа (исключая петли), покрывающих все кольцевые ребра графа; количество колец в этой системе меньше либо равно цикломатическому числу графа (минус количество петель) Graphs
TGraph.FindMinRingCovering
(Э)

построение графа, дополнительного к заданному графу Graphs
TGraph.GetComplementOf
(Э)

построение реберного графа для заданного графа Graphs
TGraph.GetLineGraphOf
(Э)

построение кратчайшего остовного дерева (SST - Shortest Spanning Tree) заданного взвешенного графа Graphs
TGraph.GetShortestSpanningTreeOf
TGraph.FindShortestSpanningTree
(Э)

поиск максимального потока в транспортной сети Graphs
TGraph.FindMaxFlowThroughNetwork
(Э)

поиск пути (путей) минимального суммарного веса между заданными вершинами во взвешенном графе с неотрицательными весами ребер Graphs
TGraph.FindMinWeightPathCond
TGraph.FindMinWeightPath
(Э); используется алгоритм Дейкстры

поиск путей минимального суммарного веса между всеми парами вершин во взвешенном орграфе с произвольными весами вершин (ребер) Graphs
TGraph.CreateMinWeightPathsMatrix
TGraph.DecodeMinWeightPath
(Э); используется алгоритм Флойда, сложность - O(n³)

поиск сильных компонент орграфа Graphs
TGraph.FindStrongComponents
(Э); сложность - O(n+m)

поиск хроматического числа и оптимальной вершинной раскраски графа GrColor
GraphColoring
(НЭ); перенесен С-код Copyright (c) 1994 by Michael Trick. For more information on this code, see Anuj Mehrotra and Michael A. Trick, "A column generation approach to graph coloring", GSIA Technical report series.

поиск приближенной раскраски графа GrColor
ApproximateColoring1
(Э); используется простой эмпирический алгоритм

проверка правильности некоторой раскраски графа GrColor
CheckColoring
(Э)

поиск эйлерова цикла в графе (граф интерпретируется как неориентированный) EulerCyc
FindEulerCycle
(Э); используется алгоритм Флёри

поиск гамильтоновых циклов в орграфе HamilCyc
FindHamiltonCycles
(НЭ); используется переборный алгоритм с редукцией графа на каждом шаге поиска (задача является NP-полной)

решение задачи почтальона (найти цикл, проходящий через каждое ребро графа по крайней мере один раз и такой, что суммарный вес входящих в него ребер минимален) для взвешенного графа с неотрицательными весами ребер (граф всегда интерпретируется как неориентированный) Postman
SolvePostmanProblem
(Э)

распознавание изоморфизма графов с учетом атрибутов Isomorph
FindMatch
VF: An efficient graph isomorphism algorithm by the Artificial Vision Group of the "Federico II" University of Naples, Italy (C++ implementation rel.0.9b, http://amalfi.dis.unina.it/graph). Reference: L.P.Cordella, P.Foggia, C.Sansone, M.Vento, "An Efficient Algorithm for the Inexact Matching of ARG Using a Contextual Transformational Model", in Proceedings of the 13th ICPR, IEEE Computer Society Press, vol.III, pp.180-184 (1996)

Задача	Модуль, процедура/функция или класс/метод	Комментарий
поиск пути (заданного количества путей) минимальной длины (в смысле минимального количества промежуточных вершин/ребер) между заданными вершинами графа	Graphs TGraph.FindMinPathCond TGraph.FindMinPathDirected TGraph.FindMinPathUndirected TGraph.FindMinPath TGraph.FindMinPaths TGraph.FindMinPathsDirected TGraph.FindMinPathsUndirected	(Э); используется волновой алгоритм, называемый также поиском в ширину (BFS - breadth first search), сложность - O(n+m)
поиск цикла минимальной длины (в смысле минимального количества промежуточных ребер), проходящего через заданную вершину графа	Graphs TGraph.FindMinRingCond TGraph.FindMinRing	(Э); волновой алгоритм
построение матрицы связности и обобщенной матрицы связности графа	Graphs TGraph.CreateConnectionMatrix TGraph.CreateExtendedConnectionMatrix	(Э); волновой алгоритм
построение матрицы достижимости графа	Graphs TGraph.CreateReachabilityMatrix	(Э)
построение матрицы расстояний графа (вес любого ребра считается равным единице)	Graphs TGraph.CreateDistanceMatrix	(Э)
проверка совпадения графов при заданном отображении вершин	Graphs TGraph.EqualToGraph	(Э)
поиск максимальных независимых множеств вершин графа	Graphs TGraph.FindMaxIndependentVertexSets	(НЭ); для данной задачи заведомо не существует эффективного алгоритма, т.к. количество максимальных независимых множеств вершин достигает 3^n/3
поиск системы независимых минимальных колец графа (исключая петли), покрывающих все кольцевые ребра графа; количество колец в этой системе меньше либо равно цикломатическому числу графа (минус количество петель)	Graphs TGraph.FindMinRingCovering	(Э)
построение графа, дополнительного к заданному графу	Graphs TGraph.GetComplementOf	(Э)
построение реберного графа для заданного графа	Graphs TGraph.GetLineGraphOf	(Э)
построение кратчайшего остовного дерева (SST - Shortest Spanning Tree) заданного взвешенного графа	Graphs TGraph.GetShortestSpanningTreeOf TGraph.FindShortestSpanningTree	(Э)
поиск максимального потока в транспортной сети	Graphs TGraph.FindMaxFlowThroughNetwork	(Э)
поиск пути (путей) минимального суммарного веса между заданными вершинами во взвешенном графе с неотрицательными весами ребер	Graphs TGraph.FindMinWeightPathCond TGraph.FindMinWeightPath	(Э); используется алгоритм Дейкстры
поиск путей минимального суммарного веса между всеми парами вершин во взвешенном орграфе с произвольными весами вершин (ребер)	Graphs TGraph.CreateMinWeightPathsMatrix TGraph.DecodeMinWeightPath	(Э); используется алгоритм Флойда, сложность - O(n³)
поиск сильных компонент орграфа	Graphs TGraph.FindStrongComponents	(Э); сложность - O(n+m)
поиск хроматического числа и оптимальной вершинной раскраски графа	GrColor GraphColoring	(НЭ); перенесен С-код Copyright (c) 1994 by Michael Trick. For more information on this code, see Anuj Mehrotra and Michael A. Trick, "A column generation approach to graph coloring", GSIA Technical report series.
поиск приближенной раскраски графа	GrColor ApproximateColoring1	(Э); используется простой эмпирический алгоритм
проверка правильности некоторой раскраски графа	GrColor CheckColoring	(Э)
поиск эйлерова цикла в графе (граф интерпретируется как неориентированный)	EulerCyc FindEulerCycle	(Э); используется алгоритм Флёри
поиск гамильтоновых циклов в орграфе	HamilCyc FindHamiltonCycles	(НЭ); используется переборный алгоритм с редукцией графа на каждом шаге поиска (задача является NP-полной)
решение задачи почтальона (найти цикл, проходящий через каждое ребро графа по крайней мере один раз и такой, что суммарный вес входящих в него ребер минимален) для взвешенного графа с неотрицательными весами ребер (граф всегда интерпретируется как неориентированный)	Postman SolvePostmanProblem	(Э)
распознавание изоморфизма графов с учетом атрибутов	Isomorph FindMatch	VF: An efficient graph isomorphism algorithm by the Artificial Vision Group of the "Federico II" University of Naples, Italy (C++ implementation rel.0.9b, http://amalfi.dis.unina.it/graph). Reference: L.P.Cordella, P.Foggia, C.Sansone, M.Vento, "An Efficient Algorithm for the Inexact Matching of ARG Using a Contextual Transformational Model", in Proceedings of the 13th ICPR, IEEE Computer Society Press, vol.III, pp.180-184 (1996)