Нахождение и исправление островков меток в сетиx

Question

У меня есть график, где каждый узел имеет целочисленную метку. Если график хорошо себя ведет, помеченные области будут непрерывными. Я хотел бы написать что-то в python networkx, чтобы "исправить" плохие графики. Например, в

Я бы хотел:

1) выявить неисправные узлы (те, что пунктирными синими линиями); то

2) удалите их метку и «заполните» правильным значением

Мой словарный запас на графике слабый; Существуют ли функции networkx, которые могут это сделать?

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

Answer 1

1) Для каждой метки создайте подграф исходного графика, содержащий все узлы с этой меткой (networkx.subgraph).

2) Для каждого подграфа найдите связанные компоненты с помощью networkx.connected_components, который возвращает генератор наборов узлов, по одному для каждого компонента.

3) Для каждого компонента, который не является самым большим компонентом своего класса, найдите соседей каждого узла с помощью networkx.neighbors;определить их метки и назначить наиболее распространенную метку (которая также не является меткой компонента) узлам в этом компоненте.

Эта процедура может потерпеть неудачу, если большие ошибочно помеченные "островки" соседствуют друг с другом, но должны работать для показанного примера.