In [1]:

    

push!(LOAD_PATH, pwd())
using JoinTreeInference.Node
using JoinTreeInference.Potential
using JoinTreeInference.parse_net


    

In [2]:

    

function create_moral_graph(node_list::Array{Node,1}, 
                potential_list::Array{Potential,1})
    a_list = Dict{String, Set{String}}()
    for n in node_list
        a_list[n.name] = Set{String}()
    end
    
    function add_edge(i, j)
        push!(a_list[i], j)
        push!(a_list[j], i)
    end
    
    for p in potential_list
        for o in p.other_nodes
            add_edge(p.node, o)
        end
        for i in 1:length(p.other_nodes)
            for j in (i+1):length(p.other_nodes)
                add_edge(p.other_nodes[i], p.other_nodes[j])
            end
        end
    end
    return a_list
end


    

    
Out[2]:





create_moral_graph (generic function with 1 method)

In [3]:

    

function get_next_node(g::Dict{String,Set{String}}, 
    node_weights::Dict{String,Int})

    best_f = 0
    best_w = 0
    best_k = 0
    function update(f, w, k)
        best_f = f
        best_w = w
        best_k = k
    end

    nodes =  collect(keys(g))
    first = true
    for (k, node) in enumerate(nodes)
        nei = collect(g[node])
        f = 0
        w = node_weights[node]
        for i in 1:length(nei)
            w += node_weights[nei[i]]
            for j in (i+1):length(nei)
                if !(nei[i] in g[nei[j]])
                    f += 1
                end
            end
        end
        if first
            first = false
            update(f, w, k)
        else
            if (f < best_f) || (f == best_f && w < best_w)
                update(f, w, k)
            end
        end
    end
    return nodes[best_k]
end


    

    
Out[3]:





get_next_node (generic function with 1 method)

In [4]:

    

function triangulate_graph(g::Dict{String,Set{String}}, 
    node_list::Array{Node, 1})
    g1 = deepcopy(g)
    g2 = deepcopy(g)    
    function add_edge(i, j)
        for g in (g1, g2)
            push!(g[i], j)
            push!(g[j], i)
        end
    end
    
    node_weights = Dict{String, Int}()
    for node in node_list
        node_weights[node.name] = length(node.states)
    end
    
    clusters = Array{Set{String}, 1}()
    function check_add(g::Dict{String, Set{String}}, node::String)
        cluster = copy(g[node])
        push!(cluster, node)
        subsumed = false
        for c in clusters
            if issubset(cluster, c)
                subsumed = true
                break
            end
        end
        if !subsumed
            push!(clusters, cluster)
        end
    end
    
    while !isempty(keys(g1))
        next_node = get_next_node(g1, node_weights)
        check_add(g1, next_node)
        nei = collect(g1[next_node])
        for i in 1:length(nei)
            for j in (i+1):length(nei)
                add_edge(nei[i], nei[j])
            end
            delete!(g1[nei[i]], next_node)
        end
        delete!(g1, next_node)
    end
    return g2, clusters
end

function triangulate_graph(node_list::Array{Node,1}, 
                potential_list::Array{Potential,1})
    mg = create_moral_graph(node_list, potential_list)
    return triangulate_graph(mg, node_list)
end


    

    
Out[4]:





triangulate_graph (generic function with 2 methods)

In [5]:

    

node_list, potential_list = parse_net("data/asia.net")
tg, clusters = triangulate_graph(node_list, potential_list)


    

    
Out[5]:





(Dict("bronc"=>Set(String["either","dysp","smoke"]),"asia"=>Set(String["tub"]),"lung"=>Set(String["either","tub","smoke"]),"either"=>Set(String["bronc","lung","dysp","tub","xray","smoke"]),"dysp"=>Set(String["bronc","either"]),"tub"=>Set(String["either","asia","lung"]),"xray"=>Set(String["either"]),"smoke"=>Set(String["bronc","either","lung"])),Set{String}[Set(String["asia","tub"]),Set(String["either","xray"]),Set(String["bronc","either","dysp"]),Set(String["either","lung","tub"]),Set(String["either","bronc","smoke"]),Set(String["either","lung","smoke"])])