1,000 Features Per Second for Node-to-Node Trace!

1,000 Features Per Second for Node-to-Node Trace!

Description of an Electric Trace for GTViewer using Bentley Utility Designer Data

 Charlie Marlin

Huntsville Utilities

Begun April 3, 2013

Revised January 14, 2014

Summary

Network traces have historically been slow – 1 feature per second, maybe 10, maybe 100.  This paper shows how to achieve 1,000 features per second using standard data structures. The primary innovation is to pre-process certain portions of the data into text files which are loaded into memory (into hash tables) when the trace application is first started.  Most of the data access during the trace uses these hash tables (which are one of the fastest data structures available) instead of disk reads, so the trace runs faster than most.

Audience

The paper is intended for anyone writing a network trace, whether with GTViewer or not, whether with data from Bentley or not.  The trace is implemented using GTViewer on data that has been converted from Bentley to the format used by GTViewer, so I will necessarily get down into the details of GTViewer and Bentley in order to explain what’s going on.  But an interested reader should be able to understand how to implement the same concepts in his own environment.

Network tracing is one of many practical applications of Graph Theory.  Here is the definition from Wikipedia:  (http://en.wikipedia.org/wiki/Graph_theory)

“In mathematics and computer science, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A "graph" in this context is made up of "vertices" or "nodes" and lines called edges that connect them. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another; see graph (mathematics) for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.”

Why is Graph Theory important to GIS?  Because our electric, gas, telephone, water, sewer, and storm drain networks  are easily modeled as graphs, thereby allowing all of the many tools from graph theory to be used to analyze GIS data.

A Note on .NET’s NameValueCollection

Before we get very far, I should share some things about a data structure that .NET calls a “NameValueCollection”.  It is implemented as a hash table (actually .NET will determine how big the thing is going to be and implement either a hash table or a simpler structure, whichever will be faster, or so I’ve read in Rod Stevens, Visual Basic 2005.)  The programmer adds keys and values.  Then when he has a key, he can retrieve the value quickly. 

I should note here one very cool thing that .NET does with the NameValueCollection.  You don’t need to know at run time how many values you may wind up with for a given key.  In most cases, you have a single value for a key.  But the value returned by GetValues(key) in .NET is a List(Of String).  So in case there is only one value, it’s value(0).  But you could add several values over the course of processing and parse them when you retrieve them.  I use this capability during the trace to find nodes for electric primaries.   

Pre-Processing

Let me describe the pre-processing first.  During development, of course, this came last.  I got the trace working and then looked for ways to speed it up and wrote the pre-processing stuff then.  But the interesting aspect of the trace depends on the results of pre-processing.  The reader will need to be patient because the reasons for generating various text files during pre-processing may be poorly motivated if you don’t know what the trace logic is going to do with them.  There is a flow chart below on page 8, and I hope it’s helpful.

A word on “keys”.  GTViewer uses a one- or two-key system to link graphic elements to tabular data.  Older readers are welcome to think DMRS, MSLINK, FRAMME, etc.  In most of what follows, I will only be concerned with the second key because the first key for Bentley data as converted to GTViewer is always zero (or some other arbitrary value set at conversion time).

The VB.NET Project:  HU_BuildConnectivityTable

HU_BuildConnectivityTable builds six text files:

1.    Connectivity.txt

2.    ConductorTable.txt

3.    StopFeature.txt

4.    StopNode.txt

5.    UnitTransformerTable.txt

6.    TransformerThick.txt

1.    Building Connectivity.txt

We begin by opening a stream reader for GTViewer’s “data.txt” file, the record of tabular data for all features.  It reads line-by-line until it finds the table for “E_OHPRIMARY”.  Then it establishes offsets for the attributes "PRIMARY_STARTID_Remap" and

"PRIMARY_ENDID_Remap". 

(Why?  And what do I mean by this?  In data.txt, GTViewer has a line for the tabular data for each element.  Attribute values are delimited by pipe characters.  Each table section begins with a description of its structure, which includes a list of the attributes in the order they appear in the pipe-delimited list.  So it is a trivial programming activity in .NET to “Split” each line of attributes into an array where I know the index of the PRIMARY_STARTID_Remap and PRIMARY_ENDID_Remap attributes.  Why “_Remap”?  The conversion from Bentley to GTViewer retains the PRIMARY_STARTID and PRIMARY_ENDID attribute values as they exist in Bentley, but it also remaps these somewhat cumbersome GUID-style values to unique integer values that are easier to work with.)

Back to data.txt.  We read each line and write the GTViewer key2 and the start node (PRIMARY_STARTID_Remap) and end node (PRIMARY_ENDID_Remap), pipe delimited, to the text file Connectivity.txt.

Later on, when the user starts the trace application, this text file will be read and loaded into a NameValueCollection called “"nvcNodes” with key2 as the key.

So what?  “So what” is that at run time, I will be able to retrieve the start and end nodes of a primary if I know the graphic-tabular link of the primary.  Specific motivation for that will need to wait for the description of the recursive subroutine at the heart of the trace code.

Electricity travels over more features than OHPRIMARY, so the code also reads the “E_UGPRIMARY” and “E_SWCABBUSBAR” tables and appends the pipe-delimited key2|start_node|end_node string to the file Connectivity.txt.

(Looking ahead to a future version, the code also has provision for E_OHSECONDARY, E_UGSECONDARY, E_OHSERVICE, and E_UGSERVICE, but our data at Huntsville Utilities does not have these values sufficiently populated with accurate values so that a secondary trace can run.)

2.    Building ConductorTable.txt

Slightly different in implementation, but with similar results.  We run a GTViewer query for E_OHPRIMARY and add key2 and ”|” and  “E_OHPRIMARY” to a List(Of String).  We then run another query for E_UGPRIMARY, and another for E_SWCABBUSBAR.  Then we walk through that List and write ConductorTable.txt.

How can I motivate such a simple-minded activity?  At times during the trace, the code will have key2 for a primary, and it will need to now what table that primary is in.  In early versions of the trace, I found this table in a clunky way that took a lot of time.  Currently, I load up another NameValueCollection (hash table) called “nvcConductorTable” when the user starts the trace, so the look-up is brisk.

3.    Building StopFeature.txt

Similar to building ConductorTable.txt except that it takes two steps.  First, we build a StopFeatureList by running a query to find every switch.  That sentence hides some complexity.  I compile a GTViewer query that returns the PRIMARY_ATTACHEDEDGEID for each E_OHSWITCH.  Then I compile similar queries for each type of stop feature.  Because each of these queries only asks for PRIMARY_ATTACHEDEDGEID, I can append them into a single query.  GTViewer queries (when run in code) return the attribute(s) you ask for, and they also return the category and offset of each element they find.  The category for all primary features is 304, so we know that without the query.  But the offset is golden.  We write the PRIMARY_ATTACHEDEDGEID and “|” and the offset of the switch to a list. In .NET speak: a List(Of String) called “StopFeatureList”.

Then we walk through StopFeatureList and use the PRIMARY_ATTACHEDEDGEID value to run another query to find primaries by PRIMARY_NETID.  The PRIMARY_NETID for a primary is, of course, the same number as the PRIMARY_ATTACHEDEDGEID for a stop feature that is attached to this primary.  So as the query returns primaries which we know have stop features attached, we note the key2 of the primary and write it to a temporary list with a pipe symbol and the PRIMARY_NETID.  Then we write this list to the file StopFeature.txt.

Again, so what?  Well, after loading StopFeature.txt into a NameValueCollection called “nvcStopFeature” when the user starts the trace application, we can quickly test whether a primary has a stop feature attached.  We use the key2 of the primary as a key to nvcStopFeatures.  If we get any values, then the primary has a stop feature attached.  If not, it doesn’t.

4.    Building StopNode.txt

We use StopFeatureList built during the previous step.  We walk through it, pulling out the PRIMARY_ATTACHEDEDGEID (which, of course, is the PRIMARY_NETID of the primary that has a Switch or other stop feature) and and the offset of the stop feature.

First we build a short list called “shortList”, a 2-element array (Of String), that holds the nodes (PRIMARY_STARTID_Remap and PRIMARY_ENDID_Remap) for this primary.  The stop node will be one of these.  Perhaps both.

Then we use the offset to do a GTViewer proximity search (within 50 feet of the origin of the stop feature) to build a list of nodes called “nodeList” from nearby primaries.  (PRIMARY_STARTID_Remap and PRIMARY_ENDID_Remap)  We omit the primary that has the stop feature attached, because we already have those nodes in shortList.

Then, if nodeList contains shortList(0), then we add it to StopNodeList along with “|” and the offset of the stop feature.

Also, if nodeList contains shortList(1), then we add it to StopNodeList along with “|” and the offset of the stop feature.

Then we process the next item in StopFeatureList.

Then we write StopNodeList to the file StopNode.txt.  When the trace initializes, we load StopNode.txt into the NameValueCollection “nvcNodeOffsets”.

So now, while we search from node to node, we can quickly tell if we have reached a node where the trace should stop.  To appreciate why I take the two steps of building both StopNode.txt and StopFeature.txt, see “Special Bentley Considerations” below.

5.    Building UnitTransformerTable.txt and TransformerThick.txt

We can skip these.  They are not used for the trace proper, but are used to sum transformer load by phase for a circuit.  I build the file UnitTransformerTable.txt first and use it to help build the file TransformerThick.txt.  I do it that way because some transformers have a KVA for a phase, and some have child records with different KVA ratings for each of the children.  The point is that, as is becoming boring to you by now, I load this file into a NameValueCollection when the user starts the trace application, and then I can use the node number (on currently processing primary, which is equal to the PRIMARY_NETID of the attached transformer) to get the KVA load for each phase.

Summary of Pre-processing

File name	Contents	Meaning	Comment
ConnectivityTable.txt (used to build nvcNodes)	key2	linkage for E_ OHPRIMARY, E_UGPRIMARY, or E_SWCABBUSBAR	Written on graphic element; points to its tabular data.
	node1	PRIMARY_STARTID_Remap	PRIMARY_STARTID mapped to an integer.
	node2	PRIMARY_ENDID_Remap	PRIMARY_ENDID mapped to an integer.
ConductorTable.txt (used to build nvcConductorTable)	key2	linkage for E_ OHPRIMARY, E_UGPRIMARY, or E_SWCABBUSBAR	Written on graphic element; points to its tabular data.
		table name: E_ OHPRIMARY, E_UGPRIMARY, or E_SWCABBUSBAR
StopFeature.txt (used to build nvcStopFeature)	key2	linkage for E_ OHPRIMARY, E_UGPRIMARY, or E_SWCABBUSBAR that has a stop feature attached to it.	Written on graphic element; points to its tabular data.
	PRIMARY_NETID	Link to PRIMARY_ATTACHEDEDGEID for the stop feature	All I really need is for key2 to have a value in the NameValueCollection.
StopNode.txt (used to build nvcNodeOffsets)	node	PRIMARY_STARTID_Remap or PRIMARY_ENDID_Remap
	offset	Position of the stop feature in the Primary category	Allows the trace to find the origin of the stop feature in order to circle it.  Other than the circle, all I need is a value in the NameValueCollection.

Looking over the summary table above, it may seem that I’m force fitting the stop feature and stop node into a NameValueCollection when all I need is a list, array, or stack.  I tried these data structures, and they were not as fast as the NameValueCollection.  My guess is that a list, array, or stack is searched in sequential order, so the seek time is N/2, whereas the seek time for a NameValueCollection (a hash table) is going to be more like a fixed value between 1 and 2. 

On my four year old Dell laptop, HU_BuildConnectivityTable runs in 121 seconds (call it 2 minutes) on a data set with 89,297 primaries, including overhead primaries, underground primaries, and bus bars.  This run time includes building the Transformer text files.  HU_TraceElectric takes about 2 or 3 seconds to initialize, which includes loading the text files into NameValueCollections.  I consider these to be acceptable times when they enable a node-to-node trace to run at about 1,000 features per second.
 
 The Trace Logic

The VB.NET project is called HU_ElectricTrace.  It is run as an external application in GTViewer.  Here is the essential section of the form shown to the user:

A simplified flowchart is presented on the next page.

Simplified Flow Chart

Sequence of Actions

The user clicks the “Trace Primary” button on the form and then clicks on a breaker at a substation (E_PRIMARYCIRCUIT).  A current limitation is that the trace can only start with a substation breaker.  Future versions will allow the user to start on any conducting feature.

Then we determine the name of the circuit from that feature and write it to the Listbox on the form.

Then we get keys for the breaker and determine its node number (PRIMARY_NETID_Remap).  This is the initialStartNode. We push that node on the node stack, push that node on the nodes visited stack, and pass it to the Node Iterator.

Node Iterator

The sub “Node Iterator” is the recursive subroutine at the heart of the trace.

It runs a special GTViewer query called a “connectivity query”, that returns 2 arrays when fed a node number.  One array is a list of key1 values.  The other is a list of key2 values.  It also returns a count of the number of values returned, so the programmer writes a For…Next loop that processes each set of key1-key2 pairs in turn.  The keys are the links to every primary that is connected to the node.  In our case, we need only use key2. 

(Now that I have learned a few things by working on this trace, I realize I could write an equivalent to the connectivity query.  It would be a NameValueCollection with the node as the key and a list of key2’s as the values.  When you define the connectivity query, you have to provide the sorts of features that can have nodes you want to consider, as well as the table and attribute names for the nodes.  For example, E_OHPRIMARY, PRIMARY_STARTID, PRIMARY_ENDID.  My code works fine using the special GTViewer query; but developers outside the GTViewer product can just as well use a NameValueCollection with the node number as key and the list of links to primaries as the values.)

Joey Rogers, designer and developer of GTViewer, has provided a note on the connectivity query:

The connectivity query in GTViewer is performing a Binary Search over records that are pre-sorted.  There is a lot of debate over using Binary Search vs. Hash Tables to look up values.  Binary Searches generally work better if you don’t have unique keys;  Hash Tables usually work better if you have unique keys.  Since there are many records with the same keys in typical GIS data, and since the connectivity query uses the same keys for each node of a feature, the Binary Search was used in GTViewer.   However, Hash tables should work better for this trace application because you can use unique keys for most/all of the different pre-processed data in the hash tables.

For each key2, we check whether it is already in a stack that contains key2 values for primaries that have already been processed.  (Since the connectivity query returns all the primaries that share that node, once you are downstream on the trace, it will return the primary you came from, which you want to disregard.  By historical accident, this stack is called “ufidStack”.  I will refer to it later.)

(At the risk of starting too many side trails, I will note here that if key2 is already in ufidStack, the code tests whether the count of connected primaries is 1.  If so, then we have a leaf node, and we add its keys to a List(Of Integer) called “leafNodes”.  I don’t use this in the current version of the trace, but in previous versions I did something with all these leaf nodes.  So I kept the ability to keep track of them, and here is where.  After this leaf node test the code skips to the …Next part of the For…Next loop.)

If key2 has not already been processed, we use it to get the table for that feature from the NameValueCollection “nvcConductorTable”.

Now we test whether the current node is a stop node and whether the primary for which we have key2 is a stop feature, using simple functions that use nvcStopNode and nvcStopFeature.  If both tests pass, we have found a stop node on a stop feature; so we add the stop feature to a highlight list for stop features and skip to the next set of keys in the For…Next loop.

If not, then we keep going.

We push the key2 of the primary onto the ufidStack.  We increment the primary counter.  We add the primary to the highlight list.  (In GTViewer, there is a concept of adding something to the highlight list and separately displaying the highlight.  This separation allows you to add lots of features to the highlight list without slowing down by updating the display.)  Based on a user setting on the trace form, we update the display after processing every nth primary or we wait until the whole circuit is complete.

Now we determine the next node to feed Node Iterator.

We look at the NameValueCollection “nvcNodes”, which was built during initialization from Connectivity.txt.  The key is the key2 for the primary; the value is the pipe-delimited list of two nodes.  The GetNextNode function merely parses out the nodes and returns the one that is not already in the nodesVisited stack. 

(Performance note:  It seems that .NET does a (slow) sequential search to find out if an item is in a List, but does a fast search to find if an item is in a Stack.  I could be wrong.  It may be that the stack of visited nodes is always relatively small (<2 and="" because="" composed="" each="" fast.="" feeder="" for="" integers="" is="" it="" of="" reinitialized="" s="" so="" span="" style="mso-spacerun: yes;" that="" why="">  Or it may be that even a sequential search of the stack from the top down will generally find the previous node soon in its path.)

Not quite done.  This new node may be a stop node.  We add it to the nodesVisited stack and test whether it is a stop node and whether the feature for which we have key2 is a stop feature.  We may have just turned up the other end of a feature that is a stop node and need to stop there.  If we do not find both stop node and feature, we push the new node onto the nodeStack and pass it to Node Iterator, which feeds the recursion. 

The very next line in the code is “nodeStack.Pop”.  It’s really magical to me.  The recursion can go down a long path, but as it unpeels, the nodeStack pops off the nodes, and can resume at a node it bypassed earlier.  When the last node on the stack is popped, it’s done.

When the Node Iterator is Done

We update the view.  In case the ShowAsYouGo box has not been checked, this is the first time the user sees the traced primaries on the screen.

We use the primary counter to show how many primaries have been processed.

  

Then we call the subroutine PostProcess.

Not too much of interest for the purposes of this paper, but I will note that if the box ShowTransformerKvaByPhase has been checked, we show a summary of load by phase.  This may have some interest for Bentley people.  For some types of transformers, it is necessary to drill down to the child records of a Transformer Bank to get the phases of the units.  The hard work is done in HU_BuildConnectivityTable where we create another text file that makes it easy (and brisk) at run time.

Special Bentley Considerations

Bentley models stop features (E_OHSWITCHBANK, E_SWCABFUSEDSWITCH, E_SWCABGROUPSWITCH) as edge devices.  Their attribute PRIMARY_ATTACHEDEDGEID maps to the PRIMARY_NETID of a conducting feature.  Therefore, stop features cannot be placed in a NODE1-NODE2 pattern.  It would simplify processing tremendously if Switches and other potential stop features had a node that matched where they connected to the primaries.  But it would require a potentially major rework of the Bentley feature model.

What the trace code has to do is test whether a node is a stop node and whether the primary it is currently processing is attached to a stop feature.  Only if both conditions are satisfied should the trace stop.  If stop features had a shared node with the primaries they connect to, this check would be simpler.

For a Bentley developer, the task of writing all these queries transforms into the task of writing a series of SQL statements.  I don’t mean to minimize the task, but it should be approachable for an SQL guy.