System and methods for creating a geospatial network model in a client environment

Abstract

System and methods for creating a geospatial network model in a client environment are disclosed. The system residing on a client device receives Geographic Information System (GIS) data for a distribution network, which includes spatial information and non-spatial information (e.g., attributes) relating to features in the distribution network, from a remote GIS database. The system uses the spatial information in the GIS data to construct an undirected graph that is represented by a set of adjacency relationships between the features and utilizes the non-spatial information to traverse the undirected graph in order to construct a directed graph that is represented as a set of directed adjacency relationships between the features. The system stores the data structure corresponding to the directed graph in the form of an array or hashtable in the client device's cache memory for use in performing network analyses such as tracing analysis without accessing the GIS database.

What is claimed is: 
     
         1 . A method for constructing a model for a distribution network comprising:
 receiving, on a hardware device, Geographic Information System (GIS) data corresponding to a distribution network or a portion thereof from a GIS database, the GIS data including a set of adjacency relationships between features in an area of interest or information for deriving the set of adjacency relationships;   performing a traversal of the distribution network or the portion thereof using the set of adjacency relationships and attributes of the features in each step of the traversal to generate a data structure representing a model for the distribution network or the portion thereof; and   storing the data structure in a local storage on the hardware device.   
     
     
         2 . The method of  claim 1 , wherein the data structure is stored in a form optimized for lookup speed in a cache memory on the hardware device. 
     
     
         3 . The method of  claim 1 , wherein the data structure comprises a set of directed adjacency relationships and corresponding attributes. 
     
     
         4 . The method of  claim 3 , wherein the distribution network is an electric distribution network and the attributes include a source identifier attribute identifying a source vertex from which the traversal began, and a phases attribute indicating which of the electrical phases from the source vertex that pass through a first vertex reach an adjacent vertex. 
     
     
         5 . The method of  claim 1 , further comprising:
 accessing the data structure representing the model for the distribution network or the portion thereof from the local storage to edit, perform a network analysis operation or visualize the distribution network or the portion thereof.   
     
     
         6 . The method of  claim 5 , wherein the editing, performing a network analysis operation or visualizing the distribution network or the portion thereof is performed against the model stored on the hardware device while the hardware device is disconnected from the GIS database. 
     
     
         7 . The method of  claim 5 , wherein the network analysis operation includes a tracing operation or an attribute query operation. 
     
     
         8 . The method of  claim 5 , wherein the network analysis operation includes an electric tracing, a load flow analysis, or operating voltage calculations. 
     
     
         9 . The method of  claim 1 , further comprising:
 renumbering objects in the data structure to store the data structure as an array on the hardware device, wherein an index of the array is a proxy for the corresponding object's original identifier in the GIS; and   mapping GIS identifiers of the objects in the data structure to index values of the array.   
     
     
         10 . The method of  claim 1 , wherein the distribution network includes any one of: an electric distribution network, a gas distribution network, a water distribution network or a telecom distribution network. 
     
     
         11 . The method of  claim 1 , further comprising:
 detecting a user request to perform a tracing analysis on a circuit in the distribution network, wherein the user request includes a selection of a point on the circuit;   in response to the user request, accessing the model for the distribution network to determine objects that are upstream and downstream of the point selected by the user;   rendering a trace of an upstream path that starts from a source vertex and flows through the objects that are upstream to the point selected by the user; and   rendering a trace of a downstream path that starts from the point selected by the user and flows through the objects that are downstream.   
     
     
         12 . A non-transitory machine-readable medium comprising instructions which when executed by a machine cause the machine to execute a method comprising:
 receiving Geographic Information System (GIS) data for a utility distribution network from a GIS database, wherein the GIS data includes objects and spatial information associated with the objects;   determining adjacency relationships between the objects using the spatial information to generate a first adjacency list;   determining upstream or downstream direction and at least one associated attribute of each adjacency between the objects in the first adjacency list to generate a second adjacency list; and   storing the second adjacency list on the machine to facilitate at least one of editing, analysis or visualization of a circuit in the utility distribution network.   
     
     
         13 . The non-transitory machine-readable medium of  claim 12 , wherein determining the upstream or downstream direction of each adjacency between the objects further comprises:
 starting from each source vertex, performing a traversal of the utility distribution network based on the adjacency relationships and attributes of the objects.   
     
     
         14 . The non-transitory machine-readable medium of  claim 12 , wherein the adjacency relationships are represented by pairs of object identifiers and complements thereof. 
     
     
         15 . The non-transitory machine-readable medium of  claim 13 , wherein the second adjacency list comprises the pairs of object identifiers from the first adjacency list arranged in an order based on the traversal of the distribution network. 
     
     
         16 . The non-transitory machine-readable medium of  claim 12 , wherein the utility distribution network is one of: an electric distribution network, a gas distribution network, a water distribution network or a telecommunication distribution network. 
     
     
         17 . The non-transitory machine-readable medium of  claim 12 , further comprising:
 detecting a user request to perform a tracing analysis on a circuit in the utility distribution network, wherein the user request includes a selection of a point on the circuit;   in response to the user request, accessing the second adjacency list stored in a form optimized for lookup speed in a cache memory on the machine to determine objects that are upstream and downstream of the point selected by the user;   rendering a trace of an upstream path that starts from a source vertex and flows through the objects that are upstream to the point selected by the user; and   rendering a trace of a downstream path that starts from the point selected by the user and flows through the objects that are downstream.   
     
     
         18 . A computer system for constructing a model for a distribution network comprising:
 a memory including a cache memory; and   one or more processors configured to execute instructions stored in the memory to:
 receive Geographic Information System (GIS) data for a distribution network from a GIS database, the GIS data including spatial information relating to objects in the distribution network; 
 construct an undirected graph utilizing the spatial information in the GIS data, wherein the undirected graph is represented by a data structure corresponding to a set of adjacency relationships between the objects; 
 construct a directed graph by traversing the undirected graph starting from each source vertex and tracking attributes of the objects in each step of the traversal, wherein the directed graph is represented by a data structure corresponding to a set of directed adjacency relationships between the objects; and 
 cache the data structure corresponding to the directed graph in the cache memory on the computer system. 
   
     
     
         19 . The system of  claim 18 , wherein the distribution network includes any one of: an electric distribution network, a gas distribution network, a water distribution network or a telecom distribution network. 
     
     
         20 . The system of  claim 18 , further configured to:
 detect a user request to perform a tracing analysis on a circuit in the distribution network, wherein the user request includes a selection of a point on a circuit;   in response to the user request, access the data structure stored in the cache memory to determine objects that are upstream and downstream of the point selected by the user, wherein the data structure is stored in the form of an array or hashtable for improved lookup speed; and   render a trace of an upstream path that starts from a source vertex and flows through the objects that are upstream to the point selected by the user; and   render a trace of a downstream path that starts from the point selected by the user and flows through the objects that are downstream.