[vtkusers] How to calculate the number of cycles|DFS-back-edges in a vtkUndirectedGraph?
Dr. Roman Grothausmann
grothausmann.roman at mh-hannover.de
Tue Apr 22 11:43:19 EDT 2014
Dear mailing list members,
I'm trying to calculate the number of loops/cycles in a graph. According to
wikipedia
(http://en.wikipedia.org/wiki/Cycle_%28graph_theory%29#Cycle_detection) the
back-edges DFS finds corresponds to the number of cycles in an undirected graph.
From the docs I'm not sure if vtkTreeDFSIterator allows to calculate the
back-edges since it demands a vtkTree in the tests (not just a vtkGrpah as it
says in the docs)
Therefore I went for boost::depth_first_search
(http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/depth_first_search.html)
which ought to take a directed graph (but seems to work even on undirected
graphs:
http://stackoverflow.com/questions/14126/how-to-create-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-search).
The test program I constructed is below.
Using
boost::undirected_dfs(graph, boost::visitor(vis));
//http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/undirected_dfs.html
result in lots of errors.
However using
boost::depth_first_search(graph, boost::visitor(vis));
the program reports as many back-edges as there are edges in the input (a test
input is attached, which I would expect to yield a result of 3 back-edges/cycles).
Does anybody know what is going wrong here?
Or how to calculate the number of loops/cycles in a vtkUndirectedGraph?
Any help or hints are very much appreciated
Roman
__________________________________________________________________
///////program to count back edges when running boost::undirected_dfs on a
vtkUndirectedGraph
////http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/depth_first_search.html
////http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/undirected_dfs.html
#include <vtkSmartPointer.h>
//for ProgressFunction(
#include <vtkCallbackCommand.h>
#include <vtkCommand.h>
#include <vtkXMLPolyDataReader.h>
#include <vtkPolyDataToGraph.h>
#include <vtkBoostGraphAdapter.h>
#include <vtkUndirectedGraph.h>
#include <boost/graph/visitors.hpp>
#include <boost/graph/undirected_dfs.hpp>
//#include <boost/graph/depth_first_search.hpp>
#define P_VERBOSE 1
#define VTK_CREATE(type, name) vtkSmartPointer<type> name =
vtkSmartPointer<type>::New()
// //// http://www.boost.org/doc/libs/1_55_0/libs/graph/example/undirected_dfs.cpp
// struct detect_loops : public boost::dfs_visitor<>{
// template <class Edge, class Graph>
// void back_edge(Edge e, const Graph& g) {
// nbe++;
// std::cout << nbe << ": " << source(e, g) << " -- " << target(e, g) << "\n";
// }
// int nbe= 0;
// };
////
http://stackoverflow.com/questions/14126/how-to-create-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-search
/// and e.g. VTK-6.1.0/Infovis/BoostGraphAlgorithms/vtkBoostBreadthFirstSearch.cxx
class MyVisitor : public boost::default_dfs_visitor{
//class MyVisitor : public boost::dfs_visitor{
public:
MyVisitor(vtkIdType& NBE) : m_nbe(NBE){
}
template <typename Edge, typename Graph>
void back_edge(Edge e, const Graph& g){
//typename graph_traits<Graph>::vertex_descriptor u = source(e, g), v =
target(e, g);
m_nbe++;
std::cout << m_nbe << ": " << source(e, g) << " -- " << target(e, g) << "\n";
}
private:
vtkIdType & m_nbe;
};
void ProgressFunction( vtkObject* caller, long unsigned int eventId, void*
clientData, void* callData ){
vtkAlgorithm *d= static_cast<vtkAlgorithm*>(caller);
if(P_VERBOSE) fprintf(stderr, "\rFilter progress: %5.1f%%", 100.0 *
d->GetProgress());
if(P_VERBOSE) std::cerr.flush();
}
int main(int argc, char* argv[]){
if( argc != 3 ) {
std::cerr << "Usage: " << argv[0];
std::cerr << " inputGraph";
std::cerr << " rootVertex";
std::cerr << std::endl;
return EXIT_FAILURE;
}
if(!(strcasestr(argv[1],".vtp"))) {
std::cout << "The input should end with .vtp" << std::endl;
return -1;
}
VTK_CREATE(vtkCallbackCommand, progressCallback);
progressCallback->SetCallback(ProgressFunction);
vtkSmartPointer<vtkXMLPolyDataReader> reader =
vtkSmartPointer<vtkXMLPolyDataReader>::New();
reader->SetFileName(argv[1]);
reader->Update();
VTK_CREATE(vtkPolyDataToGraph, polyDataToGraphFilter);
polyDataToGraphFilter->SetInputConnection(reader->GetOutputPort());
if(P_VERBOSE) std::cout << "Executing vtkPolyDataToGraph..." << std::endl;
polyDataToGraphFilter->AddObserver(vtkCommand::ProgressEvent, progressCallback);
polyDataToGraphFilter->Update();
if(P_VERBOSE) std::cout << std::endl << "done." << std::endl;
//// vtkSmartPointer does not work in this case!!! Why?
//vtkSmartPointer<vtkUndirectedGraph> graph=
vtkUndirectedGraph::SafeDownCast(polyDataToGraphFilter->GetOutput());
vtkUndirectedGraph *graph =
vtkUndirectedGraph::SafeDownCast(polyDataToGraphFilter->GetOutput());
//graph->CheckedShallowCopy(polyDataToGraphFilter->GetOutput());
vtkIdType root= atoi(argv[2]);
vtkIdType nbe= -1;
MyVisitor vis(nbe);
boost::depth_first_search(graph, boost::visitor(vis));
//boost::undirected_dfs(graph, root_vertex(root).visitor(vis));
//boost::undirected_dfs(graph, boost::visitor(vis));
std::cout << nbe << " Back-Edges found in the undirected graph" << std::endl;
return EXIT_SUCCESS;
}
--
Dr. Roman Grothausmann
Tomographie und Digitale Bildverarbeitung
Tomography and Digital Image Analysis
Institut für Funktionelle und Angewandte Anatomie, OE 4120
Medizinische Hochschule Hannover
Carl-Neuberg-Str. 1
D-30625 Hannover
Tel. +49 511 532-9574
-------------- next part --------------
<VTKFile type="PolyData" version="0.1" byte_order="LittleEndian">
<PolyData>
<Piece NumberOfPoints="96" NumberOfVerts="0" NumberOfLines="98" NumberOfStrips="0" NumberOfPolys="0">
<PointData>
</PointData>
<CellData>
</CellData>
<Points>
<DataArray type="Float32" Name="Points" NumberOfComponents="3" format="binary" RangeMin="1191.7218635" RangeMax="1204.8767572">
gAQAAACAWkQAAPlDAMAfRADAWkQAAPlDAAAgRABAWkQAgPlDAAAgRAAAW0QAgPhDAEAgRABAWkQAAPpDAEAgRABAW0QAAPhDAIAgRAAAWkQAgPpDAIAgRACAW0QAgPdDAMAgRADAWUQAgPpDAMAgRACAW0QAAPdDAMAgRADAWUQAAPtDAAAhRACAW0QAgPZDAMAgRADAWUQAAPtDAEAhRACAW0QAgPVDAMAgRACAW0QAAPZDAMAgRACAW0QAAPVDAAAhRACAW0QAgPRDAAAhRACAW0QAAPRDAEAhRADAWUQAgPtDAIAhRABAW0QAgPNDAIAhRABAW0QAAPNDAMAhRACAWUQAAPxDAMAhRABAW0QAAPNDAAAiRACAWUQAgPxDAAAiRABAW0QAAPNDAEAiRACAWUQAAP1DAEAiRABAW0QAgPJDAIAiRADAWUQAAP1DAIAiRABAW0QAgPJDAMAiRADAWUQAAP1DAMAiRABAW0QAgPJDAAAjRAAAWkQAgP1DAAAjRABAW0QAAPJDAEAjRABAWkQAAP1DAEAjRAAAWkQAAP5DAEAjRABAW0QAAPJDAIAjRABAWkQAAP1DAIAjRACAW0QAgPFDAMAjRACAWkQAgPxDAMAjRACAW0QAgPFDAAAkRACAW0QAAPJDAAAkRADAWkQAgPxDAAAkRACAW0QAAPFDAEAkRABAW0QAgPJDAAAkRAAAW0QAAPxDAAAkRADAW0QAgPBDAIAkRABAW0QAAPNDAEAkRAAAW0QAgPtDAAAkRADAW0QAAPBDAIAkRABAW0QAgPNDAEAkRAAAW0QAAPRDAIAkRAAAW0QAgPpDAAAkRAAAW0QAAPtDAAAkRAAAW0QAAPpDAEAkRADAWkQAgPlDAEAkRADAWkQAAPlDAEAkRACAW0QAgO9DAIAkRADAWkQAgPRDAMAkRADAWkQAAPVDAMAkRADAWkQAgPhDAIAkRACAWkQAAPhDAIAkRABAWkQAgPdDAMAkRAAAW0QAgO5DAIAkRABAW0QAAO9DAIAkRADAWkQAAO5DAMAkRACAWkQAAO5DAAAlRABAWkQAAO5DAEAlRADAWkQAgPVDAMAkRAAAWkQAAPdDAAAlRABAWkQAgPZDAEAlRABAWkQAAO5DAIAlRACAWkQAAPZDAAAlRAAAWkQAgPZDAIAlRABAWkQAAO5DAMAlRADAWUQAgPZDAMAlRABAWkQAAO5DAAAmRADAWUQAgPZDAAAmRAAAWkQAAO5DAEAmRACAWUQAgPZDAEAmRAAAWkQAAO5DAIAmRACAWUQAAPZDAIAmRAAAWkQAgO5DAMAmRACAWUQAgPVDAIAmRAAAWkQAAO9DAMAmRACAWUQAAPVDAMAmRAAAWkQAgO9DAMAmRADAWUQAgPRDAAAnRADAWUQAAPRDAAAnRAAAWkQAAPBDAMAmRAAAWkQAgPBDAMAmRAAAWkQAAPFDAMAmRAAAWkQAgPFDAMAmRAAAWkQAAPJDAAAnRAAAWkQAgPJDAEAnRABAWkQAAPNDAIAnRAAAWkQAgPNDAEAnRA==
</DataArray>
</Points>
<Verts>
<DataArray type="Int64" Name="connectivity" format="binary" RangeMin="1e+299" RangeMax="-1e+299">
AAAAAA==
</DataArray>
<DataArray type="Int64" Name="offsets" format="binary" RangeMin="1e+299" RangeMax="-1e+299">
AAAAAA==
</DataArray>
</Verts>
<Lines>
<DataArray type="Int64" Name="connectivity" format="binary" RangeMin="0" RangeMax="95">
IAYAAAAAAAAAAAAAAQAAAAAAAAAAAAAAAAAAAAIAAAAAAAAAAQAAAAAAAAADAAAAAAAAAAIAAAAAAAAABAAAAAAAAAADAAAAAAAAAAUAAAAAAAAABAAAAAAAAAAGAAAAAAAAAAUAAAAAAAAABwAAAAAAAAAGAAAAAAAAAAgAAAAAAAAABwAAAAAAAAAJAAAAAAAAAAgAAAAAAAAACgAAAAAAAAAJAAAAAAAAAAsAAAAAAAAACgAAAAAAAAAMAAAAAAAAAAsAAAAAAAAADgAAAAAAAAAMAAAAAAAAABIAAAAAAAAADQAAAAAAAAAOAAAAAAAAAA0AAAAAAAAADwAAAAAAAAAPAAAAAAAAABAAAAAAAAAAEAAAAAAAAAARAAAAAAAAABEAAAAAAAAAEwAAAAAAAAASAAAAAAAAABUAAAAAAAAAEwAAAAAAAAAUAAAAAAAAABQAAAAAAAAAFgAAAAAAAAAVAAAAAAAAABcAAAAAAAAAFgAAAAAAAAAYAAAAAAAAABcAAAAAAAAAGQAAAAAAAAAYAAAAAAAAABoAAAAAAAAAGQAAAAAAAAAbAAAAAAAAABoAAAAAAAAAHAAAAAAAAAAbAAAAAAAAAB0AAAAAAAAAHAAAAAAAAAAeAAAAAAAAAB0AAAAAAAAAHwAAAAAAAAAeAAAAAAAAACAAAAAAAAAAHwAAAAAAAAAhAAAAAAAAAB8AAAAAAAAAIgAAAAAAAAAgAAAAAAAAACMAAAAAAAAAIQAAAAAAAAAkAAAAAAAAACMAAAAAAAAAJQAAAAAAAAAkAAAAAAAAACYAAAAAAAAAJQAAAAAAAAAnAAAAAAAAACUAAAAAAAAAKAAAAAAAAAAmAAAAAAAAACkAAAAAAAAAJwAAAAAAAAAoAAAAAAAAACcAAAAAAAAAKgAAAAAAAAAoAAAAAAAAACsAAAAAAAAAKQAAAAAAAAAsAAAAAAAAACoAAAAAAAAALQAAAAAAAAArAAAAAAAAAC4AAAAAAAAALAAAAAAAAAAvAAAAAAAAAC0AAAAAAAAAMAAAAAAAAAAuAAAAAAAAADEAAAAAAAAALwAAAAAAAAA0AAAAAAAAADAAAAAAAAAAOAAAAAAAAAAxAAAAAAAAADIAAAAAAAAAMgAAAAAAAAA5AAAAAAAAADMAAAAAAAAANAAAAAAAAAAzAAAAAAAAADUAAAAAAAAANQAAAAAAAAA2AAAAAAAAADYAAAAAAAAANwAAAAAAAAA3AAAAAAAAADsAAAAAAAAAOAAAAAAAAAA/AAAAAAAAADkAAAAAAAAAOgAAAAAAAAA6AAAAAAAAAEMAAAAAAAAAOwAAAAAAAAA8AAAAAAAAADwAAAAAAAAAPQAAAAAAAAA9AAAAAAAAAEQAAAAAAAAAPgAAAAAAAAA/AAAAAAAAAD4AAAAAAAAAQAAAAAAAAABAAAAAAAAAAEEAAAAAAAAAQQAAAAAAAABCAAAAAAAAAEIAAAAAAAAARgAAAAAAAABDAAAAAAAAAEcAAAAAAAAARAAAAAAAAABFAAAAAAAAAEUAAAAAAAAARwAAAAAAAABFAAAAAAAAAEgAAAAAAAAARgAAAAAAAABJAAAAAAAAAEgAAAAAAAAASgAAAAAAAABJAAAAAAAAAEsAAAAAAAAASgAAAAAAAABMAAAAAAAAAEsAAAAAAAAATQAAAAAAAABMAAAAAAAAAE4AAAAAAAAATQAAAAAAAABPAAAAAAAAAE4AAAAAAAAAUAAAAAAAAABPAAAAAAAAAFEAAAAAAAAAUAAAAAAAAABSAAAAAAAAAFEAAAAAAAAAUwAAAAAAAABSAAAAAAAAAFQAAAAAAAAAUwAAAAAAAABVAAAAAAAAAFQAAAAAAAAAVgAAAAAAAABVAAAAAAAAAFgAAAAAAAAAVgAAAAAAAABXAAAAAAAAAFcAAAAAAAAAXwAAAAAAAABYAAAAAAAAAFkAAAAAAAAAWQAAAAAAAABaAAAAAAAAAFoAAAAAAAAAWwAAAAAAAABbAAAAAAAAAFwAAAAAAAAAXAAAAAAAAABdAAAAAAAAAF0AAAAAAAAAXgAAAAAAAABeAAAAAAAAAF8AAAAAAAAA
</DataArray>
<DataArray type="Int64" Name="offsets" format="binary" RangeMin="2" RangeMax="196">
EAMAAAIAAAAAAAAABAAAAAAAAAAGAAAAAAAAAAgAAAAAAAAACgAAAAAAAAAMAAAAAAAAAA4AAAAAAAAAEAAAAAAAAAASAAAAAAAAABQAAAAAAAAAFgAAAAAAAAAYAAAAAAAAABoAAAAAAAAAHAAAAAAAAAAeAAAAAAAAACAAAAAAAAAAIgAAAAAAAAAkAAAAAAAAACYAAAAAAAAAKAAAAAAAAAAqAAAAAAAAACwAAAAAAAAALgAAAAAAAAAwAAAAAAAAADIAAAAAAAAANAAAAAAAAAA2AAAAAAAAADgAAAAAAAAAOgAAAAAAAAA8AAAAAAAAAD4AAAAAAAAAQAAAAAAAAABCAAAAAAAAAEQAAAAAAAAARgAAAAAAAABIAAAAAAAAAEoAAAAAAAAATAAAAAAAAABOAAAAAAAAAFAAAAAAAAAAUgAAAAAAAABUAAAAAAAAAFYAAAAAAAAAWAAAAAAAAABaAAAAAAAAAFwAAAAAAAAAXgAAAAAAAABgAAAAAAAAAGIAAAAAAAAAZAAAAAAAAABmAAAAAAAAAGgAAAAAAAAAagAAAAAAAABsAAAAAAAAAG4AAAAAAAAAcAAAAAAAAAByAAAAAAAAAHQAAAAAAAAAdgAAAAAAAAB4AAAAAAAAAHoAAAAAAAAAfAAAAAAAAAB+AAAAAAAAAIAAAAAAAAAAggAAAAAAAACEAAAAAAAAAIYAAAAAAAAAiAAAAAAAAACKAAAAAAAAAIwAAAAAAAAAjgAAAAAAAACQAAAAAAAAAJIAAAAAAAAAlAAAAAAAAACWAAAAAAAAAJgAAAAAAAAAmgAAAAAAAACcAAAAAAAAAJ4AAAAAAAAAoAAAAAAAAACiAAAAAAAAAKQAAAAAAAAApgAAAAAAAACoAAAAAAAAAKoAAAAAAAAArAAAAAAAAACuAAAAAAAAALAAAAAAAAAAsgAAAAAAAAC0AAAAAAAAALYAAAAAAAAAuAAAAAAAAAC6AAAAAAAAALwAAAAAAAAAvgAAAAAAAADAAAAAAAAAAMIAAAAAAAAAxAAAAAAAAAA=
</DataArray>
</Lines>
<Strips>
<DataArray type="Int64" Name="connectivity" format="binary" RangeMin="0" RangeMax="95">
AAAAAA==
</DataArray>
<DataArray type="Int64" Name="offsets" format="binary" RangeMin="2" RangeMax="196">
AAAAAA==
</DataArray>
</Strips>
<Polys>
<DataArray type="Int64" Name="connectivity" format="binary" RangeMin="0" RangeMax="95">
AAAAAA==
</DataArray>
<DataArray type="Int64" Name="offsets" format="binary" RangeMin="2" RangeMax="196">
AAAAAA==
</DataArray>
</Polys>
</Piece>
</PolyData>
</VTKFile>
More information about the vtkusers
mailing list