Browse Prior Art Database

Rapid Algorithm for Finding a Proper Tree of a Graph

IP.com Disclosure Number: IPCOM000077262D
Original Publication Date: 1972-Jul-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 3 page(s) / 56K

Publishing Venue

IBM

Related People

Kugel, LE: AUTHOR

Abstract

This algorithm finds a tree of a topological graph in which certain branches have a higher priority in the tree than other branches (proper tree).

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Rapid Algorithm for Finding a Proper Tree of a Graph

This algorithm finds a tree of a topological graph in which certain branches have a higher priority in the tree than other branches (proper tree).

If in a topological graph each type of branch is assigned a priority number
(i.e., voltage sources-priority #1, capacitors- #2, conductors- #3, resistors- #4, inductors- #5, current sources- #6), then form a tree of the graph which contains as many #1 priority branches as possible, followed by #2 priority branches, then #3 priority, and so forth until a tree is formed. That tree is called a proper tree. This algorithm is designed to find a proper tree rapidly. The input to this algorithm is 1) NN - the number of nodes in the graph 2) NB - the number of branches in the graph 3) IN(^) - a list of initial nodes for each branch in order of the branch priority. 4) FN(^) - a list of final nodes for each branch in order of the branch priority.

The algorithm operates by taking the branches one at a time and using IN (^) and FN (^) to build up the network graph. As each branch with its end nodes is added to the graph, if a closed path is formed, the branch is in the cotree. If no closed path is formed the branch is in the tree. Two concepts are used in this algorithm: 1) A branch forms a closed path if and only if both end nodes are already in the graph and in the same part. 2) A branch adds a new part to the graph if and only if both end nodes are not already in the graph. The algorithm uses the following auxiliary variables. MLIST (^) - a vector in which location ^ corresponds to node, and the content of location ^ is the graph part containing node ^. PMAX - a variable which is incremented every time a new part is created. NP - the number of parts in the graph. The output is

BLIST (b) - location b contains +1 if the branch is in the tree, -1 if the branch is in the cotree. The flow chart for this algorithm is shown in Fig. 1.

As an example of how this algorithm works, see the network graph in Fig. 2. The input variables are NN (number of nodes) = 6 NB (number of branches) =...