N
N
Nem0_o2015-03-02 19:06:15
Programming
Nem0_o, 2015-03-02 19:06:15

How to apply topological sort?

There is an algorithm, implementation using depth-first search: rain.ifmo.ru/cat/view.php/vis...2007/algorithm
C++ code

boolean topological_sort(){
       boolean Cycle;
       for(int i = 1;i <= N;i ++){
           Cycle = dfs(i);
           if(Cycle)return false;
       }
       for(int i = 1;i <= n;i ++){
           Numbers[Stack.pop()] = i;
       }
      return true;
  }
  boolean dfs(int v){
      if(Color[v] == 1)return true;
      if(Color[v] == 2)return false;
      Color[v] = 1;
      for(int i = 0;i < Edges[v].size();i ++){
          if(dfs(Edges[v].get(i)))return true;
      }
      Stack.push(v);
      Color[v] = 2;
      return false;
}

The procedure returns true if the graph has been topologically sorted, false otherwise.
Color - an array that stores the colors of the vertices (0 - white, 1 - gray, 2 - black).
N is the number of vertices.
Edges is an array of lists of adjacent vertices.
Numbers is an array where the new vertex numbers are stored.
Stack - a stack in which the vertices are added after they have been processed.
Cycle - true if a cycle is found in the graph.
Description:
3-6. Depth-first traversal from all vertices is called. We terminate the algorithm if a cycle is detected.
7-9. We enter new numbers of vertices into the array.
13-14. If the vertex is gray, then we have found a cycle. We end the search in depth.
14. If the vertex is black, then finish processing it.
15. Paint the top gray.
16-18. We process the list of vertices adjacent to it.
19. Push the top onto the stack.
20. Paint the top black.
I can't figure out how it all works, and how to apply this sort to a directed graph, which is given by an adjacency matrix, and return the sort result? Can anyone show a real example?

Answer the question

In order to leave comments, you need to log in

4 answer(s)
M
Mercury13, 2015-03-07
@Nem0_o

It is necessary to rewrite this section of code for the adjacency matrix.

for(int i = 0;i < Edges[v].size();i ++){
          if(dfs(Edges[v].get(i)))return true;
      }

Something like this.
цикл (i : все вершины)
   если матрица_смежности[v, i]
         если dfs(i)
             return true;

I also don't like the constants 0, 1 and 2. I would like to declare them as
UNVISITED = 0;
PARTLY_VISITED = 1;
VISITED = 2;

Or WHITE, GRAY and BLACK, if you like - in algorithms textbooks they are painted in three colors.

E
evilelf, 2017-12-01
@evilelf

this is how it works

'<type:\w+>/<module:\w+>' =>'<module>',
'<type:\w+>/<module:\w+>/<site_id:\w+>' => '<module>/default/view',

V
Vlad, 2017-12-01
@wildvampir

add rules to rules

'<type:\w+>/<module:\w+>' =>'modules/<module>/default/index',
'<type:\w+>/<module:\w+>/<site_id:\w+>' => 'modules/<module>/default/view',

M
Maxim Timofeev, 2017-12-01
@webinar

It is not clear what you have where in modules/site/default/index
if site is a module, default is a controller, and index is an action, then what are modules? There is something clearly redundant here. There must be a number of module, controller, action or controller, action or just action. What is the fourth?
If you omit this modules and I also correctly understood the rest, then:

[
'/<type>/<modul>/' => '<modul>/default/index',
'/<type>/site/<site_id>' => 'site/default/view'
]

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question