Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package Domain;
- import java.util.*;
- import Utils.MyException;
- import Utils.Pair;
- public class AlgorithmNewman<T> extends Algorithm {
- private Grafo Graf;
- private double Infinit;
- private int Size;
- private int Limite;
- //private HashMap<String, Integer> edgeBW;
- private HashMap<T,LinkedList<T>> padres;
- private HashMap<T,HashMap<T,Integer>> edgeBW;
- private HashMap<T, HashMap<T,HashMap<T,LinkedList<T>>>> camino;
- private HashMap<T, LinkedList<T>> Acut;
- private AlgorithmEntrada Entrada;
- private AlgorithmSortida Sortida;
- public AlgorithmNewman(Grafo g, int limite) throws MyException {
- Limite = limite;
- Infinit = Double.MAX_VALUE;
- Graf = new Grafo(g);
- Size = Graf.obtenerNumVerts();
- //edgeBW = new HashMap<String, Integer>();
- edgeBW = new HashMap<T,HashMap<T,Integer>>();
- camino = new HashMap<T, HashMap<T,HashMap<T,LinkedList<T>>>>();
- padres = new HashMap<T, LinkedList<T>>();
- Acut = new HashMap<T, LinkedList<T>>();
- }
- public AlgorithmNewman() {
- Graf = null;
- Infinit = -1;
- Size = -1;
- Limite = -1;
- edgeBW = new HashMap<T,HashMap<T,Integer>>();
- Entrada = null;
- Sortida = null;
- camino = new HashMap<T, HashMap<T,HashMap<T,LinkedList<T>>>>();
- Acut = new HashMap<T, LinkedList<T>>();
- padres = new HashMap<T, LinkedList<T>>();
- }
- @Override
- public void execute(AlgorithmEntrada ae, AlgorithmSortida as) throws MyException {
- Entrada = ae;
- Sortida = as;
- Graf = Entrada.obtenirGraf();
- Size = Graf.obtenerNumVerts();
- Limite = 7;
- Infinit = Double.MAX_VALUE;
- padres = new HashMap<T, LinkedList<T>>();
- start();
- Sortida.afegirComunitats(generarSortida());
- }
- public Vector<Vector> generarSortida() throws MyException{
- HashMap<Integer, Vector> ret = new HashMap<Integer, Vector>();
- int c = 0;
- Vector vs = Graf.obtenerVertices();
- HashMap<Object, Boolean> vist = new HashMap<Object, Boolean>();
- for (Object v : vs) vist.put(v, false);
- Queue<Object> pq = new PriorityQueue<Object>();
- for (Object vi : vs) {
- if(!vist.get(vi)){
- pq.add(vi);
- ++c;
- }
- while(!pq.isEmpty()){
- Object u = pq.poll();
- if (!vist.get(u)){
- Vector ve = ret.get(c);
- if (ve == null) ve = new Vector();
- ve.add(u);
- ret.put(c, ve);
- vist.put(u, true);
- Vector a = Graf.obtenerAdyacencias(u);
- for (Object va : a) {
- pq.add(va);
- }
- }
- }
- }
- return new Vector(Arrays.asList(ret.values().toArray()));
- }
- public void start() throws MyException{
- int i = 1;
- Boolean b = false;
- int tam = Graf.obtenerNumVerts();
- Vector<T> vs = Graf.obtenerVertices();
- while(i < (double)Math.sqrt(tam)){
- for (T o : vs) {
- for (T d : vs) {
- if (b){
- if(calrecalcular(o,d)){
- reduir(o,d);
- buscarcamins(o,d);
- beetweeness(o,d);
- }
- }
- else{
- b = true;
- HashMap<T, HashMap<T, LinkedList<T>>> hash1 = new HashMap<T, HashMap<T,LinkedList<T>>>();
- HashMap<T, LinkedList<T>> hash2 = new HashMap<T, LinkedList<T>>();
- if (!camino.containsKey(o)) camino.put(o, hash1);
- LinkedList<T> padrel = new LinkedList<T>();
- padrel.add(d);
- hash2.put(d, padrel);
- hash1 = camino.get(o);
- hash1.put(d, hash2);
- camino.put(o, hash1);
- buscarcamins(o,d); // arestas con los caminos mas cortos
- beetweeness(o,d);
- }
- }
- }
- cut();
- ++i;
- }
- }
- private void reduir(T origen, T Final){
- T node;
- LinkedList<T> l = new LinkedList<T>();
- l.add(Final);
- while (!l.isEmpty()) {
- node = l.pollFirst();
- LinkedList<T> adjace = new LinkedList<T>();
- if (padres.containsKey(node)){
- adjace = padres.get(node);
- }
- HashMap<T, Integer> aux = new HashMap<>();
- LinkedList<T> Set = new LinkedList<T>();
- T nn;
- while(!adjace.isEmpty()) {
- nn = adjace.pollFirst();
- Set.add(nn);
- if(edgeBW.containsKey(node)){
- aux = edgeBW.get(node);
- if(aux.containsKey(nn)){
- Integer pes = aux.get(nn);
- pes = pes - 1;
- if (pes > 0.0) {
- aux.put(nn, pes);
- edgeBW.put(node, aux);
- }
- }
- }
- if(edgeBW.containsKey(nn)){
- aux = edgeBW.get(nn);
- if(aux.containsKey(node)){
- Integer pes = aux.get(node);
- pes = pes - 1;
- if (pes > 0.0) {
- aux.put(node, pes);
- edgeBW.put(nn, aux);
- }
- }
- }
- if (!nn.equals(origen)) {
- l.add(nn);
- }
- }
- padres.put(node, Set);
- }
- }
- private void buscarcamins(T origen, T Final) throws MyException{
- Vector<T> vs = Graf.obtenerVertices();
- HashMap<T, Double> d = new HashMap<T, Double>();
- for (T v : vs) d.put(v, Infinit);
- HashMap<T, T> p = new HashMap<T, T>();
- HashMap<T, Boolean> vist = new HashMap<T, Boolean>();
- for (T v : vs) vist.put(v, false);
- Queue<Pair<Double, T>> pq = new PriorityQueue<Pair<Double,T>>();
- pq.add(new Pair<Double, T>(0.0, origen));
- d.put(origen, 0.0);
- vist.put(origen, true);
- while(!pq.isEmpty()){
- Pair<Double, T> tmp = pq.poll();
- T u = tmp.Second;
- Vector<T> a = Graf.obtenerAdyacencias(u);
- for (T t : a) {
- Double peso = Graf.obtenerPesoArco(u, t);
- if (vist.get(u)){
- if (d.get(t) > d.get(u) + peso){
- LinkedList<T> pad = new LinkedList<T>();
- pad.add(u);
- padres.put(t,pad);
- pq.add(new Pair<Double, T>(d.get(t), t));
- d.put(t, d.get(u) + peso);
- }
- else if(d.get(t) == (d.get(u) + peso)){
- LinkedList<T> pad = padres.get(t);
- pad.add(u);
- //TODO mirar si se auto actualiza
- }
- }
- else if(!vist.get(u)){
- vist.put(u, true);
- if (!t.equals(Final))pq.add(new Pair<Double, T>(d.get(t), t));
- d.put(t, d.get(u) + peso);
- LinkedList<T> aux = new LinkedList<T>();
- aux.add(u);
- padres.put(t, aux);
- }
- }
- }
- }
- private void beetweeness(T origen, T Final) throws MyException{
- HashMap<T, HashMap<T, LinkedList<T>>> hash1 = new HashMap<T, HashMap<T,LinkedList<T>>>();
- HashMap<T, LinkedList<T>> hash2 = new HashMap<T, LinkedList<T>>();
- LinkedList<T> padrel = new LinkedList<T>();
- LinkedList<T> pq = new LinkedList<T>();
- pq.add(Final);
- while(!pq.isEmpty()){
- T u = pq.poll();
- if(padres.containsKey(u))padrel = padres.get(u);
- LinkedList<T> aux = new LinkedList<T>();
- while(!padrel.isEmpty()){
- T t = padrel.poll();
- aux.add(t);
- if (edgeBW.containsKey(u)) {
- HashMap<T,Integer> ebi = edgeBW.get(u);
- if (ebi.containsKey(t)){
- Integer BW = ebi.get(t);
- ebi.put(t, BW+1);
- }
- else{
- ebi.put(t, 1);
- }
- }
- else{
- HashMap<T,Integer> ebi = new HashMap<T, Integer>();
- ebi.put(t, 1);
- edgeBW.put(u, ebi);
- }
- if (edgeBW.containsKey(t)) {
- HashMap<T,Integer> ebi = edgeBW.get(t);
- if (ebi.containsKey(u)){
- Integer BW = ebi.get(u);
- ebi.put(u, BW+1);
- }
- else{
- ebi.put(u, 1);
- }
- }
- else{
- HashMap<T,Integer> ebi = new HashMap<T, Integer>();
- ebi.put(u, 1);
- edgeBW.put(t, ebi);
- }
- }
- padres.put(u, aux);
- hash1 = camino.get(origen);
- hash2 = hash1.get(Final);
- hash2.put(u,aux);
- camino.put(origen,hash1);
- }
- }
- private void cut() throws MyException {
- int max = 0;
- HashMap<T, LinkedList<T>> eliminats = new HashMap<T, LinkedList<T>>();
- Acut = new HashMap<T, LinkedList<T>>();
- for (T o : edgeBW.keySet()) {
- HashMap<T, Integer> aresta = new HashMap<>();
- aresta = edgeBW.get(o);
- for (T d : aresta.keySet()) {
- LinkedList<T> Aux = new LinkedList<T>();
- int aux = aresta.get(d);
- if(aux > max){
- Acut = new HashMap<T, LinkedList<T>>();
- Aux.add(d);
- Acut.put(o, Aux);
- max = aux;
- }
- else if (aux == max) {
- if(Acut.containsKey(o) || Acut.containsKey(d)){
- if(Acut.containsKey(o)){
- Aux = Acut.get(o);
- Aux.add(d);
- Acut.put(o, Aux);
- }
- else if(Acut.containsKey(d)){
- Aux = Acut.get(d);
- Aux.add(o);
- Acut.put(d, Aux);
- }
- else{
- Aux.add(d);
- Acut.put(o, Aux);
- max = aresta.get(d);
- }
- }
- }
- }
- }
- for (T o : Acut.keySet()) {
- LinkedList<T> eliminat = new LinkedList<T>();
- LinkedList<T> cutset = new LinkedList<T>();
- cutset = Acut.get(o);
- while(!cutset.isEmpty()){
- T d = cutset.poll();
- eliminat.add(d);
- if(Graf.existearco(o, d)){
- Graf.eliminarArco(o, d);
- }
- edgeBW.get(o).remove(d);
- edgeBW.get(d).remove(o);
- }
- eliminats.put(o, eliminat);
- }
- }
- Boolean calrecalcular(T origen, T Final) {
- Boolean trobat = false;
- HashMap<T, LinkedList<T>> Set = new HashMap<>();
- for (T o : Acut.keySet()) {
- if (trobat) break;
- LinkedList<T> l = Acut.get(o);
- LinkedList<T> r = new LinkedList<T>();
- while (!l.isEmpty()) {
- T d = l.poll();
- r.add(d);
- Set = camino.get(origen).get(Final);
- if(Set.containsKey(o)){
- LinkedList<T> Aux = Set.get(o);
- if (Aux.contains(d)) {
- camino.get(origen).get(Final).clear();
- trobat = true;
- }
- }
- if (Set.containsKey(d)) {
- LinkedList<T> Aux = Set.get(d);
- if (Aux.contains(o)) {
- camino.get(origen).get(Final).clear();
- trobat = true;
- }
- }
- }
- Acut.put(o,r);
- }
- return trobat;
- }
- public String obtenerGrafo(){
- return Graf.toString();
- }
- public String printarComunidad() throws MyException{
- HashMap<Object, Integer> n2c = new HashMap<Object, Integer>();
- int c = 0;
- Vector vs = Graf.obtenerVertices();
- HashMap<Object, Boolean> vist = new HashMap<Object, Boolean>();
- for (Object v : vs) vist.put(v, false);
- Queue<Object> pq = new PriorityQueue<Object>();
- for (Object vi : vs) {
- if(!vist.get(vi)){
- pq.add(vi);
- ++c;
- }
- while(!pq.isEmpty()){
- Object u = pq.poll();
- if (!vist.get(u)){
- n2c.put(u, c);
- vist.put(u, true);
- Vector a = Graf.obtenerAdyacencias(u);
- for (Object va : a) {
- pq.add(va);
- }
- }
- }
- }
- return n2c.toString();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement