| 317 | } |
| 318 | |
| 319 | bool CanContractEdge(const SimpleEdge* edge, |
| 320 | const std::unique_ptr<SimpleGraph>& graph) { |
| 321 | const auto src = edge->src(); |
| 322 | const auto dst = edge->dst(); |
| 323 | |
| 324 | // Can't contract edge if doing so would cause a cycle in the |
| 325 | // graph. So, if there is a directed path from 'src' to 'dst', other |
| 326 | // than 'edge' (or any other direct edge from 'src' to 'dst'), then |
| 327 | // combining 'src' and 'dst' will cause a cycle along that path. |
| 328 | // |
| 329 | // In practice, to avoid modifying the graph and to take advantage |
| 330 | // of existing graph functions, we perform an equivalent. |
| 331 | // 1. Get all nodes incoming to 'dst', excluding 'src' |
| 332 | // 2. Reverse DFS from those nodes |
| 333 | // 3. If reverse DFS reaches 'src' then we have a cycle |
| 334 | // |
| 335 | // TODO(aaroey): there are several problems with the current approach: |
| 336 | // 1. src->dst->src, this is not detected but it should be; |
| 337 | // 2. src->dst->...(any node sequence that doesn't contain src)...->dst, this |
| 338 | // is detected but it should not be. |
| 339 | // |
| 340 | // Note that it's fine that dst connects back to src indirectly (i.e. through |
| 341 | // a path with length > 1 that consists of intermedia nodes other than src). |
| 342 | // While loops is one example. |
| 343 | // |
| 344 | // The goal is to make sure that the trt subgraph: |
| 345 | // 1. has no loops (i.e. is a DAG), and |
| 346 | // 2. if there is a path in the subgraph from X to Y (X and Y are both nodes |
| 347 | // in the subgraph), then all paths from X to Y are in the subgraph. |
| 348 | // |
| 349 | // To achieve this goal, the correct way seems to be: |
| 350 | // 1. remove any direct edge from src->dst; |
| 351 | // 2. detect if src can reach dst, if so they cannot be merged. |
| 352 | std::vector<const SimpleNode*> dfs_start_nodes; |
| 353 | for (const SimpleNode* node : dst->in_nodes()) { |
| 354 | if (node != src) { |
| 355 | dfs_start_nodes.push_back(node); |
| 356 | } |
| 357 | } |
| 358 | bool has_cycle = false; |
| 359 | StableDFS(*graph, /*reverse=*/true, dfs_start_nodes, /*enter=*/nullptr, |
| 360 | [&has_cycle, src](const SimpleNode* n) { |
| 361 | if (n == src) { |
| 362 | has_cycle = true; |
| 363 | return false; |
| 364 | } |
| 365 | return true; |
| 366 | }); |
| 367 | return !has_cycle; |
| 368 | } |
| 369 | } // namespace |
| 370 | |
| 371 | void ContractEdge(SimpleEdge* edge, SimpleGraph* graph, |