Skip to content

Improve findEdgeCovers #21

@cruizgo

Description

@cruizgo

So far, findEdgeCovers go through ALL edges of a graph looking for edge covers. By exploring all edges we find the same solutions several times, and then we filter them. That is not efficient.

By going through the different nodes in order, checking which combinations of its edges could be added in future edge covers we could save time. We would go to node A and try all combinations of a single edge, 2 edges, and so on till the total number of edges. We would also consider the option of getting no more edges from a node if this has already been covered.

Apart from speed, this method would allow us to introduce the new constraints we use, for example, to produce noon states. The new post-selection rules can be applied faster by doing this than by working with combinations_with_replacement and then filtering tons of wrong solutions.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions