×

System and method for fast component enumeration in graphs with implicit edges

  • US 8,462,161 B1
  • Filed: 02/06/2009
  • Issued: 06/11/2013
  • Est. Priority Date: 01/20/2009
  • Status: Active Grant
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×