Jgraph: Общее прохождение и прохождение через лес

Question

Доброе утро / день / вечер.

Итак, наш курс по структурам данных дал нам задание сегментировать изображение в градациях серого в Java, используя следующий алгоритм:

Ввод: серое изображение с P пикселями и номером R
Вывод: изображение сегментировано на R областей
1. Отобразите изображение на простой взвешенный график.
2. Найдите MST графика.
3. Обрежьте MST на R - 1 самых дорогих краях.
4. Назначьте средний вес вершины дерева каждой вершине в каждом дереве в лесу
5. Сопоставьте раздел с изображением сегментации

Дело в том, что они просто бросили нас в темноте. Они дали нам пакет jgraph, с которым у нас абсолютно не было опыта (мы никогда его не изучали), практически говоря: «Иди учи себя». Ничего нового там нет.

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

Впоследствии я использовал упакованный метод Крускала для минимальных остовных деревьев и массив, чтобы обойти защищенный статус краевых весов в дереве, например:

ArrayList<WeightedEdge> edgeList = new ArrayList<>(height*width*3);
KruskalMinimumSpanningTree mst4 = new KruskalMinimumSpanningTree(map4);
Set<DefaultWeightedEdge> edges = mst4.getSpanningTree().getEdges();
for (DefaultWeightedEdge edge : edges) {
    edgeList.add(new WeightedEdge(edge, map4.getEdgeWeight(edge)));
}
edgeList.sort(null);

for (int i = 0; i < n; i++) {
    map4.removeEdge(edgeList.get(edgeList.size()-1).getEdge());
}  

Итак, теперь, когда я обрезал (R-1) самые дорогостоящие ребра на графике, мне нужно оставить лес. И вот тут я зашел в другой тупик. Как мне заставить программу пройти каждое дерево? Как я понимаю, мне нужен общий алгоритм обхода, чтобы посетить каждое дерево и назначить среднее значение для каждой вершины. Эта проблема? В пакете нет общего алгоритма обхода. И нет способа идентифицировать отдельные деревья.

Идею легко понять и реализовать на бумаге, правда. Проблемы заключаются только в том, чтобы фактически все это кодировать в Java.

Извините, если это было грязно или слишком долго, но я просто на грани ума и физических ограничений. Заранее спасибо.

Answer 1

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

Из вашего задания я не совсем понимаю шаг 1 (построение первичного взвешенного графа).Остальные должны работать с JGraphT довольно хорошо.

Вы сделали шаг 2 с KruskalMinimumSpanningTree.Теперь вы можете отсортировать ребра по весу и удалить R-1 верхних ребер из графика.

Я бы, однако, предложил вам сначала построить новый граф, который бы представлял вычисленный MST.И затем удалите удалить R-1 верхние края из этого графика.Эффективное объединение его в лес.

Как мне заставить программу пройти каждое дерево?

С лесом из предыдущего шага вы можете использовать ConnectivityInspectorчтобы получить список наборов связанных вершин.Каждый набор будет содержать вершины одного из деревьев леса.С наборами вершин легко работать, вам не нужно обходить, просто переберите множество.