20 #include <boost/graph/clustering_coefficient.hpp>
21 #include <boost/graph/betweenness_centrality.hpp>
25 : m_IsModified( false )
38 return boost::edge(vertexA, vertexB, m_Network ).second;
44 m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ].weight++;
46 SetIsModified(
true );
54 AddEdge(vertexA, vertexB, m_Network[ vertexA ].
id, m_Network[ vertexB ].
id );
60 int sourceID,
int targetID,
int weight,
double edge_weight )
62 boost::add_edge( vertexA, vertexB, m_Network );
63 m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ].sourceId = sourceID;
64 m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ].targetId = targetID;
65 m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ].weight = weight;
66 m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ].edge_weight = edge_weight;
68 SetIsModified(
true );
74 m_Network[vertex].id = id;
76 SetIsModified(
true );
84 m_Network[vertex].label = inLabel;
86 SetIsModified(
true );
92 m_Network[vertex].coordinates = inCoordinates;
94 SetIsModified(
true );
101 SetIsModified(
true );
128 std::vector< mitk::ConnectomicsNetwork::NetworkNode >
131 boost::graph_traits<NetworkType>::vertex_iterator iterator, end;
134 boost::tie(iterator, end) = boost::vertices( m_Network );
136 std::vector< NetworkNode > vectorOfNodes;
138 for ( ; iterator != end; ++iterator)
143 tempNode = m_Network[ *iterator ];
145 vectorOfNodes.push_back( tempNode );
148 return vectorOfNodes;
151 std::vector< mitk::ConnectomicsNetwork::VertexDescriptorType >
154 boost::graph_traits<NetworkType>::vertex_iterator iterator, end;
157 boost::tie(iterator, end) = boost::vertices( m_Network );
159 std::vector< VertexDescriptorType > vectorOfDescriptors;
161 for ( ; iterator != end; ++iterator)
163 vectorOfDescriptors.push_back( *iterator );
166 return vectorOfDescriptors;
169 std::vector< std::pair<
170 std::pair< mitk::ConnectomicsNetwork::NetworkNode, mitk::ConnectomicsNetwork::NetworkNode >
174 boost::graph_traits<NetworkType>::edge_iterator iterator, end;
177 boost::tie(iterator, end) = boost::edges( m_Network );
181 std::pair< NetworkNode, NetworkNode >
186 for ( ; iterator != end; ++iterator)
192 tempEdge = m_Network[ *iterator ];
193 sourceNode = m_Network[ boost::source( *iterator, m_Network ) ];
194 targetNode = m_Network[ boost::target( *iterator, m_Network ) ];
196 std::pair< NetworkNode, NetworkNode > nodePair( sourceNode, targetNode );
197 std::pair< std::pair< NetworkNode, NetworkNode > ,
NetworkEdge > edgePair( nodePair, tempEdge);
198 vectorOfEdges.push_back( edgePair );
201 return vectorOfEdges;
206 return boost::num_vertices( m_Network );
211 return boost::num_edges( m_Network );
218 boost::graph_traits<NetworkType>::edge_iterator iterator, end;
221 boost::tie(iterator, end) = boost::edges( m_Network );
223 for ( ; iterator != end; ++iterator)
228 tempWeight = m_Network[ *iterator ].weight;
230 if( tempWeight > maxWeight )
232 maxWeight = tempWeight;
241 int noOfSelfLoops( 0 );
243 std::vector< std::pair< std::pair< NetworkNode, NetworkNode > ,
NetworkEdge > >
244 edgeVector = GetVectorOfAllEdges();
246 for(
unsigned int index = 0; index < edgeVector.size() ; index++ )
248 double sourceX, sourceY, sourceZ, targetX, targetY, targetZ;
250 sourceX = edgeVector[ index ].first.first.coordinates[0] ;
251 sourceY = edgeVector[ index ].first.first.coordinates[1] ;
252 sourceZ = edgeVector[ index ].first.first.coordinates[2] ;
253 targetX = edgeVector[ index ].first.second.coordinates[0] ;
254 targetY = edgeVector[ index ].first.second.coordinates[1] ;
255 targetZ = edgeVector[ index ].first.second.coordinates[2] ;
259 sourceX > ( targetX - 0.01 ) &&
260 sourceX < ( targetX + 0.01 ) &&
261 sourceY > ( targetY - 0.01 ) &&
262 sourceY < ( targetY + 0.01 ) &&
263 sourceZ > ( targetZ - 0.01 ) &&
264 sourceZ < ( targetZ + 0.01 )
271 return noOfSelfLoops;
276 double vertices = (double) GetNumberOfVertices();
277 double edges = (double) GetNumberOfEdges();
279 return ( ( edges * 2.0 ) / vertices );
284 double vertices = (double) GetNumberOfVertices();
285 double edges = (double) GetNumberOfEdges();
286 double numberOfPossibleEdges = vertices * ( vertices - 1 ) / 2 ;
288 return ( edges / numberOfPossibleEdges );
293 std::vector< int > vectorOfDegree;
295 boost::graph_traits<NetworkType>::vertex_iterator iterator, end;
298 boost::tie( iterator, end ) = boost::vertices( m_Network );
300 vectorOfDegree.resize( this->GetNumberOfVertices() );
302 for ( ; iterator != end; ++iterator)
305 vectorOfDegree[ m_Network[ *iterator ].id ] = GetVectorOfAdjacentNodes( *iterator ).size();
307 return vectorOfDegree;
310 std::vector< mitk::ConnectomicsNetwork::VertexDescriptorType >
313 std::vector< mitk::ConnectomicsNetwork::VertexDescriptorType > vectorOfAdjacentNodes;
315 boost::graph_traits<NetworkType>::adjacency_iterator adjIter, adjEnd;
317 boost::tie( adjIter, adjEnd ) = boost::adjacent_vertices( vertex, m_Network);
319 for ( ; adjIter != adjEnd; ++adjIter)
321 vectorOfAdjacentNodes.push_back( *adjIter );
324 return vectorOfAdjacentNodes;
329 int maximumDegree( 0 );
331 std::vector< int > vectorOfDegree = GetDegreeOfNodes();
333 for(
unsigned int index( 0 ); index < vectorOfDegree.size(); ++index )
335 if( maximumDegree < vectorOfDegree[ index ] )
337 maximumDegree = vectorOfDegree[ index ];
341 return maximumDegree;
346 std::vector< double > vectorOfClusteringCoefficients;
348 typedef boost::graph_traits<NetworkType>::vertex_iterator vertexIter;
350 vectorOfClusteringCoefficients.resize( this->GetNumberOfVertices() );
352 std::pair<vertexIter, vertexIter> vertexPair;
355 int size = vectorOfClusteringCoefficients.size();
356 for (vertexPair = vertices(m_Network); vertexPair.first != vertexPair.second; ++vertexPair.first)
358 int index = m_Network[ *vertexPair.first ].id;
362 MITK_ERROR <<
"Trying to access out of bounds clustering coefficient";
366 vectorOfClusteringCoefficients[ index ] =
367 boost::clustering_coefficient(m_Network,*vertexPair.first) ;
370 return vectorOfClusteringCoefficients;
375 std::vector< double > vectorOfClusteringCoefficients = GetLocalClusteringCoefficients();
376 std::vector< int > vectorOfDegree = GetDegreeOfNodes();
378 std::vector< double > vectorOfClusteringCoefficientsByDegree;
379 vectorOfClusteringCoefficientsByDegree.resize( GetMaximumDegree() + 1, 0 );
385 for(
unsigned int degree( 0 ); degree < vectorOfClusteringCoefficientsByDegree.size(); ++degree )
387 vectorOfClusteringCoefficientsByDegree[ degree ] = 0;
389 for(
unsigned int index( 0 ); index < vectorOfDegree.size(); ++index )
391 if( degree == (
unsigned int)vectorOfDegree[ index ] )
393 vectorOfClusteringCoefficientsByDegree[ degree ] += vectorOfClusteringCoefficients[ index ];
399 vectorOfClusteringCoefficientsByDegree[ degree ] =
400 vectorOfClusteringCoefficientsByDegree[ degree ] / n_k;
404 return vectorOfClusteringCoefficientsByDegree;
409 double globalClusteringCoefficient( 0.0 );
411 std::vector< double > vectorOfClusteringCoefficientsByDegree = GetClusteringCoefficientsByDegree();
412 std::vector< int > vectorOfDegree = GetDegreeOfNodes();
413 std::vector< int > degreeDistribution;
414 degreeDistribution.resize( vectorOfClusteringCoefficientsByDegree.size(), 0 );
416 int normalizationParameter( 0 );
418 for(
unsigned int index( 0 ); index < vectorOfDegree.size(); ++index )
420 degreeDistribution[ vectorOfDegree[ index ] ]++;
421 normalizationParameter++;
426 for(
unsigned int degree( 0 ); degree < degreeDistribution.size(); ++degree )
428 globalClusteringCoefficient +=
429 degreeDistribution[ degree ] / ( (double) normalizationParameter)
430 * vectorOfClusteringCoefficientsByDegree[ degree ];
433 return globalClusteringCoefficient;
445 m_Network = *newGraph;
446 this->SetIsModified(
true );
451 typedef std::vector< std::pair< std::pair< NetworkNode, NetworkNode >,
NetworkEdge > > EdgeVectorType;
452 typedef std::vector< NetworkNode > VertexVectorType;
456 this->SetGeometry( source->GetGeometry());
457 VertexVectorType vertexVector = source->GetVectorOfAllNodes();
458 EdgeVectorType edgeVector = source->GetVectorOfAllEdges();
459 std::map< int, VertexDescriptorType > idToVertexMap;
461 for(
unsigned int loop(0); loop < vertexVector.size(); loop++ )
464 this->SetLabel( newVertex, vertexVector[ loop ].label );
465 this->SetCoordinates( newVertex, vertexVector[ loop ].coordinates );
467 if ( idToVertexMap.count( vertexVector[ loop ].id ) > 0 )
469 MITK_ERROR <<
"Aborting network import, duplicate vertex ID discovered.";
472 idToVertexMap.insert( std::pair< int, VertexDescriptorType >( vertexVector[ loop ].
id, newVertex) );
475 for(
unsigned int loop(0); loop < edgeVector.size(); loop++ )
480 this->AddEdge( source, target, edgeVector[ loop ].second.sourceId, edgeVector[ loop ].second.targetId, edgeVector[ loop ].second.weight);
483 this->SetIsModified(
true );
494 m_IsModified = value;
500 return m_Network[ vertex ];
506 if( EdgeExists(vertexA, vertexB) )
508 return m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ];
522 std::vector< mitk::ConnectomicsNetwork::NetworkNode > nodeVector = this->GetVectorOfAllNodes();
524 if( nodeVector.size() == 0 )
535 for(
auto & elem : nodeVector)
537 for(
unsigned int direction(0); direction < elem.coordinates.size(); direction++ )
539 if( elem.coordinates.at(direction) < bounds[ 2 * direction ] )
541 bounds[ 2 * direction ] = elem.coordinates.at(direction);
544 if( elem.coordinates.at(direction) > bounds[ 2 * direction + 1] )
546 bounds[ 2 * direction + 1] = elem.coordinates.at(direction);
553 for(
int i=0; i<=4; i+=2)
558 for(
int i=1; i<=5; i+=2)
563 this->GetGeometry()->SetFloatBounds(bounds);
564 this->GetTimeGeometry()->Update();
569 boost::graph_traits<NetworkType>::vertex_iterator iterator, end;
572 bool vertexHasBeenRemoved(
true );
575 while( vertexHasBeenRemoved )
577 vertexHasBeenRemoved =
false;
579 boost::tie(iterator, end) = boost::vertices( m_Network );
581 for ( ; iterator != end && !vertexHasBeenRemoved; ++iterator)
584 if( GetVectorOfAdjacentNodes( *iterator ).size() == 0 )
586 vertexHasBeenRemoved =
true;
588 boost::remove_vertex( *iterator, m_Network );
598 boost::graph_traits<NetworkType>::vertex_iterator v_i, v_end;
599 boost::graph_traits<NetworkType>::edge_iterator e_i, e_end;
602 boost::tie( v_i, v_end ) = boost::vertices( m_Network );
604 for ( ; v_i != v_end; ++v_i)
606 m_Network[*v_i].id = *v_i;
610 boost::tie(e_i, e_end) = boost::edges( m_Network );
612 for ( ; e_i != e_end; ++e_i)
614 m_Network[ *e_i ].sourceId = m_Network[ boost::source( *e_i, m_Network ) ].id;
615 m_Network[ *e_i ].targetId = m_Network[ boost::target( *e_i, m_Network ) ].id;
617 this->SetIsModified(
true );
622 std::vector< double > betweennessVector;
624 betweennessVector.clear();
625 betweennessVector.resize( this->GetNumberOfVertices() );
627 boost::brandes_betweenness_centrality(
629 boost::centrality_map(
630 boost::make_iterator_property_map( betweennessVector.begin(), boost::get( &NetworkNode::id, m_Network ), double() )
631 ).vertex_index_map( boost::get( &NetworkNode::id, m_Network ) )
634 return betweennessVector;
640 typedef std::map<EdgeDescriptorType, int> EdgeIndexStdMap;
641 EdgeIndexStdMap stdEdgeIndex;
643 typedef boost::associative_property_map< EdgeIndexStdMap > EdgeIndexMap;
644 EdgeIndexMap edgeIndex(stdEdgeIndex);
646 boost::graph_traits<NetworkType>::edge_iterator iterator, end;
649 boost::tie(iterator, end) = boost::edges( m_Network );
652 for ( ; iterator != end; ++iterator, ++i)
654 stdEdgeIndex.insert(std::pair< EdgeDescriptorType, int >( *iterator, i));
658 std::vector< double > edgeBetweennessVector(boost::num_edges( m_Network ), 0.0);
660 boost::iterator_property_map< std::vector< double >::iterator, EdgeIndexMap >
661 e_centrality_map(edgeBetweennessVector.begin(), edgeIndex);
664 typedef boost::property_map< NetworkType, boost::vertex_index_t>::type VertexIndexMap;
665 VertexIndexMap vertexIndex =
get(boost::vertex_index, m_Network );
666 std::vector< double > betweennessVector(boost::num_vertices( m_Network ), 0.0);
668 boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
669 v_centrality_map(betweennessVector.begin(), vertexIndex);
671 boost::brandes_betweenness_centrality( m_Network, v_centrality_map, e_centrality_map );
673 return edgeBetweennessVector;
678 std::vector< VertexDescriptorType > predecessorMap( boost::num_vertices( m_Network ) );
679 int numberOfNodes( boost::num_vertices( m_Network ) );
681 std::vector< double > distanceMatrix;
682 distanceMatrix.resize( numberOfNodes );
684 boost::graph_traits<NetworkType>::vertex_iterator iterator, end;
685 boost::tie(iterator, end) = boost::vertices( m_Network );
687 while( (iterator != end) && (m_Network[ *iterator ].label != targetLabel) )
692 if( iterator == end )
695 return distanceMatrix;
698 boost::dijkstra_shortest_paths(m_Network, *iterator, boost::predecessor_map(&predecessorMap[ 0 ]).distance_map(&distanceMatrix[ 0 ]).weight_map( boost::get( &NetworkEdge::edge_weight ,m_Network ) ) ) ;
700 return distanceMatrix;
705 boost::graph_traits<NetworkType>::vertex_iterator iterator, end;
706 boost::tie(iterator, end) = boost::vertices( m_Network );
708 while( (iterator != end) && (m_Network[ *iterator ].label != targetLabel) )
713 if( iterator == end )
723 bool noDifferenceFound =
true;
725 if( rightHandSide ==
nullptr )
729 MITK_INFO <<
"[Equal( ConnectomicsNetwork*, ConnectomicsNetwork* )] rightHandSide NULL.";
734 if( leftHandSide ==
nullptr )
738 MITK_INFO <<
"[Equal( ConnectomicsNetwork*, ConnectomicsNetwork* )] leftHandSide NULL.";
746 calculatorLeft->SetNetwork( leftHandSide );
747 calculatorRight->SetNetwork( rightHandSide );
748 calculatorLeft->Update();
749 calculatorRight->Update();
751 if( !
mitk::Equal( calculatorLeft->GetNumberOfVertices(), calculatorRight->GetNumberOfVertices(),
eps ) )
754 MITK_INFO <<
"[Equal( ConnectomicsNetwork*, ConnectomicsNetwork* )] Number of vertices not equal. " << calculatorLeft->GetNumberOfVertices() <<
" vs " << calculatorRight->GetNumberOfVertices();
755 noDifferenceFound =
false;
758 if( !
mitk::Equal( calculatorLeft->GetNumberOfEdges(), calculatorRight->GetNumberOfEdges(),
eps ) )
761 MITK_INFO <<
"[Equal( ConnectomicsNetwork*, ConnectomicsNetwork* )] Number of edges not equal. " << calculatorLeft->GetNumberOfEdges() <<
" vs " << calculatorRight->GetNumberOfEdges();
762 noDifferenceFound =
false;
765 if( !
mitk::Equal( calculatorLeft->GetSmallWorldness(), calculatorRight->GetSmallWorldness(),
eps ) )
768 MITK_INFO <<
"[Equal( ConnectomicsNetwork*, ConnectomicsNetwork* )] Small worldness not equal. " << calculatorLeft->GetSmallWorldness() <<
" vs " << calculatorRight->GetSmallWorldness();
769 noDifferenceFound =
false;
772 return noDifferenceFound;
virtual void UpdateOutputInformation() override
bool EdgeExists(VertexDescriptorType vertexA, VertexDescriptorType vertexB) const
itk::SmartPointer< Self > Pointer
int GetMaximumWeight() const
bool CheckForLabel(std::string targetLabel) const
virtual bool RequestedRegionIsOutsideOfTheBufferedRegion() override
Determine whether the RequestedRegion is outside of the BufferedRegion.
std::vector< double > GetNodeBetweennessVector() const
std::vector< double > GetEdgeBetweennessVector() const
void AddEdge(VertexDescriptorType vertexA, VertexDescriptorType vertexB)
double GetAverageDegree()
std::vector< VertexDescriptorType > GetVectorOfAllVertexDescriptors() const
NetworkEdge GetEdge(VertexDescriptorType vertexA, VertexDescriptorType vertexB) const
VertexDescriptorType AddVertex(int id)
virtual void SetRequestedRegion(const itk::DataObject *) override
Set the requested region from this data object to match the requested region of the data object passe...
int GetNumberOfVertices() const
void PruneUnconnectedSingleNodes()
virtual void SetRequestedRegionToLargestPossibleRegion() override
Set the RequestedRegion to the LargestPossibleRegion.
void ImportNetwort(mitk::ConnectomicsNetwork::Pointer source)
std::vector< NetworkNode > GetVectorOfAllNodes() const
int GetNumberOfEdges() const
void SetLabel(VertexDescriptorType vertex, std::string inLabel)
void SetCoordinates(VertexDescriptorType vertex, std::vector< float > inCoordinates)
NetworkNode GetNode(VertexDescriptorType vertex) const
boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, NetworkNode, NetworkEdge > NetworkType
std::vector< double > GetShortestDistanceVectorFromLabel(std::string targetLabel) const
std::vector< double > GetClusteringCoefficientsByDegree()
std::vector< VertexDescriptorType > GetVectorOfAdjacentNodes(VertexDescriptorType vertex) const
std::vector< std::pair< std::pair< NetworkNode, NetworkNode >, NetworkEdge > > GetVectorOfAllEdges() const
boost::graph_traits< NetworkType >::vertex_descriptor VertexDescriptorType
int GetMaximumDegree() const
MITKNEWMODULE_EXPORT bool Equal(mitk::ExampleDataStructure *leftHandSide, mitk::ExampleDataStructure *rightHandSide, mitk::ScalarType eps, bool verbose)
Returns true if the example data structures are considered equal.
bool GetIsModified() const
virtual ~ConnectomicsNetwork()
double GetConnectionDensity()
MITKCORE_EXPORT const ScalarType eps
double GetGlobalClusteringCoefficient()
void SetBoostGraph(NetworkType *newGraph)
std::vector< int > GetDegreeOfNodes() const
int GetNumberOfSelfLoops()
Connectomics Network Class.
NetworkType * GetBoostGraph()
std::vector< double > GetLocalClusteringCoefficients() const
void IncreaseEdgeWeight(VertexDescriptorType vertexA, VertexDescriptorType vertexB)
virtual bool VerifyRequestedRegion() override
Verify that the RequestedRegion is within the LargestPossibleRegion.