Method cycle_paths

src/detector/lock/mod.rs:904–932

Find all the cycles in the graph.

(&self)

        let mut back_edges = Vec::new();
        let nodes = self.graph.node_indices();
        for start in nodes {
            depth_first_search(&self.graph, Some(start), |event| {
                match event {
                    DfsEvent::BackEdge(u, v) => {
                        if !back_edges.contains(&(u, v)) && !back_edges.contains(&(v, u)) {
                            back_edges.push((u, v));
                        }
                    }
                    DfsEvent::Finish(_, _) => {
                        return Control::Break(());
                    }
                    _ => {}
                };
                Control::Continue
            });
        }
        back_edges
    }

    /// Find all the cycles in the graph.
    fn cycle_paths(&self) -> Vec<Vec<RelationId>> {
        let mut dedup = Vec::new();
        let mut edge_sets = Vec::new();
        for (src, target) in self.back_edges() {
            // FIXME(boqin): all_simple_paths may return infinitely many paths. I think this is a bug in petgraph.
            // The issue is tracked in https://github.com/petgraph/petgraph/issues/680.
            // Before a patch is available, I limit the path number with MAX_PATH_NUM = 100. I think 100 is enough for most cases.
            const MAX_PATH_NUM: usize = 100;
            let cycle_paths =
                algo::all_simple_paths::<Vec<_>, _>(&self.graph, target, src, 0, None)
                    .take(MAX_PATH_NUM)
                    .collect::<Vec<_>>();