Relationship Data Structure

Question

I am converting VB6 to C # and I want to create my own data structure that will support values ​​and relationships more efficiently. In VB, I have a set of values ​​and another set of relationships between these values ​​with priorities for these relationships. I also have an algorithm that, when a set of values ​​is passed, it returns all the relationships necessary to combine these values ​​together. For example, let's say that the collection of values ​​contains 1-10, and the collection of relations contains

1,2
3.2
5.2
2,8
8.10
9.10

If the input was 1,9,10, the returned relationship would be -

1,2
2,8
8.10
9.10

Since there can be several paths, the least number of relationships will be returned, but there is a caution about the priorities of the relationships. If the relationship has a higher priority, then this relationship will be added, and the rest of the relationship will be added from there. I am thinking of using a data structure with unrelated sets , but I'm not sure.

Any ideas?

thank

Additional Information -

The number of values ​​will usually be less than 100, and relationships less than 500. Collections are static, and the algorithm will be used again and again to find paths. In addition, I did not ask about this, but is the "Data structure with unrelated sets" algorithm most effective ?

Answer 1

It looks like you have a Graph . This is a structure with nodes and edges. There are many many libraries and tools that deal with charts. Microsoft has even published a document on how to deal with them. I think the graphs are very large and extremely useful in many situations.

One big advantage with graphs is the ability to prioritize edges between nodes. Then, when you want to find a path between two nodes, an arrow, the graph can select a path with perfect priority.

In your situation, your meanings are nodes, and your relationships are edges.

Answer 2

You need to ask yourself (and tell us) which usage model you expect. Whether these relationships are connected in order or randomly, your requests come in order (as you show them) or randomly, and this is essentially a batch process — load them, read requests — or do you expect it to be “on line” in in the sense that you can add some, then request some, then add some more and request more?

Do you know how much you want to save in advance, and how much do you expect to save? Dozens? Thousands? Tens of millions?

Here are some suggestions:

• if you know in advance how much you expect to save, this is not really a large number, you do not expect to add them after the first load, they are not duplicates on the left side of the pair and they are sufficiently "dense" in that there are no large spaces between the numbers on the left side of the pair then you probably want an array. Insert is O (1), access is O (1), but cannot have duplicate indices and expanding it after you create it is a pain.
• if the number is really large, for example> 10 ⁸ , you probably need some kind of database. Databases are relatively very slow - from 4 to 5 orders more than in the data structures in memory - but process really big data.
• If you have inserts after the first boot, and you care about the order, you will want a tree like 2-3 trees. insert and access O (lg n). You will probably find an implant called an "ordered list", (I'm not a C # guy.)
• In any other case, you probably want a hash. Middle insert and access to O (1) as an array; worst case [which you will not be this data] O (n)