Topological ordering
Topologically ordered graph
Topologically ordered graph

Topological ordering (topological sorting) of a graph is a sequence of its vertices, in which for each edge (u,\\; v) of the graph holds that u precedes v. Hence only acyclic graph can be ordered topologically.

When a topologically ordered graph is plotted, than all of its edges are oriented exactly in one direction.

Usage of topological ordering

Topological ordering can be, for example, used for planning of mutually dependent events/activities. If we perform activities in their topological order, then each activity will be performed after all activities it is dependent on.

Algorithm

The algorithm for topological ordering is based on depth first search. More specifically it is the order of closing vertices in a inversely oriented graph. The asymptotic complexity of this procedure is O(\\vert V \\vert + \\vert E\\vert), where \\vert V \\vert is number of vertices of the graph and \\vert E \\vert is number of its edges.

Code

     /**
      * Prints out topological ordering of the graph given
      * @param graph graph
      */
     public static void orderTopologically(GraphIface graph) {
         //states of particular nodes
         List<Integer> roots = new ArrayList<Integer>();
         for (int i = 0; i < graph.getVertexCount(); i++) {
             //if it does not have any descendants in original graph
             //than it is a root in the inverse graph
             if(graph.getEdges(i).size() == 0) roots.add(i);
         }
         GraphIface inverted = graph.inverse(); //create inversly oriented graph
         int[] state = new int[inverted.getVertexCount()];
 
         for (int i = 0; i < state.length; i++) state[i] = FRESH;
         for (Integer i : roots) {
             doOrdering(inverted, i, state);
         }
     }
     /**
      * Perform the topological ordering (sorting)
      * @param graph graph
      * @param vertexNr number of the current node
      * @param state array of states
      */
     private static void doOrdering(GraphIface graph, int vertexNr, int[] state) {
         state[vertexNr] = OPENED;
         for (Integer i : graph.getEdges(vertexNr)) {
             if (state[i] == FRESH) doOrdering(graph, i, state);
             else if (state[i] == OPENED) throw new IllegalArgumentException("Graph contains cycles");
         }
         System.out.print(" -> " + vertexNr);
         state[vertexNr] = CLOSED;
     }
 

Sources

  • KOLÁŘ, Josef. Teoretická informatika. 2. ed. Praha : Česká informatická společnost, 2004. 205 p. ISBN 80-900853-8-5.

www.EuAutodily.cz SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz





Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?