CODEWITHSUNDEEP
algorithmgraph-theory
Brad Koch
Brad Koch

Reputation: 20267

Finding associated sources and destinations on a directed graph

Background: I have a collection of nodes which represents the intersection of product as it moves through a process. These nodes are connected together into directed graphs. There are several independent graphs, as product does not always intersect.

Product will always start at an initial source node, one with no parents. It will eventually end at a final destination node, one with no children. A initial source may have one or more final destinations, and a final destination may have one or more initial sources.

We are able to compile a list of desired initial sources to follow through a set of criteria given by a user. These sources may, but not necessarily, belong to the same graph.

Objective: Given this list of initial sources, I need to be able to determine which initial sources correspond with which final destinations. These sources and destinations must be grouped by graph, no duplicates. In other words:

  1. Associate each node with its unique graph.
  2. Determine the initial sources that belong to each graph.
  3. Determine the final destinations that belong to each graph.

Example: if my list of initial sources is 1, 2, 3, 4, 5, 6, 7, and 8, I would have the following results (where my unknown destinations are A, C, D, E, G, K, L):

1,4,5,6 -> A,G,K
2 -> C
3 -> D,E
7,8 -> L

Question: What is an effective (and hopefully most efficient) algorithm for performing this task?

Current Solution, just for reference:

For each initial source:
    If we have not visited the initial source yet
        Mark as belonging to a new graph

        Add childrens to a list of nodes to visit.        

        For each node to visit:
            If we have not visited this node yet:
                Mark as belonging to current graph

                If there are no children
                    add to list of final destinations
                End if

                add all parents and all children to a list of nodes to visit
            End if
        Do next node
    End if
Do next source

Obviously, there's a bit of extra overhead since we're going to be doing a lot of visitation of nodes we've already seen before, since we're visiting all children and all parents of every node.

Upvotes: 0

Views: 931

Answers (1)

PengOne
PengOne

Reputation: 48398

The algorithm you have described is a Depth First Search. This type of problem, that of following an acyclic directed graph, is perhaps better handled by a Breadth First Search. Even if the graph is not acyclic, this still may be a better approach.

Upvotes: 3

Related Questions