Browse Prior Art Database

Detecting the Existence of Circuits in a Directed Graph and the V Involved

IP.com Disclosure Number: IPCOM000080474D
Original Publication Date: 1973-Dec-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 2 page(s) / 30K

Publishing Venue

IBM

Related People

Ingwall, RL: AUTHOR

Abstract

The normal method used to locate a circuit within a directed graph is to form the matrix representation M of the graph. M is then raised to the Nth power, where N is the number of vertices. If there are no circuits, all elements of M/N/ will be zero. If M/N/ contains nonzero entries, one or more circuits exist. To locate the vertices involved, M must be raised to the N + P power such that M/N/ = M/N+P/. The vertices involved in circuits will be generated between M/N/ and M/N+P/.

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 70% of the total text.

Page 1 of 2

Detecting the Existence of Circuits in a Directed Graph and the V Involved

The normal method used to locate a circuit within a directed graph is to form the matrix representation M of the graph. M is then raised to the Nth power, where N is the number of vertices. If there are no circuits, all elements of M/N/ will be zero. If M/N/ contains nonzero entries, one or more circuits exist. To locate the vertices involved, M must be raised to the N + P power such that M/N/ = M/N+P/. The vertices involved in circuits will be generated between M/N/ and M/N+P/.

The method described below provides the same end result of locating vertices involved in circuits or indicating no circuits exist, but at a significant savings in CPU time required. In the problem solved using this method, the absence of the program loop is the desired result.

The approach consists of systematically removing absolute sources (vertices with incoming degree of zero) and absolute sinks (vertices with outgoing degree of zero) until the graph collapses to a null graph, or until there are no more absolute sources or sinks, at which time the remaining vertices represent vertices which are part of some circuit (path where the terminal vertex coincides with the initial vertex).

The following is an APL example of the use of the method.

Let matrix DGRAPH be the matrix representation of the directed graph, such that a 1 in position DGRAPH [i, j] indicates vertices i and j are connected from i to
j. A 0 in that...