Browse Prior Art Database

Recursive Algorithm for Network Tracing

IP.com Disclosure Number: IPCOM000102320D
Original Publication Date: 1990-Nov-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 2 page(s) / 60K

Publishing Venue

IBM

Related People

Marshall, LB: AUTHOR [+2]

Abstract

Disclosed is a recursive algorithm to identify the exclusive contributors to a network output.

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

Recursive Algorithm for Network Tracing

       Disclosed is a recursive algorithm to identify the
exclusive contributors to a network output.

      This algorithm operates on a network structure that consists of
a collection of nodes connected by directional vectors (see the
figure).  Each node is associated with a set of vectors that
represent the inputs and outputs of the node.  This network typically
represents a logical structure such as a circuit or a collection of
interdependent software routines.  Starting from an output of the
network, this algorithm identifies all nodes that exclusively
contribute to the selected output. The network is represented by two
tables: a trace-forward table, and a trace-backward table.  The
trace-forward table identifies the destination of each node's output,
and the trace-backward table identifies the source of each node's
inputs.

      The key to the operation of the algorithm is the identification
of exclusive nodes and the decision on when to continue tracing a
path.  Nodes are reached as the algorithm traces paths defined in the
trace-backward table. Exclusive nodes are recognized by the following
test:
       .   Are all of the node's trace-forward entries contained in
the identified exclusive network?

      If the traced node meets this criteria, then it is an exclusive
node of the selected output and tracing continues on each of the
node's trace-backward table entries.  Tracing stops if either of...