[Insight-users] MinCut on an itkMesh?

[David Doria]

On Tue, Sep 1, 2009 at 11:50 PM, Nicholas Tustison <ntustison at gmail.com>wrote:

> Hi David,
> Okay, it's been quite awhile since I've looked at the code but I think I
> can provide you with a little bit of direction.  If you look in the
> Initialize() function (the lines in question are 198-205 in my copy), you'll
> see that Boykov's min-cut algorithm adds 2 edges to the output graph, i.e.
> the "terminal edge" and the "orphan edge". Also, if I remember correctly,
> what you do is iterate through the nodes in the graph and inspect  the
> boolean variable "IsSink" which will be either true (sink node) or false
> (source node).  Also, the class variable m_MaxFlow should hold the weight of
> the min cut.  Simply call GetMaxFlow().
>
> Nick
>

Nick,

Thanks for the help so far - however, it doesn't seem to be working as
expected.

IsSink is returning false for both nodes.
GetMaxFlow() is returning 0.

I added this:
  this->m_MaxFlow += bottleneck;
std::cout << "added " << bottleneck << " to maxflow." << std::endl;

to line 394 of itkBoykovMinCutGraphFilter.txx and nothing is ever output..
so it follows that GetMaxFlow() would return 0 - but why would it never be
incremented? Is this too degenerate of a graph for the algorithm to work
properly? I wasn't sure if multiple edges were allowed between nodes - so I
now only have one edge of weight 2. I also wasn't sure about the behavior of
directed graphs, so I removed the call to SetAllReverseEdges.   Here is the
code:
#include <iostream>

#include "itkGraph.h"
#include "itkBoykovGraphTraits.h"
#include "itkBoykovMinCutGraphFilter.h"

int main( int argc, char * argv[] )
{
    typedef itk::BoykovGraphTraits<short, 3> GraphTraitsType;

    typedef itk::Graph<GraphTraitsType>           GraphType;
    GraphType::Pointer graph = GraphType::New();

    typedef GraphType::NodePointerType      NodePointerType;
    typedef GraphType::EdgePointerType      EdgePointerType;

      // Create graph nodes
    NodePointerType Nodes[2];

    for( unsigned int i = 0; i < 2; i++ )
    {
        graph->CreateNewNode( 2 );
    }

    //get pointers to the newly created nodes
    for( unsigned int i = 0; i < 2; i++ )
    {
        Nodes[i] = graph->GetNodePointer( i );
    }

     //create three edges between nodes 0 and 1, each with weight 2
    graph->CreateNewEdge( Nodes[0], Nodes[1], 2 );
    //graph->CreateNewEdge( Nodes[0], Nodes[1], 2 );
    //graph->CreateNewEdge( Nodes[0], Nodes[1], 2 );

    // Set the reverse edges
    //graph->SetAllReverseEdges();

    //perform the cut
    typedef itk::BoykovMinCutGraphFilter  <GraphType> FilterType;
    FilterType::Pointer filter = FilterType::New();
    filter->SetInput(graph);
    filter->Update();

    //see which nodes are sinks
    typedef GraphType::NodeIterator         NodeIteratorType;
    typedef GraphType::NodeIdentifierType   NodeIdentifierType;
    NodeIteratorType nit( graph );
    for( nit.GoToBegin(); !nit.IsAtEnd(); ++nit )
    {
        NodePointerType node = nit.GetPointer();
        NodeIdentifierType Id = graph->GetNodeIdentifier( node );
        node = graph->GetNodePointer( Id );
        bool IsSink = node->IsSink;

        if(IsSink)
        {
            std::cout << "Node Id: " << Id << " is in group 1." <<
std::endl;
        }
        else
        {
            std::cout << "Node Id: " << Id << " is in group 0." <<
std::endl;
        }
    }

    //get the cut weight (min cut = max flow)
    typedef GraphType::NodeWeightType       NodeWeightType;
    NodeWeightType maxflow = filter->GetMaxFlow();
    std::cout << "Max Flow: " << maxflow << std::endl;

    return EXIT_SUCCESS;

}

The output is:
Node Id: 0 is in group 0.
Node Id: 1 is in group 0.
Max Flow: 0

The expected output is: (group 1 and 0 could possibly be switched)
Node Id: 0 is in group 0.
Node Id: 1 is in group 1.
Max Flow: 2

Any more suggestions?

Thanks,

David
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20090902/a5a3cc92/attachment.htm>