Skip to content

Project-to-DAG runtime #205

@cnellington

Description

@cnellington

Currently we do DAG projection by binary search O(logn) over sorted weights O(nlogn), checking if the graph where weights > threshold is a DAG via igraph is_dag O(n*n). The igraph implementation gets a spanning tree to check for dagness. This is prohibitively slow for large DAGs.

Can we speed this up? Maybe by using spanning trees to construct a new graph.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions