Jump to content
  • Advertisement
Sign in to follow this  
DanX2002

graph theory problem

This topic is 3346 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

You're given a directed graph. A node A in the graph is said to 'shadow' a node B if and only if the number of unique relevant paths from A to B, that do not have cycles and do not share any edges with each other, is greater than the number of such unique relevant paths from B to A. A path is considered relevant if and only if no node on the path is shadowed by the next node on the path. Find an algorithm to determine for any directed graph and for any given nodes A and B, whether A shadows B. I need this for a program I'm writing. I'm using the push-relabel maximum flow algorithm to compute the number of unique paths from A to B, but I need to make sure those paths are 'relevant', and since relevance is defined recursively by the shadow property which is defined in turn by relevance, I have an infinitely recursive definition which I can solve intuitively for small graphs but have been unable to devise an algorithm for that works in 100% of large graph cases. Any ideas?

Share this post


Link to post
Share on other sites
Advertisement
Are you sure the definitions even make sense? Would you mind walking me through how you determine if A shadows B in the graph with nodes {A, B, C} and edges {A->B, B->C, C->A}?

Share this post


Link to post
Share on other sites
Sure. Since B contains one relevant path to A, and A contains one relevant path to B, neither of them shadow each other. In checking path relevance recursively, I can use a stack of previously checked edges to ensure that there are no infinite recursions.

Share this post


Link to post
Share on other sites
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!