4

I'm looking for a clever/fast C++ algorithm, which would allow me to do grouping of several lists of objects when they contain common objects inside. Let's say I have N lists, each containing 1..M objects (O) associated with one element E:

[O1, O2]     -> E1
[O3]         -> E2
[O1, O4, O5] -> E3
[O2, O5]     -> E4
[O3, O6]     -> E5

I wish to rearrange them into the following:

[O1, O2, O4, O5] -> [E1, E3, E4]
[O3, O6]         -> [E2, E5]

The result has all common objects grouped together with all associated elements. No object is shared in the end between lists.

krojew
  • 1,297
  • 15
  • 38
  • So, what have you tried? How do you read your input data? – Mihai Todor Mar 19 '13 at 15:29
  • Have you considered [`multimap`](http://en.cppreference.com/w/cpp/container/multimap)? See [When does using a std::multimap make sense](http://stackoverflow.com/questions/8342445/when-does-using-a-stdmultimap-make-sense) – Peter Wood Mar 19 '13 at 15:34

1 Answers1

6

For each object, calculate which elements contain it.

i.e.

01 -> [E1, E3]
02 -> [E4]
03 -> [E2, E5]
04 -> [E3]
05 -> [E3, E4]
06 -> [E5]

These lists induce a graph: there's a vertex per element, and two vertices are connected if the corresponding elements show up in the same list.

enter image description here

It seems to me that what you want to calculate are the connected components of the graph.

abeln
  • 3,749
  • 2
  • 22
  • 31
  • What if objects O were used as nodes? Helpers like boost::graph::connected_components could generate object groups in linear time and simple O->E multimap could then be used to generate element groups for each object group. Haven't had chance to test it yet, so I don't know if it's a correct approach. – krojew Mar 20 '13 at 08:13