CODEWITHSUNDEEP
c++data-structureshashmap
javaLover
javaLover

Reputation: 6425

Datastructure : Many (A) to many (B) relationship, each link also has its own data (C)

What is a datastructure that is suitable to keep many-to-many relationships (A-B), each link of relation has its own user-data (C)?

I care most about performance.

Example 1

There are many 2D circles in a scene.
They can grow and overlap each other (circle A & circle B).
I have to keep track the overlap zones (C), e.g. color.

Example 2

There are many investors (A), and stocks (B).
Each investor (A) has %ownership/occupation (C) for a company (B).

Example 3

This is a real situation. I don't thing you need to read it.
I provide it just in case.

I am using entity-component-based architecture.

There are many joysticks (A), each joystick can click buttons (B).

Note that the buttons (B) are those on the game screen. (not the Joystick hardware buttons)

I have to keep track (using C) whether a button is "hovered" by a joystick, and execute callback.

One of the reasons that I have to keep track is : there are criteria whether it should callback.
It is same as standard Windows button :-

One of other reasons is : a mouse can hover many buttons at once. I have to record duration of hovering too. (for graphic)

A,B and C are all components.

Amount of A and B are not known at compile time.

My poor solutions

The 1st solution :

HashMap<A*,HashMap<B*,C*>> database;

It is a bit not symmetry. (query A before B)

The 2nd solution :

class CustomStruct{  A* a; B* b; }
HashMap<CustomStruct,C*> database;

Cannot query C from A efficiently.

The 3rd solution :

HashMap<A*,C*> databaseAC;
HashMap<B*,C*> databaseBC;

Split it into two HashMap, and query (A,B)->C by expensive intersecting two tables.

The 4th solution :

class A{HashMap<B*,C*> databaseBC;};
class B{HashMap<A*,C*> databaseAC;};

might be good?

Other thought:

Should I use HashMap at all? Should I try something more out of the box?
Are some of my solution promising? (Which one experts will pick?)
Is the best solution "depend" on the access/query pattern?

Upvotes: 0

Views: 77

Answers (1)

Gene
Gene

Reputation: 46960

A many-to-many relation with link attributes is an undirected graph. All of the options for graph implementation apply. The graph terminology for the object is "node." The relation pairs are "edges."

  • Matrix: Map your objects from indices. E.g. use an array of pointers or references to take an index to an object, then pass the indices around in your program to refer to objects. Represent edges as a square matrix of attribute records. Since your graph is undirected, the matrix can be triangular. There is a fairly cool way of addressing elements of a triangular matrix stored in a 1d vector, though changing the node count with this method is expensive. The other method is to use an array of pointers to rows of different length.

  • Adjacency list: Use the same index->object mapping array as above. Represent adjacencies as an array of sets of indices. Again since your graph is undirected, you only need to store adjacency pairs i -> j where i <= j.

There are other options for adjacency lists, but arrays and indices are handy (indices are nicer to debug than pointers), memory efficient (a 32-bit index allows 4 billion nodes; 64-bit pointers allow a lot more, but waste a factor of 2 in space in most applications), and very fast (compared to hashmap-based solutions).

The choice between the two is all about density if edges. The matrix is very fast, but if density is low, most of the matrix is empty. Just initializing it can become expensive. So if nearly all node pairs have edges, use a matrix. If connections are sparse, the adjacency list wins.

Upvotes: 1

Related Questions