nl_tokens: / ///////////////////////////////////////////////////////////////////////////////// Cycle functions portion of code to detect circular links based on Colin Fergus bl . ock https : // gist . github . com / cfergus / 3956043 Identify circles in the link objects
pl_tokens: function identifyCircles ( <mask> , id , sortNodes ) { var circularLinkID = 0 if ( sortNodes === null ) { // Building adjacency graph var adjList = [ ] for ( var i = 0 ; i < graph . links . length ; i ++ ) { var link = graph . links [ i ] ; var source = link . source . index ; var target = link . target . index ; if ( ! adjList [ source ] ) adjList [ source ] = [ ] if ( ! adjList [ target ] ) adjList [ target ] = [ ] // Add links if not already in set if ( adjList [ source ] . indexOf ( target ) === - 1 ) adjList [ source ] . push ( target ) ; } // Find all elementary circuits var cycles = findCircuits ( adjList ) ; // Sort by circuits length cycles . sort ( function ( a , b ) { return a . length - b . length ; } ) ; // Make one link circular for each elementary circuit var circularLinks = { } ; for ( i = 0 ; i < cycles . length ; i ++ ) { var cycle = cycles [ i ] ; var closed = false ; for ( var j = 0 ; j < cycle . length - 1 ; j ++ ) { if ( ! circularLinks [ cycle [ j ] ] ) circularLinks [ cycle [ j ] ] = { } ; // Check if there is already a circular link in the circuit if ( circularLinks [ cycle [ j ] ] && circularLinks [ cycle [ j ] ] [ cycle [ j + 1 ] ] ) { closed = true ; break ; } } if ( ! closed ) { // If not closed, make the last link the circular one var last = cycle . slice ( - 2 ) ; circularLinks [ last [ 0 ] ] [ last [ 1 ] ] = true } } graph . links . forEach ( function ( link ) { var target = link . target . index ; var source = link . source . index ; // If self-linking or a back-edge if ( target === source || ( circularLinks [ source ] && circularLinks [ source ] [ target ] ) ) { link . circular = true link . circularLinkID = circularLinkID circularLinkID = circularLinkID + 1 } else { link . circular = false } } ) } else { graph . links . forEach ( function ( link ) { if ( link . source [ sortNodes ] < link . target [ sortNodes ] ) { link . circular = false } else { link . circular = true link . circularLinkID = circularLinkID circularLinkID = circularLinkID + 1 } } ) } }