search

eschombu / cisc4080

Fordham CISC 4080 Computer Algorithms
0 stars 3 forks source link

greedy algorithms - set cover extra credit #4

Open cshue1 opened 6 years ago

cshue1 commented 6 years ago

https://github.com/prof-erik/cisc4080/blob/012cc97a8742edb5a9883bdf18aa4b1ed6dec3d4/set_cover.cpp#L19-L20

What's the difference between these two maps? Is covering_vertex_status a boolean map that states whether or not the vertex is in the covering_vertices vector?

prof-erik commented 6 years ago

Good question, I'll add some comments to the code. The covering_vertices vector contains the subset of vertices used to cover the graph with its edges. The vertex_cover map holds boolean values indicating whether each vertex in the graph is covered by the covering_vertices. I additionally created the covering_vertex_status map to quickly check whether a particular vertex is in the covering_vertices container, so that you don't need to search through it each time you want to check if a vertex is already in it. Does that make sense?