mysterious graph generation results

[yakra]

I want to emphasize that this is not a problem with code intended for production. The bug has already been fixed, but the symptoms for Question 2 below are odd enough that I want to take a deeper look to get a better understanding of HOW it does what it does.

Running "siteupdate4_alt.py" as in this commit:
https://github.com/TravelMapping/DataProcessing/blob/e7f2f9d0fab1982396bb8e7901e37b8cc26bc0fd/siteupdate/python-teresco/siteupdate.py

My commandline is ./siteupdate4_alt.py -t 1, and thus we should avoid any inconsistencies introduced by multithreaded reading of WPT files between trials.
Indeed, on noreaster, I get three identical copies of tm-master.tmg:
http://yakra.teresco.org/tests/tmg/noreaster/1/tm-master.tmg
http://yakra.teresco.org/tests/tmg/noreaster/2/tm-master.tmg
http://yakra.teresco.org/tests/tmg/noreaster/3/tm-master.tmg
So it looks like the graph is represented the same in memory each time.
(On my own system, I get different results, but anyway...)
Looking at the PR regional graphs, I have different results:
(1) (2) (3) PR-region-simple.tmg
(1) (2) (3) PR-region.tmg
FWIW, the vertices are in the same order, but the edges' order differs.

Question 1:

AFAIK, multithreading is only used in reading in WPTs. And again, the master graph is stored identically in memory in each case. How is that I'm getting different results for each PR graph?

Question 2:

To set the stage, look at http://yakra.teresco.org/tests/tmg/noreaster/1/PR-region-simple.tmg.html , Vertex 2954, PR7025@+X145358. This is a HIDDEN_TERMINUS error.
The version of siteupdate.py I'm using is missing the code in this commit, so the PR7025@+X145358 vertex never gets marked as unhidden. Thus the fact that a bug exists is no surprise, but the symptom leaves me scratching my head.
Now look at http://yakra.teresco.org/tests/tmg/noreaster/1/PR-region.tmg.html , Vertex 2166, PR725/PR7025. The collapsed edge goes all the way out to PR330/PR348.
(In the master graph, this edge instead goes all the way out to US69@NE48thSt in Kansas City, MO!)

Trying to look into the code to see what's happening, and I just don't understand.
First, looking into the HighwayGraphCollapsedEdgeInfo constructor. One of the first things I see is

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1241 to 1242 in e7f2f9d

	self.vertex1 = graph.vertices[segment.waypoint1.unique_name]
	self.vertex2 = graph.vertices[segment.waypoint2.unique_name]

OK, so what are vertex1 and vertex2, then?
Time to look at the HighwayGraph constructor:

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1547 to 1550 in e7f2f9d

	# One copy of the vertices
	self.vertices = {}
	for label, pointlist in self.unique_waypoints.items():
	self.vertices[label] = HighwayGraphVertexInfo(pointlist,datacheckerrors)

Looks like vertices is a dict, populated by calling the HighwayGraphVertexInfo constructor.
Can looking up a vertex by a bad unique_name produce a garbage result? Or would we just get None? Or a crash? Or... something? In any case, I don't see any reason to suspect a bad unique_name. So, looking at the HighwayGraphVertexInfo constructor...

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1128 to 1154 in e7f2f9d

	class HighwayGraphVertexInfo:
	"""This class encapsulates information needed for a highway graph
	vertex.
	"""
	def __init__(self,waypoint_list,datacheckerrors):
	self.lat = waypoint_list[0].lat
	self.lng = waypoint_list[0].lng
	self.unique_name = waypoint_list[0].unique_name
	# will consider hidden iff all colocated waypoints are hidden
	self.is_hidden = True
	# note: if saving the first waypoint, no longer need first
	# three fields and can replace with methods
	self.first_waypoint = waypoint_list[0]
	self.regions = set()
	self.systems = set()
	for w in waypoint_list:
	if not w.is_hidden:
	self.is_hidden = False
	self.regions.add(w.route.region)
	self.systems.add(w.route.system)
	self.incident_edges = []
	self.incident_collapsed_edges = []
	# VISIBLE_HIDDEN_COLOC datacheck
	if self.visible_hidden_coloc(waypoint_list):
	datacheckerrors.append(DatacheckEntry(waypoint_list[0].route,[waypoint_list[0].label],"VISIBLE_HIDDEN_COLOC",
	"("+str(waypoint_list[0].lat)+","+str(waypoint_list[0].lng)+")"))

OK, so we've got waypoint_list[0], and the rest follows from there. What waypoint_listgets passed to the constructor? Back again to...

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1547 to 1550 in e7f2f9d

	# One copy of the vertices
	self.vertices = {}
	for label, pointlist in self.unique_waypoints.items():
	self.vertices[label] = HighwayGraphVertexInfo(pointlist,datacheckerrors)

It's pointlist, from the HighwayGraph object's unique_waypoints property...
The only changes I see made to unique_waypoints are at

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1503 to 1509 in e7f2f9d

	# we're good, add the list of waypoints, either as a
	# singleton list or the colocated list a values for the
	# key of the unique name we just computed
	if w.colocated is None:
	self.unique_waypoints[point_name] = [ w ]
	else:
	self.unique_waypoints[point_name] = w.colocated

[ w ] and w.colocated look fine... so maybe the point_name used as an index gets mangled?
This could maybe be connected to a garbage lookup in the dict after all?
It's PR7025@+X145358 that's not getting chosen as our vertex1 or vertex2, so let's focus on this.
This point name should be unique and not taken, so let's look to

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1482 to 1483 in e7f2f9d

	# start with the canonical name
	point_name = w.canonical_waypoint_name(self.waypoint_naming_log)

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 319 to 330 in e7f2f9d

	def canonical_waypoint_name(self,log):
	"""Best name we can come up with for this point bringing in
	information from itself and colocated points (if active/preview)
	"""
	# start with the failsafe name, and see if we can improve before
	# returning
	name = self.simple_waypoint_name()
	# if no colocated points, there's nothing to do - we just use
	# the route@label form and deal with conflicts elsewhere
	if self.colocated is None:
	return name

PR7025@+X145358 has no colocated points, so name should be returned, and we can disregard the rest of the function.
name = self.simple_waypoint_name().

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 541 to 545 in e7f2f9d

	def simple_waypoint_name(self):
	"""Failsafe name for a point, simply the string of route name @
	label, concatenated with & characters for colocated points."""
	if self.colocated is None:
	return self.route.list_entry_name() + "@" + self.label

Is self.label anything unexpected?

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 228 to 232 in e7f2f9d

	def __init__(self,line,route):
	"""initialize object from a .wpt file line"""
	self.route = route
	parts = line.split()
	self.label = parts[0]

Looks like the '+' stays at the beginning, and the label is nothing unexpected.

So I'm out of ideas.
Unless I was barking up the wrong tree chasing down vertex1 & vertex2.
Maybe there's something funky with the segment that gets passed to the HighwayGraphCollapsedEdgeInfo constructor, but I don't see any reason to believe that should be the case.

It's been positively dizzying thinking thru & typing all this out. I hope it's possible to follow. :(

My question is:
How is that the collapsed edge connects to this seemingly random point?
And how is it that is connects to a different endpoint in the master graph and PR-region graph?

(Still haven't looked into the secondary construction, in HighwayGraphCollapsedEdgeInfo(self, vertex_info=vinfo) cases. This could be worthwhile...)

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1276 to 1280 in e7f2f9d

	# we know there are exactly 2 incident edges, as we
	# checked for that, and we will replace these two
	# with the single edge we are constructing here
	edge1 = vertex_info.incident_collapsed_edges[0]
	edge2 = vertex_info.incident_collapsed_edges[1]

Could this be it?

[yakra]

And why are these code links not showing up as code embedded in my comment? :(

[yakra]

Could this be it?

Nope.

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1577 to 1588 in e7f2f9d

	# compress edges adjacent to hidden vertices
	for label, vinfo in self.vertices.items():
	if vinfo.is_hidden:
	if len(vinfo.incident_collapsed_edges) < 2:
	continue
	if len(vinfo.incident_collapsed_edges) > 2:
	dc_waypoint = sorted(vinfo.first_waypoint.colocated, key=lambda waypoint: waypoint.route.root + "@" + waypoint.label)[0]
	datacheckerrors.append(DatacheckEntry(dc_waypoint.route,[dc_waypoint.label],"HIDDEN_JUNCTION",str(len(vinfo.incident_collapsed_edges))))
	vinfo.is_hidden = False
	continue
	# construct from vertex_info this time
	HighwayGraphCollapsedEdgeInfo(self, vertex_info=vinfo)

See that continue on line 1581? This ctor doesn't even get called.

[yakra]

Uncommenting the rest of the DEBUG text from the ctor. Still no clue.
Time to look at write_master_tmg_collapsed and write_subgraph_tmg_collapsed

[yakra]

K, think I got it!

 # write visible vertices
 vertex_num = 0
 for label, vinfo in self.vertices.items():
 if not vinfo.is_hidden:
 vinfo.vertex_num = vertex_num
 tmgfile.write(label + ' ' + str(vinfo.lat) + ' ' + str(vinfo.lng) + '\n')
 vertex_num += 1

The vertex in question is not written, because it is_hidden.
Calls to collapsed_tmg_line proceed normally.

 # line appropriate for a tmg collapsed edge file
 def collapsed_tmg_line(self, systems=None):
 line = str(self.vertex1.vertex_num) + " " + str(self.vertex2.vertex_num) + " " + self.label(systems)
 for intermediate in self.intermediate_points:
 line += " " + str(intermediate.lat) + " " + str(intermediate.lng)
 return line

Either str(self.vertex1.vertex_num) or str(self.vertex1.vertex_num) refers to a vertex, and thus a line, that never got written to the TMG file. The vertex number on the .tmg line describing the edge refers to a garbage vertex (should be the next one after the missing one).
That said, it would seem that every subsequent line would also be off by one, pointing to the wrong vertex. I'm a little surprised there wasn't much more visibly amiss. Maybe I could dive really deep into the HDX, but if ever there was a good time to leave well enough alone, this is it! :D

How'bout that Question 1, though?

[yakra]

Question 1:

AFAIK, multithreading is only used in reading in WPTs. And again, the master graph is stored identically in memory in each case. How is that I'm getting different results for each PR graph?

There's a clue in that on noreaster, the vertices in a TMG are in the same order every time, while locally, the vertices' order can differ between trials.
We know that python3 is implemented differently in FreeBSD vs UbuntuMate.

For vertices, we iterate thusly:

for label, vinfo in self.vertices.items():

Fer edges, we iterate:

for v in self.vertices.values():

I will assume that:

• Python does not have to iterate thru the things in a dict (or the items in a list) in the same order they were added to it. (Iterating by, say, the order they're stored in memory could explain the non-deterministic order.)
• The FreeBSD implementation will do this anyway when iterating for each key value

...and close this issue for my sanity's sake.

[yakra]

BOOM!

• Simple graphs are written before collapsed graphs.
• vinfo.vertex_num gets reused: it gets a raw vertex number for a simple graph in the first pass, and a visible vertex number for a collapsed graph in the second pass.
• Each vertex gets a new vertex_num, based on the number of visible vertices, each associated edge refers to it in the .tmg, and life goes on with nothing visibly amiss.
• On the 2nd pass, the HighwayGraphVertexInfo representing PR7025@+X145358 is skipped, and doesn't receive a new vertex_num. It keeps the old one.
• In PR-region-simple.tmg, vertex 2954 represents PR7025@+X145358.
• In PR-region.tmg, The line for the edge representing all of PR7025 contains the vertex number for PR7025@+X145358 -- which is still 2954. Hence the collapsed edge leading to some random faraway point.
• This explains why one test on my local machine (where .tmg point order is not deterministic) produced TMGs that would not load in HDX or HDX-Lite: The line for that edge contained a raw vertex number > the total number of visible vertices.