Thursday, January 8, 2015

Kruskal Algorithm in java

Today I explain Kruskal algorithm

From the logic I coded in java.

This is another way to find minimum spanning this.
before you read this post, prerequisite is understanding Union and Find Algorithm.
I worte last post Union and Find Algorithm. 

and you can read Prim algorithm.

the logic is below.

1. setting nodes, changing nodes to subsets;
2. sort edges order by weight ascending
3. and Use Union and Find Algorithm.

if my code is show how stange. reply and discuss











Reference:


my java code is



  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
package mybook;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;

public class Kruskal {
 /**
  * all edges
  */
 ArrayList<Edge> edges= new ArrayList<Edge>();
 
 ArrayList<ItemNode> nodes= new ArrayList<ItemNode>();
 ArrayList<HashSet<ItemNode>> subsets = new ArrayList<HashSet<ItemNode>>();
 
 public static void main(String args[]){
  Kruskal kruskal= new Kruskal();
  kruskal.init();
  

 }
 
 public void init(){
  // setting nodes;
  nodes.add(new ItemNode(0));
  nodes.add(new ItemNode(1));
  nodes.add(new ItemNode(2));
  nodes.add(new ItemNode(3));
  nodes.add(new ItemNode(4));
  nodes.add(new ItemNode(5));
  nodes.add(new ItemNode(6));
  nodes.add(new ItemNode(7));
  nodes.add(new ItemNode(8));
  
  // setting edges;
  edges.add(new Edge(0,1,4));
  edges.add(new Edge(0,7,8));
  edges.add(new Edge(1,2,8));
  edges.add(new Edge(1,7,11));
  edges.add(new Edge(2,8,2));
  edges.add(new Edge(2,3,7));
  edges.add(new Edge(2,5,4));
  edges.add(new Edge(3,4,9));
  edges.add(new Edge(3,5,14));
  edges.add(new Edge(4,5,10));
  edges.add(new Edge(5,6,2));
  edges.add(new Edge(6,7,1));
  edges.add(new Edge(6,8,6));
  edges.add(new Edge(7,8,7));
  
  // make nodes to subsets
  for(int i=0; i<nodes.size(); i++){
   HashSet<ItemNode> set = new HashSet<ItemNode>();
   set.add(nodes.get(i));
   subsets.add(set);
  }
  
  // sort
  Collections.sort(edges, new CustomComparator());
  
  System.out.println(edges);
  
  
  // union and find algorithm
  for(int i=0; i<edges.size(); i++){
   Edge edg = edges.get(i);
   ItemNode srcNode = nodes.get(edg.src);
   ItemNode destNode = nodes.get(edg.dest);
   
   if(find(srcNode) == find(destNode)){
    // same subsets
   }else{
    System.out.println( edg.src + " > " + edg.dest);
    union(find(srcNode), find(destNode));
   }
  }
 }
 
 public void union(int aSubset, int bSubset){
  HashSet<ItemNode> aSet = subsets.get(aSubset);
  HashSet<ItemNode> bSet = subsets.get(bSubset);
  
  Iterator<ItemNode> iter = bSet.iterator();
  while(iter .hasNext()){
   ItemNode b = iter.next();
   aSet.add(b);
//   System.out.println(bSet.size());
//   System.out.println("bnumber : " + b.number);
  }
  subsets.remove(bSubset);
  printSet();
  
 }
 
 public void printSet(){
  
  for(int i=0;i<subsets.size(); i++){
   HashSet<ItemNode> hashSet= subsets.get(i);
   
   Iterator<ItemNode> iter= hashSet.iterator();
   System.out.print("{");
   while(iter.hasNext()){
    ItemNode node = iter.next();
    System.out.print(node.number + ",");
   }
   System.out.print("}");
   
  }
  System.out.println();
 }
 
 public void setvalue(int [][] graph, int start, int end, int val){
  graph[start][end] = val;
  graph[end][start] = val;
 }
 class ItemNode {
  boolean isRoot = true;
  int number = 0;
  LinkedList<ItemNode> subnodes= new LinkedList<ItemNode>();
  ItemNode parendNode = null;
  
  ItemNode(int number){
   this.number = number;
  }
 }
 
 
 public int  find(ItemNode node){
  int number=-1;
  
  for(int i=0; i<subsets.size(); i++){
   HashSet<ItemNode> set = subsets.get(i);
   Iterator<ItemNode> iterator = set.iterator();
   while(iterator.hasNext()){
    ItemNode setnode = iterator.next();
    if(setnode.number == node.number){
     number= i;
     return number;
    }
    
   }
  }
  return number;
 }
}
class CustomComparator implements Comparator<Edge>{

 @Override
 public int compare(Edge o1, Edge o2) {
  return o1.weight - o2.weight;
 }
}

class Edge{
 int src;
 int dest; 
 int weight;
 
 Edge(int src, int dest, int weight){
  this.src = src;
  this.dest = dest;
  this.weight = weight;
 }
 @Override
 public String toString() {
  return "Edge [src=" + src + ", dest=" + dest + ", weight=" + weight
    + "] \n";
 }
}
- 1 comment:
Labels:

Union and Find algorithm in java

Today I wanted to post Kruskal' algorithm .
one day is too short to understand that
because I have to know union and find algorithm in first.
using it we can find whether this would be circle or not if we connect tree and one point.

It was hard to write java but i tried.

Precondition: all items are numbered and unique

refereced by http://www.algorithmist.com/index.php/Union_Find

If you have any question, comment Plz~

if my code is show how stange. reply and discuss

pseudo code is Below

func find( var element )
  while ( element is not the root ) element = element's parent
  return element
end func

func union( var setA, var setB )
  var rootA = find( setA ), rootB = find( setB )
  if ( rootA is equal to rootB ) return
  else
     set rootB as rootA's parent
end func



  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package mybook;

import java.util.LinkedList;

/**
 * @author ddavid
 *
 */
public class UnionAndFind {
 
 public static void main(String args[]){
  // aSet
  
  ItemNode itemNode4 = new ItemNode();
  itemNode4.isRoot = false;
  itemNode4.number =4;
  
  ItemNode itemNode3 = new ItemNode();
  itemNode3.isRoot = false;
  itemNode3.number =3;
  
  ItemNode itemNode2 = new ItemNode();
  itemNode2.isRoot = false;
  itemNode2.number =2;
  
  
  ItemNode itemNode1 = new ItemNode();
  itemNode1.isRoot = false;
  itemNode1.number =1;
  
  ItemNode itemNode0 = new ItemNode();
  itemNode0.isRoot = true;
  itemNode0.number =0;
  
  
  // parentNode 
  itemNode4.parendNode = itemNode3;
  itemNode3.parendNode = itemNode2;
  itemNode2.parendNode = itemNode0;
  itemNode1.parendNode = itemNode0;
  
  
  itemNode2.edges.add(itemNode3);
  itemNode3.edges.add(itemNode4);
  itemNode0.edges.add(itemNode1);
  itemNode0.edges.add(itemNode2);
  // bSet 
  
  ItemNode itemNode5 = new ItemNode();
  itemNode5.isRoot = false;
  itemNode5.number =5;
  
  ItemNode itemNode6 = new ItemNode();
  itemNode6.isRoot = true;
  itemNode6.number =6;
  
  itemNode5.parendNode = itemNode6;
  itemNode6.edges.add(itemNode5);
  
  UnionAndFind unf = new UnionAndFind();
  
  System.out.println(unf.find(itemNode0).number);
  System.out.println(unf.find(itemNode1).number);
  System.out.println(unf.find(itemNode2).number);
  System.out.println(unf.find(itemNode3).number);
  System.out.println(unf.find(itemNode4).number);
  
  
  System.out.println();
  System.out.println(unf.find(itemNode5).number);
  System.out.println(unf.find(itemNode6).number);
  
  
  unf.union(itemNode4, itemNode5);
  System.out.println("########## after union############");
  
  System.out.println(unf.find(itemNode0).number);
  System.out.println(unf.find(itemNode1).number);
  System.out.println(unf.find(itemNode2).number);
  System.out.println(unf.find(itemNode3).number);
  System.out.println(unf.find(itemNode4).number);
  
  
  System.out.println();
  System.out.println(unf.find(itemNode5).number);
  System.out.println(unf.find(itemNode6).number);
 }
 
 public ItemNode  find(ItemNode node){
  while(node.isRoot == false ){
   node = node.parendNode;
  }
  return node;
 }
 
 public void union(ItemNode a, ItemNode b){
  ItemNode aRootNode = find(a);
  ItemNode bRootNode = find(b);
  
  
  if(aRootNode == bRootNode){
   
  }else{
   aRootNode.isRoot = false;   
   aRootNode.parendNode = bRootNode;
   bRootNode.edges.add(aRootNode);
  }
 }
}

class ItemNode {
 boolean isRoot = false;
 int number = 0;
 LinkedList<ItemNode> edges= new LinkedList<ItemNode>();
 ItemNode parendNode = null; 
}
- 2 comments:
Labels:

Wednesday, January 7, 2015

prim algorithm java

Before you start prim algorithm,
I would recommend you to read BFS(Breadth First Search), DFS(Depth First Search).
late I will post about both of those algorithms.

Prim algorithm is finding minimum spanning tree in graph.

here we can see detail summary

and my code is below

% pickMinVertex is not fast so I have to tune code later

this image are from above url..


if my code is show how stange. reply and discuss













  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package mybook;

import java.util.Arrays;
import java.util.HashSet;

public class primTest {
 static int[][] graph = new int [9][9];
 int[] visited = new int[9];
 int[] tempValue = new int[9];
 static int[][] primgraph = new int [9][9];
 
 public static void main(String[] args){
  primTest prim = new primTest();
  prim.init();  
  prim.printValue(graph);
  prim.start();
  prim.printValue(primgraph);
 }
 
 public void init(){
  // first case
//  setvalue(graph, 0, 1, 8);
//  setvalue(graph, 1, 2, 10);
//  setvalue(graph, 2, 3, 5);
//  setvalue(graph, 3, 0, 9);
//  setvalue(graph, 0, 4, 11);
//  setvalue(graph, 4, 3, 13);
//  setvalue(graph, 4, 5, 8);
//  setvalue(graph, 5, 6, 7);
//  setvalue(graph, 6, 3, 12);
  
  // second case
  setvalue(graph, 0, 1, 4);
  setvalue(graph, 0, 7, 8);
  setvalue(graph, 1, 7, 11);
  setvalue(graph, 1, 2, 8);
  setvalue(graph, 2, 8, 2);
  setvalue(graph, 8, 6, 6);
  setvalue(graph, 6, 7, 1);
  setvalue(graph, 7, 8, 7);
  setvalue(graph, 2, 3, 7);
  setvalue(graph, 2, 5, 4);
  setvalue(graph, 5, 6, 2);
  setvalue(graph, 3, 5, 14);
  setvalue(graph, 3, 4, 9);
  setvalue(graph, 4, 5, 10);
  
 }
 
 public void start(){
  visited[0] = 1;
  tempValue[0] =9999;
  call(0);
  
 }
 
 public void call(int num){
  setWeight(num);
  int j = -1;
  while((j= pickMinVertex()) != -1){
   visited[j]= 1;
   
   System.out.println("visited : " + j);
   
   call(j);
  }
  ;
 }
 
 public void setWeight(int num){
  for(int i=0; i<graph.length; i++){
   if(graph[num][i]>0 && visited[i]==0){
    tempValue[i] = graph[num][i];
   }
  }
 }
 
 /**
  * find minimm weight node within not visited node
  * @param num
  * @return
  */
 public int pickMinVertex(){
  int min = Integer.MAX_VALUE;
  int position  = -1;
  int tempStart = 0;
  int tempEnd = 0;
  
  for(int i=0; i< tempValue.length; i++){
   if(tempValue[i]> 0 && visited[i] ==1){
    for(int j=0; j<graph.length; j++){
     if(visited[j] == 1){
      continue;
     }
     int val = graph[i][j] ;
     if(val > 0 && val <min){
      min = val;
      position =j;
      tempStart = i;
      tempEnd = j;
     }
    }
   }
  }
  if(position != -1){
   
   System.out.println(tempStart + " to " + tempEnd);
   
   setvalue(primgraph, tempEnd, tempStart, 1);
  }
  return position;
 }
 
 public void setvalue(int [][] graph, int start, int end, int val){
  graph[start][end] = val;
  graph[end][start] = val;
 }
 
 public  void printValue(int graph[][]){
  for(int i=0; i<graph.length; i++){
   for(int j=0; j< graph.length; j++){
    
    String pr = "";
    int val = graph[i][j];
    if(val < 10){
     pr = "0"+ val; 
    }else{
     pr = val +"";
    }
    
    System.out.print(pr + " ");
   }
   System.out.println();
  }
 }
}
- No comments:
Labels:

Tuesday, January 6, 2015

Topcoder srm 637 div2 500 problem

How I approach this problem is finding shortest path

and total path minus # path count minus short path minus will be a answer


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package srm637;

public class PathGameDiv2 {
 public static void main(String args[]){
  PathGameDiv2 pg = new PathGameDiv2();
  String[] board = {"....#.##.....#..........." 
       ,"..#......#.......#..#...."};
  
  System.out.println(pg.calc(board));
 }
 
 public int calc(String[] board){
  
  int len = board[0].length();
   
  
  int total =0;
  int p =0;
  
  total = Math.min(pathSum(p, len, board), pathSum(p+1, len, board));
  
  int minus =0;
  
  for(int i=0; i<board.length; i++){
   for(int j=0; j<board[i].length(); j++){
    if(board[i].charAt(j) == '#'){
     minus ++;
    }
   }
  }
  
  return (board[0].length()* 2) - total - minus;
 }
 
 public int pathSum(int p, int len, String[] board){
  int total =0;
  for(int i=0; i<len; i++){
   if(board[p].charAt(i) =='.'){
    total ++;
   }else{
    if(p==0){
     p=1;
     i= i-2;
    }else{
     p=0;
     i = i-2;
    }
   }
  } 
  return total;
 }
}
- No comments:
Labels:

Topcoder srm 637 div2 250point

These days ~

I feel like My coding skill is not improved.

I'm so depressed. but I will be a RED in topcoder
so have to be study very hard

My answer is  below

this is really easy~!!


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package srm637;

public class GreaterGameDiv2 {

 public static void main(String[] args) {
  GreaterGameDiv2 gg= new GreaterGameDiv2();
  int snuke[] = {3,5,9,16,14,20,15,17,13,2};
  int sothe[] = {6,18,1,8,7,10,11,19,12,4};
  
  System.out.println(gg.calc(snuke, sothe));
 }
 
 public int calc(int[] snuke, int[] sothe){
  int len = snuke.length;
  int total =0;
  for(int i=0; i<len; i++){
   if(snuke[i]>sothe[i]){
    total++;    
   }
  }
  
  return total;
 }

}
- No comments:
Labels:

Difference between LinkedList and ArrayList and Performance Test

안녕하세요 저는 쯔앙구입니다.

3년전에 학원에서 처음으로 Java언어를 배우고 안드로이드 어플 개발중 왜 실력이 늘지 않는걸까?? 라는 생각에 자바 자료구조 책을 한권샀습니다.
거기에서는 c언어랑 의사코드랑 같이 섞여있는데 제가 자바만 배웠는데 알겠나요?? 너무 어려워서 Linked에서 포기...
에라 모르겠다. 몰라도 어플동작이 잘만 되자나??
라고 생각했는데 1년뒤에 제가 짠 어플 소스를 다시 보니깐 부끄러울 정도였더군요.
혹시나 저처럼 먹고살기 힘들어서 기초 없이 학원에서 속성과정으로 자바를 시작하는 사람에게 한번더 생각하면서
코딩을 할 수 있도록 도움을 주고자 작성합니다.


ArrayList와 Linked 리스트의 차이점.

학원에서 무조건 암기하라고 했습니다.
List list = new ArrayList();
그러다 보니 2-3년간 무조건 리스트는 ArrayList를 만들었습니다.

자바에서 대표적으로 사용하는 리스트는 ArrayList와 LinkedList가 있는데
잠깐 살표볼께요.

상황에 따라서 사용을 해야하는데 무조건 ArrayList를 고집해서 사용하게 될 경우 시스템에 어떠한 영향을 끼칠지 알아봅시다.


ArrayList = 말 그대로 new Object[] 배열을 생성해서 배열을 가지고 Insert, delete 하는 방법

LinkedList = Header부분에 왼쪽 노드, 오른쪽 노드의 주소값을 가지고 찾아가는 방법
아래는 코드를 돌린 내용입니다.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package mybook;

import java.util.ArrayList;
import java.util.LinkedList;

public class DifferentList {

 public static void main(String[] args) {
  Long start =0l;
  Long end =0l;
  
  start = System.currentTimeMillis();
  
  ArrayList<String> array= new ArrayList<String>();
  for(int i=0; i<10000000; i++){
   array.add("hello");
  }
  logEnd(start, "array Insert");
  
  
  start = System.currentTimeMillis();
  LinkedList<String> linked= new LinkedList<String>();
  for(int i=0; i<10000000; i++){
   linked.add("hello");
  }
  logEnd(start, "Linked Insert");
  
  
  start = System.currentTimeMillis();
  for(int i=0; i< 10000; i++){
   array.remove(i); 
  }
  logEnd(start, "Array RemoveIndex");
  
  
  start = System.currentTimeMillis();
  for(int i=0; i< 10000; i++){
   linked.remove(i); 
  }
  logEnd(start, "Linked RemoveIndex");
  
  start = System.currentTimeMillis();
  for(int i=1000000; i< 10000; i++){
   array.remove(i); 
  }
  logEnd(start, "Array RemoveIndex");
  
  
  start = System.currentTimeMillis();
  for(int i=1000000; i< 10000; i++){
   linked.remove(i); 
  }
  logEnd(start, "Linked RemoveIndex");
 }
 
 public static void logEnd(long start,  String message){
  System.out.println(message + " : " +(System.currentTimeMillis() - start));
 }
 
 
}


== 결과 ==

array Insert : 94
Linked Insert : 1078

Array RemoveIndex : 78462
Linked RemoveIndex : 110

Array RemoveIndex : 0
Linked RemoveIndex : 0


결과를 봐서 add 하는 부분은 LinkedList에 비해 ArrayList 가 10배 정도 빠르고
index값의 데이터를 삭제하는 부분은 데이터가 크면 클수록 ArrayList 가 LinkedList에 비해 속도가 현저히 느렸습니다.

결론 : 무조건 ArrayList를 사용하는것이 아니라 고객의 Needs를 통해서 어떠한 방법으로 구현을 해야할지에 대해서 충분히 고민을 한 후 코딩을 해야한다.
- No comments:
Labels:
Subscribe to: Posts (Atom)