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

Помечено: ,

Просмотр 1 ветки ответов
  • Автор
    Сообщения
    • #2797
      @questioner

      Нужна программа на Visual Prolog, позволяющая ввести вершины и ребра графа, а также просмотреть введенные данные.

    • #2801
      @admin

      Опишем типы данных для нашей программы — нам потребуются вершины и дуги. Кроме того, при обработке графа часто полезными оказываются списки вершин и дуг (их можно собирать предикатом 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-программ«.

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