search

jaredbeck / graph_matching

Finds maximum matchings in undirected graphs.
MIT License
45 stars 17 forks source link

don't require integer vertices #4

Closed BenMusch closed 7 years ago

BenMusch commented 7 years ago

I'd like to remove the check that the vertices are integers. Theoretically, vertices only need be able to have some sort of equality function.

BenMusch commented 7 years ago

This required more work than I thought... Will update this later

jaredbeck commented 7 years ago

I'd like to remove the check that the vertices are integers. Theoretically, vertices only need be able to have some sort of equality function.

Hi Ben, I'd like to remove that check also. I think it is possible, too. IIRC, at least one of the four algorithms expects integer vertices so it can use them as array indexes. So, I don't think we want to change that, but we could maintain a data structure that maps the original input vertices to integers. An array would probably be best. When the mapping is complete, this data structure would be used to recover the original input vertices.

jaredbeck commented 7 years ago

.. we could maintain a data structure that maps the original input vertices to integers ..

I already wrote something like this, actually, see GraphMatching::IntegerVertexes. (https://github.com/jaredbeck/graph_matching#limitations) It's not automatic though.

We might be able to use IntegerVertexes as a starting point for automatic conversion.

BenMusch commented 7 years ago

Yeah, saw the README afterwards -- I'll definitely look into it once I get some free time. Thanks for the response!