Parsing Flowcharts and Series-Parallel Graphs

Abstract

The main results presented in this work are an algorithm for the recognition of General Series Parallel (GSP) digraphs and an approach to the structural analysis of the control flow graphs of programs. The GSP recognition algorithm determines in O(n+m) steps whether an acyclic diagraph with n vertices and m edges is GSP, and if it is, describes its structure in terms of two simple operations on diagraphs. The algorithm is based on the relationship between GSP diagraphs and the more standard class of TTSP multidigraphs. Our approach to the analysis of flow graphs uses the triconnected components algorithm to find single-entry, single-exit regions. Under certain conditions -- that we identify -- this method will produce structural information suitable for the global flow analysis of control flow graphs in time proportional to the number of vertices and edges of the graph being analyzed.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1978
Accession Number
ADA065265

Entities

People

  • Jacobo Valdes

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Classification
  • Computations
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Digital Computers
  • Graph Theory
  • Industrial Engineering
  • Mathematical Analysis
  • New York
  • Operations Research
  • Structural Analysis
  • Trees (Data Structures)
  • United States

Readers

  • Graph Algorithms and Convex Optimization.