Minimum Spanning Tree of weighted undirected graph

153 views
Skip to first unread message

Hannes Wiedenhofer

unread,
Apr 30, 2018, 7:42:24 AM4/30/18
to SWI-Prolog

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

unread,
May 1, 2018, 7:02:32 AM5/1/18
to Hannes Wiedenhofer, SWI-Prolog
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

unread,
May 1, 2018, 7:28:21 AM5/1/18
to SWI-Prolog
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

unread,
May 1, 2018, 8:03:50 AM5/1/18
to Hannes Wiedenhofer, SWI-Prolog

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
Reply all
Reply to author
Forward
0 new messages