graph cut compilation error
I made a super simple example: A graph with 2 nodes and an edge between them. On trying to call kolmogorov_max_flow, I am getting: error: cannot convert 'boost::detail::error_property_not_found' to 'long int' in initialization Can anyone see what I am doing wrong? #include <iostream> // for std::cout #include <utility> // for std::pair #include <algorithm> // for std::for_each #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/kolmogorov_max_flow.hpp> using namespace boost; // create a typedef for the Graph type typedef adjacency_list<vecS, vecS, bidirectionalS> Graph; int main(int,char*[]) { // declare a graph object Graph g(2); //a graph with 2 vertices // add the edges to the graph object for (int i = 0; i < 1; ++i) { add_edge(0, 1, g); //add an edge between node 0 and node 1 } //find min cut //typedef adjacency_list_traits<vecS, vecS, directedS> Traits; //if we want a directed graph typedef adjacency_list_traits<vecS, vecS, bidirectionalS> Traits; Traits::vertex_descriptor s, t; *//the error is on this line* long flow = kolmogorov_max_flow(g, s, t); // a list of sources will be returned in s, and a list of sinks will be returned in t std::cout << "Max flow is: " << flow << std::endl; return 0; } Also, I see that you can add edge weights like this:
const int num_nodes = 5; E edges[] = { E(0,2), E(1,1), E(1,3), E(1,4), E(2,1), E(2,3), E(3,4), E(4,0), E(4,1) }; int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1};
Graph G(edges + sizeof(edges) / sizeof(E), weights, num_nodes);
but if I want to add edges like this: for (int i = 0; i < 1; ++i)
{ add_edge(0, 1, g); //add an edge between node 0 and node 1 }
How would I specify the edge weights? Thanks! David
On Tue, 8 Sep 2009, David Doria wrote:
I made a super simple example: A graph with 2 nodes and an edge between them. On trying to call kolmogorov_max_flow, I am getting: error: cannot convert 'boost::detail::error_property_not_found' to 'long int' in initialization
You are missing the edge weights and other property maps described in the documentation for kolmogorov_max_flow; you can supply them either as parameters to the kolmogorov_max_flow function or as particular property maps in your graph. You can add properties as template parameters to the adjacency_list class (see the documentation for how to do that), or use external properties. Once you have properties, you can use add_edge(source, target, prop, g) to add edges with properties. -- Jeremiah Willcock
On Tue, Sep 8, 2009 at 1:17 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Tue, 8 Sep 2009, David Doria wrote:
I made a super simple example: A graph with 2 nodes and an edge between
them. On trying to call kolmogorov_max_flow, I am getting: error: cannot convert 'boost::detail::error_property_not_found' to 'long int' in initialization
You are missing the edge weights and other property maps described in the documentation for kolmogorov_max_flow; you can supply them either as parameters to the kolmogorov_max_flow function or as particular property maps in your graph. You can add properties as template parameters to the adjacency_list class (see the documentation for how to do that), or use external properties. Once you have properties, you can use add_edge(source, target, prop, g) to add edges with properties.
-- Jeremiah Willcock __
Jeremiah, Thanks for the response. I am very new to boost, so I am not quite getting the Property Map idea. It seems like you can just provide a whole list of template arguments that are of type property<> to the adjacency_list object. It the kolmogorov example ( http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/kolmogorov_max_flow.html) , it looks like the only property that is needed is edge_capacity, so I defined EdgeCapacityProperty (it was actually quite a complicated property, depending on edge_reverse as well as edge_residual_capacity). However, I am still getting "conversion from error_property_not_found to EdgeCapacityProperty requested" when I try to call the maxflow function. Is this getting closer? I guess I am following the property<> stuff, but not the property_map<> idea? Here is the latest attempt: #include <iostream> // for std::cout #include <boost/graph/adjacency_list.hpp> #include <boost/graph/kolmogorov_max_flow.hpp> using namespace boost; typedef adjacency_list_traits<vecS, vecS, bidirectionalS> Traits; typedef property<edge_reverse_t, Traits::edge_descriptor> EdgeReverseProperty; typedef property<edge_residual_capacity_t, long, EdgeReverseProperty> EdgeResidualCapacityProperty; typedef property<edge_capacity_t, double, EdgeResidualCapacityProperty> EdgeCapacityProperty; typedef adjacency_list<vecS, vecS, bidirectionalS, EdgeCapacityProperty> Graph; //simple int main(int,char*[]) { // declare a graph object Graph g(2); //a graph with 2 vertices //add an edge between node 0 and node 1 with weight (capacity) 2.3 EdgeCapacityProperty e = 2.3; add_edge(0, 1, e, g); //find min cut Traits::vertex_descriptor s, t; //double flow = kolmogorov_max_flow(g, s, t); // a list of sources will be returned in s, and a list of sinks will be returned in t EdgeCapacityProperty flow = kolmogorov_max_flow(g, s, t); // a list of sources will be returned in s, and a list of sinks will be returned in t std::cout << "Max flow is: " << flow << std::endl; return 0; } Thanks, David
On Tue, Sep 8, 2009 at 2:42 PM, David Doria <daviddoria+boost@gmail.com<daviddoria%2Bboost@gmail.com>
wrote:
On Tue, Sep 8, 2009 at 1:17 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Tue, 8 Sep 2009, David Doria wrote:
I made a super simple example: A graph with 2 nodes and an edge between
them. On trying to call kolmogorov_max_flow, I am getting: error: cannot convert 'boost::detail::error_property_not_found' to 'long int' in initialization
You are missing the edge weights and other property maps described in the documentation for kolmogorov_max_flow; you can supply them either as parameters to the kolmogorov_max_flow function or as particular property maps in your graph. You can add properties as template parameters to the adjacency_list class (see the documentation for how to do that), or use external properties. Once you have properties, you can use add_edge(source, target, prop, g) to add edges with properties.
-- Jeremiah Willcock __
Jeremiah,
Thanks for the response. I am very new to boost, so I am not quite getting the Property Map idea. It seems like you can just provide a whole list of template arguments that are of type property<> to the adjacency_list object. It the kolmogorov example ( http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/kolmogorov_max_flow.html) , it looks like the only property that is needed is edge_capacity, so I defined EdgeCapacityProperty (it was actually quite a complicated property, depending on edge_reverse as well as edge_residual_capacity). However, I am still getting "conversion from error_property_not_found to EdgeCapacityProperty requested" when I try to call the maxflow function. Is this getting closer?
I guess I am following the property<> stuff, but not the property_map<> idea? Here is the latest attempt:
#include <iostream> // for std::cout #include <boost/graph/adjacency_list.hpp> #include <boost/graph/kolmogorov_max_flow.hpp>
using namespace boost;
typedef adjacency_list_traits<vecS, vecS, bidirectionalS> Traits;
typedef property<edge_reverse_t, Traits::edge_descriptor> EdgeReverseProperty; typedef property<edge_residual_capacity_t, long, EdgeReverseProperty> EdgeResidualCapacityProperty; typedef property<edge_capacity_t, double, EdgeResidualCapacityProperty> EdgeCapacityProperty;
typedef adjacency_list<vecS, vecS, bidirectionalS, EdgeCapacityProperty> Graph; //simple
int main(int,char*[]) { // declare a graph object Graph g(2); //a graph with 2 vertices
//add an edge between node 0 and node 1 with weight (capacity) 2.3 EdgeCapacityProperty e = 2.3; add_edge(0, 1, e, g);
//find min cut
Traits::vertex_descriptor s, t; //double flow = kolmogorov_max_flow(g, s, t); // a list of sources will be returned in s, and a list of sinks will be returned in t EdgeCapacityProperty flow = kolmogorov_max_flow(g, s, t); // a list of sources will be returned in s, and a list of sinks will be returned in t std::cout << "Max flow is: " << flow << std::endl;
return 0; }
Thanks,
David
Any clues as to what I've done wrong? Maybe a simple example like this could be put on the kolmogorov documentation page? Thanks, David
Jeremiah,
Thanks for the response. I am very new to boost, so I am not quite getting the Property Map idea. It seems like you can just provide a whole list of template arguments that are of type property<> to the adjacency_list object. It the kolmogorov example (http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/kolmogorov_max_flow.html) , it looks like the only property that is needed is edge_capacity, so I defined EdgeCapacityProperty (it was actually quite a complicated property, depending on edge_reverse as well as edge_residual_capacity). However, I am still getting "conversion from error_property_not_found to EdgeCapacityProperty requested" when I try to call the maxflow function. Is this getting closer?
I guess I am following the property<> stuff, but not the property_map<> idea? Here is the latest attempt:
#include <iostream> // for std::cout #include <boost/graph/adjacency_list.hpp> #include <boost/graph/kolmogorov_max_flow.hpp>
using namespace boost;
typedef adjacency_list_traits<vecS, vecS, bidirectionalS> Traits;
typedef property<edge_reverse_t, Traits::edge_descriptor> EdgeReverseProperty; typedef property<edge_residual_capacity_t, long, EdgeReverseProperty> EdgeResidualCapacityProperty; typedef property<edge_capacity_t, double, EdgeResidualCapacityProperty> EdgeCapacityProperty;
typedef adjacency_list<vecS, vecS, bidirectionalS, EdgeCapacityProperty> Graph; //simple
int main(int,char*[]) { // declare a graph object Graph g(2); //a graph with 2 vertices
//add an edge between node 0 and node 1 with weight (capacity) 2.3 EdgeCapacityProperty e = 2.3; add_edge(0, 1, e, g);
//find min cut
Traits::vertex_descriptor s, t; //double flow = kolmogorov_max_flow(g, s, t); // a list of sources will be returned in s, and a list of sinks will be returned in t EdgeCapacityProperty flow = kolmogorov_max_flow(g, s, t); // a list of sources will be returned in s, and a list of sinks will be returned in t std::cout << "Max flow is: " << flow << std::endl;
return 0; }
Thanks,
David
Any clues as to what I've done wrong? Maybe a simple example like this could be put on the kolmogorov documentation page?
The error message you get (the conversion error) should mention an argument number and a source location where the call with property_not_found is being used. Could you please look up that source location and argument number and see which property map the code is trying to use? You added one more map, but the documentation suggests several more that are required. The error message will probably say at least one of the missing ones. -- Jeremiah Willcock
Jeremiah,
Thanks for the response. I am very new to boost, so I am not quite getting the Property Map idea. It seems like you can just provide a whole list of template arguments that are of type property<> to the adjacency_list object. It the kolmogorov example (http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/kolmogorov_max_flow.html) , it looks like the only property that is needed is edge_capacity, so I defined EdgeCapacityProperty (it was actually quite a complicated property, depending on edge_reverse as well as edge_residual_capacity). However, I am still getting "conversion from error_property_not_found to EdgeCapacityProperty requested" when I try to call the maxflow function. Is this getting closer?
I guess I am following the property<> stuff, but not the property_map<> idea? Here is the latest attempt:
#include <iostream> // for std::cout #include <boost/graph/adjacency_list.hpp> #include <boost/graph/kolmogorov_max_flow.hpp>
using namespace boost;
typedef adjacency_list_traits<vecS, vecS, bidirectionalS> Traits;
typedef property<edge_reverse_t, Traits::edge_descriptor> EdgeReverseProperty; typedef property<edge_residual_capacity_t, long, EdgeReverseProperty> EdgeResidualCapacityProperty; typedef property<edge_capacity_t, double, EdgeResidualCapacityProperty> EdgeCapacityProperty;
typedef adjacency_list<vecS, vecS, bidirectionalS, EdgeCapacityProperty> Graph; //simple
int main(int,char*[]) { // declare a graph object Graph g(2); //a graph with 2 vertices
//add an edge between node 0 and node 1 with weight (capacity) 2.3 EdgeCapacityProperty e = 2.3; add_edge(0, 1, e, g);
//find min cut
Traits::vertex_descriptor s, t; //double flow = kolmogorov_max_flow(g, s, t); // a list of sources will be returned in s, and a list of sinks will be returned in t EdgeCapacityProperty flow = kolmogorov_max_flow(g, s, t); // a list of sources will be returned in s, and a list of sinks will be returned in t std::cout << "Max flow is: " << flow << std::endl;
return 0; }
Sorry -- I tried your code and the problem is not a missing property map at all. Your code on line 28 converts from a double to an EdgeCapacityProperty, which is a boost::property. I do not see what the four-argument add_edge's property should be, so just get the result from "add_edge(0, 1, g).first" as e and then do "put(edge_capacity, g, e, 2.3)" or similar to write properties. -- Jeremiah Willcock
On Wed, 9 Sep 2009, David Doria wrote:
Any clues as to what I've done wrong? Maybe a simple example like this could be put on the kolmogorov documentation page?
Sorry to spam you with another email, but I tweaked your code so it works and attached the result. I just changed the residual capacity to a double, added the necessary vertex properties (one problem you had was that you were passing your edge properties to the graph as vertex properties), changed the edge capacity setting to what I posted a few minutes ago, and changed the result of kolmogorov_max_flow to be converted to a double. It all compiles now. -- Jeremiah Willcock
On Wed, Sep 9, 2009 at 11:07 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Wed, 9 Sep 2009, David Doria wrote:
Any clues as to what I've done wrong? Maybe a simple example like this
could be put on the kolmogorov documentation page?
Sorry to spam you with another email, but I tweaked your code so it works and attached the result. I just changed the residual capacity to a double, added the necessary vertex properties (one problem you had was that you were passing your edge properties to the graph as vertex properties), changed the edge capacity setting to what I posted a few minutes ago, and changed the result of kolmogorov_max_flow to be converted to a double. It all compiles now.
-- Jeremiah Willcock ____
Jeremiah, Rather than spam, I'd call it fantastic information! I really appreciate your time. Although it compiles, the code you sent seems to segfault on the kolmogorov call. Maybe because we didn't specify a source and sink? Shouldn't it work without specifying them, thought? There should be two different mincut problems that can be solved - 1) the min cut on the entire graph and 2) the min cut dividing a specified source and sink (or multiple sources and/or sinks). Do you know how to do that/why it is segfaulting? Some other questions: 1) So this line creates two vertices: Graph g(2); then since the V0->V1 edge already exists, the add_edge function doesn't add another edge, it simply returns something like a pointer to the already existing edge so that properties, can be assigned to it, correct? 2) Since add_edge(..).first is the actual edge, it is implied that this a pair and hence a .second - what is stored in the .second? 3) Would I get the edge weight like this:? double ew = get(edge_capacity, g, add_edge(0, 1, g).first); We're almost there! Thanks again, David
Jeremiah,
Rather than spam, I'd call it fantastic information! I really appreciate your time.
Although it compiles, the code you sent seems to segfault on the kolmogorov call. Maybe because we didn't specify a source and sink? Shouldn't it work without specifying them, thought? There should be two different mincut problems that can be solved - 1) the min cut on the entire graph and 2) the min cut dividing a specified source and sink (or multiple sources and/or sinks). Do you know how to do that/why it is segfaulting?
I believe it wants specific source and target vertices. The other properties are not initialized either.
Some other questions:
1) So this line creates two vertices: Graph g(2);
then since the V0->V1 edge already exists, the add_edge function doesn't add another edge, it simply returns something like a pointer to the already existing edge so that properties, can be assigned to it, correct?
That line creates two vertices, but does not create any edges. The add_edge function will return a pointer to the existing edge (I believe) when the edge already exists and the graph does not support parallel edges.
2) Since add_edge(..).first is the actual edge, it is implied that this a pair and hence a .second - what is stored in the .second?
Whether a new edge was added; see http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/MutableGraph.html for details.
3) Would I get the edge weight like this:? double ew = get(edge_capacity, g, add_edge(0, 1, g).first);
You would want to get the result of add_edge.first into a variable and use that. Otherwise, yes, your syntax is correct. You can look at http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/PropertyGraph.html for the get and put calls. -- Jeremiah Willcock
Ok... getting even closer... I looked at read_dimacs a little bit and the kolmogorov example again and came up with this: I put a comment in where I added the reverse edge - this stops the segfault. It seems like there should be a way to do this automatically though - when you add an edge - have it add the reverse edge automatically - is this possible? Also, the cut weight seems to be only 4.3 (the weight of the first edge - where I am expecting it to be 4.3 + 5.1 = 9.4 (the sum of the edge weights). I actually do not need a directional graph, but it seems to be what the cut function is expecting, so I guess I can just use the 2-edge method and divide the weight I actually want by 2 and put it on both edges. Does anyone have any comments on this code / know what the cut weight should be? Can this example (once we get it working) be added to the documentation? I feel like it is extremely useful... #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/kolmogorov_max_flow.hpp> using namespace boost; typedef adjacency_list_traits < vecS, vecS, directedS > Traits; typedef adjacency_list < vecS, vecS, directedS, property < vertex_name_t, std::string, property < vertex_index_t, long, property < vertex_color_t, boost::default_color_type, property < vertex_distance_t, long, property < vertex_predecessor_t, Traits::edge_descriptor > > > > >, property < edge_capacity_t, double, property < edge_residual_capacity_t, double, property < edge_reverse_t, Traits::edge_descriptor > > > > Graph; int main(int,char*[]) { Graph g; //a graph with 0 vertices property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g); //add a source and sink node, and store them in s and t, respectively Traits::vertex_descriptor s = add_vertex(g); Traits::vertex_descriptor t = add_vertex(g); //add an edge between node s and node t with weight (capacity) 2.3 Traits::edge_descriptor e1 = add_edge(s, t, g).first; Traits::edge_descriptor e2 = add_edge(t, s, g).first; put(edge_capacity, g, e1, 4.3); put(edge_capacity, g, e2, 5.1); * //adding these two lines makes the segmentation fault stop!* rev[e1] = e2; rev[e2] = e1; //find min cut double flow = kolmogorov_max_flow(g, s, t); // a list of sources will be returned in s, and a list of sinks will be returned in t std::cout << "Max flow is: " << flow << std::endl; return 0; } Thanks, David
On Wed, 9 Sep 2009, David Doria wrote:
Ok... getting even closer... I looked at read_dimacs a little bit and the kolmogorov example again and came up with this:
I put a comment in where I added the reverse edge - this stops the segfault. It seems like there should be a way to do this automatically though - when you add an edge - have it add the reverse edge automatically - is this possible?
I don't know about that.
Also, the cut weight seems to be only 4.3 (the weight of the first edge - where I am expecting it to be 4.3 + 5.1 = 9.4 (the sum of the edge weights). I actually do not need a directional graph, but it seems to be what the cut function is expecting, so I guess I can just use the 2-edge method and divide the weight I actually want by 2 and put it on both edges.
The actual cut is 4.3: the goal is to maximize the flow from s to t, and the capacity there (which can be fulfilled) is 4.3. The flow from t to s doesn't matter since that would reduce the flow in the s->t direction. Similarly, if you want to have undirected edges, you put the full weight on each direction since the algorithm cannot use both directions of a single edge pair (they cancel each other out). -- Jeremiah Willcock
participants (2)
-
David Doria -
Jeremiah Willcock