Browse Prior Art Database

A STRONG-CONNECTIVITY ALGORITHM AND APPLICATIONS IN DATA FLOW ANALYSIS

IP.com Disclosure Number: IPCOM000128173D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 7 page(s) / 25K

Publishing Venue

Software Patent Institute

Related People

M. Sharir: AUTHOR [+3]

Abstract

We present a new linear algorithm for constructing all strongly connected components of a directed graph, and show how to apply it in iterative solution of data-flow analysis problems, to obtain a simple algorithm which improves the Hecht-Ullman algorithm.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 20% of the total text.

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A STRONG-CONNECTIVITY ALGORITHM AND APPLICATIONS IN DATA FLOW ANALYSIS

BY M. Sharir

May 1979 Report No. 014 *"This work is based upon work supported partly by the National Science Foudation under Grant No. MCS076-00116. Any opinions, findings and conclusions or recommendations expressed in this publication are those of the authors) and do not necessarily reflect the views of the National Science Foundation." This work is also based upon work supported partly by the U.S. DOE Office of Energy Research Contract EY-76-C-02-3077.

ABSTRACT

We present a new linear algorithm for constructing all strongly connected components of a directed graph, and show how to apply it in iterative solution of data-flow analysis problems, to obtain a simple algorithm which improves the Hecht-Ullman algorithm.

1. Introduction

We present here a new algorithm for constructing all strongly-connected components of a directed graph. Like Tarjan's well known algorithm (cf. [AHU, Ch. 5.7]) it uses a depth-first spanning tree (forest) T, and is linear in the number of nodes and edges of the graph. However, our algorithm differs from Tarjan's in that it produces these components in reverse postorder of their roots (.relative to T), and also orders the nodes within each component in reverse postorder. Together, these orderings induce a modified reverse postorder of the graph nodes, which facilitates certain iterative algorithms related to data-flow analysis. We will describe and analyze such a data-flow algorithm which improves the algorithm of Hecht and Ullman (HUI. Even though the order-ing we are concerned with can also be obtained with one additional tree- walk using Tarjan's algorithm, we present our algorithm as a simpler alternative. . The strong- connectivity algorithm is presented and analyzed in Section 2. Section 3 discusses its applications to the solution of data-flow analysis problems.

2. A Strong-Connectivity Algorithm

Let us assume that we are given a directed graph G rooted at a unique 'entry' node r. Let N be the set of nodes of G and E the set of its edges. For each n E N denote by SCC(n) the strongZy-connected component of G containing n, i.e. the maximal set of nodes containing n such that G restricted to that set is strongly connected. Let T be a depth-first spanning tree for
G. The following algorithm will compute the following objects:. a list SCCS of roots of strongly- connected compon-ents in their reverse postorder (relative to T) and a map SCCNODES mapping each (root of a) strongly connected component to a list of its nodes in the same reverse post-order. The algora.thm proceeds in the (following steps:

Algorithm SCOMPS: (1) Initialize SCCS to the null list and SCCNODES to the null map. Also initialize an auxiliary map SCCROOT, which will map each node in N to the root of its strongly-

New York University Page 1 Dec 31, 1979

Page 2 of 7

A STRONG-CONNECTIVITY ALGORITHM AND AP...