Function only works when there is a println() statement at the end of each iteration

user_13252273 0
Viewed 91

I'm trying to implement a 3-clique (triangle) finding algorithm from a paper (p. 212-213) in Julia, but I'm running into a problem with the code

function find_triangle(graph::AdjacencyListGraphs)

    new_graph = deepcopy(graph)
    sort!(new_graph.edges, by=x->new_graph.D[x], rev=true)
    cliques = Vector{Vector{Int64}}()
    marked_nodes = Set()

    for i in 1:new_graph.n - 2
        cur = new_graph.edges[new_graph.edges.keys[1]]

        # mark vertices adjacent to i
        for j in 1:length(cur)
            push!(marked_nodes,cur[j])
        end

        # search in marked nodes
        for j in 1:length(cur)
            u = cur[j]
            for w in new_graph.edges[u]
                if w in marked_nodes
                    cur_clique = [new_graph.edges.keys[1], u, w]
                    push!(cliques, cur_clique)
                end
            delete!(marked_nodes, u)
            end
        end

        # delete node
        for key in new_graph.edges.keys
            filter!(x->x≠new_graph.edges.keys[1],new_graph.edges[key])
        end
        delete!(new_graph.edges, new_graph.edges.keys[1])

        # this println() call is currently used to prevent an unknown error. Not sure why, but this fixes it
        println(new_graph)
    end

    return cliques
end

The input to the function is the following

nodes = [1,2,3,4,5,6]

edges = OrderedDict{Int64, Vector{Int64}}()
edges[1] = [2,3,5]
edges[2] = [1,3,4,6]
edges[3] = [1,2,4,6]
edges[4] = [2,3,5,6]
edges[5] = [1,4]
edges[6] = [2,3,4]

degrees = [3,4,4,4,2,3]
graph = AdjacencyListGraphs(nodes, 6, 10, degrees, edges)
cliques = find_triangle(graph)

And the type definition for the graph is as follows:

mutable struct AdjacencyListGraphs{Int64}
    vals::Vector{Int64} # vertex list
    n::Int64 # number of vertices
    m::Int64 # number of edges
    D::Vector{Int64} # degree sequence
    edges::OrderedDict{Int64, Vector{Int64}} # adjacency list
end

The function runs properly if I include the println() statement, but if I remove just that statement, I run into the following bug

ERROR: LoadError: KeyError: key 2 not found

The issue to me looks like an error in the deletion of a node, and someohow the println() statement fixes it. The reason why I need to fix this is because I'm trying to run the code on a much bigger graph with about a million triangles, but the println() call at each step is literally crashing my computer.

Any help would be greatly appreciated; thank you!

julia graph-theory
2 Answers

The reason of the problem is that you use keys field of OrderedDict which is private. You should use accessor function e.g. like this:

function find_triangle(graph::AdjacencyListGraphs)

    new_graph = deepcopy(graph)
    sort!(new_graph.edges, by=x->new_graph.D[x], rev=true)
    cliques = Vector{Vector{Int64}}()
    marked_nodes = Set()

    for i in 1:new_graph.n - 2
        curk = first(keys(new_graph.edges))
        cur = new_graph.edges[curk]

        # mark vertices adjacent to i
        for j in 1:length(cur)
            push!(marked_nodes,cur[j])
        end

        # search in marked nodes
        for j in 1:length(cur)
            u = cur[j]
            for w in new_graph.edges[u]
                if w in marked_nodes
                    cur_clique = [curk, u, w]
                    push!(cliques, cur_clique)
                end
            delete!(marked_nodes, u)
            end
        end

        # delete node
        for key in new_graph.edges.keys
            filter!(x->x≠curk,new_graph.edges[key])
        end
        delete!(new_graph.edges, curk)

        # this println() call is currently used to prevent an unknown error. Not sure why, but this fixes it
   #     println(new_graph)
    end

    return cliques
end

The reason for the problem is that you delete keys in the dictionary, but not call rehash! on it. Incidentally rehash! is called when you call println because it calls iterate which in turn calls rehash!. So this would work:

function find_triangle(graph::AdjacencyListGraphs)

    new_graph = deepcopy(graph)
    sort!(new_graph.edges, by=x->new_graph.D[x], rev=true)
    cliques = Vector{Vector{Int64}}()
    marked_nodes = Set()

    for i in 1:new_graph.n - 2
        DataStructures.OrderedCollections.rehash!(new_graph.edges)
        cur = new_graph.edges[new_graph.edges.keys[1]]

        # mark vertices adjacent to i
        for j in 1:length(cur)
            push!(marked_nodes,cur[j])
        end

        # search in marked nodes
        for j in 1:length(cur)
            u = cur[j]
            for w in new_graph.edges[u]
                if w in marked_nodes
                    cur_clique = [new_graph.edges.keys[1], u, w]
                    push!(cliques, cur_clique)
                end
            delete!(marked_nodes, u)
            end
        end

        # delete node
        for key in new_graph.edges.keys
            filter!(x->x≠new_graph.edges.keys[1],new_graph.edges[key])
        end
        delete!(new_graph.edges, new_graph.edges.keys[1])

        # this println() call is currently used to prevent an unknown error. Not sure why, but this fixes it
        #println(new_graph)
    end

    return cliques
end

but you should not write code like this, but rather use public API.

user_12695670

Maybe some body overwrote println or show for that custom type AdjacencyListGraphs, is the only reason I cuold find for a println to change the state of the code!.

user_104807580
Related