System and method for fast component enumeration in graphs with implicit edges
First Claim
1. A system for performing graphical enumeration, comprising:
- a non-transitory computer readable storage medium storing executable program code comprising code for;
creating an ordered set of vertices for a graph, each vertex comprising a unique index and a plurality of keys, wherein each key defines an element of information associated with the vertex and the vertices are ordered based on the unique index;
creating a plurality of lists of vertices, each list associated with a key such that vertices in a list share a same element of information defined by the key;
for each list of vertices;
determining a least-valued index from vertices in the list;
pointing all vertices in the list to a root vertex associated with the least-valued index;
determining a least-valued index from vertices pointed to by the vertices in each list; and
updating the root vertex with a vertex associated with the newly determined least-valued index; and
a processor for executing the program code.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and system for graphical enumeration. The method includes creating an ordered set of vertices for a graph such that each vertex is associated with a corresponding index, and wherein each vertex in the ordered set of vertices includes information. A plurality of keys is created for defining the information. A plurality of lists of vertices is created, each of which is associated with a corresponding key such that vertices in a corresponding list include information associated with the corresponding key. For a first list of vertices, a least valued index is determined from a group of associated vertices based on vertices in the first list and vertices pointed to by the vertices in the first list. Also, all associated vertices are pointed to a root vertex associated with the least valued index.
-
Citations
19 Claims
-
1. A system for performing graphical enumeration, comprising:
-
a non-transitory computer readable storage medium storing executable program code comprising code for; creating an ordered set of vertices for a graph, each vertex comprising a unique index and a plurality of keys, wherein each key defines an element of information associated with the vertex and the vertices are ordered based on the unique index; creating a plurality of lists of vertices, each list associated with a key such that vertices in a list share a same element of information defined by the key; for each list of vertices; determining a least-valued index from vertices in the list; pointing all vertices in the list to a root vertex associated with the least-valued index; determining a least-valued index from vertices pointed to by the vertices in each list; and updating the root vertex with a vertex associated with the newly determined least-valued index; and a processor for executing the program code.
-
-
2. A method of graphical enumeration, comprising:
-
creating, by a processor, an ordered set of vertices for a graph, each vertex comprising a unique index and a plurality of keys, wherein each key defines an element of information associated with the vertex and the vertices are ordered based on the unique index; creating a plurality of lists of vertices, each list associated with a key such that vertices in a list share a same element of information defined by the key; for each list of vertices; determining a least-valued index from vertices in the list; pointing all vertices in the list to a root vertex associated with the least-valued index; determining a least-valued index from vertices pointed to by the vertices in each list; and updating the root vertex with a vertex associated with the newly determined least-valued index. - View Dependent Claims (3, 4)
-
-
5. A method of graphical enumeration, comprising:
-
creating, by a processor, an ordered set of vertices for a graph, each vertex comprising a unique index and a plurality of keys, wherein each key defines an element of information associated with the vertex and the vertices are ordered based on the unique index; storing the ordered set of vertices in a database; creating a plurality of lists of vertices, each list associated with a key such that vertices in a list share a same element of information defined by the key; for each list of vertices; determining a least-valued index from vertices in the list; pointing all vertices in the list to a root vertex associated with the least-valued index; determining a least-valued index from vertices pointed to by the vertices in each list; and updating the root vertex with a vertex associated with the newly determined least-valued index; and storing in the database the corresponding least-valued index with each vertex in each list. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A system for performing graphical enumeration, comprising:
-
a processor; a receiver for receiving information related to at least one consumer transaction from at least one source; a graph definer for creating an ordered set of vertices for a graph, each vertex comprising a unique index and a plurality of keys, wherein each key defines an element of information associated with the vertex and the vertices are ordered based on the unique index; a list creator for creating a plurality of lists of vertices, each list associated with a key such that vertices in a list share a same element of information defined by the key; and a component generator for; for each list of vertices; determining a least-valued index from vertices in the list; pointing all vertices in the list to a root vertex associated with the least-valued index; determining a least-valued index from vertices pointed to by the vertices in each list; and updating the root vertex with a vertex associated with the newly determined least-valued index. - View Dependent Claims (18, 19)
-
Specification