diff --git a/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsBetweennessHistogram.h b/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsBetweennessHistogram.h index 4393cfa26b..abb6edc74a 100644 --- a/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsBetweennessHistogram.h +++ b/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsBetweennessHistogram.h @@ -1,80 +1,90 @@ /*=================================================================== The Medical Imaging Interaction Toolkit (MITK) Copyright (c) German Cancer Research Center, Division of Medical and Biological Informatics. All rights reserved. This software is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See LICENSE.txt or http://www.mitk.org for details. ===================================================================*/ #ifndef _MITK_ConnectomicsBetweennessHistogram_H #define _MITK_ConnectomicsBetweennessHistogram_H #include + +#ifdef _MSC_VER +# pragma warning(push) +# pragma warning(disable: 4172) +#endif + #include +#ifdef _MSC_VER +# pragma warning(pop) +#endif + namespace mitk { /** * \brief A class to calculate and store the betweenness of each node */ class ConnectomicsBetweennessHistogram : public mitk::ConnectomicsHistogramBase { public: /** Enum for different ways to calculate betweenness centrality */ enum BetweennessCalculationMode { UnweightedUndirectedMode, WeightedUndirectedMode }; ConnectomicsBetweennessHistogram(); virtual ~ConnectomicsBetweennessHistogram(); /** Set the calucaltion mode */ void SetBetweennessCalculationMode( const BetweennessCalculationMode & ); /** Get the calculation mode */ BetweennessCalculationMode GetBetweennessCalculationMode(); protected: /* Typedefs */ typedef mitk::ConnectomicsNetwork::NetworkType NetworkType; typedef boost::graph_traits< NetworkType >::vertex_iterator IteratorType; typedef std::vector< double > BCMapType; /** @brief Creates a new histogram from the network source. */ virtual void ComputeFromConnectomicsNetwork( ConnectomicsNetwork* source ) override; /** Calculate betweenness centrality ignoring the weight of the edges */ void CalculateUnweightedUndirectedBetweennessCentrality( NetworkType*, IteratorType, IteratorType ); /** Calculate betweenness centrality taking into consideration the weight of the edges */ void CalculateWeightedUndirectedBetweennessCentrality( NetworkType*, IteratorType, IteratorType ); /** Converts the centrality map to a histogram by binning */ void ConvertCentralityMapToHistogram(); /** Stores which mode has been selected for betweenness centrality calculation */ BetweennessCalculationMode m_Mode; /** Stores the betweenness centralities for each node */ BCMapType m_CentralityMap; }; } #endif /* _MITK_ConnectomicsBetweennessHistogram_H */ diff --git a/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsShortestPathHistogram.cpp b/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsShortestPathHistogram.cpp index eea1b8cbd6..b8f321b01a 100644 --- a/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsShortestPathHistogram.cpp +++ b/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsShortestPathHistogram.cpp @@ -1,184 +1,193 @@ /*=================================================================== The Medical Imaging Interaction Toolkit (MITK) Copyright (c) German Cancer Research Center, Division of Medical and Biological Informatics. All rights reserved. This software is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See LICENSE.txt or http://www.mitk.org for details. ===================================================================*/ #include +#ifdef _MSC_VER +# pragma warning(push) +# pragma warning(disable: 4172) +#endif + #include +#ifdef _MSC_VER +# pragma warning(pop) +#endif + #include "mitkConnectomicsConstantsManager.h" mitk::ConnectomicsShortestPathHistogram::ConnectomicsShortestPathHistogram() : m_Mode( UnweightedUndirectedMode ) , m_EverythingConnected( true ) { m_Subject = "Shortest path"; } mitk::ConnectomicsShortestPathHistogram::~ConnectomicsShortestPathHistogram() { } void mitk::ConnectomicsShortestPathHistogram::SetShortestPathCalculationMode( const mitk::ConnectomicsShortestPathHistogram::ShortestPathCalculationMode & mode) { m_Mode = mode; } mitk::ConnectomicsShortestPathHistogram::ShortestPathCalculationMode mitk::ConnectomicsShortestPathHistogram::GetShortestPathCalculationMode() { return m_Mode; } void mitk::ConnectomicsShortestPathHistogram::ComputeFromConnectomicsNetwork( ConnectomicsNetwork* source ) { NetworkType* boostGraph = source->GetBoostGraph(); switch( m_Mode ) { case UnweightedUndirectedMode: { CalculateUnweightedUndirectedShortestPaths( boostGraph ); break; } case WeightedUndirectedMode: { CalculateWeightedUndirectedShortestPaths( boostGraph ); break; } } ConvertDistanceMapToHistogram(); } void mitk::ConnectomicsShortestPathHistogram::CalculateUnweightedUndirectedShortestPaths( NetworkType* boostGraph ) { std::vector< DescriptorType > predecessorMap( boost::num_vertices( *boostGraph ) ); int numberOfNodes( boost::num_vertices( *boostGraph ) ); m_DistanceMatrix.resize( numberOfNodes ); for(unsigned int index(0); index < m_DistanceMatrix.size(); index++ ) { m_DistanceMatrix[ index ].resize( numberOfNodes ); } IteratorType iterator, end; boost::tie(iterator, end) = boost::vertices( *boostGraph ); for ( int index(0) ; iterator != end; ++iterator, index++) { boost::dijkstra_shortest_paths(*boostGraph, *iterator, boost::predecessor_map(&predecessorMap[ 0 ]).distance_map(&m_DistanceMatrix[ index ][ 0 ]).weight_map( boost::get( &mitk::ConnectomicsNetwork::NetworkEdge::edge_weight ,*boostGraph ) ) ) ; } } void mitk::ConnectomicsShortestPathHistogram::CalculateWeightedUndirectedShortestPaths( NetworkType* /*boostGraph*/ ) { MBI_WARN << mitk::ConnectomicsConstantsManager::CONNECTOMICS_WARNING_UNIMPLEMENTED_FEATURE; } void mitk::ConnectomicsShortestPathHistogram::ConvertDistanceMapToHistogram() { // get the longest path between any two nodes in the network // we assume that no nodes are farther apart than there are nodes, // this is to filter unconnected nodes int longestPath( 0 ); int numberOfNodes( m_DistanceMatrix.size() ); m_EverythingConnected = true; for(unsigned int index(0); index < m_DistanceMatrix.size(); index++ ) { for(unsigned int innerIndex(0); innerIndex < m_DistanceMatrix[ index ].size(); innerIndex++ ) { if( m_DistanceMatrix[ index ][ innerIndex ] > longestPath ) { if( m_DistanceMatrix[ index ][ innerIndex ] < numberOfNodes ) { longestPath = m_DistanceMatrix[ index ][ innerIndex ]; } else { // these nodes are not connected m_EverythingConnected = false; } } } } m_HistogramVector.resize( longestPath + 1 ); for(unsigned int index(0); index < m_DistanceMatrix.size(); index++ ) { for( unsigned int innerIndex(0); innerIndex < m_DistanceMatrix[ index ].size(); innerIndex++ ) { if( m_DistanceMatrix[ index ][ innerIndex ] < numberOfNodes ) { m_HistogramVector[ m_DistanceMatrix[ index ][ innerIndex ] ]++; } } } // correct for every path being counted twice for( unsigned int index(1); index < m_HistogramVector.size(); index++ ) { m_HistogramVector[ index ] = m_HistogramVector[ index ] / 2; } // correct for every node being distance zero to itself if( m_HistogramVector[ 0 ] >= numberOfNodes ) { m_HistogramVector[ 0 ] = m_HistogramVector[ 0 ] - numberOfNodes; } else { MBI_WARN << mitk::ConnectomicsConstantsManager::CONNECTOMICS_WARNING_ZERO_DISTANCE_NODES; } UpdateYMax(); this->m_Valid = true; } double mitk::ConnectomicsShortestPathHistogram::GetEfficiency() { if( !this->m_Valid ) { MBI_INFO << mitk::ConnectomicsConstantsManager::CONNECTOMICS_WARNING_CAN_NOT_COMPUTE_EFFICIENCY << mitk::ConnectomicsConstantsManager::CONNECTOMICS_WARNING_NETWORK_NOT_VALID; return 0.0; } if( !m_EverythingConnected ) { // efficiency of disconnected graphs is 0 MBI_INFO << mitk::ConnectomicsConstantsManager::CONNECTOMICS_WARNING_NETWORK_DISCONNECTED; return 0.0; } double efficiency( 0.0 ); double overallDistance( 0.0 ); double numberOfPairs( 0.0 ); // add up all distances for( unsigned int index(0); index < m_HistogramVector.size(); index++ ) { overallDistance = overallDistance + m_HistogramVector[ index ] * index; numberOfPairs = numberOfPairs + m_HistogramVector[ index ]; } // efficiency = 1 / averageDistance = 1 / ( overallDistance / numberofPairs ) efficiency = numberOfPairs / overallDistance; return efficiency; } diff --git a/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsStatisticsCalculator.cpp b/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsStatisticsCalculator.cpp index fbe98fe07a..b7d9b44a40 100644 --- a/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsStatisticsCalculator.cpp +++ b/Modules/DiffusionImaging/Connectomics/Algorithms/mitkConnectomicsStatisticsCalculator.cpp @@ -1,739 +1,749 @@ /*=================================================================== The Medical Imaging Interaction Toolkit (MITK) Copyright (c) German Cancer Research Center, Division of Medical and Biological Informatics. All rights reserved. This software is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See LICENSE.txt or http://www.mitk.org for details. ===================================================================*/ #include "mitkConnectomicsStatisticsCalculator.h" #include "mitkConnectomicsNetworkConverter.h" #include -#include #include + +#ifdef _MSC_VER +# pragma warning(push) +# pragma warning(disable: 4172) +#endif +#include #include + +#ifdef _MSC_VER +# pragma warning(pop) +#endif + #include #include "vnl/algo/vnl_symmetric_eigensystem.h" template class all_pairs_shortest_recorder : public boost::default_bfs_visitor { public: typedef typename boost::graph_traits::vertex_descriptor VertexType; typedef typename boost::graph_traits::edge_descriptor EdgeType; all_pairs_shortest_recorder(int* dist, int &max, unsigned int &size) { d = dist; ecc = &max; component_size = &size; } void tree_edge(EdgeType edge, const GraphType& graph) { VertexType u = boost::source(edge, graph); VertexType v = boost::target(edge, graph); d[v] = d[u] + 1; *ecc = d[v]; *component_size = *component_size + 1; } private: int* d; int* ecc; unsigned int* component_size; }; mitk::ConnectomicsStatisticsCalculator::ConnectomicsStatisticsCalculator() : m_Network( nullptr ) , m_NumberOfVertices( 0 ) , m_NumberOfEdges( 0 ) , m_AverageDegree( 0.0 ) , m_ConnectionDensity( 0.0 ) , m_NumberOfConnectedComponents( 0 ) , m_AverageComponentSize( 0.0 ) , m_Components(0) , m_LargestComponentSize( 0 ) , m_HopPlotExponent( 0.0 ) , m_EffectiveHopDiameter( 0.0 ) , m_VectorOfClusteringCoefficientsC( 0 ) , m_VectorOfClusteringCoefficientsD( 0 ) , m_VectorOfClusteringCoefficientsE( 0 ) , m_AverageClusteringCoefficientsC( 0.0 ) , m_AverageClusteringCoefficientsD( 0.0 ) , m_AverageClusteringCoefficientsE( 0.0 ) , m_VectorOfVertexBetweennessCentralities( 0 ) , m_PropertyMapOfVertexBetweennessCentralities( ) , m_AverageVertexBetweennessCentrality( 0.0 ) , m_VectorOfEdgeBetweennessCentralities( 0 ) , m_PropertyMapOfEdgeBetweennessCentralities( ) , m_AverageEdgeBetweennessCentrality( 0.0 ) , m_NumberOfIsolatedPoints( 0 ) , m_RatioOfIsolatedPoints( 0.0 ) , m_NumberOfEndPoints( 0 ) , m_RatioOfEndPoints( 0.0 ) , m_VectorOfEccentrities( 0 ) , m_VectorOfEccentrities90( 0 ) , m_VectorOfAveragePathLengths( 0.0 ) , m_Diameter( 0 ) , m_Diameter90( 0 ) , m_Radius( 0 ) , m_Radius90( 0 ) , m_AverageEccentricity( 0.0 ) , m_AverageEccentricity90( 0.0 ) , m_AveragePathLength( 0.0 ) , m_NumberOfCentralPoints( 0 ) , m_RatioOfCentralPoints( 0.0 ) , m_VectorOfSortedEigenValues( 0 ) , m_SpectralRadius( 0.0 ) , m_SecondLargestEigenValue( 0.0 ) , m_AdjacencyTrace( 0.0 ) , m_AdjacencyEnergy( 0.0 ) , m_VectorOfSortedLaplacianEigenValues( 0 ) , m_LaplacianTrace( 0.0 ) , m_LaplacianEnergy( 0.0 ) , m_LaplacianSpectralGap( 0.0 ) , m_VectorOfSortedNormalizedLaplacianEigenValues( 0 ) , m_NormalizedLaplacianTrace( 0.0 ) , m_NormalizedLaplacianEnergy( 0.0 ) , m_NormalizedLaplacianNumberOf2s( 0 ) , m_NormalizedLaplacianNumberOf1s( 0 ) , m_NormalizedLaplacianNumberOf0s( 0 ) , m_NormalizedLaplacianLowerSlope( 0.0 ) , m_NormalizedLaplacianUpperSlope( 0.0 ) , m_SmallWorldness( 0.0 ) { } mitk::ConnectomicsStatisticsCalculator::~ConnectomicsStatisticsCalculator() { } void mitk::ConnectomicsStatisticsCalculator::Update() { CalculateNumberOfVertices(); CalculateNumberOfEdges(); CalculateAverageDegree(); CalculateConnectionDensity(); CalculateNumberOfConnectedComponents(); CalculateAverageComponentSize(); CalculateLargestComponentSize(); CalculateRatioOfNodesInLargestComponent(); CalculateHopPlotValues(); CalculateClusteringCoefficients(); CalculateBetweennessCentrality(); CalculateIsolatedAndEndPoints(); CalculateShortestPathMetrics(); CalculateSpectralMetrics(); CalculateLaplacianMetrics(); CalculateNormalizedLaplacianMetrics(); CalculateSmallWorldness(); } void mitk::ConnectomicsStatisticsCalculator::CalculateNumberOfVertices() { m_NumberOfVertices = boost::num_vertices( *(m_Network->GetBoostGraph()) ); } void mitk::ConnectomicsStatisticsCalculator::CalculateNumberOfEdges() { m_NumberOfEdges = boost::num_edges( *(m_Network->GetBoostGraph()) ); } void mitk::ConnectomicsStatisticsCalculator::CalculateAverageDegree() { m_AverageDegree = ( ( (double) m_NumberOfEdges * 2.0 ) / (double) m_NumberOfVertices ); } void mitk::ConnectomicsStatisticsCalculator::CalculateConnectionDensity() { double numberOfPossibleEdges = (double) m_NumberOfVertices * ( (double) m_NumberOfVertices - 1 ) / 2; m_ConnectionDensity = (double) m_NumberOfEdges / numberOfPossibleEdges; } void mitk::ConnectomicsStatisticsCalculator::CalculateNumberOfConnectedComponents() { m_Components.resize( m_NumberOfVertices ); m_NumberOfConnectedComponents = boost::connected_components( *(m_Network->GetBoostGraph()), &m_Components[0] ); } void mitk::ConnectomicsStatisticsCalculator::CalculateAverageComponentSize() { m_AverageComponentSize = (double) m_NumberOfVertices / (double) m_NumberOfConnectedComponents ; } void mitk::ConnectomicsStatisticsCalculator::CalculateLargestComponentSize() { m_LargestComponentSize = 0; std::vector bins( m_NumberOfConnectedComponents ); for(unsigned int i=0; i < m_NumberOfVertices; i++) { bins[ m_Components[i] ]++; } for(unsigned int i=0; i < m_NumberOfConnectedComponents; i++) { if (bins[i] > m_LargestComponentSize ) { m_LargestComponentSize = bins[i]; } } } void mitk::ConnectomicsStatisticsCalculator::CalculateRatioOfNodesInLargestComponent() { m_RatioOfNodesInLargestComponent = (double) m_LargestComponentSize / (double) m_NumberOfVertices ; } void mitk::ConnectomicsStatisticsCalculator::CalculateHopPlotValues() { std::vector bins( m_NumberOfVertices ); VertexIteratorType vi, vi_end; unsigned int index( 0 ); for( boost::tie( vi, vi_end ) = boost::vertices( *(m_Network->GetBoostGraph()) ); vi != vi_end; ++vi) { std::vector distances(m_NumberOfVertices, 0); int max_distance = 0; VertexDescriptorType src = *vi; distances[src] = 0; unsigned int size = 0; boost::breadth_first_search(*(m_Network->GetBoostGraph()), src, visitor(all_pairs_shortest_recorder< NetworkType > (&distances[0], max_distance, size))); for(index=0; index < distances.size(); index++) { if(distances[index] > 0) { bins[distances[index]]++; } } } bins[0] = m_NumberOfVertices; for(index=1; index < bins.size(); index++) { bins[index] = bins[index] + bins[index-1]; } int counter = 0; double C=0, D=0, E=0, F=0; for (unsigned int i=1; i m_VectorOfClusteringCoefficientsC; std::vector m_VectorOfClusteringCoefficientsD; std::vector m_VectorOfClusteringCoefficientsE; typedef std::set NeighborSetType; typedef NetworkType::out_edge_iterator OutEdgeIterType; for(boost::tie(vi,vi_end) = boost::vertices( *(m_Network->GetBoostGraph()) ); vi!=vi_end; ++vi) { // Get the list of vertices which are in the neighborhood of vi. std::pair adjacent = boost::adjacent_vertices(*vi, *(m_Network->GetBoostGraph()) ); //Populate a set with the neighbors of vi NeighborSetType neighbors; for(; adjacent.first!=adjacent.second; ++adjacent.first) { neighbors.insert(*adjacent.first); } // Now, count the edges between vertices in the neighborhood. unsigned int neighborhood_edge_count = 0; if(neighbors.size() > 0) { NeighborSetType::iterator iter; for(iter = neighbors.begin(); iter != neighbors.end(); ++iter) { std::pair oe = out_edges(*iter, *(m_Network->GetBoostGraph()) ); for(; oe.first != oe.second; ++oe.first) { if(neighbors.find(target(*oe.first, *(m_Network->GetBoostGraph()) )) != neighbors.end()) { ++neighborhood_edge_count; } } } neighborhood_edge_count /= 2; } //Clustering Coefficienct C,E if(neighbors.size() > 1) { double num = neighborhood_edge_count; double denum = neighbors.size() * (neighbors.size()-1)/2; m_VectorOfClusteringCoefficientsC.push_back( num / denum); m_VectorOfClusteringCoefficientsE.push_back( num / denum); } else { m_VectorOfClusteringCoefficientsC.push_back(0.0); } //Clustering Coefficienct D if(neighbors.size() > 0) { double num = neighbors.size() + neighborhood_edge_count; double denum = ( (neighbors.size()+1) * neighbors.size()) / 2; m_VectorOfClusteringCoefficientsD.push_back( num / denum); } else { m_VectorOfClusteringCoefficientsD.push_back(0.0); } } // Average Clustering coefficienies: m_AverageClusteringCoefficientsC = std::accumulate(m_VectorOfClusteringCoefficientsC.begin(), m_VectorOfClusteringCoefficientsC.end(), 0.0) / m_NumberOfVertices; m_AverageClusteringCoefficientsD = std::accumulate(m_VectorOfClusteringCoefficientsD.begin(), m_VectorOfClusteringCoefficientsD.end(), 0.0) / m_NumberOfVertices; m_AverageClusteringCoefficientsE = std::accumulate(m_VectorOfClusteringCoefficientsE.begin(), m_VectorOfClusteringCoefficientsE.end(), 0.0) / m_VectorOfClusteringCoefficientsE.size(); } void mitk::ConnectomicsStatisticsCalculator::CalculateBetweennessCentrality() { // std::map used for convenient initialization EdgeIndexStdMapType stdEdgeIndex; // associative property map needed for iterator property map-wrapper EdgeIndexMapType edgeIndex(stdEdgeIndex); EdgeIteratorType iterator, end; // sets iterator to start end end to end boost::tie(iterator, end) = boost::edges( *(m_Network->GetBoostGraph()) ); int i(0); for ( ; iterator != end; ++iterator, ++i) { stdEdgeIndex.insert(std::pair< EdgeDescriptorType, int >( *iterator, i)); } // Define EdgeCentralityMap m_VectorOfEdgeBetweennessCentralities.resize( m_NumberOfEdges, 0.0); // Create the external property map m_PropertyMapOfEdgeBetweennessCentralities = EdgeIteratorPropertyMapType(m_VectorOfEdgeBetweennessCentralities.begin(), edgeIndex); // Define VertexCentralityMap VertexIndexMapType vertexIndex = get(boost::vertex_index, *(m_Network->GetBoostGraph()) ); m_VectorOfVertexBetweennessCentralities.resize( m_NumberOfVertices, 0.0); // Create the external property map m_PropertyMapOfVertexBetweennessCentralities = VertexIteratorPropertyMapType(m_VectorOfVertexBetweennessCentralities.begin(), vertexIndex); boost::brandes_betweenness_centrality( *(m_Network->GetBoostGraph()), m_PropertyMapOfVertexBetweennessCentralities, m_PropertyMapOfEdgeBetweennessCentralities ); m_AverageVertexBetweennessCentrality = std::accumulate(m_VectorOfVertexBetweennessCentralities.begin(), m_VectorOfVertexBetweennessCentralities.end(), 0.0) / (double) m_NumberOfVertices; m_AverageEdgeBetweennessCentrality = std::accumulate(m_VectorOfEdgeBetweennessCentralities.begin(), m_VectorOfEdgeBetweennessCentralities.end(), 0.0) / (double) m_NumberOfEdges; } void mitk::ConnectomicsStatisticsCalculator::CalculateIsolatedAndEndPoints() { m_NumberOfIsolatedPoints = 0; m_NumberOfEndPoints = 0; VertexIteratorType vi, vi_end; for( boost::tie(vi,vi_end) = boost::vertices( *(m_Network->GetBoostGraph()) ); vi!=vi_end; ++vi) { int degree = boost::out_degree(*vi, *(m_Network->GetBoostGraph()) ); if(degree == 0) { m_NumberOfIsolatedPoints++; } else if (degree == 1) { m_NumberOfEndPoints++; } } m_RatioOfEndPoints = (double) m_NumberOfEndPoints / (double) m_NumberOfVertices; m_RatioOfIsolatedPoints = (double) m_NumberOfIsolatedPoints / (double) m_NumberOfVertices; } /** * Calculates Shortest Path Related metrics of the graph. The * function runs a BFS from each node to find out the shortest * distances to other nodes in the graph. The maximum of this distance * is called the eccentricity of that node. The maximum eccentricity * in the graph is called diameter and the minimum eccentricity is * called the radius of the graph. Central points are those nodes * having eccentricity equals to radius. */ void mitk::ConnectomicsStatisticsCalculator::CalculateShortestPathMetrics() { //for all vertices: VertexIteratorType vi, vi_end; //store the eccentricities in a vector. m_VectorOfEccentrities.resize( m_NumberOfVertices ); m_VectorOfEccentrities90.resize( m_NumberOfVertices ); m_VectorOfAveragePathLengths.resize( m_NumberOfVertices ); //assign diameter and radius while iterating over the ecccencirities. m_Diameter = 0; m_Diameter90 = 0; m_Radius = std::numeric_limits::max(); m_Radius90 = std::numeric_limits::max(); m_AverageEccentricity = 0.0; m_AverageEccentricity90 = 0.0; m_AveragePathLength = 0.0; //The size of the giant connected component so far. unsigned int giant_component_size = 0; VertexDescriptorType radius_src(0); //Loop over the vertices for( boost::tie(vi, vi_end) = boost::vertices( *(m_Network->GetBoostGraph()) ); vi!=vi_end; ++vi) { //We are going to start a BFS, initialize the neccessary //structures for that. Store the distances of nodes from the //source in distance vector. The maximum distance is stored in //max. The BFS will start from the node that vi is pointing, that //is the src is *vi. We also init the distance of the src node to //itself to 0. size gives the number of nodes discovered during //this BFS. std::vector distances( m_NumberOfVertices ); int max_distance = 0; VertexDescriptorType src = *vi; distances[src] = 0; unsigned int size = 0; breadth_first_search(*(m_Network->GetBoostGraph()), src, visitor(all_pairs_shortest_recorder (&distances[0], max_distance, size))); // vertex vi has eccentricity equal to max_distance m_VectorOfEccentrities[src] = max_distance; //check whether there is any change in the diameter or the radius. //note that the diameter we are calculating here is also the //diameter of the giant connected component! if(m_VectorOfEccentrities[src] > m_Diameter) { m_Diameter = m_VectorOfEccentrities[src]; } //The radius should be calculated on the largest connected //component, otherwise it is very likely that radius will be 1. //We change the value of the radius only if this is the giant //connected component so far. After all the eccentricities are //found we should loop over this connected component and find the //minimum eccentricity which is the radius. So we keep the src //node, so that we can find the connected component later on. if(size > giant_component_size) { giant_component_size = size; radius_src = src; } //Calculate in how many hops we can reach 90 percent of the //nodes. We store the number of hops we can reach in h hops in the //bucket vector. That is bucket[h] gives the number of nodes //reachable in exactly h hops. sum of bucket[i bucket (max_distance+1); int counter = 0; for(unsigned int i=0; i0) { bucket[distances[i]]++; m_VectorOfAveragePathLengths[src] += distances[i]; counter ++; } } if(counter > 0) { m_VectorOfAveragePathLengths[src] = m_VectorOfAveragePathLengths[src] / counter; } int eccentricity90 = 0; while(reachable90 > 0) { eccentricity90 ++; reachable90 = reachable90 - bucket[eccentricity90]; } // vertex vi has eccentricity90 equal to eccentricity90 m_VectorOfEccentrities90[src] = eccentricity90; if(m_VectorOfEccentrities90[src] > m_Diameter90) { m_Diameter90 = m_VectorOfEccentrities90[src]; } } //We are going to calculate the radius now. We stored the src node //that when we start a BFS gives the giant connected component, and //we have the eccentricities calculated. Iterate over the nodes of //this giant component and find the minimum eccentricity. std::vector component( m_NumberOfVertices ); boost::connected_components( *(m_Network->GetBoostGraph()), &component[0]); for (unsigned int i=0; i m_VectorOfEccentrities[i]) { m_Radius = m_VectorOfEccentrities[i]; } if(m_Radius90 > m_VectorOfEccentrities90[i]) { m_Radius90 = m_VectorOfEccentrities90[i]; } } } m_AverageEccentricity = std::accumulate(m_VectorOfEccentrities.begin(), m_VectorOfEccentrities.end(), 0.0) / m_NumberOfVertices; m_AverageEccentricity90 = std::accumulate(m_VectorOfEccentrities90.begin(), m_VectorOfEccentrities90.end(), 0.0) / m_NumberOfVertices; m_AveragePathLength = std::accumulate(m_VectorOfAveragePathLengths.begin(), m_VectorOfAveragePathLengths.end(), 0.0) / m_NumberOfVertices; //calculate Number of Central Points, nodes having eccentricity = radius. m_NumberOfCentralPoints = 0; for (boost::tie(vi, vi_end) = boost::vertices( *(m_Network->GetBoostGraph()) ); vi != vi_end; ++vi) { if(m_VectorOfEccentrities[*vi] == m_Radius) { m_NumberOfCentralPoints++; } } m_RatioOfCentralPoints = (double)m_NumberOfCentralPoints / m_NumberOfVertices; } void mitk::ConnectomicsStatisticsCalculator::CalculateSpectralMetrics() { mitk::ConnectomicsNetworkConverter::Pointer converter = mitk::ConnectomicsNetworkConverter::New(); converter->SetNetwork( m_Network ); vnl_matrix adjacencyMatrix = converter->GetNetworkAsVNLAdjacencyMatrix(); vnl_symmetric_eigensystem eigenSystem(adjacencyMatrix); m_AdjacencyTrace = 0; m_AdjacencyEnergy = 0; m_VectorOfSortedEigenValues.clear(); for(unsigned int i=0; i < m_NumberOfVertices; ++i) { double value = std::fabs(eigenSystem.get_eigenvalue(i)); m_VectorOfSortedEigenValues.push_back(value); m_AdjacencyTrace += value; m_AdjacencyEnergy += value * value; } std::sort(m_VectorOfSortedEigenValues.begin(), m_VectorOfSortedEigenValues.end()); m_SpectralRadius = m_VectorOfSortedEigenValues[ m_NumberOfVertices - 1]; m_SecondLargestEigenValue = m_VectorOfSortedEigenValues[ m_NumberOfVertices - 2]; } void mitk::ConnectomicsStatisticsCalculator::CalculateLaplacianMetrics() { mitk::ConnectomicsNetworkConverter::Pointer converter = mitk::ConnectomicsNetworkConverter::New(); converter->SetNetwork( m_Network ); vnl_matrix adjacencyMatrix = converter->GetNetworkAsVNLAdjacencyMatrix(); vnl_matrix laplacianMatrix ( m_NumberOfVertices, m_NumberOfVertices, 0); vnl_matrix degreeMatrix = converter->GetNetworkAsVNLDegreeMatrix(); m_VectorOfSortedLaplacianEigenValues.clear(); laplacianMatrix = degreeMatrix - adjacencyMatrix; int numberOfConnectedComponents = 0; vnl_symmetric_eigensystem laplacianEigenSystem( laplacianMatrix ); m_LaplacianEnergy = 0; m_LaplacianTrace = 0; for(unsigned int i(0); i < m_NumberOfVertices; ++i) { double value = std::fabs( laplacianEigenSystem.get_eigenvalue(i) ); m_VectorOfSortedLaplacianEigenValues.push_back( value ); m_LaplacianTrace += value; m_LaplacianEnergy += value * value; if ( std::fabs( value ) < mitk::eps ) { numberOfConnectedComponents++; } } std::sort(m_VectorOfSortedLaplacianEigenValues.begin(), m_VectorOfSortedLaplacianEigenValues.end()); for(unsigned int i(0); i < m_VectorOfSortedLaplacianEigenValues.size(); ++i) { if(m_VectorOfSortedLaplacianEigenValues[i] > mitk::eps ) { m_LaplacianSpectralGap = m_VectorOfSortedLaplacianEigenValues[i]; break; } } } void mitk::ConnectomicsStatisticsCalculator::CalculateNormalizedLaplacianMetrics() { vnl_matrix normalizedLaplacianMatrix(m_NumberOfVertices, m_NumberOfVertices, 0); EdgeIteratorType ei, ei_end; VertexDescriptorType sourceVertex, destinationVertex; int sourceIndex, destinationIndex; VertexIndexMapType vertexIndexMap = boost::get(boost::vertex_index, *(m_Network->GetBoostGraph()) ); m_VectorOfSortedNormalizedLaplacianEigenValues.clear(); // Normalized laplacian matrix for( boost::tie(ei, ei_end) = boost::edges( *(m_Network->GetBoostGraph()) ); ei != ei_end; ++ei) { sourceVertex = boost::source(*ei, *(m_Network->GetBoostGraph()) ); sourceIndex = vertexIndexMap[sourceVertex]; destinationVertex = boost::target(*ei, *(m_Network->GetBoostGraph()) ); destinationIndex = vertexIndexMap[destinationVertex]; int sourceDegree = boost::out_degree(sourceVertex, *(m_Network->GetBoostGraph()) ); int destinationDegree = boost::out_degree(destinationVertex, *(m_Network->GetBoostGraph()) ); normalizedLaplacianMatrix.put( sourceIndex, destinationIndex, -1 / (sqrt(double(sourceDegree * destinationDegree)))); normalizedLaplacianMatrix.put( destinationIndex, sourceIndex, -1 / (sqrt(double(sourceDegree * destinationDegree)))); } VertexIteratorType vi, vi_end; for(boost::tie(vi, vi_end)=boost::vertices( *(m_Network->GetBoostGraph()) ); vi!=vi_end; ++vi) { if(boost::out_degree(*vi, *(m_Network->GetBoostGraph()) ) > 0) { normalizedLaplacianMatrix.put(vertexIndexMap[*vi], vertexIndexMap[*vi], 1); } } //End of normalized laplacian matrix definition vnl_symmetric_eigensystem normalizedLaplacianEigensystem(normalizedLaplacianMatrix); double N1=0, C1=0, D1=0, E1=0, F1=0, b1=0; double N2=0, C2=0, D2=0, E2=0, F2=0, b2=0; m_NormalizedLaplacianNumberOf2s = 0; m_NormalizedLaplacianNumberOf1s = 0; m_NormalizedLaplacianNumberOf0s = 0; m_NormalizedLaplacianTrace = 0; m_NormalizedLaplacianEnergy = 0; for(unsigned int i(0); i< m_NumberOfVertices; ++i) { double eigenValue = std::fabs(normalizedLaplacianEigensystem.get_eigenvalue(i)); m_VectorOfSortedNormalizedLaplacianEigenValues.push_back(eigenValue); m_NormalizedLaplacianTrace += eigenValue; m_NormalizedLaplacianEnergy += eigenValue * eigenValue; //0 if(eigenValue < mitk::eps) { m_NormalizedLaplacianNumberOf0s++; } //Between 0 and 1. else if(eigenValue > mitk::eps && eigenValue< 1 - mitk::eps) { C1 += i; D1 += eigenValue; E1 += i * eigenValue; F1 += i * i; N1 ++; } //1 else if(std::fabs( std::fabs(eigenValue) - 1) < mitk::eps) { m_NormalizedLaplacianNumberOf1s++; } //Between 1 and 2 else if(std::fabs(eigenValue) > 1+mitk::eps && std::fabs(eigenValue)< 2 - mitk::eps) { C2 += i; D2 += eigenValue; E2 += i * eigenValue; F2 += i * i; N2 ++; } //2 else if(std::fabs( std::fabs(eigenValue) - 2) < mitk::eps) { m_NormalizedLaplacianNumberOf2s++; } } b1 = (D1*F1 - C1*E1)/(F1*N1 - C1*C1); m_NormalizedLaplacianLowerSlope = (E1 - b1*C1)/F1; b2 = (D2*F2 - C2*E2)/(F2*N2 - C2*C2); m_NormalizedLaplacianUpperSlope = (E2 - b2*C2)/F2; } void mitk::ConnectomicsStatisticsCalculator::CalculateSmallWorldness() { double k( this->GetAverageDegree() ); double N( this->GetNumberOfVertices() ); // The clustering coefficient of an Erdos-Reny network is equivalent to // the likelihood two random nodes are connected double gamma = this->GetAverageClusteringCoefficientsC() / ( k / N ); //The mean path length of an Erdos-Reny network is approximately // ln( #vertices ) / ln( average degree ) double lambda = this->GetAveragePathLength() / ( std::log( N ) / std::log( k ) ); m_SmallWorldness = gamma / lambda; } diff --git a/Modules/DiffusionImaging/Connectomics/IODataStructures/mitkConnectomicsNetwork.cpp b/Modules/DiffusionImaging/Connectomics/IODataStructures/mitkConnectomicsNetwork.cpp index 08fbbb2ab0..9fa38b48fe 100644 --- a/Modules/DiffusionImaging/Connectomics/IODataStructures/mitkConnectomicsNetwork.cpp +++ b/Modules/DiffusionImaging/Connectomics/IODataStructures/mitkConnectomicsNetwork.cpp @@ -1,773 +1,784 @@ /*=================================================================== The Medical Imaging Interaction Toolkit (MITK) Copyright (c) German Cancer Research Center, Division of Medical and Biological Informatics. All rights reserved. This software is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See LICENSE.txt or http://www.mitk.org for details. ===================================================================*/ #include "mitkConnectomicsNetwork.h" #include + #include + +#ifdef _MSC_VER +# pragma warning(push) +# pragma warning(disable: 4172) +#endif + #include +#ifdef _MSC_VER +# pragma warning(pop) +#endif + /* Constructor and Destructor */ mitk::ConnectomicsNetwork::ConnectomicsNetwork() : m_IsModified( false ) { } mitk::ConnectomicsNetwork::~ConnectomicsNetwork() { } /* Wrapper methods */ bool mitk::ConnectomicsNetwork::EdgeExists( mitk::ConnectomicsNetwork::VertexDescriptorType vertexA, mitk::ConnectomicsNetwork::VertexDescriptorType vertexB ) const { return boost::edge(vertexA, vertexB, m_Network ).second; } void mitk::ConnectomicsNetwork::IncreaseEdgeWeight( mitk::ConnectomicsNetwork::VertexDescriptorType vertexA, mitk::ConnectomicsNetwork::VertexDescriptorType vertexB ) { m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ].weight++; SetIsModified( true ); } void mitk::ConnectomicsNetwork::AddEdge( mitk::ConnectomicsNetwork::VertexDescriptorType vertexA, mitk::ConnectomicsNetwork::VertexDescriptorType vertexB ) { AddEdge(vertexA, vertexB, m_Network[ vertexA ].id, m_Network[ vertexB ].id ); } void mitk::ConnectomicsNetwork::AddEdge( mitk::ConnectomicsNetwork::VertexDescriptorType vertexA, mitk::ConnectomicsNetwork::VertexDescriptorType vertexB, int sourceID, int targetID, int weight, double edge_weight ) { boost::add_edge( vertexA, vertexB, m_Network ); m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ].sourceId = sourceID; m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ].targetId = targetID; m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ].weight = weight; m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ].edge_weight = edge_weight; SetIsModified( true ); } mitk::ConnectomicsNetwork::VertexDescriptorType mitk::ConnectomicsNetwork::AddVertex( int id ) { VertexDescriptorType vertex = boost::add_vertex( m_Network ); m_Network[vertex].id = id; SetIsModified( true ); return vertex; } void mitk::ConnectomicsNetwork::SetLabel( mitk::ConnectomicsNetwork::VertexDescriptorType vertex, std::string inLabel ) { m_Network[vertex].label = inLabel; SetIsModified( true ); } void mitk::ConnectomicsNetwork::SetCoordinates( mitk::ConnectomicsNetwork::VertexDescriptorType vertex, std::vector< float > inCoordinates ) { m_Network[vertex].coordinates = inCoordinates; SetIsModified( true ); } void mitk::ConnectomicsNetwork::clear() { m_Network.clear(); SetIsModified( true ); } /* Superclass methods, that need to be implemented */ void mitk::ConnectomicsNetwork::UpdateOutputInformation() { } void mitk::ConnectomicsNetwork::SetRequestedRegionToLargestPossibleRegion() { } bool mitk::ConnectomicsNetwork::RequestedRegionIsOutsideOfTheBufferedRegion() { return false; } bool mitk::ConnectomicsNetwork::VerifyRequestedRegion() { return true; } void mitk::ConnectomicsNetwork::SetRequestedRegion(const itk::DataObject * /*data*/ ) { } std::vector< mitk::ConnectomicsNetwork::NetworkNode > mitk::ConnectomicsNetwork::GetVectorOfAllNodes() const { boost::graph_traits::vertex_iterator iterator, end; // sets iterator to start end end to end boost::tie(iterator, end) = boost::vertices( m_Network ); std::vector< NetworkNode > vectorOfNodes; for ( ; iterator != end; ++iterator) { NetworkNode tempNode; // the value of an iterator is a descriptor tempNode = m_Network[ *iterator ]; vectorOfNodes.push_back( tempNode ); } return vectorOfNodes; } std::vector< mitk::ConnectomicsNetwork::VertexDescriptorType > mitk::ConnectomicsNetwork::GetVectorOfAllVertexDescriptors() const { boost::graph_traits::vertex_iterator iterator, end; // sets iterator to start end end to end boost::tie(iterator, end) = boost::vertices( m_Network ); std::vector< VertexDescriptorType > vectorOfDescriptors; for ( ; iterator != end; ++iterator) { vectorOfDescriptors.push_back( *iterator ); } return vectorOfDescriptors; } std::vector< std::pair< std::pair< mitk::ConnectomicsNetwork::NetworkNode, mitk::ConnectomicsNetwork::NetworkNode > , mitk::ConnectomicsNetwork::NetworkEdge > > mitk::ConnectomicsNetwork::GetVectorOfAllEdges() const { boost::graph_traits::edge_iterator iterator, end; // sets iterator to start end end to end boost::tie(iterator, end) = boost::edges( m_Network ); std::vector< std::pair< std::pair< NetworkNode, NetworkNode > , NetworkEdge > > vectorOfEdges; for ( ; iterator != end; ++iterator) { NetworkNode sourceNode, targetNode; NetworkEdge tempEdge; // the value of an iterator is a descriptor tempEdge = m_Network[ *iterator ]; sourceNode = m_Network[ boost::source( *iterator, m_Network ) ]; targetNode = m_Network[ boost::target( *iterator, m_Network ) ]; std::pair< NetworkNode, NetworkNode > nodePair( sourceNode, targetNode ); std::pair< std::pair< NetworkNode, NetworkNode > , NetworkEdge > edgePair( nodePair, tempEdge); vectorOfEdges.push_back( edgePair ); } return vectorOfEdges; } int mitk::ConnectomicsNetwork::GetNumberOfVertices() const { return boost::num_vertices( m_Network ); } int mitk::ConnectomicsNetwork::GetNumberOfEdges() const { return boost::num_edges( m_Network ); } int mitk::ConnectomicsNetwork::GetMaximumWeight() const { int maxWeight( 0 ); boost::graph_traits::edge_iterator iterator, end; // sets iterator to start end end to end boost::tie(iterator, end) = boost::edges( m_Network ); for ( ; iterator != end; ++iterator) { int tempWeight; // the value of an iterator is a descriptor tempWeight = m_Network[ *iterator ].weight; if( tempWeight > maxWeight ) { maxWeight = tempWeight; } } return maxWeight; } int mitk::ConnectomicsNetwork::GetNumberOfSelfLoops() { int noOfSelfLoops( 0 ); std::vector< std::pair< std::pair< NetworkNode, NetworkNode > , NetworkEdge > > edgeVector = GetVectorOfAllEdges(); for( unsigned int index = 0; index < edgeVector.size() ; index++ ) { double sourceX, sourceY, sourceZ, targetX, targetY, targetZ; sourceX = edgeVector[ index ].first.first.coordinates[0] ; sourceY = edgeVector[ index ].first.first.coordinates[1] ; sourceZ = edgeVector[ index ].first.first.coordinates[2] ; targetX = edgeVector[ index ].first.second.coordinates[0] ; targetY = edgeVector[ index ].first.second.coordinates[1] ; targetZ = edgeVector[ index ].first.second.coordinates[2] ; // if the coordinates are the same if( sourceX > ( targetX - 0.01 ) && sourceX < ( targetX + 0.01 ) && sourceY > ( targetY - 0.01 ) && sourceY < ( targetY + 0.01 ) && sourceZ > ( targetZ - 0.01 ) && sourceZ < ( targetZ + 0.01 ) ) { noOfSelfLoops++; } } return noOfSelfLoops; } double mitk::ConnectomicsNetwork::GetAverageDegree() { double vertices = (double) GetNumberOfVertices(); double edges = (double) GetNumberOfEdges(); return ( ( edges * 2.0 ) / vertices ); } double mitk::ConnectomicsNetwork::GetConnectionDensity() { double vertices = (double) GetNumberOfVertices(); double edges = (double) GetNumberOfEdges(); double numberOfPossibleEdges = vertices * ( vertices - 1 ) / 2 ; return ( edges / numberOfPossibleEdges ); } std::vector< int > mitk::ConnectomicsNetwork::GetDegreeOfNodes( ) const { std::vector< int > vectorOfDegree; boost::graph_traits::vertex_iterator iterator, end; // sets iterator to start end end to end boost::tie( iterator, end ) = boost::vertices( m_Network ); vectorOfDegree.resize( this->GetNumberOfVertices() ); for ( ; iterator != end; ++iterator) { // the value of an iterator is a descriptor vectorOfDegree[ m_Network[ *iterator ].id ] = GetVectorOfAdjacentNodes( *iterator ).size(); } return vectorOfDegree; } std::vector< mitk::ConnectomicsNetwork::VertexDescriptorType > mitk::ConnectomicsNetwork::GetVectorOfAdjacentNodes( mitk::ConnectomicsNetwork::VertexDescriptorType vertex ) const { std::vector< mitk::ConnectomicsNetwork::VertexDescriptorType > vectorOfAdjacentNodes; boost::graph_traits::adjacency_iterator adjIter, adjEnd; boost::tie( adjIter, adjEnd ) = boost::adjacent_vertices( vertex, m_Network); for ( ; adjIter != adjEnd; ++adjIter) { vectorOfAdjacentNodes.push_back( *adjIter ); } return vectorOfAdjacentNodes; } int mitk::ConnectomicsNetwork::GetMaximumDegree() const { int maximumDegree( 0 ); std::vector< int > vectorOfDegree = GetDegreeOfNodes(); for( unsigned int index( 0 ); index < vectorOfDegree.size(); ++index ) { if( maximumDegree < vectorOfDegree[ index ] ) { maximumDegree = vectorOfDegree[ index ]; } } return maximumDegree; } std::vector< double > mitk::ConnectomicsNetwork::GetLocalClusteringCoefficients( ) const { std::vector< double > vectorOfClusteringCoefficients; typedef boost::graph_traits::vertex_iterator vertexIter; vectorOfClusteringCoefficients.resize( this->GetNumberOfVertices() ); std::pair vertexPair; //for every vertex calculate the clustering coefficient int size = vectorOfClusteringCoefficients.size(); for (vertexPair = vertices(m_Network); vertexPair.first != vertexPair.second; ++vertexPair.first) { int index = m_Network[ *vertexPair.first ].id; if( index > size ) { MITK_ERROR << "Trying to access out of bounds clustering coefficient"; continue; } vectorOfClusteringCoefficients[ index ] = boost::clustering_coefficient(m_Network,*vertexPair.first) ; } return vectorOfClusteringCoefficients; } std::vector< double > mitk::ConnectomicsNetwork::GetClusteringCoefficientsByDegree( ) { std::vector< double > vectorOfClusteringCoefficients = GetLocalClusteringCoefficients(); std::vector< int > vectorOfDegree = GetDegreeOfNodes(); std::vector< double > vectorOfClusteringCoefficientsByDegree; vectorOfClusteringCoefficientsByDegree.resize( GetMaximumDegree() + 1, 0 ); // c_{mean}(k) = frac{1}_{N_{k}} sum_{i in Y(k)} c_{i} // where N_{k} is the number of vertices of degree k // Y(k) is the set of vertices of degree k // c_{i} is the local clustering coefficient of vertex i for( unsigned int degree( 0 ); degree < vectorOfClusteringCoefficientsByDegree.size(); ++degree ) { vectorOfClusteringCoefficientsByDegree[ degree ] = 0; int n_k( 0 ); for( unsigned int index( 0 ); index < vectorOfDegree.size(); ++index ) { if( degree == (unsigned int)vectorOfDegree[ index ] ) {// if in Y( degree ) vectorOfClusteringCoefficientsByDegree[ degree ] += vectorOfClusteringCoefficients[ index ]; n_k++; } } if( n_k != 0 ) { vectorOfClusteringCoefficientsByDegree[ degree ] = vectorOfClusteringCoefficientsByDegree[ degree ] / n_k; } } return vectorOfClusteringCoefficientsByDegree; } double mitk::ConnectomicsNetwork::GetGlobalClusteringCoefficient( ) { double globalClusteringCoefficient( 0.0 ); std::vector< double > vectorOfClusteringCoefficientsByDegree = GetClusteringCoefficientsByDegree(); std::vector< int > vectorOfDegree = GetDegreeOfNodes(); std::vector< int > degreeDistribution; degreeDistribution.resize( vectorOfClusteringCoefficientsByDegree.size(), 0 ); int normalizationParameter( 0 ); for( unsigned int index( 0 ); index < vectorOfDegree.size(); ++index ) { degreeDistribution[ vectorOfDegree[ index ] ]++; normalizationParameter++; } // c_{mean} = sum_{k} P_{k} c_{mean}(k) // where P_{k} is the degree distribution // k is the degree for( unsigned int degree( 0 ); degree < degreeDistribution.size(); ++degree ) { globalClusteringCoefficient += degreeDistribution[ degree ] / ( (double) normalizationParameter) * vectorOfClusteringCoefficientsByDegree[ degree ]; } return globalClusteringCoefficient; } mitk::ConnectomicsNetwork::NetworkType* mitk::ConnectomicsNetwork::GetBoostGraph() { return &m_Network; } void mitk::ConnectomicsNetwork::SetBoostGraph( NetworkType* newGraph ) { this->clear(); m_Network = *newGraph; this->SetIsModified( true ); } void mitk::ConnectomicsNetwork::ImportNetwort( mitk::ConnectomicsNetwork::Pointer source ) { typedef std::vector< std::pair< std::pair< NetworkNode, NetworkNode >, NetworkEdge > > EdgeVectorType; typedef std::vector< NetworkNode > VertexVectorType; this->clear(); this->SetGeometry( source->GetGeometry()); VertexVectorType vertexVector = source->GetVectorOfAllNodes(); EdgeVectorType edgeVector = source->GetVectorOfAllEdges(); std::map< int, VertexDescriptorType > idToVertexMap; for( unsigned int loop(0); loop < vertexVector.size(); loop++ ) { VertexDescriptorType newVertex = this->AddVertex( vertexVector[ loop ].id ); this->SetLabel( newVertex, vertexVector[ loop ].label ); this->SetCoordinates( newVertex, vertexVector[ loop ].coordinates ); if ( idToVertexMap.count( vertexVector[ loop ].id ) > 0 ) { MITK_ERROR << "Aborting network import, duplicate vertex ID discovered."; return; } idToVertexMap.insert( std::pair< int, VertexDescriptorType >( vertexVector[ loop ].id, newVertex) ); } for( unsigned int loop(0); loop < edgeVector.size(); loop++ ) { VertexDescriptorType source = idToVertexMap.find( edgeVector[ loop ].second.sourceId )->second; VertexDescriptorType target = idToVertexMap.find( edgeVector[ loop ].second.targetId )->second; this->AddEdge( source, target, edgeVector[ loop ].second.sourceId, edgeVector[ loop ].second.targetId, edgeVector[ loop ].second.weight); } this->SetIsModified( true ); } bool mitk::ConnectomicsNetwork::GetIsModified() const { return m_IsModified; } void mitk::ConnectomicsNetwork::SetIsModified( bool value) { m_IsModified = value; } mitk::ConnectomicsNetwork::NetworkNode mitk::ConnectomicsNetwork::GetNode( VertexDescriptorType vertex ) const { return m_Network[ vertex ]; } mitk::ConnectomicsNetwork::NetworkEdge mitk::ConnectomicsNetwork::GetEdge( VertexDescriptorType vertexA, VertexDescriptorType vertexB ) const { if( EdgeExists(vertexA, vertexB) ) { return m_Network[ boost::edge(vertexA, vertexB, m_Network ).first ]; } else { mitkThrow() << "Edge does not exist"; } } void mitk::ConnectomicsNetwork::UpdateBounds( ) { float min = itk::NumericTraits::min(); float max = itk::NumericTraits::max(); float bounds[] = {max, min, max, min, max, min}; std::vector< mitk::ConnectomicsNetwork::NetworkNode > nodeVector = this->GetVectorOfAllNodes(); if( nodeVector.size() == 0 ) { bounds[0] = 0; bounds[1] = 1; bounds[2] = 0; bounds[3] = 1; bounds[4] = 0; bounds[5] = 1; } // for each direction, make certain the point is in between for(auto & elem : nodeVector) { for( unsigned int direction(0); direction < elem.coordinates.size(); direction++ ) { if( elem.coordinates.at(direction) < bounds[ 2 * direction ] ) { bounds[ 2 * direction ] = elem.coordinates.at(direction); } if( elem.coordinates.at(direction) > bounds[ 2 * direction + 1] ) { bounds[ 2 * direction + 1] = elem.coordinates.at(direction); } } } // provide some border margin for(int i=0; i<=4; i+=2) { bounds[i] -=10; } for(int i=1; i<=5; i+=2) { bounds[i] +=10; } this->GetGeometry()->SetFloatBounds(bounds); this->GetTimeGeometry()->Update(); } void mitk::ConnectomicsNetwork::PruneUnconnectedSingleNodes() { boost::graph_traits::vertex_iterator iterator, end; // set to true if iterators are invalidated by deleting a vertex bool vertexHasBeenRemoved( true ); // if no vertex has been removed in the last loop, we are done while( vertexHasBeenRemoved ) { vertexHasBeenRemoved = false; // sets iterator to start and end to end boost::tie(iterator, end) = boost::vertices( m_Network ); for ( ; iterator != end && !vertexHasBeenRemoved; ++iterator) { // If the node has no adjacent vertices it should be deleted if( GetVectorOfAdjacentNodes( *iterator ).size() == 0 ) { vertexHasBeenRemoved = true; // this invalidates all iterators boost::remove_vertex( *iterator, m_Network ); } } } UpdateIDs(); } void mitk::ConnectomicsNetwork::UpdateIDs() { boost::graph_traits::vertex_iterator v_i, v_end; boost::graph_traits::edge_iterator e_i, e_end; // update node ids boost::tie( v_i, v_end ) = boost::vertices( m_Network ); for ( ; v_i != v_end; ++v_i) { m_Network[*v_i].id = *v_i; } // update edge information boost::tie(e_i, e_end) = boost::edges( m_Network ); for ( ; e_i != e_end; ++e_i) { m_Network[ *e_i ].sourceId = m_Network[ boost::source( *e_i, m_Network ) ].id; m_Network[ *e_i ].targetId = m_Network[ boost::target( *e_i, m_Network ) ].id; } this->SetIsModified( true ); } std::vector< double > mitk::ConnectomicsNetwork::GetNodeBetweennessVector() const { std::vector< double > betweennessVector; betweennessVector.clear(); betweennessVector.resize( this->GetNumberOfVertices() ); boost::brandes_betweenness_centrality( m_Network, boost::centrality_map( boost::make_iterator_property_map( betweennessVector.begin(), boost::get( &NetworkNode::id, m_Network ), double() ) ).vertex_index_map( boost::get( &NetworkNode::id, m_Network ) ) ); return betweennessVector; } std::vector< double > mitk::ConnectomicsNetwork::GetEdgeBetweennessVector() const { // std::map used for convenient initialization typedef std::map EdgeIndexStdMap; EdgeIndexStdMap stdEdgeIndex; // associative property map needed for iterator property map-wrapper typedef boost::associative_property_map< EdgeIndexStdMap > EdgeIndexMap; EdgeIndexMap edgeIndex(stdEdgeIndex); boost::graph_traits::edge_iterator iterator, end; // sets iterator to start end end to end boost::tie(iterator, end) = boost::edges( m_Network ); int i(0); for ( ; iterator != end; ++iterator, ++i) { stdEdgeIndex.insert(std::pair< EdgeDescriptorType, int >( *iterator, i)); } // Define EdgeCentralityMap std::vector< double > edgeBetweennessVector(boost::num_edges( m_Network ), 0.0); // Create the external property map boost::iterator_property_map< std::vector< double >::iterator, EdgeIndexMap > e_centrality_map(edgeBetweennessVector.begin(), edgeIndex); // Define VertexCentralityMap typedef boost::property_map< NetworkType, boost::vertex_index_t>::type VertexIndexMap; VertexIndexMap vertexIndex = get(boost::vertex_index, m_Network ); std::vector< double > betweennessVector(boost::num_vertices( m_Network ), 0.0); // Create the external property map boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap > v_centrality_map(betweennessVector.begin(), vertexIndex); boost::brandes_betweenness_centrality( m_Network, v_centrality_map, e_centrality_map ); return edgeBetweennessVector; } std::vector< double > mitk::ConnectomicsNetwork::GetShortestDistanceVectorFromLabel( std::string targetLabel ) const { std::vector< VertexDescriptorType > predecessorMap( boost::num_vertices( m_Network ) ); int numberOfNodes( boost::num_vertices( m_Network ) ); std::vector< double > distanceMatrix; distanceMatrix.resize( numberOfNodes ); boost::graph_traits::vertex_iterator iterator, end; boost::tie(iterator, end) = boost::vertices( m_Network ); while( (iterator != end) && (m_Network[ *iterator ].label != targetLabel) ) { ++iterator; } if( iterator == end ) { MITK_WARN << "Label not found"; return distanceMatrix; } 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 ) ) ) ; return distanceMatrix; } bool mitk::ConnectomicsNetwork::CheckForLabel( std::string targetLabel ) const { boost::graph_traits::vertex_iterator iterator, end; boost::tie(iterator, end) = boost::vertices( m_Network ); while( (iterator != end) && (m_Network[ *iterator ].label != targetLabel) ) { ++iterator; } if( iterator == end ) { return false; } return true; } bool mitk::Equal( mitk::ConnectomicsNetwork* leftHandSide, mitk::ConnectomicsNetwork* rightHandSide, mitk::ScalarType eps, bool verbose ) { bool noDifferenceFound = true; if( rightHandSide == nullptr ) { if(verbose) { MITK_INFO << "[Equal( ConnectomicsNetwork*, ConnectomicsNetwork* )] rightHandSide nullptr."; } return false; } if( leftHandSide == nullptr ) { if(verbose) { MITK_INFO << "[Equal( ConnectomicsNetwork*, ConnectomicsNetwork* )] leftHandSide nullptr."; } return false; } mitk::ConnectomicsStatisticsCalculator::Pointer calculatorLeft = mitk::ConnectomicsStatisticsCalculator::New(); mitk::ConnectomicsStatisticsCalculator::Pointer calculatorRight = mitk::ConnectomicsStatisticsCalculator::New(); calculatorLeft->SetNetwork( leftHandSide ); calculatorRight->SetNetwork( rightHandSide ); calculatorLeft->Update(); calculatorRight->Update(); if( ! mitk::Equal( calculatorLeft->GetNumberOfVertices(), calculatorRight->GetNumberOfVertices(), eps ) ) { if(verbose) MITK_INFO << "[Equal( ConnectomicsNetwork*, ConnectomicsNetwork* )] Number of vertices not equal. " << calculatorLeft->GetNumberOfVertices() << " vs " << calculatorRight->GetNumberOfVertices(); noDifferenceFound = false; } if( ! mitk::Equal( calculatorLeft->GetNumberOfEdges(), calculatorRight->GetNumberOfEdges(), eps ) ) { if(verbose) MITK_INFO << "[Equal( ConnectomicsNetwork*, ConnectomicsNetwork* )] Number of edges not equal. " << calculatorLeft->GetNumberOfEdges() << " vs " << calculatorRight->GetNumberOfEdges(); noDifferenceFound = false; } if( ! mitk::Equal( calculatorLeft->GetSmallWorldness(), calculatorRight->GetSmallWorldness(), eps ) ) { if(verbose) MITK_INFO << "[Equal( ConnectomicsNetwork*, ConnectomicsNetwork* )] Small worldness not equal. " << calculatorLeft->GetSmallWorldness() << " vs " << calculatorRight->GetSmallWorldness(); noDifferenceFound = false; } return noDifferenceFound; -} +} \ No newline at end of file diff --git a/Modules/DiffusionImaging/Connectomics/IODataStructures/mitkConnectomicsNetwork.h b/Modules/DiffusionImaging/Connectomics/IODataStructures/mitkConnectomicsNetwork.h index 81c8d420d2..531da69929 100644 --- a/Modules/DiffusionImaging/Connectomics/IODataStructures/mitkConnectomicsNetwork.h +++ b/Modules/DiffusionImaging/Connectomics/IODataStructures/mitkConnectomicsNetwork.h @@ -1,242 +1,238 @@ /*=================================================================== The Medical Imaging Interaction Toolkit (MITK) Copyright (c) German Cancer Research Center, Division of Medical and Biological Informatics. All rights reserved. This software is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See LICENSE.txt or http://www.mitk.org for details. ===================================================================*/ #ifndef _MITK_ConnectomicsNetwork_H #define _MITK_ConnectomicsNetwork_H #include #include "mitkBaseData.h" #ifndef Q_MOC_RUN #include #endif namespace mitk { -#ifdef _MSC_VER -# pragma warning(disable: 4172) -#endif - /** * \brief Connectomics Network Class * * This class is designed to represent a connectomics network (brain network). It encapsulates a * boost adjacency list and provides additional capabilities. The information contained in the nodes and edges is: * * Network Node: *
    *
  • int ID - The id of the node *
  • string label - The label of the node, this can be any string, such as an anatomical label *
  • vector coordinates - The coordinates the node should be displayed at *
* * Network Edge: *
    *
  • int sourceId - The Id of the source node *
  • int targetId - The Id of the target node *
  • int weight - Weight of the edge as int (used for counting fibers) *
  • double edge_weight - Used for boost and algorithms, should be between 0 and 1 *
*/ class MITKCONNECTOMICS_EXPORT ConnectomicsNetwork : public BaseData { public: /** Structs for the graph */ /** The Node */ struct NetworkNode { int id; std::string label; std::vector< float > coordinates; }; /** The Edge */ struct NetworkEdge { int sourceId; int targetId; int weight; // For now the number of times it was present double edge_weight; // For boost, currently set to 1 by default for unweighted calculations }; /** Typedefs **/ //typedef boost::adjacency_list< boost::listS, boost::listS, boost::undirectedS, NetworkNode, NetworkEdge > NetworkType; typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, NetworkNode, NetworkEdge > NetworkType; typedef boost::graph_traits::vertex_descriptor VertexDescriptorType; typedef boost::graph_traits::edge_descriptor EdgeDescriptorType; // virtual methods that need to be implemented virtual void UpdateOutputInformation() override; virtual void SetRequestedRegionToLargestPossibleRegion() override; virtual bool RequestedRegionIsOutsideOfTheBufferedRegion() override; virtual bool VerifyRequestedRegion() override; virtual void SetRequestedRegion(const itk::DataObject * ) override; // Macros mitkClassMacro( ConnectomicsNetwork, BaseData ); itkFactorylessNewMacro(Self) itkCloneMacro(Self) ////////////////// Interface /////////////////// /** return whether an edge exists between the two given vertices */ bool EdgeExists( VertexDescriptorType vertexA, VertexDescriptorType vertexB ) const; /** increase the weight of an edge between the two given vertices */ void IncreaseEdgeWeight( VertexDescriptorType vertexA, VertexDescriptorType vertexB ); /** add an edge between two given vertices */ void AddEdge( VertexDescriptorType vertexA, VertexDescriptorType vertexB); /** add an edge between two given vertices ( with a specific weight ) */ void AddEdge( VertexDescriptorType vertexA, VertexDescriptorType vertexB, int sourceID, int targetID, int weight = 1, double edge_weight = 1.0 ); /** add a vertex with a specified id */ VertexDescriptorType AddVertex( int id); /** set the label of a vertex */ void SetLabel( VertexDescriptorType vertex, std::string inLabel ); /** set the coordinates of a vertex */ void SetCoordinates( VertexDescriptorType vertex, std::vector< float > inCoordinates ); /** clear the graph */ void clear(); /** return the node struct for a given node descriptor */ NetworkNode GetNode( VertexDescriptorType vertex ) const; /** return the edge struct for two given node descriptors */ NetworkEdge GetEdge( VertexDescriptorType vertexA, VertexDescriptorType vertexB ) const; /** get vector containing all the nodes of the network */ std::vector< NetworkNode > GetVectorOfAllNodes() const; /** get vector containing all the vertex descriptors of the network */ std::vector< VertexDescriptorType > GetVectorOfAllVertexDescriptors() const; /** get vector containing the descriptors of nodes adjacent to the vertex denoted by the given descriptor */ std::vector< VertexDescriptorType > GetVectorOfAdjacentNodes( VertexDescriptorType vertex ) const; /** get vector containing all the edges of the network and the connected nodes */ std::vector< std::pair< std::pair< NetworkNode, NetworkNode > , NetworkEdge > > GetVectorOfAllEdges() const; /** get overall number of vertices in the network */ int GetNumberOfVertices() const; /** get overall number of edges in the network */ int GetNumberOfEdges() const; /** get number of vertices, that are connected to themselves */ int GetNumberOfSelfLoops(); /** get number of vertices, that are connected to themselves */ double GetAverageDegree(); /** get number of edges divided by number of possible edges */ double GetConnectionDensity(); /** Get the maximum weight of all edges */ int GetMaximumWeight() const; /** Get a vector in the format vector[ vertexID ] = degree */ std::vector< int > GetDegreeOfNodes( ) const; /** Get the maximum degree of all nodes */ int GetMaximumDegree() const; /** Get a vector in the format vector[ vertexID ] = clustering coefficient */ std::vector< double > GetLocalClusteringCoefficients( ) const; /** Get a vector in the format vector[ degree ] = average clustering coefficient */ std::vector< double > GetClusteringCoefficientsByDegree( ); /** Get the global clustering coefficient */ double GetGlobalClusteringCoefficient( ); /** Get the betweenness centrality for each vertex in form of a vector of length (number vertices)*/ std::vector< double > GetNodeBetweennessVector() const; /** Get the betweenness centrality for each edge in form of a vector of length (number edges)*/ std::vector< double > GetEdgeBetweennessVector() const; /** Check whether a vertex with the specified label exists*/ bool CheckForLabel( std::string targetLabel ) const; /** Get the shortest distance from a specified vertex to all other vertices in form of a vector of length (number vertices)*/ std::vector< double > GetShortestDistanceVectorFromLabel( std::string targetLabel ) const; /** Access boost graph directly */ NetworkType* GetBoostGraph(); /** Set the boost graph directly */ void SetBoostGraph( NetworkType* newGraph ); void ImportNetwort( mitk::ConnectomicsNetwork::Pointer source ); /** Get the modified flag */ bool GetIsModified() const; /** Set the modified flag */ void SetIsModified( bool ); /** Update the bounds of the geometry to fit the network */ void UpdateBounds( ); /** Remove nodes not connected to any other node */ void PruneUnconnectedSingleNodes(); /** This function will relabel all vertices and edges in a continuous manner * * Mainly important after removing vertices, to make sure that the ids run continuously from * 0 to number of vertices - 1 and edge target and source ids match the corresponding node. */ void UpdateIDs(); protected: ConnectomicsNetwork(); virtual ~ConnectomicsNetwork(); NetworkType m_Network; /// Flag which indicates whether the network has been modified since the last check /// /// mainly for rendering purposes bool m_IsModified; private: }; /** * \brief Returns true if the networks are considered equal. * * For now two networks are considered equal if they are equal in the following properties: * - Number of nodes * - Number of edges * - Smallworldness */ MITKCONNECTOMICS_EXPORT bool Equal( mitk::ConnectomicsNetwork* leftHandSide, mitk::ConnectomicsNetwork* rightHandSide, mitk::ScalarType eps, bool verbose); } // namespace mitk #endif /* _MITK_ConnectomicsNetwork_H */