SHA256
Связи: раскладки по смыслу – компании, интересы, города
«По группам», «Подсолнух» и «Мандала» показывали ту же близость другой формой. Вместо них – способы разобрать людей по группам, как на доске детектива: - «Компании»: кто из ваших людей знаком между собой. Знакомства берутся из графов связей самих людей (запрос на человека, хранятся на устройстве, освежаются раз в 12 часов), компании находит метод Лувена. Внутри компании люди стоят сотами – самые связанные в середине, знакомые рядом; компании – островами вокруг вас, нить между островами – сколько в них знакомых друг с другом. Название: своё (карточка компании → «Назвать»), иначе по каналу, который читают многие из компании, иначе по самому связанному человеку («Илья С. и др.»). Человека можно перетащить в другую компанию или «Перенести…» из его карточки, есть «Новая компания…» (всё с «Отменить»). - «Интересы»: люди у каналов, на которые подписаны (список «Подписки» профиля); каждый – у самого «своего» канала (общие «Новости района» не перетягивают всех). - «Города»: по полю «Город» в профиле; «Мск», «г. Москва» и «москва» – один город. - Нажатие на канал подсвечивает всех его читателей по всей карте, в любой раскладке: остров в «Интересах», «Ещё» → «Читают канал», строка «Читают:» в карточке компании или города; в списке тогда – только читатели. - Карточка группы: состав по близости, что читают, с кем знакомы, «Списком». - На общем виде касание по острову выбирает группу; подписи стоят на самих островах. - Убран «призрачный клик»: после касания карты браузер нажимал кнопку карточки, появившейся под пальцем («Написать», чип соседней группы). Список «Связей» – с теми же порядками. Сервер не менялся: всё считается на устройстве.
This commit is contained in:
@@ -0,0 +1,659 @@
|
||||
// Группы людей на карте связей: «Компании» (кто с кем знаком), «Интересы» (кто на что подписан)
|
||||
// и «Города» (кто где живёт).
|
||||
//
|
||||
// Компании ищутся по знакомствам между людьми первого круга – из их собственных графов связей.
|
||||
// Метод Лувена (максимум модулярности) собирает вместе тех, кто плотно знаком между собой:
|
||||
// школа кунг-фу знакома внутри себя, коллеги – внутри себя, а между ними редкие мостики.
|
||||
// Всё считается на устройстве за миллисекунды и детерминированно: те же данные – та же картина.
|
||||
//
|
||||
// Названия: своё (дал владелец карты) → по каналу, который читает большинство компании и
|
||||
// заметно реже остальные → по самому связанному человеку («Илья С. и др.»).
|
||||
//
|
||||
// Раскладка «островами»: внутри компании люди стоят сотами (ровный шаг, подписи не
|
||||
// налезают), в середине – самые связанные, знакомые – рядом. Острова упаковываются вокруг
|
||||
// человека в центре: крупные ближе, связанные между собой – по соседству.
|
||||
|
||||
export const REST_GROUP = 'rest';
|
||||
export const ISLAND_COLORS = 8; // цветов подложек; сами цвета – в движке карты (зависят от темы)
|
||||
|
||||
// Вес знакомства по виду связи: близкие сближают сильнее контактов.
|
||||
const TIE_WEIGHT = { close_friend: 3, family: 3, friend: 2, contact: 1 };
|
||||
const RELATION_RANK = { close_friend: 0, family: 1, friend: 2, contact: 3 };
|
||||
|
||||
export function tieWeight(type, mutual = true) {
|
||||
return (TIE_WEIGHT[type] || 1) * (mutual ? 1 : 0.6);
|
||||
}
|
||||
|
||||
function byName(a, b) {
|
||||
return String(a.name || a.id).localeCompare(String(b.name || b.id), 'ru');
|
||||
}
|
||||
|
||||
// Короткое имя для подписей: «Илья С.»; без фамилии – как есть.
|
||||
export function shortPersonName(person) {
|
||||
const first = String(person?.firstName || '').trim();
|
||||
const last = String(person?.lastName || '').trim();
|
||||
const text = first && last ? `${first} ${last[0]}.` : String(person?.name || person?.login || person?.id || '');
|
||||
return text.length > 18 ? `${text.slice(0, 17)}…` : text;
|
||||
}
|
||||
|
||||
function jaccard(a, b) {
|
||||
if (!a.size || !b.size) return 0;
|
||||
let common = 0;
|
||||
const [small, big] = a.size <= b.size ? [a, b] : [b, a];
|
||||
small.forEach((id) => { if (big.has(id)) common += 1; });
|
||||
return common / (a.size + b.size - common);
|
||||
}
|
||||
|
||||
// --- Сообщества -----------------------------------------------------------------------------
|
||||
|
||||
/**
|
||||
* Метод Лувена: узлы переходят в соседнее сообщество, пока это повышает модулярность,
|
||||
* затем сообщества сворачиваются в узлы, и всё повторяется уровнем выше.
|
||||
* @param {string[]} ids
|
||||
* @param {Map<string, Map<string, number>>} weights – веса знакомств (можно несимметрично)
|
||||
* @returns {string[][]} сообщества (одиночки – тоже сообщества)
|
||||
*/
|
||||
export function detectCommunities(ids, weights, { resolution = 1 } = {}) {
|
||||
const order = [...new Set(ids)].sort();
|
||||
if (!order.length) return [];
|
||||
const index = new Map(order.map((id, i) => [id, i]));
|
||||
// Неориентированный граф: у пары – наибольший из весов в обе стороны.
|
||||
const pairs = new Map();
|
||||
weights.forEach((near, a) => {
|
||||
const i = index.get(a);
|
||||
if (i === undefined) return;
|
||||
near.forEach((w, b) => {
|
||||
const j = index.get(b);
|
||||
if (j === undefined || j === i || !(w > 0)) return;
|
||||
const key = i < j ? i * order.length + j : j * order.length + i;
|
||||
pairs.set(key, Math.max(pairs.get(key) || 0, w));
|
||||
});
|
||||
});
|
||||
let adj = order.map(() => new Map());
|
||||
let loops = new Float64Array(order.length);
|
||||
let total = 0;
|
||||
pairs.forEach((w, key) => {
|
||||
const i = Math.floor(key / order.length);
|
||||
const j = key % order.length;
|
||||
adj[i].set(j, w);
|
||||
adj[j].set(i, w);
|
||||
total += w;
|
||||
});
|
||||
if (total <= 0) return order.map((id) => [id]);
|
||||
|
||||
let membership = order.map((_, i) => i); // исходный человек → узел текущего уровня
|
||||
for (let level = 0; level < 16; level += 1) {
|
||||
const n = adj.length;
|
||||
const degree = new Float64Array(n);
|
||||
for (let i = 0; i < n; i += 1) {
|
||||
let k = 2 * loops[i];
|
||||
adj[i].forEach((w) => { k += w; });
|
||||
degree[i] = k;
|
||||
}
|
||||
const m2 = 2 * total;
|
||||
const comm = Int32Array.from({ length: n }, (_, i) => i);
|
||||
const tot = Float64Array.from(degree);
|
||||
let improved = false;
|
||||
for (let pass = 0; pass < 40; pass += 1) {
|
||||
let moved = 0;
|
||||
for (let i = 0; i < n; i += 1) {
|
||||
const own = comm[i];
|
||||
const links = new Map();
|
||||
adj[i].forEach((w, j) => { links.set(comm[j], (links.get(comm[j]) || 0) + w); });
|
||||
tot[own] -= degree[i];
|
||||
let best = own;
|
||||
let bestGain = (links.get(own) || 0) - (resolution * tot[own] * degree[i]) / m2;
|
||||
links.forEach((w, c) => {
|
||||
if (c === own) return;
|
||||
const gain = w - (resolution * tot[c] * degree[i]) / m2;
|
||||
if (gain > bestGain + 1e-12) { best = c; bestGain = gain; }
|
||||
else if (best !== own && Math.abs(gain - bestGain) <= 1e-12 && c < best) best = c;
|
||||
});
|
||||
tot[best] += degree[i];
|
||||
if (best !== own) { comm[i] = best; moved += 1; }
|
||||
}
|
||||
if (!moved) break;
|
||||
improved = true;
|
||||
}
|
||||
if (!improved) break;
|
||||
const renum = new Map();
|
||||
for (let i = 0; i < n; i += 1) if (!renum.has(comm[i])) renum.set(comm[i], renum.size);
|
||||
if (renum.size === n) break;
|
||||
const nextAdj = Array.from({ length: renum.size }, () => new Map());
|
||||
const nextLoops = new Float64Array(renum.size);
|
||||
for (let i = 0; i < n; i += 1) {
|
||||
const ci = renum.get(comm[i]);
|
||||
nextLoops[ci] += loops[i];
|
||||
adj[i].forEach((w, j) => {
|
||||
const cj = renum.get(comm[j]);
|
||||
if (ci === cj) {
|
||||
if (i < j) nextLoops[ci] += w;
|
||||
} else {
|
||||
nextAdj[ci].set(cj, (nextAdj[ci].get(cj) || 0) + w);
|
||||
}
|
||||
});
|
||||
}
|
||||
membership = membership.map((node) => renum.get(comm[node]));
|
||||
adj = nextAdj;
|
||||
loops = nextLoops;
|
||||
}
|
||||
const groups = new Map();
|
||||
membership.forEach((c, i) => {
|
||||
if (!groups.has(c)) groups.set(c, []);
|
||||
groups.get(c).push(order[i]);
|
||||
});
|
||||
return [...groups.values()];
|
||||
}
|
||||
|
||||
// Самый связанный внутри группы: по нему компания узнаётся («Илья С. и др.»).
|
||||
// При равенстве – тот, кто ближе вам, затем по имени.
|
||||
function hubOf(members, weights, byId) {
|
||||
const inside = new Set(members);
|
||||
const rows = members.map((id) => {
|
||||
let score = 0;
|
||||
weights.get(id)?.forEach((w, other) => { if (inside.has(other)) score += w; });
|
||||
const person = byId.get(id) || { id };
|
||||
return { id, score, rank: RELATION_RANK[person.relationType] ?? 9, person };
|
||||
});
|
||||
rows.sort((a, b) => b.score - a.score || a.rank - b.rank || byName(a.person, b.person));
|
||||
return rows[0]?.id || '';
|
||||
}
|
||||
|
||||
// «Илья С. и др.»: число людей подпись покажет отдельно («· 26»), как у названных компаний.
|
||||
function autoLabel(members, hubId, byId) {
|
||||
const hub = shortPersonName(byId.get(hubId) || { id: hubId });
|
||||
return members.length > 1 ? `${hub} и др.` : hub;
|
||||
}
|
||||
|
||||
/**
|
||||
* Названия по подпискам: канал, который читает заметная часть группы и заметно чаще,
|
||||
* чем все остальные. Каждый канал – одной группе (с самым сильным перевесом).
|
||||
* @returns {Map<string, string>} id группы → ключ канала
|
||||
*/
|
||||
function channelNames(groups, subs, everyone) {
|
||||
const out = new Map();
|
||||
if (!subs?.of?.size) return out;
|
||||
const total = new Map();
|
||||
let known = 0;
|
||||
for (const id of everyone) {
|
||||
const list = subs.of.get(id);
|
||||
if (!list) continue;
|
||||
known += 1;
|
||||
list.forEach((key) => total.set(key, (total.get(key) || 0) + 1));
|
||||
}
|
||||
if (!known) return out;
|
||||
const candidates = [];
|
||||
for (const group of groups) {
|
||||
const n = group.members.length;
|
||||
if (n < 3) continue;
|
||||
const counts = new Map();
|
||||
group.members.forEach((id) => subs.of.get(id)?.forEach((key) => counts.set(key, (counts.get(key) || 0) + 1)));
|
||||
counts.forEach((count, key) => {
|
||||
const share = count / n;
|
||||
const lift = share / ((total.get(key) || count) / known);
|
||||
if (count >= 3 && share >= 0.34 && lift >= 1.3) candidates.push({ group: group.id, key, score: count * lift });
|
||||
});
|
||||
}
|
||||
candidates.sort((a, b) => b.score - a.score || (a.key < b.key ? -1 : 1));
|
||||
const usedChannels = new Set();
|
||||
for (const row of candidates) {
|
||||
if (out.has(row.group) || usedChannels.has(row.key)) continue;
|
||||
out.set(row.group, row.key);
|
||||
usedChannels.add(row.key);
|
||||
}
|
||||
return out;
|
||||
}
|
||||
|
||||
// Цвета островов: свои (сохранённые) остаются; остальным – свободный цвет, а когда свободных
|
||||
// нет – тот, что у наименее связанных с этой группой (на карте связанные стоят рядом,
|
||||
// и одинаковые цвета соседей сливались бы).
|
||||
function assignColors(groups, savedColors, weights = null) {
|
||||
const used = new Map(); // цвет → группы
|
||||
const take = (group, color) => {
|
||||
group.color = color;
|
||||
if (!used.has(color)) used.set(color, []);
|
||||
used.get(color).push(group);
|
||||
};
|
||||
groups.forEach((group) => {
|
||||
const color = savedColors.get(group.id);
|
||||
if (group.kind !== 'rest' && Number.isInteger(color) && color >= 0 && color < ISLAND_COLORS && !used.has(color)) take(group, color);
|
||||
});
|
||||
const affinity = (g1, g2) => {
|
||||
if (!weights) return 0;
|
||||
const inside = new Set(g2.members);
|
||||
let sum = 0;
|
||||
g1.members.forEach((id) => weights.get(id)?.forEach((w, other) => { if (inside.has(other)) sum += w; }));
|
||||
return sum;
|
||||
};
|
||||
groups.forEach((group) => {
|
||||
if (group.kind === 'rest' || Number.isInteger(group.color)) return;
|
||||
// Свой цвет у группы – от её id (у компании это её самый связанный человек): перенос
|
||||
// одного человека или новые знакомые не перекрашивают всю карту.
|
||||
const own = hashColor(group.id);
|
||||
let pick = -1;
|
||||
for (let k = 0; k < ISLAND_COLORS; k += 1) {
|
||||
const c = (own + k) % ISLAND_COLORS;
|
||||
if (!used.has(c)) { pick = c; break; }
|
||||
}
|
||||
if (pick < 0) {
|
||||
let best = Infinity;
|
||||
for (let c = 0; c < ISLAND_COLORS; c += 1) {
|
||||
const clash = used.get(c).reduce((sum, other) => sum + 1 + affinity(group, other), 0);
|
||||
if (clash < best) { best = clash; pick = c; }
|
||||
}
|
||||
}
|
||||
take(group, pick);
|
||||
});
|
||||
}
|
||||
|
||||
function hashColor(text) {
|
||||
let h = 2166136261;
|
||||
for (let i = 0; i < text.length; i += 1) {
|
||||
h ^= text.charCodeAt(i);
|
||||
h = Math.imul(h, 16777619);
|
||||
}
|
||||
return (h >>> 0) % ISLAND_COLORS;
|
||||
}
|
||||
|
||||
function sortGroups(groups) {
|
||||
return groups.sort((a, b) => (a.kind === 'rest') - (b.kind === 'rest')
|
||||
|| b.members.length - a.members.length
|
||||
|| String(a.label).localeCompare(String(b.label), 'ru'));
|
||||
}
|
||||
|
||||
/**
|
||||
* Компании первого круга.
|
||||
* @param {Object} o
|
||||
* @param {Array<{id:string, name:string, firstName?:string, lastName?:string, relationType:string}>} o.people
|
||||
* @param {Map<string, Map<string, number>>} o.weights – веса знакомств
|
||||
* @param {{ groups: Array<{id:string, name:string, members:string[], color?:number}>, assign: Map<string,string> }} o.saved
|
||||
* @param {{ of: Map<string,string[]>, info: Map<string,{name:string}> } | null} [o.subs] – подписки для названий
|
||||
* @returns {{ groups: Array<object>, byPerson: Map<string,string>, snapshots: Array<{id:string, members:string[]}> }}
|
||||
*/
|
||||
export function buildCompanies({ people, weights, saved, subs = null }) {
|
||||
const byId = new Map(people.map((person) => [person.id, person]));
|
||||
const ids = people.map((person) => person.id);
|
||||
const assign = new Map([...(saved?.assign || new Map())].filter(([id]) => byId.has(id)));
|
||||
const savedGroups = (saved?.groups || []).filter((group) => group && group.id);
|
||||
const savedById = new Map(savedGroups.map((group) => [group.id, group]));
|
||||
|
||||
const communities = detectCommunities(ids, weights)
|
||||
.map((members) => members.filter((id) => !assign.has(id)))
|
||||
.filter((members) => members.length);
|
||||
|
||||
// Сохранённые компании узнаются по составу: наибольшее совпадение, не меньше трети.
|
||||
const scores = [];
|
||||
communities.forEach((members, ci) => {
|
||||
const set = new Set(members);
|
||||
savedGroups.forEach((group) => {
|
||||
const score = jaccard(set, new Set((group.members || []).filter((id) => byId.has(id) && !assign.has(id))));
|
||||
if (score >= 0.3) scores.push({ ci, id: group.id, score });
|
||||
});
|
||||
});
|
||||
scores.sort((a, b) => b.score - a.score || a.ci - b.ci || (a.id < b.id ? -1 : 1));
|
||||
const matchedCommunity = new Map();
|
||||
const matchedSaved = new Set();
|
||||
for (const row of scores) {
|
||||
if (matchedCommunity.has(row.ci) || matchedSaved.has(row.id)) continue;
|
||||
matchedCommunity.set(row.ci, row.id);
|
||||
matchedSaved.add(row.id);
|
||||
}
|
||||
|
||||
const groups = new Map();
|
||||
const rest = [];
|
||||
communities.forEach((members, ci) => {
|
||||
const savedId = matchedCommunity.get(ci);
|
||||
if (savedId) {
|
||||
groups.set(savedId, { id: savedId, kind: 'company', members: [...members], saved: true });
|
||||
} else if (members.length >= 3) {
|
||||
const hub = hubOf(members, weights, byId);
|
||||
const id = `a:${hub}`;
|
||||
groups.set(id, { id, kind: 'company', members: [...members], saved: false });
|
||||
} else {
|
||||
rest.push(...members);
|
||||
}
|
||||
});
|
||||
// Перенесённые вручную – в свою компанию (даже если её состав сейчас не узнан).
|
||||
assign.forEach((groupId, personId) => {
|
||||
if (groupId === REST_GROUP) { rest.push(personId); return; }
|
||||
let group = groups.get(groupId);
|
||||
if (!group && savedById.has(groupId)) {
|
||||
group = { id: groupId, kind: 'company', members: [], saved: true };
|
||||
groups.set(groupId, group);
|
||||
}
|
||||
if (group) group.members.push(personId);
|
||||
else rest.push(personId);
|
||||
});
|
||||
|
||||
const list = [...groups.values()].filter((group) => group.members.length);
|
||||
const named = channelNames(list.filter((group) => !savedById.get(group.id)?.name), subs, ids);
|
||||
for (const group of list) {
|
||||
group.members.sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
|
||||
group.hubId = hubOf(group.members, weights, byId);
|
||||
const own = savedById.get(group.id);
|
||||
group.name = String(own?.name || '').trim();
|
||||
group.channel = named.get(group.id) || '';
|
||||
group.autoLabel = group.channel ? (subs.info.get(group.channel)?.name || '') : '';
|
||||
if (!group.autoLabel) group.autoLabel = autoLabel(group.members, group.hubId, byId);
|
||||
group.label = group.name || group.autoLabel;
|
||||
// Коротко – для подписи на мелкой карте: без «и др.».
|
||||
group.shortLabel = group.name || (group.channel ? group.autoLabel : shortPersonName(byId.get(group.hubId) || { id: group.hubId }));
|
||||
}
|
||||
if (rest.length) {
|
||||
rest.sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
|
||||
list.push({ id: REST_GROUP, kind: 'rest', members: rest, name: '', autoLabel: 'Без компании', label: 'Без компании', shortLabel: 'Без компании', hubId: '' });
|
||||
}
|
||||
sortGroups(list);
|
||||
assignColors(list, new Map(savedGroups.map((group) => [group.id, group.color])), weights);
|
||||
|
||||
// Состав узнанных компаний обновляется, чтобы их узнавать и дальше, когда люди прибавятся.
|
||||
const snapshots = [];
|
||||
list.forEach((group) => {
|
||||
const own = savedById.get(group.id);
|
||||
if (!own) return;
|
||||
const now = group.members.filter((id) => !assign.has(id));
|
||||
if (jaccard(new Set(now), new Set(own.members || [])) < 0.85 || own.color !== group.color) {
|
||||
snapshots.push({ id: group.id, members: now, color: group.color });
|
||||
}
|
||||
});
|
||||
|
||||
const byPerson = new Map();
|
||||
list.forEach((group) => group.members.forEach((id) => byPerson.set(id, group.id)));
|
||||
return { groups: list, byPerson, snapshots };
|
||||
}
|
||||
|
||||
/**
|
||||
* Интересы: люди собираются у каналов, на которые подписаны. Каждый – у одного канала, самого
|
||||
* «своего»: из читаемых им каналов – того, что реже всего встречается среди этих людей (общие
|
||||
* «Новости района» читают все, а «Ушу» – только свои). Канал, у которого так набирается
|
||||
* меньше minSize человек, группой не считается – его читатели переходят к следующему.
|
||||
* @param {Object} o
|
||||
* @param {Array<{id:string, name:string}>} o.people
|
||||
* @param {{ of: Map<string,string[]>, info: Map<string,{name:string}> }} o.subs
|
||||
*/
|
||||
export function buildInterestGroups({ people, subs }) {
|
||||
const byId = new Map(people.map((person) => [person.id, person]));
|
||||
const followers = new Map();
|
||||
people.forEach((person) => subs?.of?.get(person.id)?.forEach((key) => {
|
||||
if (!followers.has(key)) followers.set(key, []);
|
||||
followers.get(key).push(person.id);
|
||||
}));
|
||||
const minSize = people.length > 30 ? 3 : 2;
|
||||
const eligible = new Set([...followers.entries()].filter(([, ids]) => ids.length >= minSize).map(([key]) => key));
|
||||
let assignment = new Map();
|
||||
for (let round = 0; round < 12; round += 1) {
|
||||
assignment = new Map();
|
||||
for (const person of people) {
|
||||
let best = '';
|
||||
for (const key of subs?.of?.get(person.id) || []) {
|
||||
if (!eligible.has(key)) continue;
|
||||
const n = followers.get(key).length;
|
||||
if (!best || n < followers.get(best).length || (n === followers.get(best).length && key < best)) best = key;
|
||||
}
|
||||
if (best) assignment.set(person.id, best);
|
||||
}
|
||||
const sizes = new Map();
|
||||
assignment.forEach((key) => sizes.set(key, (sizes.get(key) || 0) + 1));
|
||||
let dropped = false;
|
||||
eligible.forEach((key) => {
|
||||
if ((sizes.get(key) || 0) < minSize) { eligible.delete(key); dropped = true; }
|
||||
});
|
||||
if (!dropped) break;
|
||||
}
|
||||
const byChannel = new Map();
|
||||
assignment.forEach((key, id) => {
|
||||
if (!byChannel.has(key)) byChannel.set(key, []);
|
||||
byChannel.get(key).push(id);
|
||||
});
|
||||
const list = [...byChannel.entries()].map(([key, members]) => {
|
||||
const name = String(subs.info.get(key)?.name || key);
|
||||
return { id: `c:${key}`, kind: 'interest', channel: key, members, name: '', autoLabel: name, label: name, shortLabel: name, hubId: '' };
|
||||
});
|
||||
const remaining = new Set(people.map((person) => person.id).filter((id) => !assignment.has(id)));
|
||||
for (const group of list) {
|
||||
group.members.sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
|
||||
// Что ещё читают в этой группе – для карточки группы.
|
||||
const counts = new Map();
|
||||
group.members.forEach((id) => subs.of.get(id)?.forEach((key) => {
|
||||
if (key !== group.channel) counts.set(key, (counts.get(key) || 0) + 1);
|
||||
}));
|
||||
group.alsoRead = [...counts.entries()]
|
||||
.filter(([, count]) => count >= 2)
|
||||
.sort((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1))
|
||||
.slice(0, 3)
|
||||
.map(([key, count]) => ({ key, count, name: String(subs.info.get(key)?.name || key) }));
|
||||
}
|
||||
if (remaining.size) {
|
||||
const members = [...remaining].sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
|
||||
list.push({ id: REST_GROUP, kind: 'rest', members, name: '', autoLabel: 'Без общих подписок', label: 'Без общих подписок', shortLabel: 'Без подписок', hubId: '' });
|
||||
}
|
||||
sortGroups(list);
|
||||
assignColors(list, new Map());
|
||||
const byPerson = new Map();
|
||||
list.forEach((group) => group.members.forEach((id) => byPerson.set(id, group.id)));
|
||||
return { groups: list, byPerson, snapshots: [] };
|
||||
}
|
||||
|
||||
/**
|
||||
* Города: кто где живёт (по полю «Город» в профиле). Разные написания одного города – одна
|
||||
* группа (cities.js). Когда городов много, города с одним человеком собираются в «Другие города».
|
||||
* @param {Object} o
|
||||
* @param {Array<{id:string, name:string}>} o.people
|
||||
* @param {{ of: Map<string,string> }} o.cities
|
||||
* @param {(value:string) => string} o.cityKey
|
||||
* @param {(key:string, spellings:string[]) => string} o.cityLabel
|
||||
*/
|
||||
export function buildCityGroups({ people, cities, cityKey, cityLabel }) {
|
||||
const byId = new Map(people.map((person) => [person.id, person]));
|
||||
const byCity = new Map();
|
||||
const unknown = [];
|
||||
for (const person of people) {
|
||||
const raw = cities?.of?.get(person.id) || '';
|
||||
const key = raw ? cityKey(raw) : '';
|
||||
if (!key) { unknown.push(person.id); continue; }
|
||||
if (!byCity.has(key)) byCity.set(key, { members: [], spellings: [] });
|
||||
byCity.get(key).members.push(person.id);
|
||||
byCity.get(key).spellings.push(raw);
|
||||
}
|
||||
let list = [...byCity.entries()].map(([key, row]) => {
|
||||
const name = cityLabel(key, row.spellings);
|
||||
return { id: `city:${key}`, kind: 'city', city: key, members: row.members, name: '', autoLabel: name, label: name, shortLabel: name, hubId: '' };
|
||||
});
|
||||
const singles = list.filter((group) => group.members.length === 1);
|
||||
if (list.length > 14 && singles.length > 1) {
|
||||
list = list.filter((group) => group.members.length > 1);
|
||||
const members = singles.flatMap((group) => group.members);
|
||||
list.push({ id: 'city:*', kind: 'city', city: '', members, name: '', autoLabel: 'Другие города', label: 'Другие города', shortLabel: 'Другие города', hubId: '' });
|
||||
}
|
||||
for (const group of list) group.members.sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
|
||||
if (unknown.length) {
|
||||
unknown.sort((a, b) => byName(byId.get(a) || { id: a }, byId.get(b) || { id: b }));
|
||||
list.push({ id: REST_GROUP, kind: 'rest', members: unknown, name: '', autoLabel: 'Город не указан', label: 'Город не указан', shortLabel: 'Не указан', hubId: '' });
|
||||
}
|
||||
sortGroups(list);
|
||||
assignColors(list, new Map());
|
||||
const byPerson = new Map();
|
||||
list.forEach((group) => group.members.forEach((id) => byPerson.set(id, group.id)));
|
||||
return { groups: list, byPerson, snapshots: [] };
|
||||
}
|
||||
|
||||
// --- Раскладка островами --------------------------------------------------------------------
|
||||
|
||||
export const ISLAND_STEP = 74; // шаг сот: точка и подпись под ней не налезают на соседей
|
||||
export const ISLAND_PAD = 30; // от края точек до края острова (для упаковки)
|
||||
const ISLAND_GAP = 62; // между островами: над каждым – его подпись
|
||||
const NODE_RADIUS = 22; // точка первого круга (как в движке карты)
|
||||
|
||||
// Места на шестиугольной сетке, ближайшие к середине: остров получается круглым при любом
|
||||
// числе людей (а не шестиугольником с недостроенным краем). При равном расстоянии – по углу.
|
||||
function hexSlots(count) {
|
||||
const size = ISLAND_STEP / Math.sqrt(3);
|
||||
const rings = Math.ceil(Math.sqrt(count / 3)) + 2;
|
||||
const all = [];
|
||||
for (let q = -rings; q <= rings; q += 1) {
|
||||
for (let r = Math.max(-rings, -q - rings); r <= Math.min(rings, -q + rings); r += 1) {
|
||||
const x = size * Math.sqrt(3) * (q + r / 2);
|
||||
const y = size * 1.5 * r;
|
||||
all.push({ x, y, d: Math.round(Math.hypot(x, y) * 100), a: Math.atan2(y, x) });
|
||||
}
|
||||
}
|
||||
all.sort((p, s) => p.d - s.d || p.a - s.a);
|
||||
return all.slice(0, count).map(({ x, y }) => ({ x, y }));
|
||||
}
|
||||
|
||||
/**
|
||||
* Люди острова по сотам: самые связанные – в середине, знакомые – рядом. Начальная
|
||||
* расстановка по спирали, затем жадные обмены местами, пока они сокращают сумму длин
|
||||
* знакомств (с весом) и держат связанных ближе к середине.
|
||||
*/
|
||||
function islandSlots(members, weights, rankOf) {
|
||||
const n = members.length;
|
||||
const slots = hexSlots(n);
|
||||
const index = new Map(members.map((id, i) => [id, i]));
|
||||
const links = members.map(() => []);
|
||||
const strength = new Float64Array(n);
|
||||
members.forEach((a, i) => {
|
||||
weights.get(a)?.forEach((w, b) => {
|
||||
const j = index.get(b);
|
||||
if (j === undefined || j === i) return;
|
||||
links[i].push([j, w]);
|
||||
strength[i] += w;
|
||||
});
|
||||
});
|
||||
// Начало: по связанности, при равенстве – ближе к вам, затем по имени (порядок members).
|
||||
const order = members.map((_, i) => i).sort((a, b) => strength[b] - strength[a] || rankOf(members[a]) - rankOf(members[b]) || a - b);
|
||||
const at = new Int32Array(n); // человек → номер места
|
||||
order.forEach((person, k) => { at[person] = k; });
|
||||
const radius = slots.map((p) => Math.hypot(p.x, p.y));
|
||||
const centerPull = 0.35;
|
||||
const dist = (s, t) => Math.hypot(slots[s].x - slots[t].x, slots[s].y - slots[t].y);
|
||||
const costAt = (i, s, skip) => {
|
||||
let c = centerPull * strength[i] * radius[s] + 4 * rankOf(members[i]) * radius[s] / ISLAND_STEP;
|
||||
for (const [j, w] of links[i]) if (j !== skip) c += w * dist(s, at[j]);
|
||||
return c;
|
||||
};
|
||||
if (n > 2 && n <= 260) {
|
||||
for (let pass = 0; pass < 8; pass += 1) {
|
||||
let swapped = 0;
|
||||
for (let i = 0; i < n; i += 1) {
|
||||
for (let j = i + 1; j < n; j += 1) {
|
||||
const si = at[i];
|
||||
const sj = at[j];
|
||||
const before = costAt(i, si, j) + costAt(j, sj, i);
|
||||
const after = costAt(i, sj, j) + costAt(j, si, i);
|
||||
if (after < before - 1e-6) {
|
||||
at[i] = sj;
|
||||
at[j] = si;
|
||||
swapped += 1;
|
||||
}
|
||||
}
|
||||
}
|
||||
if (!swapped) break;
|
||||
}
|
||||
}
|
||||
const out = new Map();
|
||||
members.forEach((id, i) => out.set(id, { x: slots[at[i]].x, y: slots[at[i]].y }));
|
||||
return out;
|
||||
}
|
||||
|
||||
/**
|
||||
* Острова вокруг центра. Каждый следующий – туда, где он ближе всего к центру (с учётом
|
||||
* растяжения под экран), но рядом с теми островами, с кем у него больше знакомств.
|
||||
* Положение по каждому направлению считается точно: для каждого уже стоящего острова
|
||||
* запретный отрезок расстояний – корни квадратного уравнения.
|
||||
*/
|
||||
function packIslands(islands, affinity, focusRadius, stretch) {
|
||||
const placed = [];
|
||||
const centers = new Map();
|
||||
const ANGLES = 96;
|
||||
for (const island of islands) {
|
||||
let best = null;
|
||||
for (let k = 0; k < ANGLES; k += 1) {
|
||||
const theta = -Math.PI / 2 + (k * Math.PI * 2) / ANGLES;
|
||||
const ux = Math.cos(theta) * stretch.x;
|
||||
const uy = Math.sin(theta) * stretch.y;
|
||||
const uu = ux * ux + uy * uy;
|
||||
const intervals = [];
|
||||
const keep = focusRadius + island.r + ISLAND_GAP;
|
||||
intervals.push([-Infinity, keep / Math.sqrt(uu)]);
|
||||
for (const other of placed) {
|
||||
const reach = island.r + other.r + ISLAND_GAP;
|
||||
const b = -2 * (ux * other.x + uy * other.y);
|
||||
const c = other.x * other.x + other.y * other.y - reach * reach;
|
||||
const disc = b * b - 4 * uu * c;
|
||||
if (disc <= 0) continue;
|
||||
const sq = Math.sqrt(disc);
|
||||
intervals.push([(-b - sq) / (2 * uu), (-b + sq) / (2 * uu)]);
|
||||
}
|
||||
intervals.sort((p, q) => p[0] - q[0]);
|
||||
let d = 0;
|
||||
for (let guard = 0; guard < intervals.length + 2; guard += 1) {
|
||||
let moved = false;
|
||||
for (const [d1, d2] of intervals) {
|
||||
if (d1 < d + 1e-6 && d < d2 - 1e-6) { d = d2; moved = true; }
|
||||
}
|
||||
if (!moved) break;
|
||||
}
|
||||
const x = ux * d;
|
||||
const y = uy * d;
|
||||
let pull = 0;
|
||||
let pullW = 0;
|
||||
affinity.get(island.id)?.forEach((w, otherId) => {
|
||||
const c = centers.get(otherId);
|
||||
if (!c) return;
|
||||
pull += w * Math.hypot(x - c.x, y - c.y);
|
||||
pullW += w;
|
||||
});
|
||||
const cost = d + (pullW ? (0.55 * pull) / pullW : 0) + k * 1e-6;
|
||||
if (!best || cost < best.cost) best = { x, y, cost };
|
||||
}
|
||||
const spot = { id: island.id, x: best.x, y: best.y, r: island.r };
|
||||
placed.push(spot);
|
||||
centers.set(island.id, spot);
|
||||
}
|
||||
return centers;
|
||||
}
|
||||
|
||||
/**
|
||||
* Координаты людей первого круга островами.
|
||||
* @param {Object} o
|
||||
* @param {Array<{id:string, kind:string, members:string[]}>} o.groups – по порядку (крупные первыми)
|
||||
* @param {Map<string, Map<string, number>>} o.weights
|
||||
* @param {(id:string) => number} o.rankOf – близость к центру (0 – близкий … 3 – контакт)
|
||||
* @param {number} o.focusRadius – сколько места оставить вокруг человека в центре
|
||||
* @param {{x:number, y:number}} o.stretch
|
||||
* @returns {{ positions: Map<string,{x:number,y:number}>, islands: Map<string,{x:number,y:number,r:number}> }}
|
||||
*/
|
||||
export function layoutIslands({ groups, weights, rankOf, focusRadius = 70, stretch = { x: 1, y: 1 } }) {
|
||||
const local = new Map();
|
||||
const islands = [];
|
||||
for (const group of groups) {
|
||||
if (!group.members.length) continue;
|
||||
const slots = islandSlots(group.members, weights, rankOf);
|
||||
let r = 0;
|
||||
slots.forEach((p) => { r = Math.max(r, Math.hypot(p.x, p.y)); });
|
||||
local.set(group.id, slots);
|
||||
islands.push({ id: group.id, r: r + NODE_RADIUS + ISLAND_PAD });
|
||||
}
|
||||
// Сколько знакомств между островами – соседями становятся самые связанные.
|
||||
const groupOf = new Map();
|
||||
groups.forEach((group) => group.members.forEach((id) => groupOf.set(id, group.id)));
|
||||
const affinity = new Map();
|
||||
weights.forEach((near, a) => {
|
||||
const ga = groupOf.get(a);
|
||||
if (!ga) return;
|
||||
near.forEach((w, b) => {
|
||||
const gb = groupOf.get(b);
|
||||
if (!gb || gb === ga) return;
|
||||
if (!affinity.has(ga)) affinity.set(ga, new Map());
|
||||
affinity.get(ga).set(gb, (affinity.get(ga).get(gb) || 0) + w);
|
||||
});
|
||||
});
|
||||
const centers = packIslands(islands, affinity, focusRadius, stretch);
|
||||
const positions = new Map();
|
||||
local.forEach((slots, groupId) => {
|
||||
const c = centers.get(groupId);
|
||||
slots.forEach((p, id) => positions.set(id, { x: c.x + p.x, y: c.y + p.y }));
|
||||
});
|
||||
return { positions, islands: centers };
|
||||
}
|
||||
Reference in New Issue
Block a user