import * as $N from "@/core/base/BaseNode" ; import * as $E from "@/core/base/BaseEdge" ; import * as $G from "@/core/base/BaseGraph" ; import * as $MC from "@/mincutmaxflow/MinCutMaxFlowBoykov" ; export type EnergyFunctionTerm = ( arg1 : string , arg2 : string ) => number ; export interface EMEConfig { directed : boolean ; labeled : boolean ; interactionTerm : EnergyFunctionTerm ; dataTerm : EnergyFunctionTerm ; } export interface EMEResult { graph : $G . IGraph ; } export interface IEMEBoykov { calculateCycle ( ) : EMEResult ; constructGraph ( ) : $G . IGraph ; initGraph ( graph ) : $G . IGraph ; prepareEMEStandardConfig ( ) : EMEConfig ; } export interface EMEState { expansionGraph : $G . IGraph ; labeledGraph : $G . IGraph ; activeLabel : string ; energy : number ; } /**
 *
 */ class EMEBoykov implements IEMEBoykov { private _config : EMEConfig ; private _state : EMEState = { expansionGraph : null , labeledGraph : null , activeLabel : "" , energy : Infinity , } ; private _interactionTerm : EnergyFunctionTerm ; private _dataTerm : EnergyFunctionTerm ; constructor ( private _graph , private _labels , config ? ) { this . _config = config || this . prepareEMEStandardConfig ( ) ; this . _interactionTerm = this . _config . interactionTerm ; this . _dataTerm = this . _config . dataTerm ; this . _graph = this . initGraph ( _graph ) ; this . _state . labeledGraph = this . _graph . cloneStructure ( ) ; this . _state . activeLabel = this . _labels [ 0 ] ; } /**
     *
     */ calculateCycle ( ) { let success = true ; let mincut_options = { directed : true } ; while ( success ) { success = false ; for ( let i = 0 ; i < this . _labels . length ; i ++ ) { this . _state . activeLabel = this . _labels [ i ] ; this . _state . expansionGraph = this . constructGraph ( ) ; let source = this . _state . expansionGraph . getNodeById ( "SOURCE" ) ; let sink = this . _state . expansionGraph . getNodeById ( "SINK" ) ; let MinCut ; MinCut = new $MC . MCMFBoykov ( this . _state . expansionGraph , source , sink , mincut_options ) ; let mincut_result = MinCut . calculateCycle ( ) ; if ( mincut_result . cost < this . _state . energy ) { this . _state . energy = mincut_result . cost ; this . _state . labeledGraph = this . labelGraph ( mincut_result , source ) ; success = true ; } } if ( this . _labels . length <= 2 ) { break ; } } let result = { graph : this . _state . labeledGraph , } ; return result ; } /**
     *
     */ constructGraph ( ) { let graph = this . _state . labeledGraph . cloneStructure ( ) ; let nodes = graph . getNodes ( ) ; let node_ids = Object . keys ( nodes ) ; let source = graph . addNodeByID ( "SOURCE" ) ; let sink = graph . addNodeByID ( "SINK" ) ; let edge_ids = Object . keys ( graph . getUndEdges ( ) ) ; let edges_length = edge_ids . length ; for ( let i = 0 ; i < node_ids . length ; i ++ ) { let node = nodes [ node_ids [ i ] ] ; let edge_options = { directed : true , weighted : true , weight : 0 , } ; edge_options . weight = this . _dataTerm ( this . _state . activeLabel , this . _graph . getNodeById ( node . getID ( ) ) . getLabel ( ) ) ; let edge_source = graph . addEdgeByID ( node . getID ( ) + "_" + source . getID ( ) , node , source , edge_options ) ; let edge_source_reverse = graph . addEdgeByID ( source . getID ( ) + "_" + node . getID ( ) , source , node , edge_options ) ; edge_options . weight = node . getLabel ( ) == this . _state . activeLabel ? Infinity : this . _dataTerm ( node . getLabel ( ) , this . _graph . getNodeById ( node . getID ( ) ) . getLabel ( ) ) ; let edge_sink = graph . addEdgeByID ( node . getID ( ) + "_" + sink . getID ( ) , node , sink , edge_options ) ; let edge_sink_source = graph . addEdgeByID ( sink . getID ( ) + "_" + node . getID ( ) , sink , node , edge_options ) ; } for ( let i = 0 ; i < edges_length ; i ++ ) { let edge = graph . getEdgeById ( edge_ids [ i ] ) ; let node_p = edge . getNodes ( ) . a ; let node_q = edge . getNodes ( ) . b ; let edge_options = { directed : true , weighted : true , weight : 0 , } ; if ( node_p . getLabel ( ) == node_q . getLabel ( ) ) { edge_options . weight = this . _interactionTerm ( node_p . getLabel ( ) , this . _state . activeLabel ) ; graph . deleteEdge ( edge ) ; graph . addEdgeByID ( node_p . getID ( ) + "_" + node_q . getID ( ) , node_p , node_q , edge_options ) ; graph . addEdgeByID ( node_q . getID ( ) + "_" + node_p . getID ( ) , node_q , node_p , edge_options ) ; continue ; } let node_aux = graph . addNodeByID ( "aux_" + node_p . getID ( ) + "_" + node_q . getID ( ) ) ; edge_options . weight = this . _interactionTerm ( node_p . getLabel ( ) , this . _state . activeLabel ) ; let edge_p_aux = graph . addEdgeByID ( node_p . getID ( ) + "_" + node_aux . getID ( ) , node_p , node_aux , edge_options ) ; let edge_p_aux_reverse = graph . addEdgeByID ( node_aux . getID ( ) + "_" + node_p . getID ( ) , node_aux , node_p , edge_options ) ; edge_options . weight = this . _interactionTerm ( this . _state . activeLabel , node_q . getLabel ( ) ) ; let edge_aux_q = graph . addEdgeByID ( node_aux . getID ( ) + "_" + node_q . getID ( ) , node_aux , node_q , edge_options ) ; let edge_aux_q_reverse = graph . addEdgeByID ( node_q . getID ( ) + "_" + node_aux . getID ( ) , node_q , node_aux , edge_options ) ; edge_options . weight = this . _interactionTerm ( node_p . getLabel ( ) , node_q . getLabel ( ) ) ; let edge_aux_sink = graph . addEdgeByID ( node_aux . getID ( ) + "_" + sink . getID ( ) , node_aux , sink , edge_options ) ; let edge_aux_sink_reverse = graph . addEdgeByID ( sink . getID ( ) + "_" + node_aux . getID ( ) , sink , node_aux , edge_options ) ; graph . deleteEdge ( edge ) ; } return graph ; } labelGraph ( mincut , source ) { let graph = this . _state . labeledGraph ; source = this . _state . expansionGraph . getNodeById ( "SOURCE" ) ; for ( let i = 0 ; i < mincut . edges . length ; i ++ ) { let edge = mincut . edges [ i ] ; let node_a = edge . getNodes ( ) . a ; let node_b = edge . getNodes ( ) . b ; if ( node_a . getID ( ) == source . getID ( ) ) { graph . getNodeById ( node_b . getID ( ) ) . setLabel ( this . _state . activeLabel ) ; continue ; } if ( node_b . getID ( ) == source . getID ( ) ) { graph . getNodeById ( node_a . getID ( ) ) . setLabel ( this . _state . activeLabel ) ; } } return graph ; } initGraph ( graph ) { let nodes = graph . getNodes ( ) ; let node_ids = Object . keys ( nodes ) ; let nodes_length = node_ids . length ; for ( let i = 0 ; i < nodes_length ; i ++ ) { let node = nodes [ node_ids [ i ] ] ; node . setLabel ( node . getFeature ( "label" ) ) ; } return graph ; } prepareEMEStandardConfig ( ) { let interactionTerm = function ( label_a , label_b ) { return label_a == label_b ? 0 : 1 ; } ; let dataTerm = function ( label , observed ) { let label_number = Number ( label ) ; let observed_number = Number ( observed ) ; if ( isNaN ( label_number ) || isNaN ( observed_number ) ) { throw new Error ( "Cannot convert labels to numbers!" ) ; } return 1.5 * Math . pow ( label_number - observed_number , 2 ) ; } ; return { directed : false , labeled : false , interactionTerm : interactionTerm , dataTerm : dataTerm , } ; } } export { EMEBoykov } ;