Ответ в теме: Ввод/вывод графа в prolog

      Комментарии к записи Ответ в теме: Ввод/вывод графа в prolog отключены
#2801

Опишем типы данных для нашей программы – нам потребуются вершины и дуги. Кроме того, при обработке графа часто полезными оказываются списки вершин и дуг (их можно собирать предикатом findall).

DOMAINS
	node_d = string
	edge_d = edge(node_d, node_d)
	
	nodes_d = node_d*
	edges_d = edge_d*

Затем, нужно описать формат записей базы данных, в которой будет сохраняться граф:

DATABASE
	node(node_d)
	edge(node_d, node_d)

Теперь нам нужно реализовать функцию, обеспечивающую вывод на экран меню и обработку его пунктов:

  	menu(0):-
  		write("enter:"), nl,
  		write("\t0 - exit"), nl,
  		write("\t1 - add node"), nl,
  		write("\t2 - add edge"), nl,
  		write("\t3 - view graph"), nl,
  		write(": "), read_until_not_integer(MenuPoint),
  		MenuPoint <> 0, !, menu(MenuPoint); !.
  	menu(1):-
  		write("enter node: "), readln(Node), 
  		add_node(Node), !, menu(0).
  	menu(2):-
  		write("enter node from: "), readln(From), 
  		write("enter node to: "), readln(To), !,
  		add_edge(From, To), menu(0).
  	menu(3):-
  		view_graph, !, menu(0).
  	menu(_):-
  		write("bad menu point"), nl, menu(0).

Описание обработки меню на Prolog.

Тут используется функция read_until_not_integer при считывании пункта меню чтобы в случае, если пользователь введет не целочисленное значение (например строку) – вывести ему предупреждение и попросить ввести данные повторно.

Кроме того, приведенный фрагмент кода содержит функции add_edge (для добавления дуги), add_node (добавление узла) и view_graph (вывод графа), которые тоже предстоит реализовать. Тут все эти функции используются так, что их выполнение должно всегда завершаться успешно, т.е. обработка возможных ошибок должна происходить внутри:

add_node(Node):-
  	node(Node), !, write("such node already exist"), nl;
  	assert(node(Node)).

При добавлении узла мы должны убедиться что такой узел не был добавлен ранее. Если узел уже есть – выводим сообщение, не изменяя содержимое базы данных.

add_edge(From, To):-
  	exist_edge(From, To), !, write("such edge already exist"), nl;
  	node(From), node(To), !, assert(edge(From, To));
  	write("ends nodes for this edge do not exist"), nl.

При добавлении дуги мы проверяем не только, что такая дуга не была добавлена ранее (функция exist_edge), но о то, что в графе присутствуют узлы, задающие концы дуги.

Функция exist_edge должна завершаться удачей лишь если искомая дуга есть в базе. В случае, если граф неориентированный, – нужно проверить наличие дуги, ведущей в противоположную сторону:

exist_edge(From, To):-
  	edge(From, To), !; edge(To, From), !.

Функция вывода графа выводит узлы в виде списка, полученного при помощи findall, а для вывода дуг использует вспомогательную функцию (для более красивого и наглядного представления графа на экране):

view_graph:-
  	findall(Node, node(Node), Nodes), 
  	write("nodes: "), write(Nodes), nl,
  	write("edges: "), print_edges, nl.

Функция вывода дуг использует механизм перебора с возвратами для перебора всех дуг базы данных:

print_edges:-
  	edge(From, To),
  	write(From), write("->"), write(To), nl,
  	fail; !.

После вывода очередной дуги выполняется оператор fail, приводящий к неудачному завершению функции и, как следствие, попытке поиска других решений (других дуг базы данных). Когда все дуги будут перебраны, управление получит код, размещенный после оператора "точка с запятой", состоящий из отсечения, всегда завершающегося успешно. Более подробно про порядок обработки операторов и операторы Prolog можно прочитать в теме “Семантика Prolog-программ“.