Question

I am writing a simulation in c++ with a lot of little entities indexed by an integer, each having relationships of various types with one another. I have a basic structure storing the data about the relationship, and the relationships are unidirectional (A can be friends with B but B doesn't necessarily have any relationship with A).

So I have a lot of data that has the form (integer index, integer index, data...)

  1. I will very often need to start with an entity (index) and find all of the relationships it has with others (so all triples with the first entry equal to some index).

  2. I also will sometimes need to remove entities from the simulation and destroy all relationships that reference them (remove all triples with either the first or second entry equal to a given integer).

On one extreme, I can store everything in arbitrary order and search through it every time to construct any of the lists I need to get out of it (the lists I refer to in #1 and #2 above). This requires the least amount of data, but will also be very slow. Another extreme is where I keep track of multiple indexing structures that allow me to do the two operations I described above more quickly but that take up some memory. It's hard to compactly describe what I mean, but you could imagine a list of lists that allow you to quickly answer the question "what are all the relationships that have 47 as their first entry in the triple."

I don't know anything about data structures, but I imagine this must be a problem people have encountered and thought about before. Are there any C++ libraries with data structures that would automatically keep track of this type of indexing information or that are relevant to what I'm describing? Thanks!

Was it helpful?

Solution

I'd do something like this:

class Entity;

class Relationship // usually called Edge
{
  Entity *from;
  Entity *to;
  // other data
};

class Entity // usually called Node
{
  list<Relationship*> incoming;
  list<Relationship*> outgoing;
};

vector<Entity*> roster;

You might want to wrap roster in some sort of EntityHandler class, to manage all of those pointers.

For #1, look up an Entity in the roster by its number (e.g. roster[5]), and that Entity's outgoing is what you want -- you can do a shallow copy (of the pointers), or a deep copy (of the Relationships).

For #2, look up the Entity and iterate over both of its Relationship lists; for each Relationship, remove the corresponding pointer from the list in the Entity at the other end, then delete the Relationship. Then delete the Entity. And don't forget to set the pointer in the roster to NULL.

OTHER TIPS

Wikipedia has a good section on how to implement graphs, even has time and storage complexity. There three main types are Incidence matrix adjacency matrix's and adjacency lists. Genrally speaking:

Incidence matrix's use a node*edge sized matrix and are best for hyper-graphs, graphs with edges/connections of to more than one node and multi-graphs, graphs witch allow more than one connection between two nodes. However the more edges, the more space.

adjacency lists are most efficient if they is lots of resizing, as data is non continuous, and sparse graphs, as they only allocate space for links that are there, but use pointers which take up more space. Adjacency lists are probably the easiest to implement for directed graphs)

lastly is the adjacency matrix, which stores a node*node matrix to check if two nodes are connected, for example if [1][3] is true the 1st node is connected to the third.

https://en.wikipedia.org/wiki/Graph_(data_structure) has good descriptions on their implementations, just watch out though, they say they is an 'incidence list', but it is just a link to an adjacency list implementation

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top