public void createRootPathMap ( ) throws WikiApiException { // do only create rootPathMap, if it was not already computed if ( rootPathMap != null ) { return ; } File rootPathFile = new File ( wiki . getWikipediaId ( ) + "_" + this . rootPathMapFilename ) ; // try to load rootPathMap from precomputed file if ( rootPathFile . exists ( ) ) { logger . info ( "Loading saved rootPathMap ..." ) ; rootPathMap = deserializeMap ( rootPathFile ) ; logger . info ( "Done loading saved rootPathMap" ) ; return ; } logger . info ( "Computing rootPathMap" ) ; rootPathMap = new HashMap < Integer , List < Integer > > ( ) ; // a queue holding the nodes to process List < Integer > queue = new ArrayList < Integer > ( ) ; // initialize the queue with all leaf nodes Set < Integer > leafNodes = this . __getLeafNodes ( ) ; queue . addAll ( leafNodes ) ; logger . info ( queue . size ( ) + " leaf nodes." ) ; fillRootPathMap ( queue ) ; queue . clear ( ) ; // queue should be empty now, but clear anyway // add non-leaf nodes that have not been on a shortest, yet for ( Category cat : wiki . getCategories ( ) ) { if ( ! rootPathMap . containsKey ( cat . getPageId ( ) ) ) { queue . add ( cat . getPageId ( ) ) ; } } logger . info ( queue . size ( ) + " non leaf nodes not on a shortest leaf-node to root path." ) ; fillRootPathMap ( queue ) ; for ( Category cat : wiki . getCategories ( ) ) { if ( ! rootPathMap . containsKey ( cat . getPageId ( ) ) ) { logger . info ( "no path for " + cat . getPageId ( ) ) ; } } // from the root path map, we can very easily get the depth this . depth = getDepthFromRootPathMap ( ) ; logger . info ( "Setting depth of category graph: " + this . depth ) ; logger . info ( "Serializing rootPathMap" ) ; this . serializeMap ( rootPathMap , rootPathFile ) ; }
Computes the paths from each category node to the root . Computing n paths will take some time . Thus efficient computing is based on the assumption that all subpaths in the shortest path to the root are also shortest paths for the corresponding nodes . Starting with the leaf nodes gives the longest initial paths with most subpaths .