Skip to content

HopcroftKarpMatching Bug #34

@kazimierz-256

Description

@kazimierz-256

Given a simple fully connected bipartite graph K_{3,3} the maximum matching algorithm crashes with an error:
assuming U={A, B, C} and V={D, E, F}
the exception is raised in the following line:

https://github.com/justcoding121/Advanced-Algorithms/blob/0e1b90aaf322104ec9bdf7e5b4ab55a39e920aed/src/Advanced.Algorithms/Graph/Matching/HopcroftKarp.cs#L57

System.ArgumentException: 'An item with the same key has already been added. Key: E'

Since rightMatch dictionary already contains a mapping between E and A the algorithm cannot add a mapping between E and C on top of it

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