¿Cómo puedo agrupar puntos que están conectados en MATLAB?

graph connect

Question

Imagina que tenemos muchos puntos que algunos de ellos están conectados y queremos agruparlos.

Por favor, eche un vistazo a la siguiente figura.

Si tenemos la " matriz de conectividad " de puntos, ¿cómo podemos agruparlos en dos grupos (grupos de puntos conectados)?

ConnectivityMatrix=
                    [1 2
                     1 3
                     2 4
                     2 3
                     2 1
                     3 1
                     3 2
                     3 4
                     4 3
                     4 2
                     5 8
                     5 7
                     5 6
                     6 5
                     6 7
                     7 6
                     7 5
                     7 8
                     8 7
                     8 5]

El resultado final debe ser nodos de 1,2,3,4 en un primer grupo (grupo) y nodos de 5,6,7,8 en un segundo grupo (grupo).

Answer 1

Aquí hay un código para comenzar. Básicamente implementé Depth First Search ... una implementación muy cruda de todos modos.

La primera búsqueda de profundidad es un algoritmo que se utiliza para el cruce de árboles. Los gráficos son esencialmente un caso especial de árboles donde hay nodos de hojas que se conectan a la raíz. El algoritmo básico para la primera búsqueda de profundidad es el siguiente:

• Comienza en la raíz del árbol y agrégalo a una pila
• Para cada nodo que esté conectado a la raíz, agréguelo a la pila y colóquelo en una lista de nodos visitados
• Mientras todavía hay un nodo en la pila ...
  1. Saca un nodo de la pila
  2. Verifique la lista de nodos visitados. Si este es un nodo que ya hemos visitado, omita.
  3. De lo contrario, visite los nodos que están conectados a este nodo que quitamos y agregamos a la pila

Si hemos desconectado gráficos como los anteriores, básicamente ejecutamos la búsqueda de profundidad primero varias veces. Cada vez será para un grupo. Después de un primer resultado de Búsqueda de profundidad, descubriremos nodos que pertenecen a un clúster. Reiniciamos la Búsqueda inicial de profundidad nuevamente con cualquier nodo que aún no hayamos tocado, que será un nodo de otro clúster que no hayamos visitado. Como claramente tiene dos grupos en su estructura de gráficos, tendremos que ejecutar primero la búsqueda de profundidad dos veces. Esto se conoce comúnmente como encontrar todos los componentes conectados en un gráfico general .

Para encontrar los componentes conectados, estos son los pasos que hice:

1. Crear una matriz de conectividad
2. Inicialice una lista booleana que nos indique si hemos visitado o no un nodo en su gráfico
3. Inicializa una lista de clústeres vacía
4. Inicializa una pila vacía que contiene los nodos que deberíamos visitar.
5. Si bien hay al menos un nodo, debemos visitar ...
   • Encuentra tal nodo
   • Inicializa nuestra pila para contener este nodo
   • Si bien nuestra pila no está vacía
     1. Pop off un nodo de la pila
     2. Si hemos visitado este nodo, continuemos
     3. Otra marca como visitada
     4. Recuperar todos los nodos conectados a este nodo
     5. Elimine los nodos que no están en la pila en (4)
     6. Agregue estos nodos a la pila y la lista de clústeres
6. Una vez que la pila está vacía, tenemos una lista de todos los nodos contenidos en un solo clúster. Agregue este clúster a una lista final.
7. Repita del 1 al 6 hasta que visitemos todos los nodos

Sin más preámbulos, este es el código. Tenga en cuenta que esto no se prueba en batalla. Si tiene estructuras de gráficos que generarán un error, eso será suficiente para solucionarlo :)

ConnectivityMatrix = [1 2
                     1 3
                     2 4
                     2 3
                     2 1
                     3 1
                     3 2
                     3 4
                     4 3
                     4 2
                     5 8
                     5 7
                     5 6
                     6 5
                     6 7
                     7 6
                     7 5
                     7 8
                     8 7
                     8 5];

%// Find all possible node IDs
nodeIDs = unique(ConnectivityMatrix(:));

%// Flag that tells us if there are any nodes we should visit
nodeIDList = false(1,numel(nodeIDs));

%// Stores our list of clusters
clusterList = {};

%// Keeps track of how many clusters we have
counter = 1;

%// Stack - initialize to empty
stackNodes = [];

%// While there is at least one node we need to visit
while (~all(nodeIDList))    
    % Find any node
    stackNodes = find(nodeIDList == false, 1);
    % Initialize our stack to contain this node
    nodesCluster = stackNodes;

    %// While our stack is not empty
    while (~isempty(stackNodes))
        % Grab the node off the stack and pop off
        node = stackNodes(end);
        stackNodes(end) = [];        

        %// If we have marked this node as visited, skip
        if (nodeIDList(node))
            continue;
        end

        %// Mark as visited 
        nodeIDList(node) = true;

        %// Retrieve all nodes connected to this node
        connectedNodes = ConnectivityMatrix(ConnectivityMatrix(:,1) == node, :);
        nodesToVisit = unique(connectedNodes(:,2).'');

        %// Remove those already visited
        visitedNodes = ~nodeIDList(nodesToVisit);
        finalNodesToVisit = nodesToVisit(visitedNodes);

        %// Add to cluster
        nodesCluster = unique([nodesCluster finalNodesToVisit]);

        %// Add to stack
        stackNodes = unique([stackNodes finalNodesToVisit]);                
    end

    %// Add connected components to its own cluster
    clusterList{counter} = nodesCluster;
    counter = counter + 1;
end

Una vez que hemos ejecutado este código, podemos mostrar nuestros clústeres de esta manera:

celldisp(clusterList)

clusterList{1} =

 1     2     3     4


clusterList{2} =

 5     6     7     8

Como tal, el cluster # 1 contiene los nodos 1,2,3,4, mientras que el cluster # 2 contiene los nodos 5,6,7,8.

Tenga en cuenta que este código solo funcionará si etiqueta secuencialmente sus nodos como lo hizo en su diagrama. No puede omitir ningún número de etiqueta (es decir, no puede hacer 1,2,4,6,9, etc. Esto debería ser 1,2,3,4,5).

¡Buena suerte!

Answer 2

Puede usar comandos de Matlab "listos para usar" para este problema. Por ejemplo, puede usar graphconncomp .

Answer 3

La respuesta de rayryeng es bastante buena . Sin embargo, aquí hay algunos detalles que me gustaría señalar:

• " numel(nodeIDs) " generaría posibles errores si la etiqueta de su nodo no es secuencial (es decir, tiene 10 nodos y la etiqueta de nodo máxima es 20). Podría cambiar " numel(nodeIDs) " a " max(nodeIDs) o un valor mayor".

• También creo que el siguiente código traerá algunos problemas (es decir, faltan algunos nodos y se convierten en nodos aislados) cuando se utiliza esta función:

  connectedNodes = ConnectivityMatrix(ConnectivityMatrix(:,1) == node, :);
  nodesToVisit = unique(connectedNodes(:,2).'');

  Modifiqué las dos líneas simples con el siguiente código desordenado:

  connectedNodes1 = ConnectivityMatrix (ConnectivityMatrix (:,1) == node, :);
  connectedNodes2 = ConnectivityMatrix (ConnectivityMatrix (:,2) == node, :);
  AC=connectedNodes1(:,2).'';
  AD=connectedNodes2(:,1).'';
  ACA=reshape(AC,[],1);
  ADA=reshape(AD,[],1);
  AE= [ACA; ADA] ;
  AEA=reshape(AE,[],1);
  AEA=AEA'';
  nodesToVisit = unique(AEA);

  Después de modificar estos dos puntos, no hay problemas con el código inicial de rayryeng.