API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jun 2nd, 2015
234
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.19 KB | None | 0 0
raw download clone embed print report
  1. package Domain;
  2.  
  3. import java.util.*;
  4.  
  5. import Utils.MyException;
  6. import Utils.Pair;
  7.  
  8. public class AlgorithmNewman<T> extends Algorithm {
  9. private Grafo Graf;
  10. private double Infinit;
  11. private int Size;
  12. private int Limite;
  13. //private HashMap<String, Integer> edgeBW;
  14. private HashMap<T,LinkedList<T>> padres;
  15. private HashMap<T,HashMap<T,Integer>> edgeBW;
  16. private HashMap<T, HashMap<T,HashMap<T,LinkedList<T>>>> camino;
  17. private HashMap<T, LinkedList<T>> Acut;
  18. private AlgorithmEntrada Entrada;
  19. private AlgorithmSortida Sortida;
  20.  
  21. public AlgorithmNewman(Grafo g, int limite) throws MyException {
  22. Limite = limite;
  23. Infinit = Double.MAX_VALUE;
  24. Graf = new Grafo(g);
  25. Size = Graf.obtenerNumVerts();
  26. //edgeBW = new HashMap<String, Integer>();
  27. edgeBW = new HashMap<T,HashMap<T,Integer>>();
  28. camino = new HashMap<T, HashMap<T,HashMap<T,LinkedList<T>>>>();
  29. padres = new HashMap<T, LinkedList<T>>();
  30. Acut = new HashMap<T, LinkedList<T>>();
  31. }
  32.  
  33. public AlgorithmNewman() {
  34. Graf = null;
  35. Infinit = -1;
  36. Size = -1;
  37. Limite = -1;
  38. edgeBW = new HashMap<T,HashMap<T,Integer>>();
  39. Entrada = null;
  40. Sortida = null;
  41. camino = new HashMap<T, HashMap<T,HashMap<T,LinkedList<T>>>>();
  42. Acut = new HashMap<T, LinkedList<T>>();
  43. padres = new HashMap<T, LinkedList<T>>();
  44. }
  45.  
  46. @Override
  47. public void execute(AlgorithmEntrada ae, AlgorithmSortida as) throws MyException {
  48. Entrada = ae;
  49. Sortida = as;
  50. Graf = Entrada.obtenirGraf();
  51. Size = Graf.obtenerNumVerts();
  52. Limite = 7;
  53. Infinit = Double.MAX_VALUE;
  54. padres = new HashMap<T, LinkedList<T>>();
  55. start();
  56. Sortida.afegirComunitats(generarSortida());
  57. }
  58.  
  59. public Vector<Vector> generarSortida() throws MyException{
  60. HashMap<Integer, Vector> ret = new HashMap<Integer, Vector>();
  61. int c = 0;
  62. Vector vs = Graf.obtenerVertices();
  63. HashMap<Object, Boolean> vist = new HashMap<Object, Boolean>();
  64. for (Object v : vs) vist.put(v, false);
  65. Queue<Object> pq = new PriorityQueue<Object>();
  66.  
  67. for (Object vi : vs) {
  68. if(!vist.get(vi)){
  69. pq.add(vi);
  70. ++c;
  71. }
  72. while(!pq.isEmpty()){
  73. Object u = pq.poll();
  74. if (!vist.get(u)){
  75. Vector ve = ret.get(c);
  76. if (ve == null) ve = new Vector();
  77. ve.add(u);
  78. ret.put(c, ve);
  79. vist.put(u, true);
  80. Vector a = Graf.obtenerAdyacencias(u);
  81. for (Object va : a) {
  82. pq.add(va);
  83. }
  84. }
  85. }
  86. }
  87. return new Vector(Arrays.asList(ret.values().toArray()));
  88. }
  89. public void start() throws MyException{
  90. int i = 1;
  91. Boolean b = false;
  92. int tam = Graf.obtenerNumVerts();
  93. Vector<T> vs = Graf.obtenerVertices();
  94. while(i < (double)Math.sqrt(tam)){
  95. for (T o : vs) {
  96. for (T d : vs) {
  97. if (b){
  98. if(calrecalcular(o,d)){
  99. reduir(o,d);
  100. buscarcamins(o,d);
  101. beetweeness(o,d);
  102. }
  103. }
  104. else{
  105. b = true;
  106. HashMap<T, HashMap<T, LinkedList<T>>> hash1 = new HashMap<T, HashMap<T,LinkedList<T>>>();
  107. HashMap<T, LinkedList<T>> hash2 = new HashMap<T, LinkedList<T>>();
  108. if (!camino.containsKey(o)) camino.put(o, hash1);
  109. LinkedList<T> padrel = new LinkedList<T>();
  110. padrel.add(d);
  111. hash2.put(d, padrel);
  112. hash1 = camino.get(o);
  113. hash1.put(d, hash2);
  114. camino.put(o, hash1);
  115. buscarcamins(o,d); // arestas con los caminos mas cortos
  116. beetweeness(o,d);
  117. }
  118. }
  119. }
  120. cut();
  121. ++i;
  122. }
  123. }
  124. private void reduir(T origen, T Final){
  125. T node;
  126. LinkedList<T> l = new LinkedList<T>();
  127. l.add(Final);
  128. while (!l.isEmpty()) {
  129. node = l.pollFirst();
  130. LinkedList<T> adjace = new LinkedList<T>();
  131. if (padres.containsKey(node)){
  132. adjace = padres.get(node);
  133. }
  134. HashMap<T, Integer> aux = new HashMap<>();
  135. LinkedList<T> Set = new LinkedList<T>();
  136. T nn;
  137. while(!adjace.isEmpty()) {
  138. nn = adjace.pollFirst();
  139. Set.add(nn);
  140. if(edgeBW.containsKey(node)){
  141. aux = edgeBW.get(node);
  142. if(aux.containsKey(nn)){
  143. Integer pes = aux.get(nn);
  144. pes = pes - 1;
  145. if (pes > 0.0) {
  146. aux.put(nn, pes);
  147. edgeBW.put(node, aux);
  148. }
  149. }
  150. }
  151. if(edgeBW.containsKey(nn)){
  152. aux = edgeBW.get(nn);
  153. if(aux.containsKey(node)){
  154. Integer pes = aux.get(node);
  155. pes = pes - 1;
  156. if (pes > 0.0) {
  157. aux.put(node, pes);
  158. edgeBW.put(nn, aux);
  159. }
  160. }
  161. }
  162. if (!nn.equals(origen)) {
  163. l.add(nn);
  164. }
  165. }
  166. padres.put(node, Set);
  167. }
  168. }
  169. private void buscarcamins(T origen, T Final) throws MyException{
  170. Vector<T> vs = Graf.obtenerVertices();
  171. HashMap<T, Double> d = new HashMap<T, Double>();
  172. for (T v : vs) d.put(v, Infinit);
  173. HashMap<T, T> p = new HashMap<T, T>();
  174. HashMap<T, Boolean> vist = new HashMap<T, Boolean>();
  175. for (T v : vs) vist.put(v, false);
  176. Queue<Pair<Double, T>> pq = new PriorityQueue<Pair<Double,T>>();
  177. pq.add(new Pair<Double, T>(0.0, origen));
  178. d.put(origen, 0.0);
  179. vist.put(origen, true);
  180. while(!pq.isEmpty()){
  181. Pair<Double, T> tmp = pq.poll();
  182. T u = tmp.Second;
  183. Vector<T> a = Graf.obtenerAdyacencias(u);
  184. for (T t : a) {
  185. Double peso = Graf.obtenerPesoArco(u, t);
  186. if (vist.get(u)){
  187. if (d.get(t) > d.get(u) + peso){
  188. LinkedList<T> pad = new LinkedList<T>();
  189. pad.add(u);
  190. padres.put(t,pad);
  191. pq.add(new Pair<Double, T>(d.get(t), t));
  192. d.put(t, d.get(u) + peso);
  193. }
  194. else if(d.get(t) == (d.get(u) + peso)){
  195. LinkedList<T> pad = padres.get(t);
  196. pad.add(u);
  197. //TODO mirar si se auto actualiza
  198. }
  199. }
  200. else if(!vist.get(u)){
  201. vist.put(u, true);
  202. if (!t.equals(Final))pq.add(new Pair<Double, T>(d.get(t), t));
  203. d.put(t, d.get(u) + peso);
  204. LinkedList<T> aux = new LinkedList<T>();
  205. aux.add(u);
  206. padres.put(t, aux);
  207. }
  208. }
  209. }
  210. }
  211.  
  212. private void beetweeness(T origen, T Final) throws MyException{
  213. HashMap<T, HashMap<T, LinkedList<T>>> hash1 = new HashMap<T, HashMap<T,LinkedList<T>>>();
  214. HashMap<T, LinkedList<T>> hash2 = new HashMap<T, LinkedList<T>>();
  215. LinkedList<T> padrel = new LinkedList<T>();
  216. LinkedList<T> pq = new LinkedList<T>();
  217.  
  218. pq.add(Final);
  219. while(!pq.isEmpty()){
  220. T u = pq.poll();
  221. if(padres.containsKey(u))padrel = padres.get(u);
  222. LinkedList<T> aux = new LinkedList<T>();
  223. while(!padrel.isEmpty()){
  224. T t = padrel.poll();
  225. aux.add(t);
  226. if (edgeBW.containsKey(u)) {
  227. HashMap<T,Integer> ebi = edgeBW.get(u);
  228. if (ebi.containsKey(t)){
  229. Integer BW = ebi.get(t);
  230. ebi.put(t, BW+1);
  231. }
  232. else{
  233. ebi.put(t, 1);
  234. }
  235. }
  236. else{
  237. HashMap<T,Integer> ebi = new HashMap<T, Integer>();
  238. ebi.put(t, 1);
  239. edgeBW.put(u, ebi);
  240. }
  241. if (edgeBW.containsKey(t)) {
  242. HashMap<T,Integer> ebi = edgeBW.get(t);
  243. if (ebi.containsKey(u)){
  244. Integer BW = ebi.get(u);
  245. ebi.put(u, BW+1);
  246. }
  247. else{
  248. ebi.put(u, 1);
  249. }
  250. }
  251. else{
  252. HashMap<T,Integer> ebi = new HashMap<T, Integer>();
  253. ebi.put(u, 1);
  254. edgeBW.put(t, ebi);
  255. }
  256. }
  257. padres.put(u, aux);
  258. hash1 = camino.get(origen);
  259. hash2 = hash1.get(Final);
  260. hash2.put(u,aux);
  261. camino.put(origen,hash1);
  262.  
  263.  
  264. }
  265. }
  266.  
  267. private void cut() throws MyException {
  268. int max = 0;
  269. HashMap<T, LinkedList<T>> eliminats = new HashMap<T, LinkedList<T>>();
  270. Acut = new HashMap<T, LinkedList<T>>();
  271. for (T o : edgeBW.keySet()) {
  272. HashMap<T, Integer> aresta = new HashMap<>();
  273. aresta = edgeBW.get(o);
  274. for (T d : aresta.keySet()) {
  275. LinkedList<T> Aux = new LinkedList<T>();
  276. int aux = aresta.get(d);
  277. if(aux > max){
  278. Acut = new HashMap<T, LinkedList<T>>();
  279. Aux.add(d);
  280. Acut.put(o, Aux);
  281. max = aux;
  282. }
  283. else if (aux == max) {
  284. if(Acut.containsKey(o) || Acut.containsKey(d)){
  285. if(Acut.containsKey(o)){
  286. Aux = Acut.get(o);
  287. Aux.add(d);
  288. Acut.put(o, Aux);
  289. }
  290. else if(Acut.containsKey(d)){
  291. Aux = Acut.get(d);
  292. Aux.add(o);
  293. Acut.put(d, Aux);
  294. }
  295. else{
  296. Aux.add(d);
  297. Acut.put(o, Aux);
  298. max = aresta.get(d);
  299. }
  300. }
  301. }
  302. }
  303. }
  304. for (T o : Acut.keySet()) {
  305. LinkedList<T> eliminat = new LinkedList<T>();
  306. LinkedList<T> cutset = new LinkedList<T>();
  307. cutset = Acut.get(o);
  308. while(!cutset.isEmpty()){
  309. T d = cutset.poll();
  310. eliminat.add(d);
  311. if(Graf.existearco(o, d)){
  312. Graf.eliminarArco(o, d);
  313. }
  314. edgeBW.get(o).remove(d);
  315. edgeBW.get(d).remove(o);
  316. }
  317. eliminats.put(o, eliminat);
  318. }
  319. }
  320.  
  321. Boolean calrecalcular(T origen, T Final) {
  322. Boolean trobat = false;
  323. HashMap<T, LinkedList<T>> Set = new HashMap<>();
  324. for (T o : Acut.keySet()) {
  325. if (trobat) break;
  326. LinkedList<T> l = Acut.get(o);
  327. LinkedList<T> r = new LinkedList<T>();
  328. while (!l.isEmpty()) {
  329. T d = l.poll();
  330. r.add(d);
  331. Set = camino.get(origen).get(Final);
  332. if(Set.containsKey(o)){
  333. LinkedList<T> Aux = Set.get(o);
  334. if (Aux.contains(d)) {
  335. camino.get(origen).get(Final).clear();
  336. trobat = true;
  337. }
  338. }
  339. if (Set.containsKey(d)) {
  340. LinkedList<T> Aux = Set.get(d);
  341. if (Aux.contains(o)) {
  342. camino.get(origen).get(Final).clear();
  343. trobat = true;
  344. }
  345. }
  346. }
  347. Acut.put(o,r);
  348. }
  349. return trobat;
  350. }
  351.  
  352. public String obtenerGrafo(){
  353. return Graf.toString();
  354. }
  355.  
  356. public String printarComunidad() throws MyException{
  357. HashMap<Object, Integer> n2c = new HashMap<Object, Integer>();
  358. int c = 0;
  359. Vector vs = Graf.obtenerVertices();
  360. HashMap<Object, Boolean> vist = new HashMap<Object, Boolean>();
  361. for (Object v : vs) vist.put(v, false);
  362. Queue<Object> pq = new PriorityQueue<Object>();
  363.  
  364. for (Object vi : vs) {
  365. if(!vist.get(vi)){
  366. pq.add(vi);
  367. ++c;
  368. }
  369. while(!pq.isEmpty()){
  370. Object u = pq.poll();
  371. if (!vist.get(u)){
  372. n2c.put(u, c);
  373. vist.put(u, true);
  374. Vector a = Graf.obtenerAdyacencias(u);
  375. for (Object va : a) {
  376. pq.add(va);
  377. }
  378. }
  379. }
  380. }
  381. return n2c.toString();
  382. }
  383.  
  384. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!