Проверить является ли заданный граф блоком SWI prolog
Формулировка задачи:
Граф задается списком ребер, нужно проверить является ли заданный граф блоком на SWI prolog.
Блок - связный, непустой, не имеющий точек сочленения неориентированный граф.
Есть код разбиения графа на блоки на visual prolog:
Просьба помочь, спасибо.
Листинг программы
- domains
- дуга=д(integer,integer)
- дуги=дуга*
- циклы=дуги*
- il=integer*
- predicates
- блоки(дуги,циклы,циклы)
- nondeterm взять(дуги,дуга,дуги)
- nondeterm простой_цикл(integer,integer,дуги,дуги,il,дуги)
- объединение(циклы,дуги,дуги)
- разность(дуги,дуги,дуги)
- принадл(integer,il)
- clauses
- блоки(Граф,Блоки,Ответ):-
- взять(Граф,д(X,Y),Граф1),
- findall(Цикл,простой_цикл(Y,X,Граф,[д(X,Y)],[Y],Цикл),Циклы),
- объединение(Циклы,[],Блок),
- разность(Граф1,Блок,Граф2),!,
- блоки(Граф2,[Блок|Блоки],Ответ).
- блоки([],Блоки,Блоки).
- взять([д(X,Y)|Граф],Ребро,Граф):- Ребро=д(X,Y);Ребро=д(Y,X).
- взять([Дуга|Граф],Ребро,[Дуга|Граф1]):- взять(Граф,Ребро,Граф1).
- простой_цикл(Y,X,Граф,Ребра,Вершины,Цикл):- Y<>X,
- взять(Граф,д(Y,Z),Граф1),not(принадл(Z,Вершины)),
- простой_цикл(Z,X,Граф1,[д(Y,Z)|Ребра],[Z|Вершины],Цикл).
- простой_цикл(X,X,_,Цикл,_,Цикл).
- объединение([[Д|Цикл]|Циклы],Ребра,Блок):- взять(Ребра,Д,_),!,
- объединение([Цикл|Циклы],Ребра,Блок).
- объединение([[Д|Цикл]|Циклы],Ребра,Блок):- объединение([Цикл|Циклы],[Д|Ребра],Блок).
- объединение([[]|Циклы],Ребра,Блок):- объединение(Циклы,Ребра,Блок).
- объединение([],Блок,Блок).
- разность([Д|Граф],Блок,Граф1):- взять(Блок,Д,Блок1),!,
- разность(Граф,Блок1,Граф1).
- разность([Д|Граф],Блок,[Д|Граф1]):- разность(Граф,Блок,Граф1).
- разность([],_,[]).
- принадл(Вершина,[Вершина|_]):- !.
- принадл(Вершина,[_|Вершины]):- принадл(Вершина,Вершины).
- goal
- блоки([д(1,2),д(2,3),д(3,4),д(4,5),д(5,6),д(2,5),д(6,1),д(5,7),д(5,8),д(7,8),д(2,9)],[],Блоки).
Решение задачи: «Проверить является ли заданный граф блоком SWI prolog»
textual
Листинг программы
- blocks([d(1,2),d(2,3),d(3,4),d(4,5),d(5,6),d(2,5),d(6,1),d(5,7),d(5,8),d(7,8),d(2,9)],[],Blocks).
- checkBlock([d(1,2),d(2,3),d(3,4),d(4,5),d(5,6),d(2,5),d(6,1),d(5,7),d(5,8),d(7,8),d(2,8)]).
Объяснение кода листинга программы
- В первом аргументе функции
blocks
перечислены пары вершин графа, соединенные ребрами. - Второй аргумент функции
blocks
пуст, он должен быть таким же, как и первый. - Третий аргумент функции
blocks
- это список списков, где каждый внутренний список содержит пары вершин графа, соединенные ребрами. - В функции
checkBlock
перечислены пары вершин графа, соединенные ребрами. - Функция
checkBlock
проверяет, является ли переданный ей граф блоком SWI prolog. - Результатом выполнения функции
checkBlock
будетtrue
, если граф является блоком SWI prolog, иfalse
в противном случае.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д