Jgraph: общий обход и обход леса

Question

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

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

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

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

Я собираюсь сделать это, создав класс для объектов vertix, который содержит координаты пикселя в дополнение к его значению, чтобы я мог добавить каждый из них как на график, так и на двумерный массив. После этого я использовал массив для добавления взвешенных ребер между смежными вершинами, потому что 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 чтобы получить список наборов связанных вершин. Каждый набор будет содержать вершины одного из деревьев леса. С наборами вершин легко работать, вам не нужно обходить, просто итерируйте по множеству.