Skip to content
Snippets Groups Projects
Select Git revision
  • c6abd9d643f6865960de1e474afb2ae48bb97727
  • master default
2 results

2019-11-11-nary-trees.pl

Blame
  • 2019-11-11-nary-trees.pl 1.29 KiB
    % The tree definition from the homework assignment.
    istree(tree(Value,Children)) :-
        string(Value),subtrees(Children).
    subtrees([]).
    subtrees([(Cost,T)|Rest]) :-
        number(Cost),istree(T), subtrees(Rest).
    
    
    % An example tree.
    % If you want to call e.g. addweights with this tree, you can do it with the following trick:
    % tree1(X), addweights(X, Sum).
    tree1(tree("A", [(2, tree("B", [(1, tree("E", [])), (2, tree("F", []))])),
                     (5, tree("C", [(2, tree("G", []))])),
                     (2, tree("D", [(1, tree("X", [(1, tree("Y", []))]))]))])).
    
    % Add up all the weights of the edges in the tree.
    % (we called it cw in the tutorial)
    addweights(tree(_, []), 0).
    addweights(tree(_, [(X, T)|Rest]), S) :-
       addweights(T, S1),
       addweights(tree("asdf", Rest), S2),
       S is X + S1 + S2.
    
    % Also adds up all the weights, but in a different way:
    % In the previous attempt, we always expected a tree as argument and constructed trees on demand.
    % In this approach we'll take a list of (Cost, Tree) pairs instead.
    % This is not as pretty, but a useful approach for some tree search algorithms.
    addweights2([], 0).
    addweights2([(X, tree(_, Children))|Rest], S) :-
        addweights2(Rest, S1),
        addweights2(Children, S2),
        S is S1 + S2 + X.
    addweights2(T, S) :-
        istree(T),
        addweights2([(0, T)], S).