Thursday, January 8, 2015

Topology algorithm in java

Today I'm writing topology algorithm..

I'm not graduated from computer science. so I was hesitated that I could post article about algorithm???
No fear, Tried it.
and I posted fewer things.
I just believe that this is just start.

I plan to post more than 100 algorithm and testcase.


Anyway.
below is pseudocode from wikipedia


L ← Empty list that will contain the sorted elements    
S ← Set of all nodes with no incoming edges             
while S is non-empty do                                  
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)


explain ~

1. make empty list or stack~
2. make Set of all nodes with no incoming edges.
  - this means add Set if node has no parent node.
3. if set is not empty remove a node "n" from Set
4. add n to tail of List or stack
5. find n's destination nodes
6. remove edges destination nodes,
7. if nodes has no incoming edges insert S
and

print list or stack

later on I will write java code

if my code is show how stange. reply and discuss


this picture is from wikipedia.


  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
package mybook;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Stack;

/**
 * @author ddavid
 *
 */
public class Topology {
 
 int[][] graph = new int [12][12];   // from to start 
 HashSet<Integer> rootSet = new HashSet<Integer>(); 
 Stack stack = new Stack();
 
 public static void main(String args[]){
  Topology topology = new Topology();
  topology.init();
 }
 
 /**
  * unidirectional graph
  */
 public void init(){
  graph[7][11] = 1;
  graph[7][8] = 1;
  graph[5][11] = 1;
  graph[3][8] = 1;
  graph[3][10] = 1;
  graph[11][2] = 1;
  graph[11][9] = 1;
  graph[11][10] = 1;
  graph[8][9] = 1;
  
  
  for(int i=0; i<12; i++){
   findRootAndSet(i);
  }
  
  while(!rootSet.isEmpty()){
   Integer a = rootSet.iterator().next();

   stack.push(a);
   //remove 길
   for(int i=0; i<12; i++){
    if(graph[a][i]==1){
     graph[a][i] = 0;
     if(!hasRoot(i)){
      rootSet.add(i);
     }
    }
   }
   rootSet.remove(a);
  }
  
  printHashSet();
  System.out.println(stack);
 }
 
 public boolean hasRoot(int val){
  for(int i=0; i<12; i++){
   if(graph[i][val] == 1){
    return true;
   }
  }
  return false;
 }
 
 public boolean findRootAndSet(int a){
  boolean found =false;
  
  for(int i=0; i<graph.length; i++){
   if(graph[i][a] == 1){
    found = findRootAndSet(i);
    if(found == false){
     // root
     found = true;
     // 
     rootSet.add(i);
    }
   }
  }
  return found;
 }
 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";
  }
 }
 
 public void printHashSet(){
  Iterator<Integer> iter = rootSet.iterator();
  while(iter.hasNext()){
   Integer number = iter.next();
   System.out.println("" + number +",");
  }
 }
}
-
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)