<div class="gmail_quote">On Tue, Sep 1, 2009 at 11:50 PM, Nicholas Tustison <span dir="ltr"><<a href="mailto:ntustison@gmail.com">ntustison@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div style="word-wrap: break-word;">Hi David,<div><br></div><div>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().</div>
<div><br></div><div>Nick </div><div></div></div></blockquote><div><br>Nick,<br><br>Thanks for the help so far - however, it doesn't seem to be working as expected.<br><br>IsSink is returning false for both nodes.<br>
GetMaxFlow() is returning 0.<br><br>I added this:<br> this->m_MaxFlow += bottleneck;<br>std::cout << "added " << bottleneck << " to maxflow." << std::endl;<br><br>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:<br>
#include <iostream><br><br>#include "itkGraph.h"<br>#include "itkBoykovGraphTraits.h"<br>#include "itkBoykovMinCutGraphFilter.h"<br><br>int main( int argc, char * argv[] )<br>{<br> typedef itk::BoykovGraphTraits<short, 3> GraphTraitsType;<br>
<br> typedef itk::Graph<GraphTraitsType> GraphType;<br> GraphType::Pointer graph = GraphType::New();<br><br> typedef GraphType::NodePointerType NodePointerType;<br> typedef GraphType::EdgePointerType EdgePointerType;<br>
<br> // Create graph nodes<br> NodePointerType Nodes[2];<br> <br> for( unsigned int i = 0; i < 2; i++ )<br> {<br> graph->CreateNewNode( 2 );<br> }<br> <br> //get pointers to the newly created nodes<br>
for( unsigned int i = 0; i < 2; i++ )<br> {<br> Nodes[i] = graph->GetNodePointer( i );<br> }<br><br> //create three edges between nodes 0 and 1, each with weight 2<br> graph->CreateNewEdge( Nodes[0], Nodes[1], 2 );<br>
//graph->CreateNewEdge( Nodes[0], Nodes[1], 2 );<br> //graph->CreateNewEdge( Nodes[0], Nodes[1], 2 );<br><br> // Set the reverse edges<br> //graph->SetAllReverseEdges();<br><br> //perform the cut<br>
typedef itk::BoykovMinCutGraphFilter <GraphType> FilterType;<br> FilterType::Pointer filter = FilterType::New();<br> filter->SetInput(graph);<br> filter->Update();<br><br> //see which nodes are sinks<br>
typedef GraphType::NodeIterator NodeIteratorType;<br> typedef GraphType::NodeIdentifierType NodeIdentifierType;<br> NodeIteratorType nit( graph );<br> for( nit.GoToBegin(); !nit.IsAtEnd(); ++nit )<br>
{<br> NodePointerType node = nit.GetPointer();<br> NodeIdentifierType Id = graph->GetNodeIdentifier( node );<br> node = graph->GetNodePointer( Id );<br> bool IsSink = node->IsSink;<br>
<br> if(IsSink)<br> {<br> std::cout << "Node Id: " << Id << " is in group 1." << std::endl;<br> }<br> else<br> {<br> std::cout << "Node Id: " << Id << " is in group 0." << std::endl;<br>
}<br> }<br> <br> //get the cut weight (min cut = max flow)<br> typedef GraphType::NodeWeightType NodeWeightType;<br> NodeWeightType maxflow = filter->GetMaxFlow();<br> std::cout << "Max Flow: " << maxflow << std::endl;<br>
<br> return EXIT_SUCCESS;<br> <br>}<br><br>The output is:<br>Node Id: 0 is in group 0.<br>Node Id: 1 is in group 0.<br>Max Flow: 0<br><br>The expected output is: (group 1 and 0 could possibly be switched)<br>Node Id: 0 is in group 0.<br>
Node Id: 1 is in group 1.<br>
Max Flow: 2<br>
<br>Any more suggestions?<br><br clear="all">Thanks,<br><br>David<br></div></div>