[vtkusers] vtkGraph
Jeff Baumes
jeff.baumes at kitware.com
Fri Sep 11 08:43:54 EDT 2009
Try changing the line
AddEdge(v1, v2, rev, 8.0, g);
to
AddEdge(v1, v3, rev, 8.0, g);
Then you would actually make the graph that your diagram shows :) The
graph you create in your code does indeed have max flow 7.
Jeff
On Thu, Sep 10, 2009 at 7:15 PM, David Doria <daviddoria+vtk at gmail.com> wrote:
> On Wed, Sep 9, 2009 at 10:50 AM, Jeff Baumes <jeff.baumes at kitware.com>
> wrote:
>>>
>>> I don't understand this function:
>>>>
>>>> void vtkGraph::AddEdgePoint (vtkIdType e, double x[3])
>>>>
>>>> Adds a point to the end of the list of edge points for a certain edge..
>>>
>>> is an edge allowed to have more than 2 points?
>>
>> "edge points" are only for extra points in an edge (e.g. to make
>> curved/routed edges). When converted to lines, edges always start/end at the
>> vertex location. What you are looking for is vtkGraph::GetPoints(), which
>> returns a vtkPoints structure that contains the locations of each vertex.
>> You may want to look at the classes ending with "LayoutStrategy" under
>> Infovis. These are modules that can be plugged into vtkGraphLayout.
>>>
>>> Also, is there a min cut / max flow function?
>>
>> There is not currently a VTK algorithm for it, but you can use a vtkGraph
>> as an input to any Boost algorithm by including "vtkBoostGraphAdapter.h".
>> The Boost Graph Library does contain a min cut / max flow algorithm. See the
>> implementation of some filters like vtkBoostBreadthFirstSearch for an idea
>> of how to adapt a vtkGraph to Boost.
>>
>> Jeff
>
> Does anyone here actually use boost graph cuts? I've been pinging the boost
> mailing list but no one seems to be able to see what I'm doing wrong. Here
> is the email I sent to boost if anyone thinks they could help:
>
> I made this simple graph:
> http://rpi.edu/~doriad/graph.png
>
> The min cut between node 0 (source) and node 3 (sink) should be 11, right?
> But it is returning 7.
>
> My code is below:
>
> #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;
>
> Traits::edge_descriptor AddEdge(Traits::vertex_descriptor &v1,
> Traits::vertex_descriptor &v2, property_map < Graph, edge_reverse_t >::type
> &rev, const double capacity, Graph &g);
>
> 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 v0 = add_vertex(g);
> Traits::vertex_descriptor v1 = add_vertex(g);
> Traits::vertex_descriptor v2 = add_vertex(g);
> Traits::vertex_descriptor v3 = add_vertex(g);
>
> AddEdge(v0, v1, rev, 6.0, g);
> AddEdge(v0, v2, rev, 5.0, g);
> AddEdge(v1, v2, rev, 8.0, g);
> AddEdge(v2, v3, rev, 7.0, g);
>
> //find min cut
> double flow = kolmogorov_max_flow(g, v0, v3); // 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;
>
> property_map<Graph, edge_capacity_t>::type
> capacity = get(edge_capacity, g);
> property_map<Graph, edge_residual_capacity_t>::type
> residual_capacity = get(edge_residual_capacity, g);
>
>
> graph_traits<Graph>::vertex_iterator u_iter, u_end;
> graph_traits<Graph>::out_edge_iterator ei, e_end;
> for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
> for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
> if (capacity[*ei] > 0)
> std::cout << "Source: " << *u_iter << " destination: " <<
> target(*ei, g) << " capacity: " << capacity[*ei] << "residual cap: " <<
> residual_capacity[*ei] << " diff: "
> << (capacity[*ei] - residual_capacity[*ei]) <<
> std::endl;
>
> return 0;
> }
>
> Traits::edge_descriptor AddEdge(Traits::vertex_descriptor &v1,
> Traits::vertex_descriptor &v2, property_map < Graph, edge_reverse_t >::type
> &rev, const double capacity, Graph &g)
> {
> Traits::edge_descriptor e1 = add_edge(v1, v2, g).first;
> Traits::edge_descriptor e2 = add_edge(v2, v1, g).first;
> put(edge_capacity, g, e1, capacity);
> put(edge_capacity, g, e2, capacity);
>
> rev[e1] = e2;
> rev[e2] = e1;
> }
>
> The output is:
> Max flow is: 7
>
> Source: 0 destination: 1 capacity: 6residual cap: 4 diff: 2
> Source: 0 destination: 2 capacity: 5residual cap: 0 diff: 5
> Source: 1 destination: 0 capacity: 6residual cap: 8 diff: -2
> Source: 1 destination: 2 capacity: 8residual cap: 6 diff: 2
> Source: 2 destination: 0 capacity: 5residual cap: 5 diff: 0
> Source: 2 destination: 1 capacity: 8residual cap: 10 diff: -2
> Source: 2 destination: 3 capacity: 7residual cap: 0 diff: 7
> Source: 3 destination: 2 capacity: 7residual cap: 9 diff: -2
>
> Here are my questions:
> 1) Why is the max flow wrong?
>
> 2) I'm confused what that output is showing - for example, there is a Source
> 1 Destination 2 edge that is not a real edge. It is also missing the edge
> from node 3 to node 1.
>
> 3) What is the best way to determine which nodes are on the source side of
> the cut, and which are on the sink side? The goal is to partition the graph
> into two sets.
>
> 4) Is it possible to pass a list of sources and a list of sinks to
> kolmogorov_max_flow instead of just a single source node and a single sink
> node? (Or can a different boost maxflow algorithm handle that?) These are
> just additional constraints on where the cut should be allowed to be placed.
>
> Maybe this is not the type of thing BGL is intended for? If it is, I really
> think the answers to these questions should be added to the documentation!
>
> Thanks,
>
> David
>
>
> _______________________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Please keep messages on-topic and check the VTK FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ
>
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers
>
>
--
Jeff Baumes, Ph.D.
R&D Engineer, Kitware Inc.
(518) 881-4932
jeff.baumes at kitware.com
More information about the vtkusers
mailing list