
Dear All I would like some help with graph structure for the edmund_karp max flow min cut function. I have a general graph in which I have many properties + edge and vertex. I sould like to run edmund karp on this graph however I have not been able to make the structure right for edmund karp and therefore I have made a second graph a flow graph. However I do not want to copy edges over every time I change something in the original graph. I was wundering if I could make it the same graph or just make the flow graph a filteret version of the original graph. The graphs are defined as follows:: original:: typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VertexProperties, EdgeProperties, GraphProperties> Graph; typedef boost::graph_traits<Graph> DirectedTraits; typedef DirectedTraits::vertex_descriptor DirectedVertex; typedef DirectedTraits::edge_descriptor DirectedEdge; typedef DirectedTraits::vertex_iterator VertexIterator; typedef DirectedTraits::edge_iterator DirectedEdgeIterator; typedef DirectedTraits::out_edge_iterator DirectedOutEdgeIterator; typedef DirectedTraits::in_edge_iterator DirectedInEdgeIterator; typedef boost::property_map<Graph, boost::edge_name_t>::type EdgeNameMap; flow graph:: typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> FlowTraits; typedef FlowTraits::edge_descriptor edge_descriptor; typedef FlowTraits::vertex_descriptor vertex_descriptor; typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_capacity_t, double, boost::property<boost::edge_residual_capacity_t, double, boost::property<shipping_graph::vertex_start_indicator_t, double, boost::property<boost::edge_reverse_t, FlowTraits::edge_descriptor> > > > > FlowGraph; typedef boost::graph_traits<FlowGraph> DirectedFlowTraits; typedef DirectedFlowTraits::out_edge_iterator FlowOutEdgeIterator; typedef boost::property_map<FlowGraph, boost::edge_capacity_t>::type MaxEdgeWeightMap; Thanks for your help Line

On Dec 10, 2007 7:37 AM, Line B. Reinhardt <lbr@ctt.dtu.dk> wrote:
Dear All I would like some help with graph structure for the edmund_karp max flow min cut function. I have a general graph in which I have many properties + edge and vertex. I sould like to run edmund karp on this graph however I have not been able to make the structure right for edmund karp and therefore I have made a second graph a flow graph. However I do not want to copy edges over every time I change something in the original graph. I was wundering if I could make it the same graph or just make the flow graph a filteret version of the original graph. The graphs are defined as follows::
<snip> Hi Line, Can you explain what you mean by "have not been able to make the structure right"? Your original graph needs to have reversed edges (for every edge (u,v) in the graph, (v,u) needs to also be in the graph), but unless you're missing that, you should be able to avoid having to create a separate graph to pass in. If you are missing reversed edges, you won't be able to add them through a filtered graph - a filtered graph only lets you remove some set of vertices and/or edges from the graph. Regards, Aaron
participants (2)
-
Aaron Windsor
-
Line B. Reinhardt