HighwayGraph.matching_edges

[yakra]

Similar changes yielded a 37.7% speed improvement Creating regional data graphs in the C++ version:

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1518 to 1520 in 791e6be

	self.unique_waypoints = dict()
	all_waypoint_list = all_waypoints.point_list()
	self.highway_systems = highway_systems

Add:

self.edges = set()
self.collapsed_edges = set()

---

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1267 to 1269 in 791e6be

	if not duplicate:
	graph.vertices[s.waypoint1.unique_name].incident_edges.append(self)
	graph.vertices[s.waypoint2.unique_name].incident_edges.append(self)

Add graph.edges.add(self) here.

---

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1334 to 1336 in 791e6be

	if not duplicate:
	self.vertex1.incident_collapsed_edges.append(self)
	self.vertex2.incident_collapsed_edges.append(self)

Add graph.collapsed_edges.add(self) here.

---

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1345 to 1346 in 791e6be

	edge1 = vertex_info.incident_collapsed_edges[0]
	edge2 = vertex_info.incident_collapsed_edges[1]

Add graph.collapsed_edges.add(self) here.

---

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1399 to 1400 in 791e6be

	if removed != 1:
	print("ERROR: edge1 " + str(edge1) + " removed from " + str(removed) + " adjacency lists instead of 1.")

Add graph.collapsed_edges.remove(edge1) here.

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1408 to 1409 in 791e6be

	if removed != 1:
	print("ERROR: edge2 " + str(edge2) + " removed from " + str(removed) + " adjacency lists instead of 1.")

Add graph.collapsed_edges.remove(edge2) here.

---

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1718 to 1723 in 791e6be

	def matching_edges(self, regions=None, systems=None, placeradius=None):
	# return a set of edges from the graph, optionally
	# restricted by region or system or placeradius area
	edge_set = set()
	for v in self.vertices.values():
	for e in v.incident_edges:

Lose the first for loop, and change the second to for e in self.edges:.

---

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1736 to 1745 in 791e6be

	def matching_collapsed_edges(self, regions=None, systems=None,
	placeradius=None):
	# return a set of edges from the graph edges for the collapsed
	# edge format, optionally restricted by region or system or
	# placeradius area
	edge_set = set()
	for v in self.vertices.values():
	if v.is_hidden:
	continue
	for e in v.incident_collapsed_edges:

Lose the first for loop, and the if v.is_hidden: check.
Change the second loop to for e in self.collapsed_edges:.

[yakra]

Tested on noreaster

task	before	after	time ratio	% speed increase
Creating area data graphs	396.2	290.5	0.733	36.4
Creating regional data graphs	710.2	486.8	0.685	45.9
Creating system data graphs	13.2	9.6	0.727	37.5
Creating multisystem graphs	16.4	13.5	0.823	21.5
Creating multiregion graphs	14.1	10.8	0.766	30.6
Creating country graphs	72.8	61.1	0.839	19.1
Creating continent graphs	76.8	69.4	0.904	10.7
TOTAL	1299.7	941.7	0.725	38.0

Saves almost 6 minutes in all. Not bad.

[jteresco]

Not just not bad, that 6 minutes is really good! Thanks for the work on this.

[yakra]

It would probably be a little bit more efficient to use lists instead of sets.
The "Setting up for graphs of highway data" process only went from 28.9 to 29.8 s, so this is relatively minor, but still...

Edit: LOL nope. Sets are much more efficient. #180 closes this.

[yakra]

Ironically enough, it may be even faster, now that #182 is in place, to undo all these changes, and only modify the outer FOR loops: Why iterate thru all the edges in the master graph, when we can examine just those incident to the vertices already known to be in our subgraph?
I think I'll give #183 a crack before looking into this.

[yakra]

Prediction:

• Not much time savings for continent graphs, possibly taking a bit more time for NA & EUR.
  (Right now, these take 11s & 9s respectively, C++ on BiggaTomato.)
• Considerable time savings for area graphs.

[yakra]

C++ on BiggaTomato:

task	before	after	time ratio	% speed increase
Creating area data graphs	37.2	11.3	0.304	229.2
Creating regional data graphs	164.7	83.8	0.509	96.5
Creating system data graphs	3.7	2.6	0.703	42.3
Creating multisystem graphs	6.6	5.6	0.848	17.9
Creating multiregion graphs	4.6	3.5	0.761	31.4
Creating country graphs	29.4	24.8	0.844	18.5
Creating continent graphs	36.0	33.7	0.936	6.8
TOTAL:	282.2	165.3	0.586	70.7

Saves just under 2 minutes in all.

As predicted, considerable time savings for area graphs.
Happily contrary to prediction, continent graphs are still a little faster too.

[yakra]

Python on noreaster:

Compared to the version in #185:

task	before	after	time ratio>	% speed increase
Creating area data graphs	171.1	50.0	0.3	242.2
Creating regional data graphs	142.9	71.7	0.5	99.3
Creating system data graphs	5.0	3.3	0.7	51.5
Creating multisystem graphs	6.4	4.8	0.8	33.3
Creating multiregion graphs	4.2	2.9	0.7	44.8
Creating country graphs	24.3	18.6	0.8	30.6
Creating continent graphs	28.4	24.2	0.9	17.4
TOTAL:	382.3	175.5	0.5	117.8

saving 3:27

---

Compared to 791e6be:

task	before	after	time ratio	% speed increase
Creating area data graphs	447.2	50.0	0.112	794.4
Creating regional data graphs	724.6	71.7	0.099	910.6
Creating system data graphs	13.3	3.3	0.248	303.0
Creating multisystem graphs	16.9	4.8	0.284	252.1
Creating multiregion graphs	14.2	2.9	0.204	389.7
Creating country graphs	73.5	18.6	0.253	295.2
Creating continent graphs	78.8	24.2	0.307	225.6
TOTAL:	1368.5	175.5	0.128	679.8

saving 19:53 since all this began. Neato!