Issue 6002059: 2 - Shtokhov Alexander - shtokhov@gmail.com 2013 - 4
|
Created:
14 years, 1 month ago by shtokhov Modified:
9 years, 10 months ago Reviewers:
ys.algorithms CC:
ys.algorithms+andrey_gmail.com Visibility:
Public. |
Patch Set 1 #
Total comments: 14
Patch Set 2 : Fix first group remarks #
Total comments: 6
Patch Set 3 : Fix second group remarks #
Total comments: 13
Patch Set 4 : Fix third group remarks #Patch Set 5 : Fix all third group remarks #
Total comments: 1
Patch Set 6 : Fix fourth group remarks #
Total comments: 32
Patch Set 7 : Fix fifths group remarks #Patch Set 8 : Fix fifths group remarks add #
Total comments: 2
Patch Set 9 : Fix sixth group remarks #
Total comments: 1
MessagesTotal messages: 13
Надо вынести весь фукционал по решению конкретной задачи из класса графа. -- Петя. https://codereview.appspot.com/6002059/diff/1/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode21 main.cpp:21: m_vertices[endVertexIndex].m_reverseEdges.push_back(Edge(startVertexIndex, weight)); Нет смысла хранить обратные ребра в графе. Лучше когда будет надо инвертировать граф. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode24 main.cpp:24: int FindMinimumVertexIndexInNegativeCycle() { В классе с графом не должно быть никаких реализаций конкретных алгоритмов. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode90 main.cpp:90: Color m_color; Никаких цветов и индексов ни для каких алгоритмов в вершине графа не должно храниться. Если алгоритму нужны эти данные, он должен хранить их отдельно. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode94 main.cpp:94: class StronglyConnectedComponent Такой класс с одним полем не нужен, вместо этого надо сделать typedef. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode110 main.cpp:110: int minimumIndex = m_vertexIndices[0]; Для этого есть std::min_element. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode148 main.cpp:148: DFSOrder edgesOrder, У перенесенного заголовка должен быть больше отступ, чтобы он не сливался с телом функции. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode267 main.cpp:267: (*graph).AddEdge(startVertexIndex - 1, endVertexIndex - 1, weight); Есть оператор '->'
Sign in to reply to this message.
https://codereview.appspot.com/6002059/diff/1/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode21 main.cpp:21: m_vertices[endVertexIndex].m_reverseEdges.push_back(Edge(startVertexIndex, weight)); On 2012/04/16 16:36:07, ys.algorithms wrote: > Нет смысла хранить обратные ребра в графе. > Лучше когда будет надо инвертировать граф. Done. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode24 main.cpp:24: int FindMinimumVertexIndexInNegativeCycle() { On 2012/04/16 16:36:07, ys.algorithms wrote: > В классе с графом не должно быть никаких реализаций конкретных алгоритмов. Done. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode90 main.cpp:90: Color m_color; On 2012/04/16 16:36:07, ys.algorithms wrote: > Никаких цветов и индексов ни для каких алгоритмов в вершине графа не должно > храниться. Если алгоритму нужны эти данные, он должен хранить их отдельно. Done. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode94 main.cpp:94: class StronglyConnectedComponent On 2012/04/16 16:36:07, ys.algorithms wrote: > Такой класс с одним полем не нужен, вместо этого надо сделать typedef. Done. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode110 main.cpp:110: int minimumIndex = m_vertexIndices[0]; On 2012/04/16 16:36:07, ys.algorithms wrote: > Для этого есть std::min_element. Done. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode148 main.cpp:148: DFSOrder edgesOrder, On 2012/04/16 16:36:07, ys.algorithms wrote: > У перенесенного заголовка должен быть больше отступ, чтобы он не сливался с > телом функции. Done. https://codereview.appspot.com/6002059/diff/1/main.cpp#newcode267 main.cpp:267: (*graph).AddEdge(startVertexIndex - 1, endVertexIndex - 1, weight); On 2012/04/16 16:36:07, ys.algorithms wrote: > Есть оператор '->' Done.
Sign in to reply to this message.
-- Петя. https://codereview.appspot.com/6002059/diff/5001/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/5001/main.cpp#newcode49 main.cpp:49: m_adjacentEdgesList(0) { Это и так делает конструктор вектора по умолчанию. https://codereview.appspot.com/6002059/diff/5001/main.cpp#newcode173 main.cpp:173: int FindMinimumVertexIndexInComponent(const StronglyConnectedComponent& component) { Эта функция не используется. https://codereview.appspot.com/6002059/diff/5001/main.cpp#newcode184 main.cpp:184: bool HasComponentNegativeCycle( Лучше сделать две функции: bool HasNegativeCycle(const Graph& graph); Graph CutOutSubraph(const Graph& graph, const std::vector<int>& vertices); Тогда этот код будет легко повторно использовать.
Sign in to reply to this message.
https://codereview.appspot.com/6002059/diff/5001/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/5001/main.cpp#newcode49 main.cpp:49: m_adjacentEdgesList(0) { On 2012/04/29 17:41:50, ys.algorithms wrote: > Это и так делает конструктор вектора по умолчанию. Done. https://codereview.appspot.com/6002059/diff/5001/main.cpp#newcode173 main.cpp:173: int FindMinimumVertexIndexInComponent(const StronglyConnectedComponent& component) { On 2012/04/29 17:41:50, ys.algorithms wrote: > Эта функция не используется. Да, точно...я ее заменил на std::min. https://codereview.appspot.com/6002059/diff/5001/main.cpp#newcode184 main.cpp:184: bool HasComponentNegativeCycle( On 2012/04/29 17:41:50, ys.algorithms wrote: > Лучше сделать две функции: > bool HasNegativeCycle(const Graph& graph); > Graph CutOutSubraph(const Graph& graph, const std::vector<int>& vertices); > > Тогда этот код будет легко повторно использовать. Done.
Sign in to reply to this message.
-- Петя. https://codereview.appspot.com/6002059/diff/9001/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode172 main.cpp:172: Graph CutOutSubraph( Разве не влезет на одну строку? Зачем переносить? https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode176 main.cpp:176: for (int vertexIndex = 0; Лучше объявить индекс как size_t и не делать cast. Это и к остальным циклам относится. Тогда и не пришлось бы переносить заголовки на три строки. https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode184 main.cpp:184: for (int canBeTailVertex = 0; Вместо этого цикла лучше воспользоваться std::find. https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode199 main.cpp:199: bool HasNegativeCycle( Не надо тут переносить. https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode202 main.cpp:202: distances[0] = 0; Применительно к поиску цикла отрицательного веса, можно расстояния инициализировать нулями сразу для всех вершин. https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode204 main.cpp:204: for (int interationIndex = 0; И снова cast'ы.
Sign in to reply to this message.
https://codereview.appspot.com/6002059/diff/9001/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode172 main.cpp:172: Graph CutOutSubraph( On 2012/05/06 11:47:03, ys.algorithms wrote: > Разве не влезет на одну строку? Зачем переносить? Done. https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode176 main.cpp:176: for (int vertexIndex = 0; использование типа size_t приводит к warning в среде разработки visual studio. Среди предупреждений могут оказаться важные (например, предупреждения о присвоении переменной себя же, хотя это может быть ошибка в имени переменной), и эти важные предупреждения можно не заметить в списке остальных предупреждений. Поэтому стараются писать код без предупреждений. On 2012/05/06 11:47:03, ys.algorithms wrote: > Лучше объявить индекс как size_t и не делать cast. > Это и к остальным циклам относится. Тогда и не пришлось бы переносить заголовки > на три строки. https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode184 main.cpp:184: for (int canBeTailVertex = 0; On 2012/05/06 11:47:03, ys.algorithms wrote: > Вместо этого цикла лучше воспользоваться std::find. Done. https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode199 main.cpp:199: bool HasNegativeCycle( On 2012/05/06 11:47:03, ys.algorithms wrote: > Не надо тут переносить. Done. https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode202 main.cpp:202: distances[0] = 0; On 2012/05/06 11:47:03, ys.algorithms wrote: > Применительно к поиску цикла отрицательного веса, можно расстояния > инициализировать нулями сразу для всех вершин. Done. https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode204 main.cpp:204: for (int interationIndex = 0; On 2012/05/06 11:47:03, ys.algorithms wrote: > И снова cast'ы. Done.
Sign in to reply to this message.
Хорошо. +Андрей. -- Петя. https://codereview.appspot.com/6002059/diff/9001/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/9001/main.cpp#newcode176 main.cpp:176: for (int vertexIndex = 0; Понятно, что дело было в устранении warning'а, это хорошая практика. Часто, то, что приходится размер контейнера явно приводить к знаковому типу, является приметой того, что типы чего-то в программе, которые по смыслу являются беззнаковыми, сделаны знаковыми. Если такой проблемы нет, а изменение типа счетчика на size_t добавляет warning'и в других местах, то лучше оставить, как было до моего комментария. On 2012/05/07 08:51:08, shtokhov wrote: > использование типа size_t приводит к warning в среде разработки visual studio. > Среди предупреждений могут оказаться важные (например, предупреждения о > присвоении переменной себя же, хотя это может быть ошибка в имени переменной), и > эти важные предупреждения можно не заметить в списке остальных предупреждений. > Поэтому стараются писать код без предупреждений. > > On 2012/05/06 11:47:03, ys.algorithms wrote: > > Лучше объявить индекс как size_t и не делать cast. > > Это и к остальным циклам относится. Тогда и не пришлось бы переносить > заголовки > > на три строки. > https://codereview.appspot.com/6002059/diff/16004/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/16004/main.cpp#newcode222 main.cpp:222: Зачем пустая строка?
Sign in to reply to this message.
Надо исправить. Андрей. https://codereview.appspot.com/6002059/diff/21001/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode10 main.cpp:10: const int NOT_VISIT_VERTEX_OPEN_TIME = -1; not visited А open time можно и не включать в название. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode64 main.cpp:64: m_adjacentEdgesList[headVertex].push_back(Edge(headVertex, tailVertex, edgeWeight)); Я тоже в этом месте раньше ошибался: оказывается, в графовой терминологии дуга в орграфе идёт из tail в head, что, если подумать, можно даже найти логичным. У тебя же явно хранится список исходящих дуг, а не входящих. И ниже в коде тоже есть где исправить употребление терминов. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode73 main.cpp:73: Edge edge, Лучше по константной ссылке - на стеке рекурсии меньше места займёт. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode76 main.cpp:76: vector<int>* vertexVisitOrder) { Порядок бывает разным. Надо указать, какой именно - post order, или exit order. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode92 main.cpp:92: const StronglyConnectedComponent* component, Зачем указатель? В других местах классы передаются по константной ссылке. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode135 main.cpp:135: int stronglyConnectedComponentIndex = 0; Равно размеру вектора с компонентами? https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode136 main.cpp:136: StronglyConnectedComponent component; Эта переменная дважды объявлена - здесь и в цикле. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode141 main.cpp:141: vector<int> componentVertexOpenedTime(graph.VerticesCount(), NOT_VISIT_VERTEX_OPEN_TIME); Почему для времени используется та же переменная time, а для вектора времён входа создаётся новая переменная? https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode164 main.cpp:164: Graph CutOutSubgraph(const Graph& graph, const std::vector<int>& vertices) { Почему здесь подграф возвращается по значению (а это удобно), а функция обращения графа принимает указатель? https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode174 main.cpp:174: std::find(vertices.begin(), vertices.end(), tailVertex) - vertices.begin(); В этой задаче это, конечно, неважно, но вообще так эффективно найти КСС и после этого так неэффективно вырезать подграф - странно. Алгоритм работает за O(VE). Быстрее сделать легко: предпосчитать номер каждой необходимой вершины, а тем, которые не входят в подграф, проставить специальный флажок. Это делается за O(V). https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode219 main.cpp:219: int minVertexIndex = -1; Это в именованную константу, ведь она используется и в другой функции.
Sign in to reply to this message.
https://codereview.appspot.com/6002059/diff/21001/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode10 main.cpp:10: const int NOT_VISIT_VERTEX_OPEN_TIME = -1; On 2012/05/19 16:39:53, ys.algorithms wrote: > not visited > А open time можно и не включать в название. Done. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode64 main.cpp:64: m_adjacentEdgesList[headVertex].push_back(Edge(headVertex, tailVertex, edgeWeight)); On 2012/05/19 16:39:53, ys.algorithms wrote: > Я тоже в этом месте раньше ошибался: оказывается, в графовой терминологии дуга в > орграфе идёт из tail в head, что, если подумать, можно даже найти логичным. У > тебя же явно хранится список исходящих дуг, а не входящих. > И ниже в коде тоже есть где исправить употребление терминов. Я не очень понимаю. Что значит "в графовой терминологии"? У меня хранятся все исходящие ребра из вершины графа. А как надо хранить? Не понимаю, что надо исправить? https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode73 main.cpp:73: Edge edge, On 2012/05/19 16:39:53, ys.algorithms wrote: > Лучше по константной ссылке - на стеке рекурсии меньше места займёт. Done. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode92 main.cpp:92: const StronglyConnectedComponent* component, On 2012/05/19 16:39:53, ys.algorithms wrote: > Зачем указатель? В других местах классы передаются по константной ссылке. Done. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode135 main.cpp:135: int stronglyConnectedComponentIndex = 0; On 2012/05/19 16:39:53, ys.algorithms wrote: > Равно размеру вектора с компонентами? Done. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode136 main.cpp:136: StronglyConnectedComponent component; On 2012/05/19 16:39:53, ys.algorithms wrote: > Эта переменная дважды объявлена - здесь и в цикле. Done. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode141 main.cpp:141: vector<int> componentVertexOpenedTime(graph.VerticesCount(), NOT_VISIT_VERTEX_OPEN_TIME); On 2012/05/19 16:39:53, ys.algorithms wrote: > Почему для времени используется та же переменная time, а для вектора времён > входа создаётся новая переменная? Done. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode164 main.cpp:164: Graph CutOutSubgraph(const Graph& graph, const std::vector<int>& vertices) { On 2012/05/19 16:39:53, ys.algorithms wrote: > Почему здесь подграф возвращается по значению (а это удобно), а функция > обращения графа принимает указатель? Не очень понимаю в чем проблема - на вход метод получает граф и набор вершин. Строит новый граф - подграф на этом наборе вершин. В чем ошибка? https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode174 main.cpp:174: std::find(vertices.begin(), vertices.end(), tailVertex) - vertices.begin(); On 2012/05/19 16:39:53, ys.algorithms wrote: > В этой задаче это, конечно, неважно, но вообще так эффективно найти КСС и после > этого так неэффективно вырезать подграф - странно. Алгоритм работает за O(VE). > Быстрее сделать легко: предпосчитать номер каждой необходимой вершины, а тем, > которые не входят в подграф, проставить специальный флажок. Это делается за > O(V). Если посмотреть по истории коммитов, то вначале так и было сделано. Не совсем так, но идея такая же. Метод поиска отрицательного цикла использовал в качестве таких флажков, собственно, саму компоненту связности. Но Петр предложил сделать более универсальный метод, который находил отрицательный цикл в графе, поэтому предложил мне реализовать метод строящий подграф на вершинах компоненты. Вернуть назад? или оставить текущую версию? https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode219 main.cpp:219: int minVertexIndex = -1; On 2012/05/19 16:39:53, ys.algorithms wrote: > Это в именованную константу, ведь она используется и в другой функции. А логично было бы завести еще одну именованную константу, также со значение -1? Ведь, откровенно говоря, это разные по смыслу константы.
Sign in to reply to this message.
Надо исправить. Андрей. https://codereview.appspot.com/6002059/diff/21001/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode64 main.cpp:64: m_adjacentEdgesList[headVertex].push_back(Edge(headVertex, tailVertex, edgeWeight)); Надо исправить названия по всему коду. Дуга - ребро из i в j - имеет хвост i и голову j. Ты хочешь хранить в векторе e[i] набор выходящих из i рёбер - это естественно. При этом i - это не head vertex, а tail. On 2012/05/23 20:22:41, shtokhov wrote: > On 2012/05/19 16:39:53, ys.algorithms wrote: > > Я тоже в этом месте раньше ошибался: оказывается, в графовой терминологии дуга > в > > орграфе идёт из tail в head, что, если подумать, можно даже найти логичным. У > > тебя же явно хранится список исходящих дуг, а не входящих. > > И ниже в коде тоже есть где исправить употребление терминов. > > Я не очень понимаю. Что значит "в графовой терминологии"? У меня хранятся все > исходящие ребра из вершины графа. А как надо хранить? Не понимаю, что надо > исправить? https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode164 main.cpp:164: Graph CutOutSubgraph(const Graph& graph, const std::vector<int>& vertices) { Я не писал, что есть ошибка. Я задал вопрос, почему здесь результат - граф - возвращается по значению из функции (это когда пишут return graph), а выше в функции обращения графа та же задача решается путём приёма указателя на ответ? Следует соблюдать единство, причём стиль этой функции предпочтителен. On 2012/05/23 20:22:41, shtokhov wrote: > On 2012/05/19 16:39:53, ys.algorithms wrote: > > Почему здесь подграф возвращается по значению (а это удобно), а функция > > обращения графа принимает указатель? > Не очень понимаю в чем проблема - на вход метод получает граф и набор вершин. > Строит новый граф - подграф на этом наборе вершин. В чем ошибка? https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode174 main.cpp:174: std::find(vertices.begin(), vertices.end(), tailVertex) - vertices.begin(); Одно другому не мешает. Я полностью поддерживаю, что функция нахождения цикла должна работать от любого графа. Я лишь предлагаю оптимизировать именно эту функцию получения подграфа. С точки зрения интерфейса ничего не изменится, всё внутри. On 2012/05/23 20:22:41, shtokhov wrote: > On 2012/05/19 16:39:53, ys.algorithms wrote: > > В этой задаче это, конечно, неважно, но вообще так эффективно найти КСС и > после > > этого так неэффективно вырезать подграф - странно. Алгоритм работает за O(VE). > > Быстрее сделать легко: предпосчитать номер каждой необходимой вершины, а тем, > > которые не входят в подграф, проставить специальный флажок. Это делается за > > O(V). > Если посмотреть по истории коммитов, то вначале так и было сделано. Не совсем > так, но идея такая же. Метод поиска отрицательного цикла использовал в качестве > таких флажков, собственно, саму компоненту связности. Но Петр предложил сделать > более универсальный метод, который находил отрицательный цикл в графе, поэтому > предложил мне реализовать метод строящий подграф на вершинах компоненты. Вернуть > назад? или оставить текущую версию? https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode219 main.cpp:219: int minVertexIndex = -1; Конечно, причём это обязательно надо сделать. On 2012/05/23 20:22:41, shtokhov wrote: > On 2012/05/19 16:39:53, ys.algorithms wrote: > > Это в именованную константу, ведь она используется и в другой функции. > А логично было бы завести еще одну именованную константу, также со значение -1? > Ведь, откровенно говоря, это разные по смыслу константы. > https://codereview.appspot.com/6002059/diff/25003/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/25003/main.cpp#newcode139 main.cpp:139: verticesOpenedTime.resize(graph.VerticesCount(), NOT_VISITED_VERTEX); Эти две операции заменяются на одну - assign вместо resize.
Sign in to reply to this message.
https://codereview.appspot.com/6002059/diff/21001/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode64 main.cpp:64: m_adjacentEdgesList[headVertex].push_back(Edge(headVertex, tailVertex, edgeWeight)); On 2012/05/23 21:59:41, ys.algorithms wrote: > Надо исправить названия по всему коду. Дуга - ребро из i в j - имеет хвост i и > голову j. Ты хочешь хранить в векторе e[i] набор выходящих из i рёбер - это > естественно. При этом i - это не head vertex, а tail. > > > On 2012/05/23 20:22:41, shtokhov wrote: > > On 2012/05/19 16:39:53, ys.algorithms wrote: > > > Я тоже в этом месте раньше ошибался: оказывается, в графовой терминологии > дуга > > в > > > орграфе идёт из tail в head, что, если подумать, можно даже найти логичным. > У > > > тебя же явно хранится список исходящих дуг, а не входящих. > > > И ниже в коде тоже есть где исправить употребление терминов. > > > > Я не очень понимаю. Что значит "в графовой терминологии"? У меня хранятся все > > исходящие ребра из вершины графа. А как надо хранить? Не понимаю, что надо > > исправить? > Разобрался. Важное замечание, спасибо. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode76 main.cpp:76: vector<int>* vertexVisitOrder) { On 2012/05/19 16:39:53, ys.algorithms wrote: > Порядок бывает разным. Надо указать, какой именно - post order, или exit order. Done. https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode164 main.cpp:164: Graph CutOutSubgraph(const Graph& graph, const std::vector<int>& vertices) { On 2012/05/23 21:59:41, ys.algorithms wrote: > Я не писал, что есть ошибка. > Я задал вопрос, почему здесь результат - граф - возвращается по значению из > функции (это когда пишут return graph), а выше в функции обращения графа та же > задача решается путём приёма указателя на ответ? > Следует соблюдать единство, причём стиль этой функции предпочтителен. > > > On 2012/05/23 20:22:41, shtokhov wrote: > > On 2012/05/19 16:39:53, ys.algorithms wrote: > > > Почему здесь подграф возвращается по значению (а это удобно), а функция > > > обращения графа принимает указатель? > > Не очень понимаю в чем проблема - на вход метод получает граф и набор вершин. > > Строит новый граф - подграф на этом наборе вершин. В чем ошибка? > Я раньше все возвращал по ссылке, чтобы не выполнять лишнего копирования объектов. Возвращаемые по значению, при возврате в вызывающий метод копируются в стеке, правильно я понимаю? это же не эффективно, почему "причём стиль этой функции предпочтителен" ? Вроде как и советовал Миша (я могу ошибаться) передавать объекты ко указателю, если объект будет меняться, и по константной ссылке, если объект остается неизменным в методе. В других языках оперируют ссылками, и такой проблемы вообще не стоит. Конечно же, удобнее писать, что метод возвращает какой то объект(по сути возвращается ссылка на объект из кучи), поэтому случайно возникло "отсутствие единообразия":) https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode174 main.cpp:174: std::find(vertices.begin(), vertices.end(), tailVertex) - vertices.begin(); On 2012/05/23 21:59:41, ys.algorithms wrote: > Одно другому не мешает. Я полностью поддерживаю, что функция нахождения цикла > должна работать от любого графа. > Я лишь предлагаю оптимизировать именно эту функцию получения подграфа. С точки > зрения интерфейса ничего не изменится, всё внутри. > > On 2012/05/23 20:22:41, shtokhov wrote: > > On 2012/05/19 16:39:53, ys.algorithms wrote: > > > В этой задаче это, конечно, неважно, но вообще так эффективно найти КСС и > > после > > > этого так неэффективно вырезать подграф - странно. Алгоритм работает за > O(VE). > > > Быстрее сделать легко: предпосчитать номер каждой необходимой вершины, а > тем, > > > которые не входят в подграф, проставить специальный флажок. Это делается за > > > O(V). > > Если посмотреть по истории коммитов, то вначале так и было сделано. Не совсем > > так, но идея такая же. Метод поиска отрицательного цикла использовал в > качестве > > таких флажков, собственно, саму компоненту связности. Но Петр предложил > сделать > > более универсальный метод, который находил отрицательный цикл в графе, поэтому > > предложил мне реализовать метод строящий подграф на вершинах компоненты. > Вернуть > > назад? или оставить текущую версию? > Я сделал такую маску с пред подсчитанными номерами вершин для подграфа, но работает за O(VE). Раньше работал за O(V^2*E), но не понимаю как сделать за O(V) - такое возможно вообще? мы для каждой вершины, должны добавить все возможные ребра. То есть для каждой вершины подграфа мы проходим циклом по всем ребрам и добавляем ребро или нет - это уже O(VE). https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode219 main.cpp:219: int minVertexIndex = -1; On 2012/05/23 21:59:41, ys.algorithms wrote: > Конечно, причём это обязательно надо сделать. > > On 2012/05/23 20:22:41, shtokhov wrote: > > On 2012/05/19 16:39:53, ys.algorithms wrote: > > > Это в именованную константу, ведь она используется и в другой функции. > > А логично было бы завести еще одну именованную константу, также со значение > -1? > > Ведь, откровенно говоря, это разные по смыслу константы. > > > Done.
Sign in to reply to this message.
Засчитываем. Андрей. https://codereview.appspot.com/6002059/diff/21001/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode164 main.cpp:164: Graph CutOutSubgraph(const Graph& graph, const std::vector<int>& vertices) { Объект может копироваться, но на практике этого не происходит, потому что все компиляторы умеют делать return value optimization. Поэтому если функция возвращает одно значение, можно смело писать return result; и не думать о скорости работы - о нас позаботились. По указателю надо передавать объекты, если или они уже инициализированы и мы их изменяем, или если требуется из функции вернуть несколько объектов. On 2012/05/25 22:05:55, shtokhov wrote: > On 2012/05/23 21:59:41, ys.algorithms wrote: > > Я не писал, что есть ошибка. > > Я задал вопрос, почему здесь результат - граф - возвращается по значению из > > функции (это когда пишут return graph), а выше в функции обращения графа та же > > задача решается путём приёма указателя на ответ? > > Следует соблюдать единство, причём стиль этой функции предпочтителен. > > > > > > On 2012/05/23 20:22:41, shtokhov wrote: > > > On 2012/05/19 16:39:53, ys.algorithms wrote: > > > > Почему здесь подграф возвращается по значению (а это удобно), а функция > > > > обращения графа принимает указатель? > > > Не очень понимаю в чем проблема - на вход метод получает граф и набор > вершин. > > > Строит новый граф - подграф на этом наборе вершин. В чем ошибка? > > > Я раньше все возвращал по ссылке, чтобы не выполнять лишнего копирования > объектов. Возвращаемые по значению, при возврате в вызывающий метод копируются в > стеке, правильно я понимаю? это же не эффективно, почему "причём стиль этой > функции предпочтителен" ? Вроде как и советовал Миша (я могу ошибаться) > передавать объекты ко указателю, если объект будет меняться, и по константной > ссылке, если объект остается неизменным в методе. В других языках оперируют > ссылками, и такой проблемы вообще не стоит. Конечно же, удобнее писать, что > метод возвращает какой то объект(по сути возвращается ссылка на объект из кучи), > поэтому случайно возникло "отсутствие единообразия":) https://codereview.appspot.com/6002059/diff/21001/main.cpp#newcode174 main.cpp:174: std::find(vertices.begin(), vertices.end(), tailVertex) - vertices.begin(); O(V) - я имел в виду именну ту часть. Сейчас функция работает, разумеется, за O(E). Иначе, рассуждая аналогично, ты бы и на DFS получил оценку O(VE). Она верная - бесспорно, но грубая. On 2012/05/25 22:05:55, shtokhov wrote: > On 2012/05/23 21:59:41, ys.algorithms wrote: > > Одно другому не мешает. Я полностью поддерживаю, что функция нахождения цикла > > должна работать от любого графа. > > Я лишь предлагаю оптимизировать именно эту функцию получения подграфа. С точки > > зрения интерфейса ничего не изменится, всё внутри. > > > > On 2012/05/23 20:22:41, shtokhov wrote: > > > On 2012/05/19 16:39:53, ys.algorithms wrote: > > > > В этой задаче это, конечно, неважно, но вообще так эффективно найти КСС и > > > после > > > > этого так неэффективно вырезать подграф - странно. Алгоритм работает за > > O(VE). > > > > Быстрее сделать легко: предпосчитать номер каждой необходимой вершины, а > > тем, > > > > которые не входят в подграф, проставить специальный флажок. Это делается > за > > > > O(V). > > > Если посмотреть по истории коммитов, то вначале так и было сделано. Не > совсем > > > так, но идея такая же. Метод поиска отрицательного цикла использовал в > > качестве > > > таких флажков, собственно, саму компоненту связности. Но Петр предложил > > сделать > > > более универсальный метод, который находил отрицательный цикл в графе, > поэтому > > > предложил мне реализовать метод строящий подграф на вершинах компоненты. > > Вернуть > > > назад? или оставить текущую версию? > > > Я сделал такую маску с пред подсчитанными номерами вершин для подграфа, но > работает за O(VE). Раньше работал за O(V^2*E), но не понимаю как сделать за O(V) > - такое возможно вообще? мы для каждой вершины, должны добавить все возможные > ребра. То есть для каждой вершины подграфа мы проходим циклом по всем ребрам и > добавляем ребро или нет - это уже O(VE). https://codereview.appspot.com/6002059/diff/25003/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/25003/main.cpp#newcode91 main.cpp:91: void SetStronglyConnectedComponentIndexes( И код упростился, и эффективнее стало. https://codereview.appspot.com/6002059/diff/31001/main.cpp File main.cpp (right): https://codereview.appspot.com/6002059/diff/31001/main.cpp#newcode149 main.cpp:149: vector<int> subgraphVertexIndices(graph.VerticesCount(), -1); И этот -1 в именованную константу, аж 3 раза встречается.
Sign in to reply to this message.
|
