Expiring Today—Celebrate National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

directed graph traversal

Posted on 2014-12-16
7
Medium Priority
?
82 Views
Last Modified: 2015-01-29
i have the following graph that i am trying to create a sequence out of for the nodes. it's very similar to a DFS traversal excepted nodes may be visited multiple times.  i am trying to find the best algorithm to create the sequence, the final result is listed below (see attached).  note that E should have been 4th but because of the false route, its sequence got updated to 6th (the higher sequence number).

i want to traverse the TRUE route first and then the nearest FALSE route (if there are children conditionals).  

my initial take on the algorithm is this:
1) keep getting sequence until i hit a conditional or end node
2) if hit end node, stop
3) if hit conditional, take the TRUE route
4) once the TRUE route is done, traverse the nearest false route
workflow.jpg
0
Comment
Question by:mmingfeilam
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
7 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 40503062
What is the relationship between the desired sequence and the directed graph?
Is the goal to visit all the nodes?
0
 

Author Comment

by:mmingfeilam
ID: 40503246
The directed graph is used to show parent/child relationship.  So we go from parent to child in the direction of the arrow. I want to go thru all the nodes, some multiple times, to generate a sequence in case I want to save to DB.
0
 
LVL 84

Expert Comment

by:ozo
ID: 40503322
Are there some nodes that you are required to go through multiple times?
Are there requirements on the order other than those imposed by the arrows in the graph?
0
Moving data to the cloud? Find out if you’re ready

Before moving to the cloud, it is important to carefully define your db needs, plan for the migration & understand prod. environment. This wp explains how to define what you need from a cloud provider, plan for the migration & what putting a cloud solution into practice entails.

 

Author Comment

by:mmingfeilam
ID: 40503380
yes, if the arrow brings you back to a node already visited, then you have to reset that node's sequence number to the newer, higher number.  other than that, the arrow determines the order.
0
 
LVL 84

Accepted Solution

by:
ozo earned 2000 total points
ID: 40503402
So is the only requirement to follow the arrows and visit all nodes?
Breadth-first instead of Depth-first may be better at finding the shortest such path, but is that something you care about?
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 40577915
I've requested that this question be deleted for the following reason:

Not enough information to confirm an answer.
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

If you’re thinking to yourself “That description sounds a lot like two people doing the work that one could accomplish,” you’re not alone.
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

718 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question