仅当每次迭代结束时有 println() 语句时，该函数才起作用

Question

我正在尝试在 Julia 中实现一篇论文（第 212-213 页）中的 3-clique（三角形）查找算法，但我遇到了代码问题

\n

function find_triangle(graph::AdjacencyListGraphs)\n\n    new_graph = deepcopy(graph)\n    sort!(new_graph.edges, by=x->new_graph.D[x], rev=true)\n    cliques = Vector{Vector{Int64}}()\n    marked_nodes = Set()\n\n    for i in 1:new_graph.n - 2\n        cur = new_graph.edges[new_graph.edges.keys[1]]\n\n        # mark vertices adjacent to i\n        for j in 1:length(cur)\n            push!(marked_nodes,cur[j])\n        end\n\n        # search in marked nodes\n        for j in 1:length(cur)\n            u = cur[j]\n            for w in new_graph.edges[u]\n                if w in marked_nodes\n                    cur_clique = [new_graph.edges.keys[1], u, w]\n                    push!(cliques, cur_clique)\n                end\n            delete!(marked_nodes, u)\n            end\n        end\n\n        # delete node\n        for key in new_graph.edges.keys\n            filter!(x->x\xe2\x89\xa0new_graph.edges.keys[1],new_graph.edges[key])\n        end\n        delete!(new_graph.edges, new_graph.edges.keys[1])\n\n        # this println() call is currently used to prevent an unknown error. Not sure why, but this fixes it\n        println(new_graph)\n    end\n\n    return cliques\nend\n

\n

该函数的输入如下

\n

nodes = [1,2,3,4,5,6]\n\nedges = OrderedDict{Int64, Vector{Int64}}()\nedges[1] = [2,3,5]\nedges[2] = [1,3,4,6]\nedges[3] = [1,2,4,6]\nedges[4] = [2,3,5,6]\nedges[5] = [1,4]\nedges[6] = [2,3,4]\n\ndegrees = [3,4,4,4,2,3]\ngraph = AdjacencyListGraphs(nodes, 6, 10, degrees, edges)\ncliques = find_triangle(graph)\n

\n

图的类型定义如下：

\n

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

\n

如果我包含 println() 语句，该函数会正常运行，但如果我仅删除该语句，则会遇到以下错误

\n

ERROR: LoadError: KeyError: key 2 not found\n

\n

对我来说，这个问题看起来像是删除节点时的错误，并且 println() 语句以某种方式修复了它。我需要解决这个问题的原因是因为我试图在一个更大的图形上运行代码，其中包含大约一百万个三角形，但每一步的 println() 调用实际上都会使我的计算机崩溃。

\n

任何帮助将不胜感激; 谢谢你！

\n

Answer 1

问题的原因是您使用了私有keys字段。OrderedDict您应该使用访问器函数，例如：

\n

function find_triangle(graph::AdjacencyListGraphs)\n\n    new_graph = deepcopy(graph)\n    sort!(new_graph.edges, by=x->new_graph.D[x], rev=true)\n    cliques = Vector{Vector{Int64}}()\n    marked_nodes = Set()\n\n    for i in 1:new_graph.n - 2\n        curk = first(keys(new_graph.edges))\n        cur = new_graph.edges[curk]\n\n        # mark vertices adjacent to i\n        for j in 1:length(cur)\n            push!(marked_nodes,cur[j])\n        end\n\n        # search in marked nodes\n        for j in 1:length(cur)\n            u = cur[j]\n            for w in new_graph.edges[u]\n                if w in marked_nodes\n                    cur_clique = [curk, u, w]\n                    push!(cliques, cur_clique)\n                end\n            delete!(marked_nodes, u)\n            end\n        end\n\n        # delete node\n        for key in new_graph.edges.keys\n            filter!(x->x\xe2\x89\xa0curk,new_graph.edges[key])\n        end\n        delete!(new_graph.edges, curk)\n\n        # this println() call is currently used to prevent an unknown error. Not sure why, but this fixes it\n   #     println(new_graph)\n    end\n\n    return cliques\nend\n

\n

问题的原因是您删除了字典中的键，但没有调用rehash!它。顺便rehash!说一下，当你调用时，println它会被调用，因为iterate它会依次调用rehash!。所以这会起作用：

\n

function find_triangle(graph::AdjacencyListGraphs)\n\n    new_graph = deepcopy(graph)\n    sort!(new_graph.edges, by=x->new_graph.D[x], rev=true)\n    cliques = Vector{Vector{Int64}}()\n    marked_nodes = Set()\n\n    for i in 1:new_graph.n - 2\n        DataStructures.OrderedCollections.rehash!(new_graph.edges)\n        cur = new_graph.edges[new_graph.edges.keys[1]]\n\n        # mark vertices adjacent to i\n        for j in 1:length(cur)\n            push!(marked_nodes,cur[j])\n        end\n\n        # search in marked nodes\n        for j in 1:length(cur)\n            u = cur[j]\n            for w in new_graph.edges[u]\n                if w in marked_nodes\n                    cur_clique = [new_graph.edges.keys[1], u, w]\n                    push!(cliques, cur_clique)\n                end\n            delete!(marked_nodes, u)\n            end\n        end\n\n        # delete node\n        for key in new_graph.edges.keys\n            filter!(x->x\xe2\x89\xa0new_graph.edges.keys[1],new_graph.edges[key])\n        end\n        delete!(new_graph.edges, new_graph.edges.keys[1])\n\n        # this println() call is currently used to prevent an unknown error. Not sure why, but this fixes it\n        #println(new_graph)\n    end\n\n    return cliques\nend\n

\n

但你不应该编写这样的代码，而应该使用公共 API。

\n