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

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

Помечено: ,

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

  • Автор
    Сообщения
  • #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-программ«.

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