Матрица смежности на PHP, не могу разобраться как реализовать?

Question

[Wonddez]

Добрый день.
Стоит задача, расчета матрицы смежности. Т.е. мне надо получить расстояние между POI (точками на карте)
Не понимаю как построить матрицу.

Есть ли примеры данного алгоритма не в математической формуле а в виде реализации?

upd.
Уточню, если описание не понятно, извиняюсь.
данные в виде массива координат

["37.7880555555556,-122.399166666667", "40.7252222222222,-73.9993888888889"]

Comments

[Perzh]

В каком виде у вас данные по которым нужно построить матрицу?

[Wonddez]

обычный массив координат

["37.7880555555556,-122.399166666667", "40.7252222222222,-73.9993888888889"]

Answer 1

[Sergej]

# $citys массив городов, у которых есть poi. 
# poi являются массивом в виде строки.
# calcRange
public function createdMatrix ($citys)
    {
        # Пробегаем грода
        for ($i = 0; count($citys) > $i; $i++) {
            $poi = $citys[$i]->poi;
            $count_poi = count($poi);
            for ($r = 0; $count_poi > $r; $r++) {
                $data[$i][$r] = []; 
                for ($v = 0; $count_poi > $v; $v++) {
                    $sqrt = $this->calcRange($poi[$r]['coordinates'], $poi[$v]['coordinates']);
                    $data[$i][$r][] = $sqrt;
                }
                $data[$i][$r]['max'] = $this->maxHorizontSum($data[$i][$r]);

            }
            $data[$i]['max'][] = max($data[$i]);

        }
        return $data;
    }

# Получаем разницу между точками
 public function calcRange($cdr1, $cdr2)
    {
        $cdr1 = explode(',', $cdr1);
        $cdr2 = explode(',', $cdr2);
        $sqrt = sqrt(pow(( $cdr1[0] - $cdr2[0] ), 2) + pow(( $cdr1[1] - $cdr2[1] ), 2));
        return round($sqrt, 6);
    }

В итоге вы получите примерно следующие. Если конечно в HTML будите выводить.
11 поле, сложение горизонтали

Answer 2

[Alexander Movchan]

В данном примере задаётся по три числа: индексы двух вершин и вес ребра между ними.

int N;
cin >> N;

int** am = new int*[N];
for(int i = 0; i != N; ++i)
    am[i] = new int[N];

int i, j, l;
while(cin) {
    cin >> i >> j >> l;
    am[i][j] = l;
}

upd.
Окей, если вершины - это точки, а рёбра расстояния между ними, делаем следующим образом:

// N - количество точек
// points - список точек
// points[i].x - x-координата i-той точки
// points[i].y - y-координата i-той точки

int** am = new int*[N];
for(int i = 0; i != N; ++i)
    am[i] = new int[N];

for(int i = 0; i != N; ++i) {
    for(int j = 0; j != N; ++j) {
        am[i][j] = sqrt( sqr(points[i].x - points[j].x) + sqr(points[i].y - points[j].y) );
    }
}

Можете также оптимизировать, высчитав не всё матрицу, а только её половину (треугольник). А вторую половину заполнить зеркально главной диагонали.

Comments

[Кирилл Пензин]

brainick вы не уточняли на каком языке хотите реализацию. Но вам всё показали досконально. Создаёте двумерный массив. Индексы массива это координаты точки. Значение в ячейке вес ребра между ними. Вот и вся матрица смежности.

[Wonddez]

Кирилл Пензин: Извините, а что значит - "вер ребра между ними"

[Кирилл Пензин]

Wonddez: в вашем случае это расстояние между точками должно быть. Постарайтесь освоить основную терминологию работы с графами, если приступаете к подобным задачам. На википедии довольно неплохое описание матрицы смежности есть.

[Alexander Movchan]

Wonddez: Вес. В данном случае - длинна, характеризует расстояние между вершинами. Вам видимо стоит подучить теорию графов. https://ru.wikipedia.org/wiki/%D0%93%D0%BB%D0%BE%D...

[Wonddez]

Александр: Кирилл Пензин:
Вы правы, с этим я толкнулся впервые и данного материала в голове нет.
Видимо с возрастом тупею, т.к. этот алгоритм дается с большим трудом.

[Кирилл Пензин]

Wonddez: Вам даже лучше не просто двумерный массив использовать, а двумерный ассоциативный массив, потому как координаты точек лучше оставить строчкой и использовать в качестве ключа.

[Alexander Movchan]

Кирилл Пензин: в данном случае не вижу преимуществ у ассоциативного массива. Обычный массив имеет скорость доступа О(1), а ассоциативный лишь замедлит алгоритм. А хранить координаты в строках - бессмысленно и беспощадно по отношению к памяти и процессору.

[Валерий Рябошапко]

Александр: прошу прощения за оффтоп, но использовать PHP^W скриптовый язык для математических расчётов "на лету" - бессмысленно и беспощадно по отношению к памяти и процессору.

[Кирилл Пензин]

Валерий Рябошапко: кто ж спорит. Но если точек немного(10-20), то можно, наверное.

[Кирилл Пензин]

Александр: окей. Как тогда и где хранить данные координаты? Вещественное число как индекс массива?

[Alexander Movchan]

Кирилл Пензин: в любом случае чтоб запросить точку в ассоциативном массиве по строке координат, нужно сначала эту строку достать из уже данного массива точек используя индекс. Но зная индекс быстрее сразу получить её из двумерного массива.

[Sergej]

Валерий Рябошапко: Все делается просто, прогоняется несколько циклов, используем мат. функции.
Только что построил на 500 позиций. Обработка заняла менее секунды, плюс отрисовка таблицы.