Minimum Spanning Tree of weighted undirected graph

[Hannes Wiedenhofer]

I need to write a predicate that creates a minimum spanning tree of a weighted undirected graph, using Prim's Algorithm. How do I approach this problem?

The graph consists of multiple edge(v1, v2, length) predicates.

A minimum spanning tree is the shortest path that connects all edges without cycles.

Prim's algorithm:

Pick one arbitrary node and add it to the visited list.

Choose the smallest edge that connects it to another node.

Add that node to the visited list.

Look at all the nodes in the visited list and pick the smallest edge connected to one of them.

Add that node to the visited list.

Continue like this.

If the smallest edge connects two nodes that are already in the visited list, do not pick it.

[Kuniaki Mukai]

As far as I understand your description of the problem correctly,  the builtins  setof/3 or findall/3 might be 

useful for solving the problem.  It seems fairy easy with them but difficult without them, at leas for me.

Kuniaki Mukai

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.
Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

[Hannes Wiedenhofer]

It doesn't seem that easy for me.

% call the method with the list of all nodes as argument

msp(T) :- nodes(L), msp(T,L). 

% start with the first element

msp(T, [H|T] :- msp_1(H,T).

% the recursive step using setof (this is where I have problems)

msp_1(T, L) :- setof(C, connection(L, X, C), Y), ...?

[Kuniaki Mukai]

On May 1, 2018, at 20:28, Hannes Wiedenhofer <hon...@gmail.com> wrote:

It doesn't seem that easy for me.

By this, all nodes are collected into a list.

allnodes(Nodes):- findall(X, (connect(X,_,_); connect(_,X,_)), Bag),  sort(Bag, Nodes).

   minimum_weight(M) :-  allnodes(Nodes),  solve(Nodes, [],  _,  0, M).

where solve/5 is a main predicate, say

  solve(Nodes, Visitted, NewVisited, TotalWeight, NewTotalWeight)

which describe transitions of computation configurations (S,V,W),

where S is a set of nodes not yet in the visited list,

V is the visited list,  W is the weight.

(S, V, W)          ->            (S-{x], V+{x}, W+w)

select node x from S and weight w according to the condition of the problem

Hope this help.

Kuniaki Mukai