Skip to content

from_graph seems to enter infinite loop #25

Description

@MrD4rkne

Hi, I've noticed that for some of the graph there's a chance that the algo will enter what seems to be an indefinite loop.
At least it looks like from logs, but I haven't dug into it. I've left it for quite a time and it was still running.

Example

use env_logger;
use log::info;
use petgraph::stable_graph::StableDiGraph;
use rust_sugiyama::configure::Config;
use rust_sugiyama::from_graph;

fn main() {
    // let _ = env_logger::Builder::from_env(env_logger::Env::default().default_filter_or("trace"))
    //     .try_init();
    info!("running repro_hang_n5 example");

    let mut g: StableDiGraph<(), ()> = StableDiGraph::new();
    let nodes: Vec<_> = (0..5).map(|_| g.add_node(())).collect();

    let edges = vec![
        (0, 1),
        (0, 2),
        (0, 3),
        (1, 0),
        (1, 3),
        (2, 0),
        (2, 3),
        (3, 0),
        (4, 1),
        (4, 2),
    ];
    for (t, h) in edges {
        g.add_edge(nodes[t], nodes[h], ());
    }

    let cfg = Config::default();
    let layouts = from_graph(&g, &|_, _| (40.0, 20.0), &cfg);
    info!("layouts computed: {} components", layouts.len());
}

it seems to be stuck inside calculate_cut_values. Happens only for

ranking_type: rust_sugiyama::configure::RankingType::MinimizeEdgeLength,

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions