### 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

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.

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 edgeswhileS is non-emptydoremove a node n from S add n totailof Lfor eachnode m with an edgeefrom n to mdoremove edge e from the graphifm has no other incoming edgestheninsert m into Sifgraph has edgesthenreturn error (graph has at least one cycle)elsereturn 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 +","); } } } |

## Comments

## Post a Comment