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; }

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, 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

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