Hi All, I have a question regarding CSR graph. Does anyone know if a CSR graph can be used as input to push_relabel_max_flow or edmonds_karp_max_flow algorithm in BOOST? The existing examples only use adjacency_list with the maximum flow algorithms. I need to use CSR graph with the max flow implementations, but do not know how and if it is feasible at all. If answer is yes, can anyone give a simple example? I am having trouble in setting capacity map and reverse_edge map in CSR before passing it to the max flow algorithms. -Thanks a lot for your time. Dan Jiang _________________________________________________________________ Live connected. Get Hotmail & Messenger on your phone. http://go.microsoft.com/?linkid=9724462
On Thu, 15 Apr 2010, Dan Jiang wrote:
Hi All, I have a question regarding CSR graph. Does anyone know if a CSR graph can be used as input to push_relabel_max_flow or edmonds_karp_max_flow algorithm in BOOST? The existing examples only use adjacency_list with the maximum flow algorithms. I need to use CSR graph with the max flow implementations, but do not know how and if it is feasible at all. If answer is yes, can anyone give a simple example? I am having trouble in setting capacity map and reverse_edge map in CSR before passing it to the max flow algorithms. -Thanks a lot for your time. Dan Jiang
Are there any issues you're having now that are not addressed by my previous email? These algorithms should work with CSR graphs; the property maps need to be changed to be bundled properties, though, and so the access method to get them differs from the adjacency_list version. -- Jeremiah Willcock
I see several replies from you. But none of them answered my question of how to setup capacity map and reverse_edge map for CSR graph (I got compile error). Did you get that email? If not I can resend it. -Thanks Dan
Date: Thu, 15 Apr 2010 11:48:53 -0400 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] CSR graph in max flow
On Thu, 15 Apr 2010, Dan Jiang wrote:
Hi All, I have a question regarding CSR graph. Does anyone know if a CSR graph can be used as input to push_relabel_max_flow or edmonds_karp_max_flow algorithm in BOOST? The existing examples only use adjacency_list with the maximum flow algorithms. I need to use CSR graph with the max flow implementations, but do not know how and if it is feasible at all. If answer is yes, can anyone give a simple example? I am having trouble in setting capacity map and reverse_edge map in CSR before passing it to the max flow algorithms. -Thanks a lot for your time. Dan Jiang
Are there any issues you're having now that are not addressed by my previous email? These algorithms should work with CSR graphs; the property maps need to be changed to be bundled properties, though, and so the access method to get them differs from the adjacency_list version.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_________________________________________________________________ Live connected. Get Hotmail & Messenger on your phone. http://go.microsoft.com/?linkid=9724462
On Thu, 15 Apr 2010, Dan Jiang wrote:
I see several replies from you. But none of them answered my question of how to setup capacity map and reverse_edge map for CSR graph (I got compile error). Did you get that email? If not I can resend it. -Thanks Dan
I sent one with the example for how to get the capacity map -- your bundled edge property didn't have a reverse map. The capacity map is: boost::property_map<Graph, EdgeProp::*float>::type capacity_map = get(&EdgeProp::capacity, g); and similar for the other maps. -- Jeremiah Willcock
Hi Jeremiah, I did not get that email. I did this which seems to work as well: boost::property_map<Graph, float EdgeProp::float>::type capacity_map = get(&EdgeProp::capacity, g); Now since you said CSR has no reverse_edge map, then I cannot use edmonds_karp_max_flow after using push_relabel_max_flow. I need to get the color map output by edmonds_karp_max_flow. The one from push_relabel_max_flow does not serve my needs. Any way to convert the former to the latter without actually calling edmonds_karp_max_flow? Many thanks for your help. I think I am getting close to it. Dan
Date: Thu, 15 Apr 2010 13:26:37 -0400 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] CSR graph in max flow
On Thu, 15 Apr 2010, Dan Jiang wrote:
I see several replies from you. But none of them answered my question of how to setup capacity map and reverse_edge map for CSR graph (I got compile error). Did you get that email? If not I can resend it. -Thanks Dan
I sent one with the example for how to get the capacity map -- your bundled edge property didn't have a reverse map. The capacity map is:
boost::property_map<Graph, EdgeProp::*float>::type capacity_map = get(&EdgeProp::capacity, g);
and similar for the other maps.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_________________________________________________________________ Hotmail & Messenger are available on your phone. Try now. http://go.microsoft.com/?linkid=9724461
Date: Thu, 15 Apr 2010 13:26:37 -0400 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] CSR graph in max flow
On Thu, 15 Apr 2010, Dan Jiang wrote:
I see several replies from you. But none of them answered my question of how to setup capacity map and reverse_edge map for CSR graph (I got compile error). Did you get that email? If not I can resend it. -Thanks Dan
I sent one with the example for how to get the capacity map -- your bundled edge property didn't have a reverse map. The capacity map is:
boost::property_map<Graph, EdgeProp::*float>::type capacity_map = get(&EdgeProp::capacity, g);
and similar for the other maps.
Ok, I did that, but push_relabel_max_flow errors out at all lines that try to access the capacity or reverse_capacity, e.g.: residual_capacity[*ei] = capacity[*ei];Because both capacity and residual_capacity maps in push_relabel_max_flow are keyed on edge_descriptor while the above definition is key on a "float". How do I fix this if possible? Also, I have another question regarding reverse_edge_map creation from a CSR graph.In case of adjacency list, I can use add_edge to create both forward and backward edges and then add both to reverse_edge map, i.e.,edge_descriptor e1 = add_edge(v1, v2);edge_descriptor e2 = add_edge(v2, v1);rev[e1] = e2;rev[e2] = e1;In case CSR, I am passing an array of std::pair<int, int> to CSR constructor using "unsorted_edges" flag, i.e., I can not get e1 and e2 edge_descriptors as above. So I am thinking of looping through each edge to populate the reverse edge "rev" map: BGL_FORALL_EDGES(e, g, BOOST_Graph) { BOOST_Graph::vertex_descriptor src = boost::source(e, g); BOOST_Graph::vertex_descriptor dst = boost::target(e, g); // Here compiler errors out: term does not evaluate to a function taking 3 arguments std::pair<edge_descriptor, bool> edge = edge(src, dst, g); std::pair<edge_descriptor, bool> edge_rev = edge(dst, src, g); // But compiler errors out here rev[edge.first] = edge_rev.first; }Can you tell me how to fix the compiler errors? Thanks, Dan _________________________________________________________________ Live connected. Get Hotmail & Messenger on your phone. http://go.microsoft.com/?linkid=9724462
On Thu, 15 Apr 2010, Dan Jiang wrote:
Date: Thu, 15 Apr 2010 13:26:37 -0400 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] CSR graph in max flow
On Thu, 15 Apr 2010, Dan Jiang wrote:
I see several replies from you. But none of them answered my question of how to setup capacity map and reverse_edge map for CSR graph (I got compile error). Did you get that email? If not I can resend it. -Thanks Dan
I sent one with the example for how to get the capacity map -- your bundled edge property didn't have a reverse map. The capacity map is:
boost::property_map<Graph, EdgeProp::*float>::type capacity_map = get(&EdgeProp::capacity, g);
and similar for the other maps.
Ok, I did that, but push_relabel_max_flow errors out at all lines that try to access the capacity or reverse_capacity, e.g.: residual_capacity[*ei] = capacity[*ei];Because both capacity and residual_capacity maps in push_relabel_max_flow are keyed on edge_descriptor while the above definition is key on a "float". How do I fix this if possible? Also, I have another question regarding reverse_edge_map creation from a CSR graph.In case of adjacency list, I can use add_edge to create both forward and backward edges and then add both to reverse_edge map, i.e.,edge_descriptor e1 = add_edge(v1, v2);edge_descriptor e2 = add_edge(v2, v1);rev[e1] = e2;rev[e2] = e1;In case CSR, I am passing an array of std::pair<int, int> to CSR constructor using "unsorted_edges" flag, i.e., I can not get e1 and e2 edge_descriptors as above. So I am thinking of looping through each edge to populate the reverse edge "rev" map: BGL_FORALL_EDGES(e, g, BOOST_Graph) { BOOST_Graph::vertex_descriptor src = boost::source(e, g); BOOST_Graph::vertex_descriptor dst = boost::target(e, g); // Here compiler errors out: term does not evaluate to a function taking 3 arguments std::pair<edge_descriptor, bool> edge = edge(src, dst, g); std::pair<edge_descriptor, bool> edge_rev = edge(dst, src, g); // But compiler errors ou! t h ere rev[edge.first] = edge_rev.first; }Can you tell me how to fix the compiler errors?
What compiler errors do you have? Could you please post a complete piece of code that gives an error, as well as the errors themselves? Also, please put newlines in your code so it is easier to read. -- Jeremiah Willcock
Hi Jeremiah, Here is the code and error. Thanks again for your help. -Dan ========================================== typedef compressed_sparse_row_graph<directedS> Traits; struct EdgeProp{ float capacity; float residual_capacity; Traits::edge_descriptor reverse_edge; }; typedef compressed_sparse_row_graph<directedS, property<vertex_index_t, DWORD32>, EdgeProp, no_property, // Graph Property DWORD32, // Vertex Type DWORD32> // EdgeIndex Type BOOST_Graph; The code that errors out: flow = (float)push_relabel_max_flow(g, s, t); Errors: (Note that line 146 in push_relabel_flow.hpp is: residual_capacity[*ei] = capacity[*ei];) C:\Program Files (x86)\boost\boost_1_42\boost/graph/push_relabel_max_flow.hpp(146) : error C2679: binary '[' : no operator found which takes a right-hand operand of type 'const boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>' (or there is no acceptable conversion) with [ Vertex=size_t, EdgeIndex=size_t ] C:\Program Files (x86)\boost\boost_1_42\boost/property_map/property_map.hpp(553): could be 'unsigned int boost::typed_identity_property_map<T>::operator [](const unsigned int &) const' with [ T=size_t ] while trying to match the argument list '(boost::typed_identity_property_map<T>, const boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>)' with [ T=size_t ] and [ Vertex=size_t, EdgeIndex=size_t ] C:\Program Files (x86)\boost\boost_1_42\boost/graph/push_relabel_max_flow.hpp(114) : while compiling class template member function 'boost::detail::push_relabel<Graph,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,VertexIndexMap,FlowValue>::push_relabel(Graph &,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,unsigned int,unsigned int,VertexIndexMap)' with [ Graph=BOOST_Graph, EdgeCapacityMap=boost::typed_identity_property_map<size_t>, ResidualCapacityEdgeMap=boost::typed_identity_property_map<size_t>, ReverseEdgeMap=boost::typed_identity_property_map<size_t>, VertexIndexMap=boost::typed_identity_property_map<size_t>, FlowValue=FlowValue ] C:\Program Files (x86)\boost\boost_1_42\boost/graph/push_relabel_max_flow.hpp(680) : see reference to class template instantiation 'boost::detail::push_relabel<Graph,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,VertexIndexMap,FlowValue>' being compiled with [ Graph=BOOST_Graph, EdgeCapacityMap=boost::typed_identity_property_map<size_t>, ResidualCapacityEdgeMap=boost::typed_identity_property_map<size_t>, ReverseEdgeMap=boost::typed_identity_property_map<size_t>, VertexIndexMap=boost::typed_identity_property_map<size_t>, FlowValue=FlowValue ] C:\Program Files (x86)\boost\boost_1_42\boost/graph/push_relabel_max_flow.hpp(707) : see reference to function template instantiation 'unsigned int boost::push_relabel_max_flow<Graph,boost::typed_identity_property_map<T>,boost::typed_identity_property_map<T>,boost::typed_identity_property_map<T>,boost::typed_identity_property_map<T>>(Graph &,unsigned int,unsigned int,CapacityEdgeMap,ResidualCapacityEdgeMap,ReverseEdgeMap,VertexIndexMap)' being compiled with [ Graph=BOOST_Graph, T=size_t, CapacityEdgeMap=boost::typed_identity_property_map<size_t>, ResidualCapacityEdgeMap=boost::typed_identity_property_map<size_t>, ReverseEdgeMap=boost::typed_identity_property_map<size_t>, VertexIndexMap=boost::typed_identity_property_map<size_t> ] C:\Program Files (x86)\boost\boost_1_42\boost/graph/push_relabel_max_flow.hpp(720) : see reference to function template instantiation 'unsigned int boost::push_relabel_max_flow<Graph,int,boost::buffer_param_t,boost::no_property>(Graph &,unsigned int,unsigned int,const boost::bgl_named_params<T,Tag> &)' being compiled with [ Graph=BOOST_Graph, T=int, Tag=boost::buffer_param_t ] .\NetFlow.cpp(270) : see reference to function template instantiation 'unsigned int boost::push_relabel_max_flow<BOOST_Graph>(Graph &,unsigned int,unsigned int)' being compiled with [ Graph=BOOST_Graph ]C:\Program Files (x86)\boost\boost_1_42\boost/graph/push_relabel_max_flow.hpp(146) : error C2679: binary '[' : no operator found which takes a right-hand operand of type 'const boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>' (or there is no acceptable conversion) with [ Vertex=size_t, EdgeIndex=size_t ] C:\Program Files (x86)\boost\boost_1_42\boost/property_map/property_map.hpp(553): could be 'unsigned int boost::typed_identity_property_map<T>::operator [](const unsigned int &) const' with [ T=size_t ] while trying to match the argument list '(boost::typed_identity_property_map<T>, const boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>)' with [ T=size_t ] and [ Vertex=size_t, EdgeIndex=size_t ] C:\Program Files (x86)\boost\boost_1_42\boost/graph/push_relabel_max_flow.hpp(161) : error C2679: binary '[' : no operator found which takes a right-hand operand of type 'const boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>' (or there is no acceptable conversion) with [ Vertex=size_t, EdgeIndex=size_t ] C:\Program Files (x86)\boost\boost_1_42\boost/property_map/property_map.hpp(553): could be 'unsigned int boost::typed_identity_property_map<T>::operator [](const unsigned int &) const' with [ T=size_t ] while trying to match the argument list '(boost::typed_identity_property_map<T>, const boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>)' with [ T=size_t ] and [ Vertex=size_t, EdgeIndex=size_t ]C:\Program Files (x86)\boost\boost_1_42\boost/graph/push_relabel_max_flow.hpp(174) : error C2679: binary '[' : no operator found which takes a right-hand operand of type 'boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>' (or there is no acceptable conversion) with [ Vertex=size_t, EdgeIndex=size_t ] C:\Program Files (x86)\boost\boost_1_42\boost/property_map/property_map.hpp(553): could be 'unsigned int boost::typed_identity_property_map<T>::operator [](const unsigned int &) const' with [ T=size_t ] while trying to match the argument list '(boost::typed_identity_property_map<T>, boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>)' with [ T=size_t ] and [ Vertex=size_t, EdgeIndex=size_t ] C:\Program Files (x86)\boost\boost_1_42\boost/graph/push_relabel_max_flow.hpp(175) : error C2679: binary '[' : no operator found which takes a right-hand operand of type 'boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>' (or there is no acceptable conversion) with [ Vertex=size_t, EdgeIndex=size_t ] C:\Program Files (x86)\boost\boost_1_42\boost/property_map/property_map.hpp(553): could be 'unsigned int boost::typed_identity_property_map<T>::operator [](const unsigned int &) const' with [ T=size_t ] while trying to match the argument list '(boost::typed_identity_property_map<T>, boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>)' with [ T=size_t ] and [ Vertex=size_t, EdgeIndex=size_t ] C:\Program Files (x86)\boost\boost_1_42\boost/graph/push_relabel_max_flow.hpp(176) : error C2679: binary '[' : no operator found which takes a right-hand operand of type 'boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>' (or there is no acceptable conversion) with [ Vertex=size_t, EdgeIndex=size_t ] C:\Program Files (x86)\boost\boost_1_42\boost/property_map/property_map.hpp(553): could be 'unsigned int boost::typed_identity_property_map<T>::operator [](const unsigned int &) const' with [ T=size_t ] while trying to match the argument list '(boost::typed_identity_property_map<T>, boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>)' with [ T=size_t ] and [ Vertex=size_t, EdgeIndex=size_t ]
What compiler errors do you have? Could you please post a complete piece of code that gives an error, as well as the errors themselves? Also, please put newlines in your code so it is easier to read.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_________________________________________________________________ Hotmail & Messenger are available on your phone. Try now. http://go.microsoft.com/?linkid=9724461
On Fri, 16 Apr 2010, Dan Jiang wrote:
Hi Jeremiah, Here is the code and error. Thanks again for your help. -Dan ========================================== typedef compressed_sparse_row_graph<directedS> Traits; struct EdgeProp{ float capacity; float residual_capacity; Traits::edge_descriptor reverse_edge; }; typedef compressed_sparse_row_graph<directedS, property<vertex_index_t, DWORD32>, EdgeProp, no_property, // Graph Property DWORD32, // Vertex Type DWORD32> // EdgeIndex Type BOOST_Graph; The code that errors out: flow = (float)push_relabel_max_flow(g, s, t);
Since you are using bundled properties, you need to give the capacity, residual, and reverse edge maps explicitly as arguments to push_relabel_max_flow. Please add those as separate arguments (using the named parameter mechanism) and see if that helps. I don't know why the maps default to identity_property_map -- that seems like it will basically never work. Also, the push_relabel_max_flow code shouldn't be using operator[]. Are you using the Boost trunk or a release version? I can put some fixes into the trunk for some of these issues. -- Jeremiah Willcock
Ok. Using named parameters works (i.e., no compile errors). Now I'd have to wait for your fix for the edge() issue. I am using the release load 1.42. Since this is minor change (I hope), can I simply use your fix as a patch without switching to use development branch? If yes, can you send me the fix by email? Many thanks, Dan
Date: Fri, 16 Apr 2010 15:42:23 -0400 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] CSR graph in max flow
On Fri, 16 Apr 2010, Dan Jiang wrote:
Hi Jeremiah, Here is the code and error. Thanks again for your help. -Dan ========================================== typedef compressed_sparse_row_graph<directedS> Traits; struct EdgeProp{ float capacity; float residual_capacity; Traits::edge_descriptor reverse_edge; }; typedef compressed_sparse_row_graph<directedS, property<vertex_index_t, DWORD32>, EdgeProp, no_property, // Graph Property DWORD32, // Vertex Type DWORD32> // EdgeIndex Type BOOST_Graph; The code that errors out: flow = (float)push_relabel_max_flow(g, s, t);
Since you are using bundled properties, you need to give the capacity, residual, and reverse edge maps explicitly as arguments to push_relabel_max_flow. Please add those as separate arguments (using the named parameter mechanism) and see if that helps. I don't know why the maps default to identity_property_map -- that seems like it will basically never work. Also, the push_relabel_max_flow code shouldn't be using operator[]. Are you using the Boost trunk or a release version? I can put some fixes into the trunk for some of these issues.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_________________________________________________________________ Hotmail & Messenger. Get them on your phone now. http://go.microsoft.com/?linkid=9724463
Yes, you can just use a patch, or just copy over <URL:https://svn.boost.org/svn/boost/trunk/boost/graph/ compressed_sparse_row_graph.hpp> on top of your version. -- Jeremiah Willcock On Fri, 16 Apr 2010, Dan Jiang wrote:
Ok. Using named parameters works (i.e., no compile errors). Now I'd have to wait for your fix for the edge() issue. I am using the release load 1.42. Since this is minor change (I hope), can I simply use your fix as a patch without switching to use development branch? If yes, can you send me the fix by email? Many thanks, Dan
Date: Fri, 16 Apr 2010 15:42:23 -0400 From: jewillco@osl.iu.edu To: boost@lists.boost.org Subject: Re: [boost] CSR graph in max flow
On Fri, 16 Apr 2010, Dan Jiang wrote:
Hi Jeremiah, Here is the code and error. Thanks again for your help. -Dan ========================================== typedef compressed_sparse_row_graph<directedS> Traits; struct EdgeProp{ float capacity; float residual_capacity; Traits::edge_descriptor reverse_edge; }; typedef compressed_sparse_row_graph<directedS, property<vertex_index_t, DWORD32>, EdgeProp, no_property, // Graph Property DWORD32, // Vertex Type DWORD32> // EdgeIndex Type BOOST_Graph; The code that errors out: flow = (float)push_relabel_max_flow(g, s, t);
Since you are using bundled properties, you need to give the capacity, residual, and reverse edge maps explicitly as arguments to push_relabel_max_flow. Please add those as separate arguments (using the named parameter mechanism) and see if that helps. I don't know why the maps default to identity_property_map -- that seems like it will basically never work. Also, the push_relabel_max_flow code shouldn't be using operator[]. Are you using the Boost trunk or a release version? I can put some fixes into the trunk for some of these issues.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_________________________________________________________________ Hotmail & Messenger. Get them on your phone now. http://go.microsoft.com/?linkid=9724463 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (2)
-
Dan Jiang -
Jeremiah Willcock