{"action":"closed","issue":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/438","repository_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl","labels_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/438/labels{/name}","comments_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/438/comments","events_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/438/events","html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/issues/438","id":175159228,"number":438,"title":"Infinite loop in push-relabel","user":{"login":"Azzaare","id":4535131,"avatar_url":"https://avatars.githubusercontent.com/u/4535131?v=3","gravatar_id":"","url":"https://api.github.com/users/Azzaare","html_url":"https://github.com/Azzaare","followers_url":"https://api.github.com/users/Azzaare/followers","following_url":"https://api.github.com/users/Azzaare/following{/other_user}","gists_url":"https://api.github.com/users/Azzaare/gists{/gist_id}","starred_url":"https://api.github.com/users/Azzaare/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Azzaare/subscriptions","organizations_url":"https://api.github.com/users/Azzaare/orgs","repos_url":"https://api.github.com/users/Azzaare/repos","events_url":"https://api.github.com/users/Azzaare/events{/privacy}","received_events_url":"https://api.github.com/users/Azzaare/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/labels/bug","name":"bug","color":"fc2929"}],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":12,"created_at":"2016-09-06T04:44:39Z","updated_at":"2016-09-18T21:53:55Z","closed_at":"2016-09-18T21:53:55Z","body":"I found out a couple of instances where push-relabel enter an infinite loop. The loop in question is in the push_relabel.jl file around line 55.\r\n```julia\r\n    while length(Q) > 0\r\n      println(\"Debug Max-Flow\")\r\n        v = pop!(Q)\r\n        active[v] = false\r\n        discharge!(residual_graph, v, capacity_matrix, flow_matrix, excess, height, active, count, Q)\r\n    end\r\n```\r\n\r\nBelow is a small instance, with source = 1 and target = 1, that is enough to enter the infinite loop.\r\n[0 1 0 0 1 0 1 0\r\n 1 0 0 0 1 1 0 1\r\n 0 0 0 1 0 0 0 0\r\n 0 0 0 0 0 0 0 0\r\n 1 0 1 0 0 0 1 0\r\n 0 0 0 0 1 0 0 0\r\n 0 0 0 0 1 0 0 0\r\n 0 0 0 0 0 0 0 0]"}}
{"actor":{"display_login":"sbromberger"}}