nl_tokens: / * To compute the cut value of the edge parent - > child we consider it and any other graph edges to or from the child . parent | child / \ u v
pl_tokens: function setCutValue ( graph , tree , child ) { var parentEdge = tree . inEdges ( child ) [ 0 ] ; // List of child's children in the spanning tree. var grandchildren = [ ] ; var grandchildEdges = tree . outEdges ( child ) ; for ( var gce in grandchildEdges ) { grandchildren . push ( tree . target ( grandchildEdges [ gce ] ) ) ; } var cutValue = 0 ; // TODO: Replace unit increment/decrement with edge weights. var E = 0 ; // Edges from child to grandchild's subtree. var F = 0 ; // Edges to child from grandchild's subtree. var G = 0 ; // Edges from child to nodes outside of child's subtree. var H = 0 ; // Edges from nodes outside of child's subtree to child. // Consider all graph edges from child. var outEdges = graph . outEdges ( child ) ; var gc ; for ( var oe in outEdges ) { var succ = graph . target ( outEdges [ oe ] ) ; for ( gc in grandchildren ) { if ( inSubtree ( tree , succ , grandchildren [ gc ] ) ) { E ++ ; } } if ( ! inSubtree ( tree , succ , child ) ) { G ++ ; } } // Consider all graph edges to child. var inEdges = graph . inEdges ( child ) ; for ( var ie in inEdges ) { var pred = graph . source ( inEdges [ ie ] ) ; for ( gc in grandchildren ) { if ( inSubtree ( tree , pred , grandchildren [ gc ] ) ) { F ++ ; } } if ( ! inSubtree ( tree , pred , child ) ) { H ++ ; } } // Contributions depend on the alignment of the parent -> child edge // and the child -> u or v edges. var grandchildCutSum = 0 ; for ( gc in grandchildren ) { var cv = <mask> . edge ( grandchildEdges [ gc ] ) . cutValue ; if ( ! tree . edge ( grandchildEdges [ gc ] ) . reversed ) { grandchildCutSum += cv ; } else { grandchildCutSum -= cv ; } } if ( ! tree . edge ( parentEdge ) . reversed ) { cutValue += grandchildCutSum - E + F - G + H ; } else { cutValue -= grandchildCutSum - E + F - G + H ; } tree . edge ( parentEdge ) . cutValue = cutValue ; }