## 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 ; // from to start HashSet rootSet = new HashSet(); Stack stack = new Stack(); public static void main(String args[]){ Topology topology = new Topology(); topology.init(); } /** * unidirectional graph */ public void init(){ graph = 1; graph = 1; graph = 1; graph = 1; graph = 1; graph = 1; graph = 1; graph = 1; graph = 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 iter = rootSet.iterator(); while(iter.hasNext()){ Integer number = iter.next(); System.out.println("" + number +","); } } } ```