MODULE CHACO_Constants
      USE Precision
      IMPLICIT NONE
      PUBLIC
      
      INTEGER(KIND=i_word),PARAMETER::&
      CHACO_hypercube=0,CHACO_mesh1D=1,CHACO_mesh2D=2,CHACO_mesh3D=3,&
      CHACO_multilevel=1,CHACO_spectral=2,CHACO_inertial=3,&
      CHACO_linear=4,CHACO_local_KL=1,CHACO_local_none=2,&
      CHACO_RQI=1,CHACO_Lanczos=0,CHACO_dummy=-1
      
      
      END MODULE CHACO_Constants
      
      MODULE CHACO_Interface
      USE Precision
      USE CHACO_Constants
      USE Error_Handling
      USE System_Monitors
      USE Random_Numbers
      USE Graph_Algorithms
      USE Network_Data_Types
      IMPLICIT NONE
      PRIVATE
      PUBLIC::CHACO_InitializeMapping,CHACO_ComputeMapping,CHACO_DestroyMapping
      
      ML_EXTERNAL::CHACO_CInterface
      INTEGER::CHACO_CInterface
      
      PUBLIC::CHACO_Graph,CHACO_Strategy,CHACO_Architecture,CHACO_Mapping_Partitioning
      TYPE CHACO_Graph
      PRIVATE
      INTEGER(KIND=i_word)::n_vertices=0,n_edges=0
      INTEGER(KIND=i_word),DIMENSION(:),POINTER::start,adjacency,vwgts,incident
      REAL(KIND=r_word),DIMENSION(:),POINTER::ewgts,&
      x=>NULL(),y=>NULL(),z=>NULL()
      ENDTYPE
      TYPE CHACO_Strategy
      INTEGER(KIND=i_word)::sequence=0,&
      global_method=CHACO_dummy,local_method=CHACO_dummy,&
      rqi_flag=0,vmax=1,ndims=1
      REAL(KIND=r_dp)::eigtol=1E-3_r_word
      ENDTYPE
      TYPE CHACO_Architecture
      INTEGER(KIND=i_word)::architecture=1,ndims_tot=1,mesh_dims(3)=(/1,1,1/)
      ENDTYPE
      TYPE CHACO_Mapping_Partitioning
      TYPE(Directed_Graph),POINTER::graph
      TYPE(Support_Tree_Mapping),POINTER::ST_mapping
      TYPE(CHACO_Graph)::chaco_graph
      TYPE(CHACO_Strategy)::strategy
      TYPE(CHACO_Architecture)::architecture
      REAL(KIND=r_word),DIMENSION(:,:),POINTER::coordinates=>NULL()
      INTEGER(KIND=i_word),POINTER::i_dummy=>NULL()
      REAL(KIND=r_word),POINTER::r_dummy=>NULL()
      LOGICAL::allocated_mapping=.FALSE.
      ENDTYPE
      
      CONTAINS
      
      
      SUBROUTINE CHACO_InitializeMapping(mapping_partitioning)
      IMPLICIT NONE
      TYPE(CHACO_Mapping_Partitioning),INTENT(INOUT),TARGET::mapping_partitioning
      
      TYPE(Directed_Graph),POINTER::graph
      INTEGER::alloc_status,result
      INTEGER(KIND=i_word)::n_vertices,n_edges
      INTEGER(KIND=i_wp)::n_special_nodes,n_nodes,n_special_arcs,n_arcs
      LOGICAL::valid_graph
      
      graph=>mapping_partitioning%graph
      valid_graph=.TRUE.
      IF(.NOT.ASSOCIATED(graph))THEN
      valid_graph=.FALSE.
      ELSE
      IF(.NOT.ASSOCIATED(graph%heads_tails))valid_graph=.FALSE.
      END IF
      IF(.NOT.valid_graph)THEN
      CALL CriticalError(message="Incomplete or no graph passed to CHACO library",&
      caller="CHACO_InitializeMapping")
      RETURN
      END IF
      
      n_special_nodes=graph%n_special_nodes
      n_nodes=graph%n_nodes
      n_special_arcs=graph%n_special_arcs
      n_arcs=graph%n_arcs
      
      n_vertices=n_nodes+n_special_nodes+1
      n_edges=2*(n_arcs+n_special_arcs+1)
      
      IF(.NOT.ASSOCIATED(mapping_partitioning%ST_mapping))THEN
      ALLOCATE(mapping_partitioning%ST_mapping,STAT=alloc_status)
      mapping_partitioning%allocated_mapping=.TRUE.
      END IF
      
      
      IF(.NOT.ASSOCIATED(mapping_partitioning%ST_mapping%arcs_weights))THEN
      ALLOCATE(mapping_partitioning%ST_mapping%arcs_weights(-n_special_arcs:n_arcs),STAT=alloc_status)
      CALL RecordAllocation(n_elements=(n_arcs)-(-n_special_arcs)+1,mold=1.0_r_wp,&
      caller="CHACO_InitializeMapping",alloc_status=alloc_status)
      END IF
      
      
      IF(.NOT.ASSOCIATED(mapping_partitioning%ST_mapping%nodes_mapping))THEN
      ALLOCATE(mapping_partitioning%ST_mapping%nodes_mapping(-n_special_nodes:n_nodes),STAT=alloc_status)
      CALL RecordAllocation(n_elements=(n_nodes)-(-n_special_nodes)+1,mold=1_i_wp,&
      caller="CHACO_InitializeMapping",alloc_status=alloc_status)
      END IF
      
      IF(.NOT.ASSOCIATED(mapping_partitioning%chaco_graph%start))THEN
      ALLOCATE(mapping_partitioning%chaco_graph%start(0:n_vertices+1),STAT=alloc_status)
      CALL RecordAllocation(n_elements=(n_vertices+1)-(0)+1,mold=1_i_word,&
      caller="CHACO_InitializeMapping",alloc_status=alloc_status)
      END IF
      
      IF(.NOT.ASSOCIATED(mapping_partitioning%chaco_graph%adjacency))THEN
      ALLOCATE(mapping_partitioning%chaco_graph%adjacency(0:n_edges),STAT=alloc_status)
      CALL RecordAllocation(n_elements=(n_edges)-(0)+1,mold=1_i_word,&
      caller="CHACO_InitializeMapping",alloc_status=alloc_status)
      END IF
      
      IF(.NOT.ASSOCIATED(mapping_partitioning%chaco_graph%incident))THEN
      ALLOCATE(mapping_partitioning%chaco_graph%incident(0:n_edges),STAT=alloc_status)
      CALL RecordAllocation(n_elements=(n_edges)-(0)+1,mold=1_i_word,&
      caller="CHACO_InitializeMapping",alloc_status=alloc_status)
      END IF
      
      IF(.NOT.ASSOCIATED(mapping_partitioning%chaco_graph%ewgts))THEN
      ALLOCATE(mapping_partitioning%chaco_graph%ewgts(0:n_edges),STAT=alloc_status)
      CALL RecordAllocation(n_elements=(n_edges)-(0)+1,mold=1_r_word,&
      caller="CHACO_InitializeMapping",alloc_status=alloc_status)
      END IF
      
      CALL CreateAdjacencyArrays(node_offset=n_special_nodes,arc_offset=n_special_arcs,&
      heads_tails=graph%heads_tails,neighbours=mapping_partitioning%chaco_graph%adjacency,&
      my_neighbours=mapping_partitioning%chaco_graph%start,incident_arcs=mapping_partitioning%chaco_graph%incident,&
      include_loops=.FALSE.,n_edges=n_edges)
      mapping_partitioning%chaco_graph%n_vertices=n_vertices
      mapping_partitioning%chaco_graph%n_edges=n_edges
      
      IF(ASSOCIATED(mapping_partitioning%coordinates).AND.(mapping_partitioning%strategy%global_method==CHACO_inertial))THEN
      
      
      IF(.NOT.ASSOCIATED(mapping_partitioning%chaco_graph%x))THEN
      ALLOCATE(mapping_partitioning%chaco_graph%x(0:n_vertices),STAT=alloc_status)
      CALL RecordAllocation(n_elements=(n_vertices)-(0)+1,mold=1.0_r_word,&
      caller="CHACO_InitializeMapping",alloc_status=alloc_status)
      END IF
      mapping_partitioning%chaco_graph%x=mapping_partitioning%coordinates(1,:)
      IF(SIZE(mapping_partitioning%coordinates,DIM=1)>=2)THEN
      
      IF(.NOT.ASSOCIATED(mapping_partitioning%chaco_graph%y))THEN
      ALLOCATE(mapping_partitioning%chaco_graph%y(0:n_vertices),STAT=alloc_status)
      CALL RecordAllocation(n_elements=(n_vertices)-(0)+1,mold=1.0_r_word,&
      caller="CHACO_InitializeMapping",alloc_status=alloc_status)
      END IF
      mapping_partitioning%chaco_graph%y=mapping_partitioning%coordinates(2,:)
      END IF
      IF(SIZE(mapping_partitioning%coordinates,DIM=1)>=3)THEN
      
      IF(.NOT.ASSOCIATED(mapping_partitioning%chaco_graph%z))THEN
      ALLOCATE(mapping_partitioning%chaco_graph%z(0:n_vertices),STAT=alloc_status)
      CALL RecordAllocation(n_elements=(n_vertices)-(0)+1,mold=1.0_r_word,&
      caller="CHACO_InitializeMapping",alloc_status=alloc_status)
      END IF
      mapping_partitioning%chaco_graph%z=mapping_partitioning%coordinates(3,:)
      END IF
      ELSE IF(.NOT.ASSOCIATED(mapping_partitioning%coordinates).AND.(mapping_partitioning%strategy%global_method==CHACO_inertial))&
     &THEN
      mapping_partitioning%strategy%global_method=CHACO_linear
      CALL NonCriticalError(message="No coordinates passed to CHACO with inertial partitioning",&
      caller="CHACO_InitializeMapping")
      END IF
      
      END SUBROUTINE CHACO_InitializeMapping
      
      
      
      SUBROUTINE CHACO_ComputeMapping(mapping_partitioning,mapping_offset)
      IMPLICIT NONE
      TYPE(CHACO_Mapping_Partitioning),INTENT(INOUT),TARGET::mapping_partitioning
      INTEGER(KIND=i_wp),INTENT(IN),OPTIONAL::mapping_offset
      
      INTEGER(KIND=i_wp)::arc
      INTEGER(KIND=i_word)::edge,seed,max_chaco_weight
      REAL(KIND=r_wp)::max_weight
      INTEGER::alloc_status,result
      
      max_weight=MAXVAL(mapping_partitioning%ST_mapping%arcs_weights)
      max_chaco_weight=HUGE(1_i_word)/10/(mapping_partitioning%chaco_graph%n_vertices+mapping_partitioning%chaco_graph%n_edges)
      DO edge=1,mapping_partitioning%chaco_graph%n_edges
      arc=mapping_partitioning%chaco_graph%incident(edge)
      mapping_partitioning%chaco_graph%ewgts(edge)=REAL(INT(REAL(max_chaco_weight)*mapping_partitioning%ST_mapping%arcs_weights(ar&
     &c)/max_weight)+1)
      END DO
      mapping_partitioning%chaco_graph%ewgts(0)=0.0_r_wp
      
      
      CALL RandomUniform(seed)
      result=CHACO_CInterface(%VAL(mapping_partitioning%chaco_graph%n_vertices),mapping_partitioning%chaco_graph%start(1),mapping_&
     &partitioning%chaco_graph%adjacency(0),&
      mapping_partitioning%i_dummy,mapping_partitioning%chaco_graph%ewgts(1),&
      mapping_partitioning%chaco_graph%x(1),mapping_partitioning%chaco_graph%y(1),mapping_partitioning%chaco_graph%z(1),&
      mapping_partitioning%i_dummy,mapping_partitioning%i_dummy,&
      mapping_partitioning%ST_mapping%nodes_mapping(-mapping_partitioning%graph%n_special_nodes),&
      %VAL(mapping_partitioning%architecture%architecture),%VAL(mapping_partitioning%architecture%ndims_tot),&
      mapping_partitioning%architecture%mesh_dims(1),mapping_partitioning%r_dummy,&
      %VAL(mapping_partitioning%strategy%sequence),&
      %VAL(mapping_partitioning%strategy%global_method),%VAL(mapping_partitioning%strategy%local_method),&
      %VAL(mapping_partitioning%strategy%rqi_flag),%VAL(mapping_partitioning%strategy%vmax),%VAL(mapping_partitioning%strategy%ndi&
     &ms),&
      %VAL(mapping_partitioning%strategy%eigtol),%VAL(seed))
      IF(result>0)CALL CriticalError("CHACO did not partition the graph successfully",&
      caller="CHACO_ComputeMapping")
      
      IF(mapping_partitioning%strategy%sequence==1)THEN
      IF(PRESENT(mapping_offset))THEN
      mapping_partitioning%ST_mapping%nodes_mapping=INT(REAL(mapping_partitioning%ST_mapping%nodes_mapping)*&
      REAL(mapping_partitioning%architecture%ndims_tot)/REAL(mapping_partitioning%chaco_graph%n_vertices))+mapping_offset
      ELSE
      mapping_partitioning%ST_mapping%nodes_mapping=INT(REAL(mapping_partitioning%ST_mapping%nodes_mapping)*&
      REAL(mapping_partitioning%architecture%ndims_tot)/REAL(mapping_partitioning%chaco_graph%n_vertices))
      END IF
      ELSE
      IF(PRESENT(mapping_offset))mapping_partitioning%ST_mapping%nodes_mapping=mapping_partitioning%ST_mapping%nodes_mapping+mappi&
     &ng_offset
      END IF
      
      END SUBROUTINE CHACO_ComputeMapping
      
      
      
      SUBROUTINE CHACO_DestroyMapping(mapping_partitioning)
      IMPLICIT NONE
      TYPE(CHACO_Mapping_Partitioning),INTENT(INOUT),TARGET::mapping_partitioning
      
      INTEGER::alloc_status,result
      
      IF(mapping_partitioning%allocated_mapping)THEN
      
      IF(ASSOCIATED(mapping_partitioning%ST_mapping%arcs_weights))THEN
      CALL RecordAllocation(n_elements=-INT(SIZE(mapping_partitioning%ST_mapping%arcs_weights),KIND=i_wp),mold=1.0_r_wp)
      DEALLOCATE(mapping_partitioning%ST_mapping%arcs_weights,STAT=alloc_status)
      END IF
      
      IF(ASSOCIATED(mapping_partitioning%ST_mapping%nodes_mapping))THEN
      CALL RecordAllocation(n_elements=-INT(SIZE(mapping_partitioning%ST_mapping%nodes_mapping),KIND=i_wp),mold=1_i_wp)
      DEALLOCATE(mapping_partitioning%ST_mapping%nodes_mapping,STAT=alloc_status)
      END IF
      DEALLOCATE(mapping_partitioning%ST_mapping,STAT=alloc_status)
      END IF
      
      
      IF(ASSOCIATED(mapping_partitioning%chaco_graph%start))THEN
      CALL RecordAllocation(n_elements=-INT(SIZE(mapping_partitioning%chaco_graph%start),KIND=i_wp),mold=1_i_word)
      DEALLOCATE(mapping_partitioning%chaco_graph%start,STAT=alloc_status)
      END IF
      
      IF(ASSOCIATED(mapping_partitioning%chaco_graph%adjacency))THEN
      CALL RecordAllocation(n_elements=-INT(SIZE(mapping_partitioning%chaco_graph%adjacency),KIND=i_wp),mold=1_i_word)
      DEALLOCATE(mapping_partitioning%chaco_graph%adjacency,STAT=alloc_status)
      END IF
      
      IF(ASSOCIATED(mapping_partitioning%chaco_graph%incident))THEN
      CALL RecordAllocation(n_elements=-INT(SIZE(mapping_partitioning%chaco_graph%incident),KIND=i_wp),mold=1_i_word)
      DEALLOCATE(mapping_partitioning%chaco_graph%incident,STAT=alloc_status)
      END IF
      
      IF(ASSOCIATED(mapping_partitioning%chaco_graph%ewgts))THEN
      CALL RecordAllocation(n_elements=-INT(SIZE(mapping_partitioning%chaco_graph%ewgts),KIND=i_wp),mold=1_i_word)
      DEALLOCATE(mapping_partitioning%chaco_graph%ewgts,STAT=alloc_status)
      END IF
      
      
      IF(ASSOCIATED(mapping_partitioning%chaco_graph%x))THEN
      CALL RecordAllocation(n_elements=-INT(SIZE(mapping_partitioning%chaco_graph%x),KIND=i_wp),mold=1.0_r_word)
      DEALLOCATE(mapping_partitioning%chaco_graph%x,STAT=alloc_status)
      END IF
      
      IF(ASSOCIATED(mapping_partitioning%chaco_graph%y))THEN
      CALL RecordAllocation(n_elements=-INT(SIZE(mapping_partitioning%chaco_graph%y),KIND=i_wp),mold=1.0_r_word)
      DEALLOCATE(mapping_partitioning%chaco_graph%y,STAT=alloc_status)
      END IF
      
      IF(ASSOCIATED(mapping_partitioning%chaco_graph%z))THEN
      CALL RecordAllocation(n_elements=-INT(SIZE(mapping_partitioning%chaco_graph%z),KIND=i_wp),mold=1.0_r_word)
      DEALLOCATE(mapping_partitioning%chaco_graph%z,STAT=alloc_status)
      END IF
      
      END SUBROUTINE CHACO_DestroyMapping
      
      
      
      END MODULE CHACO_Interface