Path compression of a network graph

Patent metadata

Field	Value
Publication number	US-9747513-B2
Application number	US-201514856789-A
Country	US
Kind code	B2
Filing date	Sep 17, 2015
Priority date	Sep 17, 2015
Publication date	Aug 29, 2017
Grant date	Aug 29, 2017

Abstract

In an approach to analyzing a path on a graph, a computer receives a graph comprising a plurality of vertices and edges, each edge linking two vertices. The computer, for each one of said plurality of vertices, analyzes edges linked to said one of plurality of vertices to determine a number of outbound links from said one of plurality of vertices, orders said edges, and assigns a value to each ordered edge. The computer, for the graph, receives a path comprising a plurality of edges linking two of said plurality of vertices through at least one other of said plurality of vertices, encodes said path, the encoding using said number of outbound links and said assigned values of each of said one or more edges linking said two of said plurality of vertices, compresses the encoded path, and analyzes said path on said graph using said compressed, encoded path.

First claim

What is claimed is:

1. A computer system for analyzing and encoding a path on a network graph, the computer system comprising:
one or more computer processors;
one or more non-transitory computer readable storage device; and
program instructions stored on the one or more non-transitory computer readable storage device for execution by at least one of the one or more computer processors, the stored program instructions executable to cause the one or more computer processors to:
receive a graph, said graph comprising a plurality of vertices and a plurality of edges, each of said edges linking two of said plurality of vertices;
for each one of said plurality of vertices:
analyze said edges linked to said one of said plurality of vertices to determine a number of outbound links from said one of said plurality of vertices; and
order said edges and assigning a value to each of said ordered edges; for the graph:
receive a path, said path comprising a plurality of said plurality of edges linking two of said plurality of vertices through at least one other of said plurality of vertices;
encode said path, the encoding using said determined number of outbound links and said assigned values of each of said one or more edges linking said two of said plurality of vertices and said encoded path comprises at least a path length of said path, a start vertex of said path and one or more associated outbound links from said number of outbound links to traverse said path;
compress said encoded path; and
analyze said path on said graph using said compressed, encoded path.

2. The computer system of claim 1 , wherein said value assigned to each of said ordered edges represents an offset from a first one of said edges.

3. The computer system of claim 1 , wherein said edges are ordered lexicographically.

4. The computer system of claim 1 , wherein said encoding said path comprises encoding each of the assigned values as an integer in a range between zero and said number of outbound links.

5. The computer system of claim 1 , wherein said encoding said path comprises encoding each of the assigned values as a minimum number of bits needed to represent said assigned value in a range between zero and said number of outbound links.

6. The computer system of claim 1 , wherein said encoded path is compressed using a DEFLATE algorithm.

7. The computer system of claim 1 , the stored program instructions further executable to decode said compressed, encoded path.

8. A computer program product for analyzing and encoding a path on a network graph, the computer program product comprising:
one or more non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to:
receive a graph, said graph comprising a plurality of vertices and a plurality of edges, each of said edges linking two of said plurality of vertices;
for each one of said plurality of vertices:
analyze said edges linked to said one of said plurality of vertices to determine a number of outbound links from said one of said plurality of vertices; and
order said edges and assigning a value to each of said ordered edges;

for the graph:
receive a path, said path comprising a plurality of said plurality of edges linking two of said plurality of vertices through at least one other of said plurality of vertices;
encode said path, the encoding using said determined number of outbound links and said assigned values of each of said one or more edges linking said two of said plurality of vertices and said encoded path comprises at least a path length of said path, a start vertex of said path and one or more associated outbound links from said number of outbound links to traverse said path;
compress said encoded path; and
analyze said path on said graph using said compressed, encoded path.

9. The computer program product of claim 8 , wherein said value assigned to each of said ordered edges represents an offset from a first one of said edges.

10. The computer program product of claim 8 , wherein said edges are ordered lexicographically.

11. The computer program product of claim 8 , wherein said encoding said path comprises encoding each of the assigned values as an integer in a range between zero and said number of outbound links.

12. The computer program product of claim 8 , wherein said encoding said path comprises encoding each of the assigned values as a minimum number of bits needed to represent said assigned value in a range between zero and said number of outbound links.

13. The computer program product of claim 8 , wherein said encoded path is compressed using a DEFLATE algorithm.

Assignees

• IBM

Inventors

• Glover Raymond S

Classifications

• G06F17/10 Primary

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06K9/4638 Primary

  Physics · mapped topic

• G06K9/469

  Physics · mapped topic

• H03M7/30

  Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction · CPC title

• G06F17/30958

  Physics · mapped topic