C# Many To Many Relationship

Question

So, I need some way to implement an undirected network ( I think this is the correct term ) in C#

Let's say I have the following data:

Foo1 <-> Bar1
Foo2 <-> Bar1
Foo2 <-> Bar2
Foo2 <-> Bar3
Foo3 <-> Bar2
Foo3 <-> Bar3

How would I implement something that could support this?

One way to do this would be to create a class containing a Foo, and a Bar, and for my example I'd have 6 of these, with each possible combination, however this doubles up data.

With this data, I need to be able to perform calculations on Foo1 based on how many Bar's it points too, and how many Foo's the Bar's point too etc etc.

I'm not looking for an answer, I'd rather some direction on how to implement this, maybe even a few links.

Answer 1

Well, without giving you an answer, think about what can be done with 2-dimensional arrays and thinking about the problem from the perspective of storing information about edges.

Answer 2

each class could have a list of the type of the other. You dont duplicate the data this way unless you are using value types. the cross references could make for memory leaks.

Answer 3

This smells like a relational database problem to me. What you have described is two tables with a many-to-many relationship. Whether this answer is appropriate will depend a lot on what your data actually looks like. The previous suggestion of having each object contain a List of the other object is one way, but let's call a spade a spade, this is a relational database. Consider using a technology like the ADO.Net Entity Framework or LINQ to define your data as a relational database and use LINQ to query the data.

You mention that you're concerned about doubling the memory. Again this depends on what your real-world data looks like, but unless you have massive amounts of data, this is probably not going to be an issue. The only wasted memory is empty memory. Use the memory, if it (a) makes the problem easier to solve or (b) gives you more flexibility. Don't optimise unless you have a performance problem.

Answer 4

What Joe said is on the right track. Each Loan would have a list of Security instances and each Security would have a list of Loan instances. The trick is to make sure you never have a Loan that thinks it's related to a Security but that Security doesn't agree. I would suggest allowing Add or Remove operations only on pairs, to ensure that they're done in parallel. I don't see how this would cause memory leaks, since the GC is smart enough to handle this. Reference-counting, in contrast, can't handle this without some tricks.

Answer 5

You've basically outlined a graph model, traditionally thought of as 'nodes' and 'edges'. But the securities/loans works.

There are two classic answers to this sort of thing.

It depends what questions you want to be able to ask of your data, how efficiently you want to store it, and how dense your data is.

If, say, 30% of possible relations between securities and loans exist, then a dense data structure will definitely pay off. Just keep a big matrix: Securities on X. Loans on Y. (X,Y) means that the loan exists.

If the set isn't very dense, then you start using "sparse edge data structures." Depending on your application, you might:

1. Any S object has a list of it's Ls. { S->L,L,L; S->L; S->L,L,L }. Makes it really easy to find S's neighbors, but hard to find L's

2. S objects have a list of Ls, Ls have a list of S's: (S->L,L,L and L->S,S,S). Uses more space, but gives you both-directional queries.

3. Store a set of just (S,L) pairs. Pretty bad unless you mostly need to ask "are this S and and that L related?"

4. Store a list of both S,L and L,S and index it somehow. This is what we mean by "make your database do the work."

See also http://stackoverflow.com/questions/386464/data-structure-for-relationships