Apparatus and methods for analyzing graphs

• US 6,941,236 B2
• Filed: 03/31/2003
• Issued: 09/06/2005
• Est. Priority Date: 03/31/2003
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Mencer, Oskar, Huelsbergen, Lorenz Francis
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): Gutierrez, Anthony
• Application Number:
  US10/400,904
• Publication Number:
  US 20040204905A1
• Time in Patent Office: 890 Days
• Field of Search: 702/66, 702/67, 716/4
• US Class Current: 702/66
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

A plurality of hardware cells are defined, wherein at least a given one of the hardware cells corresponds to sets of vertices from a graph having vertices and edges interconnecting the vertices, and each of the sets are from a corresponding one of a number of portions of the graph. The given hardware cell is adapted to select one of the sets of vertices and to define for the selected set of vertices whether an edge exists in the graph between the vertices in the selected set. The hardware cells are used to analyze one or more properties of the graph, such as reachability or shortest path. The graph is mapped into an adjacency matrix, which contains a number of contexts, each context having a number of elements, and where the given hardware cell corresponds to multiple contexts of the adjacency matrix.

Claims

1. A method for analyzing a graph comprising a plurality of vertices and a plurality of edges interconnecting selected ones of the vertices, comprising the steps of:

defining a plurality of hardware cells in a hardware array, wherein at least a given one of the plurality of hardware cells corresponds to sets of vertices, each of the sets from a corresponding one of a plurality of portions of the graph, and wherein the given hardware cell is adapted to select one of the plurality of sets of vertices and to define for the selected set of vertices whether an edge exists in the graph between the vertices in the selected set; and

analyzing at least one property of the graph by using the plurality of hardware cells.

2. The method of claim 1,

further comprising the steps of:

mapping the graph into an adjacency matrix comprising a plurality of elements, each element corresponding to a set of vertices of the graph and defining whether an edge exists between vertices in the set; and

defining a plurality of contexts for the adjacency matrix, each of the plurality contexts comprising one or more of the plurality of elements, each of the plurality of contexts corresponding to a portion of the graph; and

wherein each of the sets corresponding to the given hardware cell corresponds to a context.

3. The method of claim 2, further comprising the step of changing the context to a particular context, wherein the step of changing the context causes the given hardware cell to select one of the sets of vertices corresponding to the particular context.

4. The method of claim 2, wherein the step of analyzing further comprises the step of determining whether a vertex is reachable from a source vertex.

5. The method of claim 4, wherein the step of determining what vertices are reachable from a source vertex comprises the steps of:

selecting a source vertex;

switching at least the given hardware cell to a context corresponding to the source vertex;

determining which sets of vertices in the context have an edge interconnecting vertices in a set of vertices;

selecting one vertex from the sets of vertices in the context having an edge interconnecting vertices in a set of vertices;

switching at least the given hardware cell to a context corresponding to the one vertex;

performing the steps of determining which sets, selecting one vertex, and switching at least the given hardware cell to a context corresponding to the one vertex until all sets of vertices having an edge interconnecting vertices in a set of vertices have been selected,

wherein any sets of vertices having an edge interconnecting vertices in the set indicate the vertices reachable from the source vertex.

6. The method of claim 2, wherein the step of analyzing further comprises the step of determining a shortest path from a source vertex to a destination vertex.

7. The method of claim 6, wherein the step of determining a shortest path further comprises the steps of:

selecting a source vertex;

switching at least the given hardware cell to a context corresponding to the source vertex;

determining a current vertex group, which comprises sets of vertices in the context having an edge interconnecting vertices in a set of vertices;

determining if a destination vertex has been reached by determining if the destination vertex is in the current vertex group;

when the destination vertex has not been reached;

selecting a candidate vertex from the current vertex group;

switching at least the given hardware cell to a context corresponding to the candidate vertex;

determining a next vertex group, which comprises sets of vertices in the context having an edge interconnecting vertices in a set of vertices;

recording vertex information for vertices in the next vertex group; and

performing the steps of selecting a candidate vertex, switching at least the given hardware cell to a context corresponding to the candidate vertex, determining a next vertex group, and recording until all vertices in the current vertex group have been selected;

increasing a distance measure;

making the next vertex group be the current vertex group; and

when the destination vertex has been reached, determining the shortest path by using the vertex information.

8. The method of claim 7, wherein the vertex information comprises a number for each of the sets of vertices having an edge interconnecting vertices in a set, and wherein the step of determining the shortest path by using the vertex information comprises the step of starting at the destination vertex and using the numbers as a linked list in order to determine each vertex in the shortest path.

9. The method of claim 1, wherein a set of vertices corresponding to the given hardware cell comprises a single vertex and another set of vertices corresponding to the given hardware cell comprises two vertices.

10. The method of claim 1, wherein at least the given hardware cell corresponds to a first and second interconnects, each first interconnect corresponding to one vertex from the graph and each second interconnect corresponding to another vertex in the graph, wherein the one vertex and the other vertex may or may not be the same vertex.

11. The method of claim 1, wherein the step of defining a plurality of hardware cells further comprises the step of defining the plurality of hardware cells on a gate array.

12. An apparatus for analyzing a graph comprising a plurality of vertices and a plurality of edges interconnecting selected ones of the vertices, comprising:

a plurality of hardware cells of a hardware array, wherein at least a given one of the plurality of hardware cells corresponds to sets of vertices, each of the sets from a corresponding one of a plurality of portions of the graph, and wherein the given hardware cell is adapted to select one of the plurality of sets of vertices and to define for the selected set of vertices whether an edge exists in the graph between the vertices in the selected set,

wherein at least one property of the graph may be analyzed by using the plurality of hardware cells.

13. The apparatus of claim 12, wherein at least the given hardware cell comprises a device having a plurality of states and coupled to at least one memory element, wherein at least the given hardware cell is coupled to first and second interconnects, each of the first and second interconnects corresponding to a vertex from the graph, wherein each of the at least one memory elements selects one of the plurality of states of a hardware cell, wherein one state of a hardware cell couples the first and second interconnects, and wherein another state of a hardware cell decouples the first and second interconnects.

14. The apparatus of claim 13, wherein the device comprises a tri-state buffer.

15. The apparatus of claim 13, wherein each of the at least one memory elements for each of the given hardware cells comprises a plurality of memory elements adapted to be selected using an address, and wherein the apparatus further comprises:

a candidate columns detection module coupled to one or more of the first interconnects, the candidate columns detection module adapted to determine whether the one or more of the first interconnects is in a first state, the first state indicating that a set of vertices corresponding to a given hardware cell has an edge connecting vertices in the set, the candidate columns detection module coupled to a leading vertex detector module and also adapted to couple signals indicating which of the one or more of the first interconnects is in the first state to the leading vertex detector module;

the leading vertex detector module coupled to the signals from the candidate columns detection module and adapted to select candidate vertices corresponding to the one or more of the first interconnects and also adapted to determine and output an address in order to select a context corresponding to a selected candidate vertex; and

a vertex inputs module coupled to the leading vertex detector module and one or more of the second interconnects, the vertex inputs module adapted to determine a selected candidate vertex from the leading vertex detector module and to drive a second interconnect corresponding to the selected candidate vertex to the first state.

16. The apparatus of claim 15, further comprising a signal output monitor adapted to output which first signals are the first state.

17. The apparatus of claim 13, wherein each of the at least one memory elements for each of the given hardware cells comprises a plurality of memory elements adapted to be selected using an address, and wherein the apparatus further comprises:

a candidate columns detection module coupled to one or more of the first interconnects, the candidate columns detection module adapted to determine whether the one or more of the first interconnects is in a first state, the first state indicating that a set of vertices corresponding to a given hardware cell has an edge connecting vertices in the set, the candidate columns detection module coupled to a leading vertex detector module and also adapted to couple signals indicating which of the one or more of the first interconnects is in the first state to the leading vertex detector module;

the leading vertex detector module coupled to the signals from the candidate columns detection module and adapted to select candidate vertices corresponding to the one or more of the first interconnects and also adapted to determine and output an address in order to select a context corresponding to a selected candidate vertex; and

a current row number module coupled to the leading vertex detector module and one or more of the second interconnects, the vertex inputs module adapted to determine a selected candidate vertex from the leading vertex detector module and to drive a second interconnect corresponding to the selected candidate vertex to the first state.

18. The apparatus of claim 17, further comprising a register file module, the register file module having one or more registers, each register corresponding to a first interconnect, wherein the register file module is adapted to store a number in a register, the number corresponding to a context when a corresponding one of the first interconnect becomes the first value.

19. The apparatus of claim 18, wherein the register file is coupled to the address and is adapted to use the address to determine context.

20. An article of manufacture for analyzing a graph comprising a plurality of vertices and a plurality of edges interconnecting selected ones of the vertices, comprising:

a machine readable medium containing one or more programs which when executed implement the steps of;

defining a plurality of hardware cells, wherein at least a given one of the plurality of hardware cells corresponds to sets of vertices, each of the sets from a corresponding one of a plurality of portions of the graph, and wherein the given hardware cell is adapted to select one of the plurality of sets of vertices and to define for the selected set of vertices whether an edge exists in the graph between the vertices in the selected set; and

analyzing at least one property of the graph by using the plurality of hardware cells.