Jump to content
  • Advertisement
Sign in to follow this  
fleabay

C++ Programming attribute connections in a dependency graph

Recommended Posts

I am looking for resources on best practices (really any info at this point) on how to program a dependency graph with functions that create nodes, create attributes and connect attributes.

For some reason this topic is kryptonite for my Google Fu.

Share this post


Link to post
Share on other sites
Advertisement

You'll need a Node and an Arrow (or Edge), where Arrow represents the dependency between two nodes. For uni-directional dependencies, a Node has a collection of Arrows, an Arrow points to the other Node. Also you need to decide what A -> B means. Does it mean that A needs B, or B needs A? What you pick isn't very important, except you have to select one.

You can also have bi-drectional arrows, where both nodes can find the Arrow, and the other side. The arrow becomes fully symmetric in that case. Another way to code a bi-drecional arrow is to use two uni-directional arrows.

How to actually represent that in code depends on the kind of information that you have, and the scale of things. If a Node is a single integer number, you can have a list of lists. (First list indexes on the node number giving you the container of links to other nodes,) The link can be as simple as another node number (ie no attributes on the Arrow), or you can make the inner list a List of Arrow, where the Arrow class stores the attributes of the link and a node number.

If a Node is an object, the simplest is to store the container with links in your Node, and directly point to other node objects,

Having a list of Arrows works nicely if you don't remove Arrows often, and you typically need to access all successors in any order. If you need a specific successor node, you may want to use a map of arrows at the cost of some memory overhead. In fact, the map may become the arrow, the key points to the successor node, its value can contain the attributes of the link.

 

There really isn't a single best solution. It all depends on how much information a node or edge has, how many nodes and edges you have, and the kind of graph operations you want to do. There are many dedicated algorithms for performing graph operations, and they typically expect a special form of the graph for maximum performance. You may want to start at this end, so you can design your graph structure to fit the needs of the algorithms you want to perform.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!