root/InOutExpositor/oGraph.pde

//////////////////////////////////////////////////////////////////////////
// Class with sub graphs + dijkstra for minimal distances
class GraphUtils {
  Vector groups ;
  int idOfBiggestGroup ;
  
  GraphUtils( Vector cells, boolean[] config) {
    groups = new Vector() ;
    buildSubGroups() ;
  }
  ////////////////////////////////////////////////////////
  void buildSubGroups() {
    int maxClientInAGroup = 0 ;
    int currentIdOfGroup = 0 ;
    idOfBiggestGroup = 0 ;
    
    boolean aloneFound = true ;
    boolean[] made = new boolean[nClients] ;
    int done = 0 ;

    while(aloneFound && done<nClients) {
      //print("Doing a Group : "+currentIdOfGroup+"\n") ;

      Vector G = new Vector() ;
      ///// Searching alone point de depart
      aloneFound = false ;
      int af = -1 ;
      while(!aloneFound) {
        af++ ;
        if(af==nClients) break ;
        if(!made[af]) {
          aloneFound = true ;
          G.addElement( getClient(af) ) ;
          made[af] = true ;
          //print("Searching from "+af+"\n") ;
        }
      }

      ///// Filling the group
      boolean decouvrNouv = true ;
      while(decouvrNouv) {
        decouvrNouv = false ;
        for(int u=0;u<G.size();u++) {
          Vector amis = getOutLinkedClients( (Client)G.elementAt(u) ) ;
          Vector amisI = getInLinkedClients( (Client)G.elementAt(u) ) ;
          for(int k=0;k<amisI.size();k++) amis.addElement( amisI.elementAt(k) ) ;
          for(int v=0;v<amis.size();v++) {
            Client newAmi = (Client)amis.elementAt(v) ;
            if( !G.contains(newAmi) ) {
              decouvrNouv = true ;
              G.addElement(newAmi) ;
              done++ ;
              if(done>maxClientInAGroup) {
               maxClientInAGroup = done ;
               idOfBiggestGroup = currentIdOfGroup ;
              }
              made[newAmi.id] = true ;
              //print("Ading one Cell\n") ;
            }
          }
        }
      }
      //// the group is finished
      if(aloneFound) groups.addElement(G) ;
      currentIdOfGroup ++ ;
    }
  }
  Client getRandomOfBiggestGroup() {
    Vector gp = (Vector)groups.elementAt( idOfBiggestGroup ) ;
    int id = int( random(0,gp.size()) ) ;
    Client res = (Client)gp.elementAt( id ) ;
    return res ;
  }
  ////////////////////////////////////////////
  Pt getGroupUniformPosition(int i, int N) { // quadrillage uniforme
    int nbCoteCarre = int(sqrt(N))+1 ;
    int px = i%(nbCoteCarre) ;
    int py = int(i/nbCoteCarre) ;
    float marg = width/4 ;
    float distEntreX = (width - 2*marg)/(nbCoteCarre-1) ;
    float distEntreY = (height - 2*marg)/(nbCoteCarre-1) ;
    Pt res = new Pt( marg+px*distEntreX, marg+py*distEntreY ) ;
    return res ;
  }
  void moveClientsByGroups() {
  int ng = groups.size() ;
  float x,y,gx,gy ;
  print("NB de groupes :"+ng +"\n") ;
  for(int i=0;i<ng;i++) {
    float dg = 40 ; // random in groups
    
    Pt groupPos = getGroupUniformPosition(i,ng) ;

    int nh = ((Vector)groups.elementAt(i)).size() ;
    for(int j=0;j<nh;j++) {
      //x = 20 + width*j/nh ;
      x = groupPos.x + random(-dg,dg); 
      y = groupPos.y + random(-dg,dg) ;
      ((Client)((Vector)groups.elementAt(i)).elementAt(j)).moveTo(x,y) ;
      //stri += " ,"+ ((Cell)((Vector)gu.groups.elementAt(i)).elementAt(j)).id ;
    }
    //print("Grp "+i+" :"+stri+"\n");
  }
  }
  ////////////////////////////////////////////////////////
  float getDijkstraDistance( Vector group, int idDeb, int idFin) {
    int dd = Dijkstra( (Vector)clientGraphUtils.groups.elementAt(0), idDeb, idFin ) ;
    print("distance("+selected.id+","+highlighted.id+ ")= "+dd +"\n") ;
    return dd ;
  }
  ////////////////////////////////////////////////////////
  int dijPoids(int u, int v)
  {
    if(drawnState.isAnyLink(u,v)) return 1 ;
    else return 90 ;
  }
  int dijGetMin(Vector vus, Vector afaire, int[] distDij)
  {
    int resMin = 200 ;
    int res = -1 ;
    for(int k=0;k<afaire.size();k++) {

      int aid = ((Client)afaire.elementAt(k)).id ;
      for(int v=0;v<vus.size();v++) {
        int vid = ((Client)vus.elementAt(v)).id ;
        if(drawnState.isAnyLink(vid,aid)) {
          resMin = min( resMin, distDij[vid] + 1 ) ;
          if(resMin>=distDij[vid]+1) res = aid ;
        }
      }
    }
    print("Le minim trajet pese : "+resMin+"\n") ;
    return res ;
  }
  int Dijkstra(Vector g,int sdeb, int ff)
  {

    int[] dijDist = new int[nClients] ;
    int[] dijPrec = new int[nClients] ;

    for(int i=0;i<g.size();i++) {
      dijPrec[i]=-1 ;
      dijDist[i]=999 ;
    }
    dijDist[sdeb]=0 ;

    Vector afaire = new Vector() ;
    Vector vus = new Vector() ;
    vus.addElement( getClient(sdeb) ) ;
    for(int l=0;l<nClients;l++) {
      if(l!=sdeb)
        afaire.addElement( getClient(l) ) ;
    }

    int s1 = sdeb ;

    while( afaire.size()>0 ) {
      s1 = dijGetMin( vus, afaire, dijDist ) ; 
      print("Sommet Minimum : "+s1+"\nA faire = "+ afaire.size()+"\n") ;
      afaire.removeElement(getClient(s1)) ;
      vus.addElement(getClient(s1)) ;

      for(int i=0;i<nClients;i++) {
        if(drawnState.isAnyLink(i,s1)) {

          if( dijDist[s1] > (dijDist[i] + dijPoids(i,s1)) ) {
            dijDist[s1] = dijDist[i] + dijPoids(i,s1) ;
            dijPrec[s1] = i ;
          } 
        }
      }
    }
    return dijDist[ff] ;
  }
  ///////////////////////////////

}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////