Graph-Like Data Structure amp Implementation In C

Questions

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...)

• 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).
• 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!

Answers

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.

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/23480523/graph-like-data-structure-implementation-in-c

Related