Create a list of nodes from a graph in Prolog?

0
votes

I'm trying to use the information from edges in a graph. I want to create a list of nodes from the edges in the graph I'm given. For example:

? - graph([edge(1,2),edge(2,3),edge(3,4)],List).
List = [1,2,3,4]

Here's a base case:

graph([edge(X,Y)],[X,Y]).

I have no idea how to do this, without a knowledge base. And why doesn't this just work on its own? Or something like this?

graph([edge(X,Y)], List) :- append(X,Y,List).

I'm very new to Prolog and would appreciate the help.

3
listrecursionprologgraph-theory

3 Answers

1
votes

Here is a solution that uses only basic Prolog: I think the base case should be the empty graph, not the graph with just one element. It has no nodes:

nodes([],[]).

For every non-empty graph, you collect the two nodes of the first edge, then continue with the rest of the graph:

nodes([edge(X,Y)|RestGraph],[X,Y|RestNodes]) :-
  nodes(RestGraph,RestNodes).

The problem with this solution is that you have a node probably several times in the result. You can eliminate such duplicates with sort/2:

nodes2(Graph,Nodes) :- nodes(Graph,Unsorted), sort(Unsorted,Nodes).

CapelliC's solution is more elegant and concise, but maybe harder to understand for beginners.

1
votes

without a knowledge base is a weird statement. If you have some edge/2, you can easily collect all nodes identifiers with with snippet:

nodes(Ns) :- setof(N, M^(edge(N, M) ; edge(M, N)), Ns).

edit Given code from comment, I would suggest

nodes_of_graph(graph(Edges), Ns) :-
  setof(N, M^(member(edge(N, M), Edges) ; member(edge(M, N), Edges)), Ns).

yields

1 ?- nodes_of_graph(graph([edge(1,2),edge(1,3)]),L).
L = [1, 2, 3].
1
votes

Carlo's solution can be improved by avoiding the performance penalty of the double call to member/2 by using an auxiliary predicate for the setof/3 goal. For example:

nodes_of_graph(graph(Edges), Nodes) :-
    setof(Node, edge_node(Edges, Node), Nodes).

edge_node(Edges, Node) :-
    member(edge(Begin, End), Edges),
    (   Node = Begin
    ;   Node = End
    ).

This alternative also improves readability (but at the cost of adding one more auxiliary predicate).