Вы хотите найти библиотеку или другое решение для подграфа (path) в графе?

Например, существует график, который может быть представлен в виде матрицы смежности, какВы хотите найти библиотеку или другое решение для подграфа (path) в графе?

G = {{ 0, 1, 0 }, { 1, 0, 1 }, { 1, 0, 0 }}

Таким образом, существуют четыре направленныекрая:

node_1 to node_2, node_2 to node_3, node_2 to node_1 and node_3 to node_1.

Я хочу заключается в вычислении сходства между подграфом (путь) {node_2 to node_3} и подграф (путь) { node_2 - node_3 - node_1}.

Что я могу найти больше всего - проблема изоморфизма подграфа, которая пытается определить, соответствует ли подграф (является частью) более крупным графиком. Это не мое желание.

Моя основная задача - определить, насколько похожи два подграфа (путь), которые оба существуют в графе, который я знал.

Любые существующие подходы, которые вы могли бы порекомендовать? Документы? Пример кода?

Заранее спасибо.

источник

2015-02-04 Xingsheng Guo

Как вы измеряете «как похожи два подграфа». Изоморфизм - это один из способов (который вы уже сказали, что не хотите). Какую метрику вы используете или хотите использовать? – TravisJ

@TravisJ Thx для комментария. Это то, что я хочу понять. «Как измерить сходство между двумя подграфами (путями) внутри графика». Я пытаюсь предложить решение для этого ... –

Levenshtein distance измеряет разницу между двумя последовательностями путем подсчета количества одноэлементных изданий, необходимых для изменения одной последовательности в другой.

Если сохранить последовательность вершин каждого пути в виде списка или массива вы можете рассчитать расстояние, используя следующую реализацию (если у вас есть Vertex тип):

int levenshteinDistance(List<Vertex> path, int lenPath, List<Vertex> other, int lenOther) { 
    if (path.equals(other)) return 0; 
    if (lenPath == 0) return lenOther; 
    if (lenOther == 0) return lenPath; 

    int cost; 
    if (path.get(lenPath - 1).equals(other.get(lenOther - 1))) { 
     cost = 0; 
    } else { 
     cost = 1; 
    } 

    int dist1 = levenshteinDistance(path, lenPath - 1, other, lenOther) + 1; 
    int dist2 = levenshteinDistance(path, lenPath, other, lenOther - 1) + 1; 
    int dist3 = levenshteinDistance(path, lenPath - 1, other, lenOther - 1) + cost; 
    return Math.min(dist1, Math.min(dist2, dist3)); 
}

Это неэффективно, хотя, как он пересчитывает расстояние для многих подпоследовательностей. Более эффективную реализацию можно найти на странице http://rosettacode.org/wiki/Levenshtein_distance#Java. Обратите внимание, что он использует String в качестве входных данных, но для его использования необходимо просто переопределить его.

источник

2015-02-04 15:48:19

Thx. Используя это, вы хотите измерить, сколько узлов, которые один путь должен преобразовать в другой путь? Или вы могли бы привести более конкретные примеры? Я просто гуляю по Левенштейну, но никогда не использую его раньше. Thx миллион. –

Отлично! Спасибо за советы. Я попробую их –

Вы хотите найти библиотеку или другое решение для подграфа (path) в графе?

ответ

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