Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Can we remove Directed trait constraint? #588

Open
Fomalhauthmj opened this issue Sep 30, 2023 · 0 comments
Open

Can we remove Directed trait constraint? #588

Fomalhauthmj opened this issue Sep 30, 2023 · 0 comments

Comments

@Fomalhauthmj
Copy link

After check the source code, I think from_sorted_edges also apply to undirected csr.

Source:
https://github.com/petgraph/petgraph/blame/2cf4969eefc8001a5135904fce2f8976e57d033d/src/csr.rs#L137

impl<N, E, Ix> Csr<N, E, Directed, Ix>
where
    Ix: IndexType,
{
    /// Create a new `Csr` from a sorted sequence of edges
    ///
    /// Edges **must** be sorted and unique, where the sort order is the default
    /// order for the pair *(u, v)* in Rust (*u* has priority).
    ///
    /// Computes in **O(|E| + |V|)** time.
    /// # Example
    /// ```rust
    /// use petgraph::csr::Csr;
    /// use petgraph::prelude::*;
    ///
    /// let graph = Csr::<(),()>::from_sorted_edges(&[
    ///                     (0, 1), (0, 2),
    ///                     (1, 0), (1, 2), (1, 3),
    ///                     (2, 0),
    ///                     (3, 1),
    /// ]);
    /// ```
    pub fn from_sorted_edges<Edge>(edges: &[Edge]) -> Result<Self, EdgesNotSorted>
    where
        Edge: Clone + IntoWeightedEdge<E, NodeId = NodeIndex<Ix>>,
        N: Default,
    {
        let max_node_id = match edges
            .iter()
            .map(|edge| {
                let (x, y, _) = edge.clone().into_weighted_edge();
                max(x.index(), y.index())
            })
            .max()
        {
            None => return Ok(Self::with_nodes(0)),
            Some(x) => x,
        };
        let mut self_ = Self::with_nodes(max_node_id + 1);
        let mut iter = edges.iter().cloned().peekable();
        {
            let mut rows = self_.row.iter_mut();

            let mut rstart = 0;
            let mut last_target;
            'outer: for (node, r) in (&mut rows).enumerate() {
                *r = rstart;
                last_target = None;
                'inner: loop {
                    if let Some(edge) = iter.peek() {
                        let (n, m, weight) = edge.clone().into_weighted_edge();
                        // check that the edges are in increasing sequence
                        if node > n.index() {
                            return Err(EdgesNotSorted {
                                first_error: (n.index(), m.index()),
                            });
                        }
                        /*
                        debug_assert!(node <= n.index(),
                                      concat!("edges are not sorted, ",
                                              "failed assertion source {:?} <= {:?} ",
                                              "for edge {:?}"),
                                      node, n, (n, m));
                                      */
                        if n.index() != node {
                            break 'inner;
                        }
                        // check that the edges are in increasing sequence
                        /*
                        debug_assert!(last_target.map_or(true, |x| m > x),
                                      "edges are not sorted, failed assertion {:?} < {:?}",
                                      last_target, m);
                                      */
                        if !last_target.map_or(true, |x| m > x) {
                            return Err(EdgesNotSorted {
                                first_error: (n.index(), m.index()),
                            });
                        }
                        last_target = Some(m);
                        self_.column.push(m);
                        self_.edges.push(weight);
                        rstart += 1;
                    } else {
                        break 'outer;
                    }
                    iter.next();
                }
            }
            for r in rows {
                *r = rstart;
            }
        }

        Ok(self_)
    }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant