# HG changeset patch
# User Teemu Piippo <teemu@hecknology.net>
# Date 1497117398 -10800
# Node ID a22cdf28930fd1b5e24e63e59fec3a1f0b7a0c86
# Parent  b4fbc92cd915bfacfccf0780f57b55b62d8a9ffa
Lisätty bussipysäkkien ryhmittely

diff -r b4fbc92cd915 -r a22cdf28930f buses.py
--- a/buses.py	Sat Jun 10 18:06:27 2017 +0300
+++ b/buses.py	Sat Jun 10 20:56:38 2017 +0300
@@ -62,6 +62,8 @@
 class Pysäkki:
 	def __init__(self, tunniste, nimi, sijainti):
 		self.tunniste, self.nimi, self.sijainti = tunniste, nimi, sijainti
+		self.cluster = None
+		self.pairs = set() # samannimiset lähellä olevat pysäkit
 	def __repr__(self):
 		return 'pysäkit[%r]' % self.tunniste
 	def aikataulu(self, määrä = 50):
@@ -131,6 +133,7 @@
 ajot_per_numero = {}
 palvelut = {}
 pysäkit = {}
+all_clusters = set()
 
 print('Ladataan linjat... ', file = stderr, end = '', flush = True)
 with open('gtfs/routes.txt') as tiedosto:
@@ -194,6 +197,131 @@
 		pysäkit[pysäkkitunniste].alue = alue
 print('%d pysäkkiä' % len(pysäkit), file = stderr)
 
+class BusStopCluster:
+	def __init__(self):
+		self.stops = set()
+		self._center = None
+		self.name = None
+	def add_stop(self, stop):
+		assert not stop.cluster
+		stop.cluster = self
+		self.stops.add(stop)
+		self._center = None
+	@property
+	def center(self):
+		if not self._center:
+			if self.stops:
+				from statistics import median
+				pointtype = type(next(iter(self.stops)).sijainti)
+				self._center = pointtype(
+					median(stop.sijainti.x for stop in self.stops),
+					median(stop.sijainti.y for stop in self.stops),
+				)
+			else:
+				raise ValueError('an empty cluster has no center point')
+		return self._center
+	def merge(self, other):
+		for bus_stop in other.stops:
+			bus_stop.cluster = self
+		self.stops |= other.stops
+		other.stops = set()
+		other._center = None
+
+from collections import defaultdict
+bus_stops_by_name = defaultdict(set)
+for bus_stop in pysäkit.values():
+	bus_stops_by_name[bus_stop.nimi].add(bus_stop)
+bus_stops_by_name = dict(bus_stops_by_name)
+
+# ryhmittele pysäkit nimen mukaan
+all_clusters = []
+def cluster_bus_stops():
+	sorted_bus_stops = sorted(pysäkit.values(), key = lambda bus_stop: bus_stop.nimi)
+	for bus_stop in sorted_bus_stops:
+		if not bus_stop.cluster:
+			stops_to_cluster = {bus_stop}
+			# etsi pysäkin samannimiset vastaparit
+			for pair_candidate in bus_stops_by_name[bus_stop.nimi]:
+				distance = pair_candidate.sijainti.etäisyys(bus_stop.sijainti)
+				if pair_candidate is not bus_stop and distance <= 0.3:
+					stops_to_cluster.add(pair_candidate)
+			for stop_to_cluster in stops_to_cluster:
+				if stop_to_cluster.cluster:
+					cluster = stop_to_cluster.cluster
+					break
+			else:
+				cluster = BusStopCluster()
+				all_clusters.append(cluster)
+			for stop_to_cluster in stops_to_cluster:
+				if not stop_to_cluster.cluster:
+					cluster.add_stop(stop_to_cluster)
+	# Merkitse muistiin pysäkkien vastaparit käyttäen hyväksi tämänhetkistä ryhmittelytietoa
+	for bus_stop in pysäkit.values():
+		if bus_stop.cluster:
+			bus_stop.pairs = bus_stop.cluster.stops - {bus_stop}
+	# Ryhmitä ne pysäkit, joilla ei ollut omaa vastaparia, muiden pysäkkien kanssa
+	for bus_stop in sorted_bus_stops:
+		if len(bus_stop.cluster.stops) == 1:
+			possibilities = set()
+			for cluster in all_clusters:
+				if cluster is not bus_stop.cluster:
+					distance = cluster.center.etäisyys(bus_stop.sijainti)
+					if distance <= 0.3:
+						possibilities.add((distance, cluster))
+			if possibilities:
+				best = min(possibilities)[1]
+				all_clusters.remove(bus_stop.cluster)
+				best.merge(bus_stop.cluster)
+
+def shared_elements_in_n_sets(sets):
+	from itertools import combinations
+	result = set()
+	for pair in combinations(sets, 2):
+		result |= pair[0] & pair[1]
+	return result
+
+def name_clusters():
+	from collections import defaultdict
+	from pprint import pprint
+	clusters_per_name = defaultdict(set)
+	for cluster in all_clusters:
+		name_representing_stop = min((len(pysäkki.tunniste), pysäkki.tunniste, pysäkki) for pysäkki in cluster.stops)[2]
+		name = name_representing_stop.nimi.lower().replace(' ', '-')
+		clusters_per_name[name].add(cluster)
+	for name, clusters in clusters_per_name.items():
+		if len(clusters) == 1:
+			# Ryhmä on ainoa jolla on varaus tälle nimelle. Sen kuin vaan.
+			next(iter(clusters)).name = name
+		else:
+			# Olisiko kaikki klusterit eri alueilla?
+			common_regions = shared_elements_in_n_sets({stop.alue for stop in cluster.stops} for cluster in clusters)
+			# Esitys: ryhmä -> ne alueet jotka ovat tälle ryhmälle ainutlaatuisia
+			proposal = {
+				cluster: {stop.alue for stop in cluster.stops} - common_regions - {None}
+				for cluster in clusters
+			}
+			# Jos enintään yksi klusteri tässä esityksessä on kokonaan ilman omaa aluetta, jolla se voisi eritellä,
+			# niin nimetään klusterit näiden alueiden mukaan.
+			# Se klusteri jolla ei ole omaa aluetta (jos on) jätetään ilman aluepäätettä.
+			if sum([1 for unique_areas in proposal.values() if not unique_areas]) <= 1:
+				for cluster, unique_areas in proposal.items():
+					individual_cluster_name = name
+					if unique_areas:
+						individual_cluster_name += '-' + min(unique_areas).lower().replace(' ', '-')
+					cluster.name = individual_cluster_name
+			else:
+				# Typerä reunatapaus. Indeksoidaan numeroin...
+				for n, (_, cluster) in enumerate(sorted(
+					min((stop.tunniste.lower(), cluster) for stop in cluster.stops)
+					for cluster in clusters
+				), 1):
+					individual_cluster_name = name + '-' + str(n)
+					cluster.name = individual_cluster_name
+
+print('Ryhmitellään pysäkit...')
+cluster_bus_stops()
+name_clusters()
+
 print('Ladataan aikataulut... ', end = '', flush = True, file = stderr)
 with open('gtfs/stop_times.txt') as file:
 	rivimäärä = sum(line.count('\n') for line in file)