Medical Imaging Interaction Toolkit  2018.4.99-a3d2e8fb
Medical Imaging Interaction Toolkit
mitkTubeGraph.cpp
Go to the documentation of this file.
1 /*============================================================================
2 
3 The Medical Imaging Interaction Toolkit (MITK)
4 
5 Copyright (c) German Cancer Research Center (DKFZ)
6 All rights reserved.
7 
8 Use of this source code is governed by a 3-clause BSD license that can be
9 found in the LICENSE file.
10 
11 ============================================================================*/
12 
13 #include "mitkTubeGraph.h"
14 #include "mitkGeometry3D.h"
15 
17  std::pair<VertexDescriptorType, VertexDescriptorType>(boost::graph_traits<GraphType>::null_vertex(),
18  boost::graph_traits<GraphType>::null_vertex());
19 
21 {
22 }
23 
25 {
26 }
27 
29 {
30 }
31 
32 std::vector<mitk::TubeGraph::TubeDescriptorType> mitk::TubeGraph::SearchShortestPath(
33  const TubeDescriptorType &, const TubeDescriptorType &)
34 {
35  std::vector<TubeDescriptorType> shortestPath;
36  return shortestPath;
37 }
38 
39 std::vector<mitk::TubeGraph::TubeDescriptorType> mitk::TubeGraph::SearchAllPathBetweenVertices(
40  const mitk::TubeGraph::TubeDescriptorType &startTube,
41  const mitk::TubeGraph::TubeDescriptorType &endTube /*, std::vector<unsigned long> barrier*/)
42 { // http://lists.boost.org/boost-users/att-9001/maze.cpp
43  // http://www.boost.org/doc/libs/1_49_0/libs/graph/example/bfs.cpp
44 
45  typedef std::map<VertexDescriptorType, EdgeDescriptorType> EdgeMap;
46  typedef boost::associative_property_map<EdgeMap> PredecessorMap;
47  typedef boost::edge_predecessor_recorder<PredecessorMap, boost::on_tree_edge> PredecessorVisitor;
48  typedef boost::dfs_visitor<std::pair<PredecessorVisitor, boost::null_visitor>> DFSVisitor;
49 
50  EdgeMap edgesMap;
51  PredecessorMap predecessorMap(edgesMap);
52 
53  PredecessorVisitor predecessorVisitor(predecessorMap);
54  boost::null_visitor nullVisitor;
55  DFSVisitor visitor = boost::make_dfs_visitor(std::make_pair(predecessorVisitor, nullVisitor));
56 
57  std::map<VertexDescriptorType, boost::default_color_type> vertexColorMap;
58  std::map<EdgeDescriptorType, boost::default_color_type> edgeColorMap;
59 
60  boost::undirected_dfs(
61  m_Graph, visitor, make_assoc_property_map(vertexColorMap), make_assoc_property_map(edgeColorMap), startTube.second);
62 
63  std::vector<TubeDescriptorType> solutionPath;
64  solutionPath.push_back(endTube);
65  VertexDescriptorType pathEdgeSource = endTube.first;
66  VertexDescriptorType pathEdgeTarget;
67 
68  MITK_INFO << "Source: [" << startTube.first << "," << startTube.second << "] Target: [" << endTube.first << ","
69  << endTube.second << "]";
70  MITK_INFO << "tube [" << endTube.first << "," << endTube.second << "]";
71  do
72  {
73  if (pathEdgeSource == 10393696)
74  break;
75  EdgeDescriptorType edge = get(predecessorMap, pathEdgeSource);
76  pathEdgeSource = boost::source(edge, m_Graph);
77  pathEdgeTarget = boost::target(edge, m_Graph);
78  TubeDescriptorType tube(pathEdgeSource, pathEdgeTarget);
79  MITK_INFO << "tube [" << tube.first << "," << tube.second << "]";
80  solutionPath.push_back(tube);
81  } while (pathEdgeSource != startTube.second);
82 
83  return solutionPath;
84 }
85 
86 std::vector<mitk::TubeGraph::TubeDescriptorType> mitk::TubeGraph::SearchPathToPeriphery(
87  const mitk::TubeGraph::TubeDescriptorType &startTube /*, std::vector<unsigned long> barrier*/)
88 {
89  std::vector<mitk::TubeGraph::TubeDescriptorType> pathToPeriphery;
90 
91  if (m_RootTube == ErrorId)
92  {
93  m_RootTube = this->GetThickestTube();
94  if (m_Root == m_RootTube.first)
95  m_Root = m_RootTube.second;
96  else
97  m_Root = m_RootTube.first;
98  }
99 
100  // Attention!! No check which one is the right one
101  DirectedGraphType directedGraph = this->GetDirectedGraph(m_Root);
102 
103  // Only the target vertex: it's a directed Graph, and we want only the "after tube" tubes and the clicked ones
104  // this->GetOutEdgesOfAVertex(startTube.first, directedGraph, pathToPeriphery);
105  pathToPeriphery.push_back(startTube);
106  this->GetOutEdgesOfAVertex(startTube.second, directedGraph, pathToPeriphery);
107 
108  return pathToPeriphery;
109 }
110 
111 void mitk::TubeGraph::GetOutEdgesOfAVertex(mitk::TubeGraph::VertexDescriptorType vertex,
112  mitk::TubeGraph::DirectedGraphType &directedGraph,
113  std::vector<mitk::TubeGraph::TubeDescriptorType> &pathToPeriphery)
114 {
115  typedef boost::graph_traits<DirectedGraphType>::out_edge_iterator OutEdgeIteratorType;
116  std::pair<OutEdgeIteratorType, OutEdgeIteratorType> outEdges = boost::out_edges(vertex, directedGraph);
117  for (; outEdges.first != outEdges.second; ++outEdges.first)
118  {
119  TubeDescriptorType tube;
120  tube.first = boost::source(*outEdges.first, directedGraph);
121  tube.second = boost::target(*outEdges.first, directedGraph);
122 
123  if (std::find(pathToPeriphery.begin(), pathToPeriphery.end(), tube) == pathToPeriphery.end())
124  {
125  pathToPeriphery.push_back(tube);
126  this->GetOutEdgesOfAVertex(tube.second, directedGraph, pathToPeriphery);
127  }
128  }
129 }
130 
132 {
133  TubeDescriptorType thickestTube;
134  float tubeDiameter = 0.0;
135 
136  EdgeIteratorType iterator, end;
137 
138  boost::tie(iterator, end) = boost::edges(m_Graph);
139 
140  for (; iterator != end; ++iterator)
141  {
142  TubeGraphEdge edge = this->GetEdge(*iterator);
143 
144  std::pair<TubeGraphVertex, TubeGraphVertex> soureTargetPair = this->GetVerticesOfAnEdge(*iterator);
145 
146  float tempDiameter = edge.GetEdgeAverageDiameter(soureTargetPair.first, soureTargetPair.second);
147  if (tempDiameter > tubeDiameter)
148  {
149  tubeDiameter = tempDiameter;
150  thickestTube.first = this->GetVertexDescriptor(soureTargetPair.first);
151  thickestTube.second = this->GetVertexDescriptor(soureTargetPair.second);
152  }
153  }
154  return thickestTube;
155 }
156 
158 {
159  DirectedGraphType directedGraph(boost::num_vertices(m_Graph));
160  DirectedGraphBfsVisitor vis(this, directedGraph);
161  boost::breadth_first_search(m_Graph, startVertex, visitor(vis));
162  return directedGraph;
163 }
164 
165 mitk::TubeGraph::Pointer mitk::TubeGraph::CreateSubGraph(std::vector<TubeDescriptorType> subGraphTubes)
166 {
167  TubeGraph::Pointer subGraph = new TubeGraph();
168  // store the descriptor from origin graph to the correspondent new descriptors
169  std::map<VertexDescriptorType, VertexDescriptorType> vertexDescriptorOldToNewMap;
170 
171  // add a new edge and if necessary also the vertices of each tube to the new sub graph
172  for (auto it = subGraphTubes.begin(); it != subGraphTubes.end(); it++)
173  {
174  // search for the source vertex in the subgraph; if it is already added continue, otherwise add it
175  if (vertexDescriptorOldToNewMap.find(it->first) == vertexDescriptorOldToNewMap.end())
176  {
177  // add the vertex to the subgraph
178  VertexDescriptorType newVertexDescriptor = subGraph->AddVertex(this->GetVertex(it->first));
179  // add the pair of descriptor from the origin graph to the descriptor from the subgraph
180  vertexDescriptorOldToNewMap.insert(
181  std::pair<VertexDescriptorType, VertexDescriptorType>(it->first, newVertexDescriptor));
182  }
183  // and now...search for the target vertex...
184  if (vertexDescriptorOldToNewMap.find(it->second) == vertexDescriptorOldToNewMap.end())
185  {
186  VertexDescriptorType newVertexDescriptor = subGraph->AddVertex(this->GetVertex(it->second));
187  vertexDescriptorOldToNewMap.insert(
188  std::pair<VertexDescriptorType, VertexDescriptorType>(it->second, newVertexDescriptor));
189  }
190  // Get the EdgeDescriptor from origin graph
191  EdgeDescriptorType edgeDescriptor = this->GetEdgeDescriptorByVerices(it->first, it->second);
192 
193  TubeGraphEdge oldEdge = this->GetEdge(edgeDescriptor);
194 
195  // AddEdge needs the source vertex, the target vertex and the edge data
196  // source Vertex: get the subgraph VertexDescriptor by the origin descriptor (tubeDescriptor->first)from the
197  // assigning map
198  // target Vertex: get the subgraph VertexDescriptor by the origin descriptor (tubeDescriptor->second)from the
199  // assigning map
200  // edge data: copy the TubeGraphEdge object using the origin edge desciptor and the origin graph
201  VertexDescriptorType sourceVertex = vertexDescriptorOldToNewMap[it->first];
202  VertexDescriptorType targetVertex = vertexDescriptorOldToNewMap[it->second];
203  subGraph->AddEdge(sourceVertex, targetVertex, this->GetEdge(edgeDescriptor));
204  }
205  subGraph->CopyInformation(this);
206 
208  geometry->Initialize();
209  subGraph->SetGeometry(geometry);
210 
211  this->Modified();
212 
213  return subGraph;
214 }
215 
216 void mitk::TubeGraph::RemoveSubGraph(std::vector<TubeDescriptorType> deletedTubes)
217 {
218  for (auto it = deletedTubes.begin(); it != deletedTubes.end(); it++)
219  {
220  VertexDescriptorType source = it->first;
221  VertexDescriptorType target = it->second;
222 
223  EdgeDescriptorType edge = this->GetEdgeDescriptorByVerices(source, target);
224  this->RemoveEdge(edge);
225 
226  if (this->GetAllEdgesOfAVertex(source).size() == 0)
227  {
228  this->RemoveVertex(source);
229  }
230  if (this->GetAllEdgesOfAVertex(target).size() == 0)
231  {
232  this->RemoveVertex(target);
233  }
234  }
235  this->Modified();
236 }
237 
239 {
240  if (root != TubeGraph::ErrorId)
241  {
242  m_RootTube = root;
243  if (m_Root == root.first)
244  m_Root = root.second;
245  else
246  m_Root = root.first;
247  this->Modified();
248  }
249 }
250 
252 {
253  if (root != TubeGraph::ErrorId.first)
254  {
255  m_Root = root;
256  }
257 }
258 
260 {
261  return m_RootTube;
262 }
263 
265 {
266  return m_Root;
267 }
268 
270 {
272  return *this;
273 }
boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS > DirectedGraphType
Definition: mitkTubeGraph.h:55
EdgeDescriptorType GetEdgeDescriptorByVerices(const VertexDescriptorType &vertexA, const VertexDescriptorType &vertexB) const
~TubeGraph() override
static const TubeDescriptorType ErrorId
Definition: mitkTubeGraph.h:61
#define MITK_INFO
Definition: mitkLogMacros.h:18
void RemoveSubGraph(std::vector< TubeDescriptorType > deletedTubes)
void RemoveVertex(const VertexDescriptorType &vertex)
Base Class for Tube Graphs.
Definition: mitkTubeGraph.h:43
Base Class for Tube Graph Vertices.
VertexDescriptorType GetVertexDescriptor(const VertexType &vertexData) const
static Pointer New()
VertexType GetVertex(const VertexDescriptorType &vertex)
void SetRoot(const VertexDescriptorType &root)
std::vector< TubeDescriptorType > SearchAllPathBetweenVertices(const TubeDescriptorType &startTube, const TubeDescriptorType &endTube)
std::vector< EdgeType > GetAllEdgesOfAVertex(const VertexDescriptorType &vertex) const
float GetEdgeAverageDiameter(TubeGraphVertex &source, TubeGraphVertex &target)
std::vector< TubeDescriptorType > SearchPathToPeriphery(const TubeDescriptorType &startTube)
void RemoveEdge(const EdgeDescriptorType &edge)
boost::graph_traits< GraphType >::edge_descriptor EdgeDescriptorType
std::pair< VertexDescriptorType, VertexDescriptorType > TubeDescriptorType
Definition: mitkTubeGraph.h:49
TubeGraph::Pointer CreateSubGraph(std::vector< TubeDescriptorType > subGraphTubes)
EdgeType GetEdge(const EdgeDescriptorType &edge)
TubeDescriptorType GetThickestTube()
boost::graph_traits< GraphType >::edge_iterator EdgeIteratorType
boost::graph_traits< GraphType >::out_edge_iterator OutEdgeIteratorType
TubeDescriptorType GetRootTube()
Base Class for Tube Graph Edges.
std::pair< VertexType, VertexType > GetVerticesOfAnEdge(const EdgeDescriptorType &edge) const
DirectedGraphType GetDirectedGraph(VertexDescriptorType startVertex)
Template class for undirected graphs.Paramters should be the vertex and edge classes, which contains the information.
boost::graph_traits< GraphType >::vertex_descriptor VertexDescriptorType
UndirectedGraph< VertexType, EdgeType > & operator=(const UndirectedGraph< VertexType, EdgeType > &rhs)
std::vector< TubeDescriptorType > SearchShortestPath(const TubeDescriptorType &startTube, const TubeDescriptorType &endTube)
void SetRootTube(const TubeDescriptorType &root)
VertexDescriptorType GetRootVertex()
TubeGraph & operator=(const TubeGraph &rhs)