Ввод/вывод графа в prolog

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

Помечено: ,

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 8 мес., 2 нед. назад.

  • Автор
    Сообщения
  • #2797

    questioner
    Участник

    Нужна программа на Visual 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-программ“.

Для ответа в этой теме необходимо авторизоваться.