Browse Prior Art Database

Concurrent Detection of Feedback Loops in Directed Graphs

IP.com Disclosure Number: IPCOM000120368D
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 3 page(s) / 120K

Publishing Venue

IBM

Related People

Kane, TJ: AUTHOR

Abstract

A solution to finding feedback loops in a directed graph is presented that: processes subtrees from each input concurrently, uses separate processes for Searchers and Identifiers to locate the feedback loops, and uses a unique graph-marking scheme to reduce the amount of redundant searching. Search All Inputs Concurrently

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

Concurrent Detection of Feedback Loops in Directed Graphs

      A solution to finding feedback loops in a directed graph
is presented that:
      processes subtrees from each input concurrently,
      uses separate processes for Searchers and Identifiers
      to locate the feedback loops,
      and uses a unique graph-marking scheme to reduce the
      amount of redundant searching.
Search All Inputs Concurrently

      One problem with using a depth first search to identify the
feedback loops is that the power of parallel processing is not
applied.  A way to exploit parallelism is to search the trees from
each primary input in parallel.  A separate Searcher is created for
each input.  These Searchers process their subgraphs in a
straightforward manner - each one performing a complete depth first
search of the tree with that input as its root.

      If a node is reached that has been flagged as already-visited
by that particular Searcher, then a feedback loop has been found.  At
that point, an Identifier is created to flag all nodes belonging to
the loop.  These Identifiers would run concurrently with the
Searchers.  This would allow the Searching part of the algorithm to
continue at a steady pace regardless of how many loops were found and
which Searchers found them.  The actions of the Identifiers could
vary depending on what type of parallel processing architecture was
used and the application processing the loops.
Graph-Marking Scheme

      The concurrent method outlined above has one problem that a
standard current sequential method for finding feedback loops with
graph- marking does not have; namely, it does not share information
about which subgraphs have been searched among the searchers.  The
concurrent search would speed up the process compared to the current
solution since all inputs are searched in parallel and the
identifying can be done while searching is continuing.  But even
greater efficiency could be achieved if redundant searching could be
avoided.  This section will first show why the graph-marking scheme
described above for a sequential search is insufficient and then a
new method for marking which nodes are visited is explained.

      Due to the fact that all inputs are searched concurrently,
rather than sequentially, a standard graph-marking scheme above could
give incorrect results as it searches for feedback loops (see the
example).

      With a slight modification to a graph-marking scheme for
sequential processing, a marking scheme can be developed that will
avoid some, but not all, redundant searching for a concurrent search
of the inputs.  The solution is to wait until all successors of the
node are visited before flagging the node as visited.  Since the
feedback loop nodes are successors of each other, they cannot be
flagged as visited until the loop has been found in this new method.
This avoids the problem of missing loops during the search.

  ...