{"action":"created","issue":{"url":"https://api.github.com/repos/jgrapht/jgrapht/issues/250","repository_url":"https://api.github.com/repos/jgrapht/jgrapht","labels_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/250/labels{/name}","comments_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/250/comments","events_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/250/events","html_url":"https://github.com/jgrapht/jgrapht/issues/250","id":169789092,"number":250,"title":"Bug in PushRelabel algorithm for undirected graphs","user":{"login":"jkinable","id":2742474,"avatar_url":"https://avatars.githubusercontent.com/u/2742474?v=3","gravatar_id":"","url":"https://api.github.com/users/jkinable","html_url":"https://github.com/jkinable","followers_url":"https://api.github.com/users/jkinable/followers","following_url":"https://api.github.com/users/jkinable/following{/other_user}","gists_url":"https://api.github.com/users/jkinable/gists{/gist_id}","starred_url":"https://api.github.com/users/jkinable/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jkinable/subscriptions","organizations_url":"https://api.github.com/users/jkinable/orgs","repos_url":"https://api.github.com/users/jkinable/repos","events_url":"https://api.github.com/users/jkinable/events{/privacy}","received_events_url":"https://api.github.com/users/jkinable/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2016-08-07T09:52:51Z","updated_at":"2016-08-11T00:39:13Z","closed_at":"2016-08-11T00:39:13Z","body":"There's a bug in the PushRelableImpl class for undirected graphs.\r\n\r\nTest case:\r\n```\r\npublic void testZeroFlow(){\r\n        Graph<Integer, DefaultWeightedEdge> graph=new SimpleWeightedGraph<>(DefaultWeightedEdge.class);\r\n        Graphs.addEdgeWithVertices(graph, 1, 2, 0);\r\n        Graphs.addEdgeWithVertices(graph, 2, 6, 1);\r\n        Graphs.addEdgeWithVertices(graph, 2, 3, 1);\r\n        Graphs.addEdgeWithVertices(graph, 3, 6, 1);\r\n        Graphs.addEdgeWithVertices(graph, 3, 4, 0);\r\n        Graphs.addEdgeWithVertices(graph, 1, 4, 1);\r\n        Graphs.addEdgeWithVertices(graph, 1, 5, 1);\r\n        Graphs.addEdgeWithVertices(graph, 4, 5, 1);\r\n\r\n        MaximumFlowAlgorithm<Integer, DefaultWeightedEdge> solver = createSolver(graph);\r\n        MaximumFlowAlgorithm.MaximumFlow<DefaultWeightedEdge> maxFlow=solver.buildMaximumFlow(1, 2);\r\n        System.out.println(\"Maxflow: \"+maxFlow);\r\n    }\r\n```\r\n\r\nExpected result:\r\nFlow: 0, Flow on each edge: 0\r\n\r\nActual result:\r\n```\r\nMaxflow: Flow Value: 0.0\r\nFlow map:\r\n{**(1 : 4)=1.0**, (2 : 6)=0.0, (3 : 6)=0.0, (2 : 3)=0.0, (1 : 2)=0.0, (3 : 4)=0.0, **(1 : 5)=1.0**, **(4 : 5)=1.0**}\r\n```\r\n\r\nNotice the non-zero flow on some of the edges."},"comment":{"url":"https://api.github.com/repos/jgrapht/jgrapht/issues/comments/239046461","html_url":"https://github.com/jgrapht/jgrapht/issues/250#issuecomment-239046461","issue_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/250","id":239046461,"user":{"login":"jkinable","id":2742474,"avatar_url":"https://avatars.githubusercontent.com/u/2742474?v=3","gravatar_id":"","url":"https://api.github.com/users/jkinable","html_url":"https://github.com/jkinable","followers_url":"https://api.github.com/users/jkinable/followers","following_url":"https://api.github.com/users/jkinable/following{/other_user}","gists_url":"https://api.github.com/users/jkinable/gists{/gist_id}","starred_url":"https://api.github.com/users/jkinable/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jkinable/subscriptions","organizations_url":"https://api.github.com/users/jkinable/orgs","repos_url":"https://api.github.com/users/jkinable/repos","events_url":"https://api.github.com/users/jkinable/events{/privacy}","received_events_url":"https://api.github.com/users/jkinable/received_events","type":"User","site_admin":false},"created_at":"2016-08-11T00:39:13Z","updated_at":"2016-08-11T00:39:13Z","body":"No longer an issue. Implementation of push relabel algorithm seems correct."}}
{"actor":{"display_login":"jkinable"}}