/// Convert a point graph to a euler graph.
///
/// This determines the minimum number of blank segments necessary to create a euler circuit
/// from the given point graph. A euler circuit is useful as it represents a graph that can be
/// drawn unicursally (one continuous path that covers all nodes while only traversing each edge
/// once).
Convert a point graph to a euler graph.
This determines the minimum number of blank segments necessary to create a euler circuit
from the given point graph. A euler circuit is useful as it represents a graph that can be
drawn unicursally (one continuous path that covers all nodes while only traversing each edge
once).
Convert a point graph to a euler graph . This determines the minimum number of blank segments necessary to create a euler circuit from the given point graph . A euler circuit is useful as it represents a graph that can be drawn unicursally ( one continuous path that covers all nodes while only traversing each edge once ) .
pub fn point_graph_to_euler_graph(pg: &PointGraph) -> EulerGraph {
    // Find the connected components.
    let ccs = petgraph::algo::kosaraju_scc(pg);
    // The indices of the connected components whose nodes all have an even degree.
    let euler_components: hashbrown::HashSet<_> = ccs
        .iter()
        .enumerate()
        .filter(|(_, cc)| cc.iter().all(|&n| pg.edges(n).count() % 2 == 0))
        .map(|(i, _)| i)
        .collect();
    // Represents the nodes to be connected for a single component.
    struct ToConnect {
        // Connection to the previous component.
        prev: NodeIndex,
        // Consecutive connections within the component.
        inner: Vec<NodeIndex>,
        // Connection to the next component.
        next: NodeIndex,
    }
    // Collect the free nodes from each connected component that are to be connected by blanks.
    let mut to_connect = vec![];
    for (i, cc) in ccs.iter().enumerate() {
        if euler_components.contains(&i) {
            // Take the first point.
            let n = cc[0];
            to_connect.push(ToConnect {
                prev: n,
                inner: vec![],
                next: n,
            });
        } else {
            let v: Vec<_> = cc
                .iter()
                .filter(|&&n| pg.edges(n).count() % 2 != 0)
                .collect();
            // If there's a single point, connect to itself.
            if v.len() == 1 {
                let p = *v[0];
                let prev = p;
                let inner = vec![];
                let next = p;
                to_connect.push(ToConnect { prev, inner, next });
                continue;
            // Otherwise convert to a euler component.
            } else {
                assert_eq!(
                    v.len() % 2,
                    0,
                    "expected even number of odd-degree nodes for non-Euler component",
                );
                let prev = *v[0];
                let inner = v[1..v.len() - 1].iter().map(|&&n| n).collect();
                let next = *v[v.len() - 1];
                to_connect.push(ToConnect { prev, inner, next });
            }
        }
    }
    // Convert the `to_connect` Vec containing the nodes to be connected for each connected
    // component to a `Vec` containing the pairs of nodes which will be directly connected.
    let mut pairs = vec![];
    let mut iter = to_connect.iter().enumerate().peekable();
    while let Some((i, this)) = iter.next() {
        for ch in this.inner.chunks(2) {
            pairs.push((ch[0], ch[1]));
        }
        match iter.peek() {
            Some((_, next)) => pairs.push((this.next, next.prev)),
            None if i > 0 => pairs.push((this.next, to_connect[0].prev)),
            None => match euler_components.contains(&0) {
                // If there is only one component and it is euler, we are done.
                true => (),
                // If there is only one non-euler, connect it to itself.
                false => pairs.push((this.next, this.prev)),
            },
        }
    }
    // Turn the graph into a euler graph by adding the blanks.
    let mut eg = pg.map(|_n_ix, n| n.clone(), |_e_ix, _| SegmentKind::Lit);
    for (na, nb) in pairs {
        eg.add_edge(na, nb, SegmentKind::Blank);
    }
    eg
}
pub fn point_graph_to_euler_graph ( pg : & PointGraph ) -> EulerGraph { // Find the connected components. let ccs = petgraph :: algo :: kosaraju_scc ( pg ) ; // The indices of the connected components whose nodes all have an even degree. let euler_components : hashbrown :: HashSet < _ > = ccs . iter ( ) . enumerate ( ) . filter ( | ( _ , cc ) | cc . iter ( ) . all ( | & n | pg . edges ( n ) . count ( ) % 2 == 0 ) ) . map ( | ( i , _ ) | i ) . collect ( ) ; // Represents the nodes to be connected for a single component. struct ToConnect { // Connection to the previous component. prev : NodeIndex , // Consecutive connections within the component. inner : Vec < NodeIndex > , // Connection to the next component. next : NodeIndex , } // Collect the free nodes from each connected component that are to be connected by blanks. let mut to_connect = vec ! [ ] ; for ( i , cc ) in ccs . iter ( ) . enumerate ( ) { if euler_components . contains ( & i ) { // Take the first point. let n = cc [ 0 ] ; to_connect . push ( ToConnect { prev : n , inner : vec ! [ ] , next : n , } ) ; } else { let v : Vec < _ > = cc . iter ( ) . filter ( | & & n | pg . edges ( n ) . count ( ) % 2 != 0 ) . collect ( ) ; // If there's a single point, connect to itself. if v . len ( ) == 1 { let p = * v [ 0 ] ; let prev = p ; let inner = vec ! [ ] ; let next = p ; to_connect . push ( ToConnect { prev , inner , next } ) ; continue ; // Otherwise convert to a euler component. } else { assert_eq ! ( v len ( ) 2 0 " " ) ; let prev = * v [ 0 ] ; let inner = v [ 1 .. v . len ( ) - 1 ] . iter ( ) . map ( | & & n | n ) . collect ( ) ; let next = * v [ v . len ( ) - 1 ] ; to_connect . push ( ToConnect { prev , inner , next } ) ; } } } // Convert the `to_connect` Vec containing the nodes to be connected for each connected // component to a `Vec` containing the pairs of nodes which will be directly connected. let mut pairs = vec ! [ ] ; let mut iter = to_connect . iter ( ) . enumerate ( ) . peekable ( ) ; while let Some ( ( i , this ) ) = iter . next ( ) { for ch in this . inner . chunks ( 2 ) { pairs . push ( ( ch [ 0 ] , ch [ 1 ] ) ) ; } match iter . peek ( ) { Some ( ( _ , next ) ) => pairs . push ( ( this . next , next . prev ) ) , None if i > 0 => pairs . push ( ( this . next , to_connect [ 0 ] . prev ) ) , None => match euler_components . contains ( & 0 ) { // If there is only one component and it is euler, we are done. true => ( ) , // If there is only one non-euler, connect it to itself. false => pairs . push ( ( this . next , this . prev ) ) , } , } } // Turn the graph into a euler graph by adding the blanks. let mut eg = pg . map ( | _n_ix , n | n . clone ( ) , | _e_ix , _ | SegmentKind :: Lit ) ; for ( na , nb ) in pairs { eg . add_edge ( na , nb , SegmentKind :: Blank ) ; } eg }
Convert a point graph to a euler graph.
Convert a point graph to a euler graph .
pg
&PointGraph