import * as $N from "@/core/base/BaseNode" ; import * as $E from "@/core/base/BaseEdge" ; import * as $G from "@/core/base/BaseGraph" ; import { Logger } from "@/utils/Logger" ; export interface MCMFConfig { directed : boolean ; } export interface MCMFResult { edges : Array < $E . IBaseEdge > ; edgeIDs : Array < string > ; cost : number ; } export interface IMCMFBoykov { calculateCycle ( ) : MCMFResult ; convertToDirectedGraph ( graph ) : $G . IGraph ; prepareMCMFStandardConfig ( ) : MCMFConfig ; } export interface MCMFState { residGraph : $G . IGraph ; activeNodes : { [ key ] : $N . IBaseNode ; } ; orphans : { [ key ] : $N . IBaseNode ; } ; treeS : { [ key ] : $N . IBaseNode ; } ; treeT : { [ key ] : $N . IBaseNode ; } ; parents : { [ key ] : $N . IBaseNode ; } ; path : Array < $N . IBaseNode > ; tree : { [ key ] : string ; } ; } /**
 *
 */ class MCMFBoykov implements IMCMFBoykov { private _config : MCMFConfig ; private _state : MCMFState = { residGraph : null , activeNodes : { } , orphans : { } , treeS : { } , treeT : { } , parents : { } , path : [ ] , tree : { } , } ; constructor ( private _graph , private _source , private _sink , config ? ) { this . _config = config || this . prepareMCMFStandardConfig ( ) ; if ( this . _config . directed ) { this . renameEdges ( _graph ) ; } this . _state . residGraph = this . _graph ; if ( ! this . _config . directed ) { this . _state . residGraph = this . convertToDirectedGraph ( this . _state . residGraph ) ; this . _source = this . _state . residGraph . getNodeById ( this . _source . getID ( ) ) ; this . _sink = this . _state . residGraph . getNodeById ( this . _sink . getID ( ) ) ; } } calculateCycle ( ) { const result = { edges : [ ] , edgeIDs : [ ] , cost : 0 , } ; this . _state . treeS [ this . _source . getID ( ) ] = this . _source ; this . _state . tree [ this . _source . getID ( ) ] = "S" ; this . _state . treeT [ this . _sink . getID ( ) ] = this . _sink ; this . _state . tree [ this . _sink . getID ( ) ] = "T" ; this . _state . activeNodes [ this . _source . getID ( ) ] = this . _source ; this . _state . activeNodes [ this . _sink . getID ( ) ] = this . _sink ; let nrCycles = 0 ; while ( true ) { this . grow ( ) ; if ( ! this . _state . path . length ) { break ; } this . augmentation ( ) ; this . adoption ( ) ; ++ nrCycles ; } /**
         * computing result
         */ const smallTree = Object . keys ( this . _state . treeS ) . length < Object . keys ( this . _state . treeT ) . length ? this . _state . treeS : this . _state . treeT ; const smallTree_size = Object . keys ( smallTree ) . length ; const smallTree_ids = Object . keys ( smallTree ) ; for ( let i = 0 ; i < smallTree_size ; i ++ ) { const node_id = smallTree_ids [ i ] ; const node = this . _graph . getNodeById ( node_id ) ; if ( ! this . _config . directed ) { const undEdges = node . undEdges ( ) ; const undEdges_size = Object . keys ( undEdges ) . length ; const undEdges_ids = Object . keys ( undEdges ) ; for ( let i = 0 ; i < undEdges_size ; i ++ ) { let edge = undEdges [ undEdges_ids [ i ] ] ; let neighbor = edge . getNodes ( ) . a . getID ( ) == node . getID ( ) ? edge . getNodes ( ) . b : edge . getNodes ( ) . a ; if ( this . _state . tree [ neighbor . getID ( ) ] != this . _state . tree [ node . getID ( ) ] ) { result . edges . push ( edge ) ; result . edgeIDs . push ( edge . getID ( ) ) ; result . cost += edge . getWeight ( ) ; } } } else { const outEdges_ids = Object . keys ( node . outEdges ( ) ) ; const outEdges_length = outEdges_ids . length ; const inEdges_ids = Object . keys ( node . inEdges ( ) ) ; const inEdges_length = inEdges_ids . length ; for ( let i = 0 ; i < outEdges_length ; i ++ ) { let edge = this . _graph . getEdgeById ( outEdges_ids [ i ] ) ; let neighbor = edge . getNodes ( ) . b ; if ( this . _state . tree [ neighbor . getID ( ) ] != this . _state . tree [ node . getID ( ) ] ) { result . edges . push ( edge ) ; result . edgeIDs . push ( edge . getID ( ) ) ; result . cost += edge . getWeight ( ) ; } } for ( let i = 0 ; i < inEdges_length ; i ++ ) { let edge = this . _graph . getEdgeById ( inEdges_ids [ i ] ) ; let neighbor = edge . getNodes ( ) . a ; if ( this . tree ( neighbor ) != this . tree ( node ) ) { result . edges . push ( edge ) ; result . edgeIDs . push ( edge . getID ( ) ) ; result . cost += edge . getWeight ( ) ; } } } } return result ; } renameEdges ( graph ) { const edges = graph . getDirEdges ( ) ; const edges_ids = Object . keys ( edges ) ; const edges_length = edges_ids . length ; for ( let i = 0 ; i < edges_length ; i ++ ) { const edge = edges [ edges_ids [ i ] ] ; const weight = edge . getWeight ( ) ; graph . deleteEdge ( edge ) ; const node_a = edge . getNodes ( ) . a ; const node_b = edge . getNodes ( ) . b ; const options = { directed : true , weighted : true , weight : weight } ; const new_edge = graph . addEdgeByID ( node_a . getID ( ) + "_" + node_b . getID ( ) , node_a , node_b , options ) ; } } convertToDirectedGraph ( uGraph ) { const dGraph = new $G . BaseGraph ( uGraph . label + "_directed" ) ; const nodes = uGraph . getNodes ( ) ; const nodes_ids = Object . keys ( nodes ) ; const nodes_length = nodes_ids . length ; for ( let i = 0 ; i < nodes_length ; i ++ ) { const node = nodes [ nodes_ids [ i ] ] ; dGraph . addNodeByID ( node . getID ( ) ) ; } const edges = uGraph . getUndEdges ( ) ; const edges_ids = Object . keys ( edges ) ; const edges_length = edges_ids . length ; for ( let i = 0 ; i < edges_length ; i ++ ) { const und_edge = edges [ edges_ids [ i ] ] ; const node_a_id = und_edge . getNodes ( ) . a . getID ( ) ; const node_b_id = und_edge . getNodes ( ) . b . getID ( ) ; const options = { directed : true , weighted : true , weight : und_edge . getWeight ( ) , } ; dGraph . addEdgeByID ( node_a_id + "_" + node_b_id , dGraph . getNodeById ( node_a_id ) , dGraph . getNodeById ( node_b_id ) , options ) ; dGraph . addEdgeByID ( node_b_id + "_" + node_a_id , dGraph . getNodeById ( node_b_id ) , dGraph . getNodeById ( node_a_id ) , options ) ; } return dGraph ; } tree ( node ) { let tree = "" ; if ( node . getID ( ) in this . _state . treeS ) { tree = "S" ; return tree ; } if ( node . getID ( ) in this . _state . treeT ) { tree = "T" ; return tree ; } return tree ; } getPathToRoot ( node ) { const path_root = [ ] ; let node_id = node . getID ( ) ; path_root . push ( this . _graph . getNodeById ( node_id ) ) ; const sink_id = this . _sink . getID ( ) ; const source_id = this . _source . getID ( ) ; while ( node_id != sink_id && node_id != source_id ) { if ( this . _state . parents [ node_id ] == null ) { return path_root ; } node_id = this . _state . parents [ node_id ] . getID ( ) ; path_root . push ( this . _graph . getNodeById ( node_id ) ) ; } return path_root ; } getBottleneckCapacity ( ) { let min_capacity = 0 ; min_capacity = this . _state . residGraph . getEdgeById ( this . _state . path [ 0 ] . getID ( ) + "_" + this . _state . path [ 1 ] . getID ( ) ) . getWeight ( ) ; const path_length = this . _state . path . length - 1 ; for ( let i = 0 ; i < path_length ; i ++ ) { const node_a = this . _state . path [ i ] ; const node_b = this . _state . path [ i + 1 ] ; const edge = this . _state . residGraph . getEdgeById ( node_a . getID ( ) + "_" + node_b . getID ( ) ) ; if ( edge . getWeight ( ) < min_capacity ) { min_capacity = edge . getWeight ( ) ; } } return min_capacity ; } grow ( ) { let nr_active_nodes = Object . keys ( this . _state . activeNodes ) . length ; const active_nodes_ids = Object . keys ( this . _state . activeNodes ) ; while ( nr_active_nodes ) { const activeNode = this . _state . activeNodes [ active_nodes_ids [ 0 ] ] ; const edges = this . _state . tree [ activeNode . getID ( ) ] == "S" ? activeNode . outEdges ( ) : activeNode . inEdges ( ) ; const edges_ids = Object . keys ( edges ) ; const edges_length = edges_ids . length ; for ( let i = 0 ; i < edges_length ; i ++ ) { const edge = edges [ edges_ids [ i ] ] ; const neighborNode = this . _state . tree [ activeNode . getID ( ) ] == "S" ? edge . getNodes ( ) . b : edge . getNodes ( ) . a ; if ( edge . getWeight ( ) <= 0 ) { continue ; } if ( ! this . _state . tree [ neighborNode . getID ( ) ] ) { if ( this . _state . tree [ activeNode . getID ( ) ] == "S" ) { this . _state . treeS [ neighborNode . getID ( ) ] = neighborNode ; this . _state . tree [ neighborNode . getID ( ) ] = "S" ; } else { this . _state . treeT [ neighborNode . getID ( ) ] = neighborNode ; this . _state . tree [ neighborNode . getID ( ) ] = "T" ; } this . _state . parents [ neighborNode . getID ( ) ] = activeNode ; this . _state . activeNodes [ neighborNode . getID ( ) ] = neighborNode ; active_nodes_ids . push ( neighborNode . getID ( ) ) ; ++ nr_active_nodes ; } else if ( this . _state . tree [ neighborNode . getID ( ) ] != this . _state . tree [ activeNode . getID ( ) ] ) { let complete_path ; let nPath = this . getPathToRoot ( neighborNode ) ; let aPath = this . getPathToRoot ( activeNode ) ; const root_node_npath = nPath [ nPath . length - 1 ] ; if ( this . _state . tree [ root_node_npath . getID ( ) ] == "S" ) { nPath = nPath . reverse ( ) ; complete_path = nPath . concat ( aPath ) ; } else { aPath = aPath . reverse ( ) ; complete_path = aPath . concat ( nPath ) ; } this . _state . path = complete_path ; return ; } } delete this . _state . activeNodes [ activeNode . getID ( ) ] ; active_nodes_ids . shift ( ) ; -- nr_active_nodes ; } this . _state . path = [ ] ; return ; } augmentation ( ) { const min_capacity = this . getBottleneckCapacity ( ) ; for ( let i = 0 ; i < this . _state . path . length - 1 ; i ++ ) { const node_a = this . _state . path [ i ] , node_b = this . _state . path [ i + 1 ] ; let edge = this . _state . residGraph . getEdgeById ( node_a . getID ( ) + "_" + node_b . getID ( ) ) ; const reverse_edge = this . _state . residGraph . getEdgeById ( node_b . getID ( ) + "_" + node_a . getID ( ) ) ; this . _state . residGraph . getEdgeById ( edge . getID ( ) ) . setWeight ( edge . getWeight ( ) - min_capacity ) ; this . _state . residGraph . getEdgeById ( reverse_edge . getID ( ) ) . setWeight ( reverse_edge . getWeight ( ) + min_capacity ) ; edge = this . _state . residGraph . getEdgeById ( edge . getID ( ) ) ; if ( ! edge . getWeight ( ) ) { if ( this . _state . tree [ node_a . getID ( ) ] == this . _state . tree [ node_b . getID ( ) ] ) { if ( this . _state . tree [ node_b . getID ( ) ] == "S" ) { delete this . _state . parents [ node_b . getID ( ) ] ; this . _state . orphans [ node_b . getID ( ) ] = node_b ; } if ( this . _state . tree [ node_a . getID ( ) ] == "T" ) { delete this . _state . parents [ node_a . getID ( ) ] ; this . _state . orphans [ node_a . getID ( ) ] = node_a ; } } } } } adoption ( ) { const orphans_ids = Object . keys ( this . _state . orphans ) ; let orphans_size = orphans_ids . length ; while ( orphans_size ) { const orphan = this . _state . orphans [ orphans_ids [ 0 ] ] ; delete this . _state . orphans [ orphan . getID ( ) ] ; orphans_ids . shift ( ) ; -- orphans_size ; const edges = this . _state . tree [ orphan . getID ( ) ] == "S" ? orphan . inEdges ( ) : orphan . outEdges ( ) ; const edge_ids = Object . keys ( edges ) ; const edge_length = edge_ids . length ; let found = false ; for ( let i = 0 ; i < edge_length ; i ++ ) { let edge = edges [ edge_ids [ i ] ] ; let neighbor = this . _state . tree [ orphan . getID ( ) ] == "S" ? edge . getNodes ( ) . a : edge . getNodes ( ) . b ; if ( this . _state . tree [ orphan . getID ( ) ] == this . _state . tree [ neighbor . getID ( ) ] && edge . getWeight ( ) ) { const neighbor_root_path = this . getPathToRoot ( neighbor ) ; const neighbor_root = neighbor_root_path [ neighbor_root_path . length - 1 ] ; if ( neighbor_root . getID ( ) == this . _sink . getID ( ) || neighbor_root . getID ( ) == this . _source . getID ( ) ) { this . _state . parents [ orphan . getID ( ) ] = neighbor ; found = true ; break ; } } } if ( found ) { continue ; } for ( let i = 0 ; i < edge_length ; i ++ ) { let edge = edges [ edge_ids [ i ] ] ; let neighbor = this . _state . tree [ orphan . getID ( ) ] == "S" ? edge . getNodes ( ) . a : edge . getNodes ( ) . b ; if ( this . _state . tree [ orphan . getID ( ) ] == this . _state . tree [ neighbor . getID ( ) ] ) { if ( edge . getWeight ( ) ) { this . _state . activeNodes [ neighbor . getID ( ) ] = neighbor ; } if ( this . _state . parents [ neighbor . getID ( ) ] == null ) { continue ; } if ( this . _state . parents [ neighbor . getID ( ) ] . getID ( ) == orphan . getID ( ) ) { this . _state . orphans [ neighbor . getID ( ) ] = neighbor ; orphans_ids . push ( neighbor . getID ( ) ) ; ++ orphans_size ; delete this . _state . parents [ neighbor . getID ( ) ] ; } } } const orphan_tree = this . _state . tree [ orphan . getID ( ) ] ; if ( orphan_tree == "S" ) { delete this . _state . treeS [ orphan . getID ( ) ] ; delete this . _state . tree [ orphan . getID ( ) ] ; } else if ( orphan_tree == "T" ) { delete this . _state . treeT [ orphan . getID ( ) ] ; delete this . _state . tree [ orphan . getID ( ) ] ; } delete this . _state . activeNodes [ orphan . getID ( ) ] ; } } prepareMCMFStandardConfig ( ) { return { directed : true , } ; } } export { MCMFBoykov } ;