Алгоритм и константа графа Tricolor

Question

Чтобы сделать топологическую сортировку, мне нужно применить триколорный алгоритм [1] на графике. То есть, если предположить, что вершины WHITE, алгоритм будет реализован как

void visit(Vertex& v) 
    { 
    v.color=GRAY; 
    auto child=v.children.begin(); 
    auto v_end=v.children.end(); 
    while(child!=v_end) 
     { 
     if(child->color==GRAY) 
      {throw "Loop detected";} 
     if(child->color==WHITE) 
      {visit(*child);} 
     ++child; 
     } 
    v.color=BLACK; 
    } 

Теперь я хочу, чтобы алгоритм не изменять v, поэтому он может быть const без mutable. Каков наиболее эффективный способ сделать эту работу? Некоторые идеи

• Скопируйте график перед обработкой его
• Используйте std::map<Vertex*,color_type>
• Дайте каждую вершину идентификатора во время предыдущего прохода, такие идентификаторы соответствуют порядку, который посетили вершины. Затем цвет можно сохранить в массиве.

[1] http://www.cs.cornell.edu/courses/cs2112/2012sp/lectures/lec24/lec24-12sp.html

Answer 1

Я решил проблему, давая каждый узел в графе идентификатор во время строительства. Затем я использовал временный массив при сортировке графика. Сложность:

• Две дополнительные операции во время строительства (получить счетчик узлов и присвоить идентификатор). Постоянное время.
• Один массив поиска, чтобы получить цвет вершины. Постоянное время

Таким образом, дополнительной сложности не требуется.