[vtkusers] vtkGraph

[David Doria]

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 <http://rpi.edu/%7Edoriad/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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.vtk.org/pipermail/vtkusers/attachments/20090910/4717de3b/attachment.htm>