Идентификация графов в куче подключенных узлов - как это называется?

У меня есть таблица SQL с тремя столбцами X, Y, Z. Мне нужно разбить ее по группам таким образом, чтобы все записи с одинаковым значением X или Y или Z были назначены одной и той же группе. Мне нужно убедиться, что записи с одинаковым значением X или Y или Z никогда не разбиваются на несколько групп.Идентификация графов в куче подключенных узлов - как это называется?

Если вы считаете, что записи как узлы и значения X, Y, Z в качестве ребер, эта проблема такая же, как и поиск всех графиков, где узлы в каждом графе будут связаны прямо или косвенно через X, Y или Z -edge, но каждый график не будет иметь никаких ребер вместе с другими графами (иначе он будет частью одного и того же графика).

Несколько лет назад я знал, что это называется и даже помнит алгоритм, но теперь он ускользает от меня. Скажите, пожалуйста, как эта проблема называется так, что я могу найти решение Google. Если у вас сейчас хороший алгоритм, пожалуйста, укажите мне его. Если у Вас есть реализация SQL - я женюсь вас :)

Пример:

X     Y    Z   BUCKET 
---------  ----------------  ---------  ----------- 
    1     34    56    1 
    54     43    45    2 
    1     12    22    1 
    2     34    11    1

В последней строке в ведро 1 из-за величины Y = 34, которая является такой же, как первый ряд, который находится в ведре 1.

источник

2010-09-10 zvolkov

Вы говорите о ['GROUP BY'] (http://www.w3schools.com/sql/sql_groupby.asp) статье? – Oded

@Oded Я не уверен, как относиться к вашему комментарию, будь то шутка или преступление, но, учитывая вашу репутацию в 48 тыс., Я буду рассматривать ее как шутку. Добавлен пример для тех, кто предпочитает изображение тысячам слов. – zvolkov

Не было совершено преступления - разные пользователи имеют разные уровни знаний для разных технологий. Я не предполагаю знания, если этот вопрос не продемонстрирует этого. Я предположил, что ваш SQL не очень хорош ... Я также затрудняюсь понять этот вопрос и несколько расплывчатый, следовательно, мой комментарий. – Oded

Это не похоже на график, более похожий на simplicial complex. Но если мы рассматриваем этот комплекс как его скелетный граф (числа рассматриваются как вершины, а строка в таблице означает, что все эти три вершины связаны ребром), то мы можем просто использовать любой алгоритм, чтобы найти connected components этого графика , Я не уверен, есть ли способ сделать это в SQL, хотя, возможно, было бы разумнее использовать graph database.

Однако для этой конкретной проблемы может быть какое-то простое решение, доступное с помощью SQL, которого я не искал.

источник

2010-09-10 21:20:32 viaclectic

Подключенный компонент является ключевым словом! Благодаря! – zvolkov

, чтобы найти, как много узлов в каждой группе х:

select x, count(x) 
from mytable 
group by x

или найти список множеств х:

select distinct x from mytable;

источник

2010-09-10 21:07:15 Randy

Все значения X не представляют полную группу. Группа также включает в себя все значения Y, которые соответствуют любому из значений Y в записях с тем же значением X. И так далее, рекурсивно для всех других значений X, Y и Z. – zvolkov

Почему вы не изначально выбрали GROUP BY один из колонок (скажем, X), сделайте ведра, а затем сделайте это для Y и Z, каждый раз, когда вы объединяете все ведра с предыдущего шага, если вы найдете новые группы.

Повторите процесс для X, Y и Z, пока ведра не перестанут меняться.

Вы работаете в LinkedIn или Facebook? :)

источник

2010-09-10 21:25:02

Идентификация графов в куче подключенных узлов - как это называется?

ответ

Смежные вопросы