Zeilen in Numpy-Array löschen, die Elemente enthalten, welche bestimmte Kriterien erfüllen

[mcl33]

Hallo zusammen,

ich habe folgendes numpy Array:

Code: Alles auswählen

edge_array =
[[10 11]
 [11 12]
 [12 13]
 [13 14]
 [14 15]
 [15 16]
 [16 22]
 [12 20]
 [20 21]
 [21 22]
 [22 23]
 [23 30]
 [30 31]
 [31 32]
 [32 33]
 [33 34]
 [34 31]
 [31 32]
 [21 40]
 [40 41]
 [41 42]
 [42 23]
 [15 32]

Die Zahlen stellen Knoten in einem Netzwerk dar, jede Zeile im Array ist eine Kante im Netzwerk. Zur Vereinfachung des Netzwerks möchte ich Knoten löschen, die nur Eckpunkte der Kanten oder Endpunkte sind.

Ziel ist es also, in diesem Array die Kanten (Zeilen) zu löschen, in denen Knoten enthalten sind, die im gesamten Array nur ein- oder zweimal vorkommen (z.B. 10, 11, 13, 14, 16 ...). Stattdessen sollen dann Kanten eingefügt werden, welche die gelöschten Kanten ersetzen.
Beispielsweise sollen die Kanten [12,13] , [13,14] und [14,15] gelöscht werden und dafür die Kante [12,15] eingefügt werden.

Problematisch ist auch folgendes Szenario: es würden die Kanten [10,11], [11,12] gelöscht werden, weil sie eine Art Sackgasse darstellen. Dadurch würde aber auch der Knoten 12 nur noch an zwei Kanten angrenzen. Da er aber im ursprünglichen Netz eine Kreuzung darstellt, soll er nicht gelöscht werden! Es muss sich beim Löschen also immer auf das Ausgangsnetzwerk bezogen werden.

Als totaler Python-Neuling habe ich hiermit meine Probleme. Vielleicht könnte man irgendwie mit edge_array.flat über das Array iterieren, dann mit np.sum die Knoten zählen und mit np.delete gewisse Zeilen löschen. Aber ich habe auch in der Numpydokumentation gelesen, dass man in einigen fällen mit nditer iteriert.

Das ganze soll dann natürlich auf größere Netzwerke anwendbar sein, der Einfachheit halber ist dies nur ein kleines Beispielhaftes Netzwerk.

Kann jemand weiterhelfen?

Danke, Michael

[pillmuncher]

In Python 3.4, aber ohne numpy:

Code: Alles auswählen

from collections import defaultdict
from pprint import pprint

def make_graph(edges):
    graph = defaultdict(set)
    for a, b in edges:
        graph[a].add(b)
        graph[b].add(a)
    return dict(graph)

def main():

    edges = [
        [10, 11],
        [11, 12],
        [12, 13],
        [13, 14],
        [14, 15],
        [15, 16],
        [16, 22],
        [12, 20],
        [20, 21],
        [21, 22],
        [22, 23],
        [23, 30],
        [30, 31],
        [31, 32],
        [32, 33],
        [33, 34],
        [34, 31],
        [31, 32],
        [21, 40],
        [40, 41],
        [41, 42],
        [42, 23],
        [15, 32],
    ]

    graph = make_graph(edges)
    three_nodes = {node for node, nodes in graph.items() if len(nodes) >= 3}

    def three_node_edges(nodes, seen):
        for n in nodes - seen:
            if n in three_nodes:
                yield n
            else:
                yield from three_node_edges(graph[n], seen | set([n]))

    result = {
        node: set(three_node_edges(graph[node], set([node])))
        for node in three_nodes
    }
    pprint(result)

    print()
    result_edges = sorted(set(
        tuple(sorted((k1, k2))) for k1, ns in result.items() for k2 in ns
    ))
    pprint(result_edges)

if __name__ == '__main__':
    main()

Ergebnis:

Code: Alles auswählen

{12: {21, 15},
 15: {32, 12, 22},
 21: {12, 22, 23},
 22: {23, 21, 15},
 23: {21, 22, 31},
 31: {32, 23},
 32: {31, 15}}

[(12, 15),
 (12, 21),
 (15, 22),
 (15, 32),
 (21, 22),
 (21, 23),
 (22, 23),
 (23, 31),
 (31, 32)]

Bitte Meldung geben, falls Fragen auftauchen.

[pillmuncher]

Es wird ca. doppelt so schnell, wenn man in der Zeile 41 das hier einfügt:

Code: Alles auswählen

# @admins: wenn hier nichts steht, macht die Codebox ein left trim und die Einrückung geht kaputt...
    seen = set()
    for node in three_nodes:
        graph[node] -= seen
        seen |= graph[node]
        seen.add(node)

[pillmuncher]

@mcl33: Noch eine Lösung. Diesmal ohne Rekursion, dafür mit verbundenen Komponenten und Mengenoperationen.

Code: Alles auswählen

from collections import defaultdict
from pprint import pprint

def make_graph(edges):
    graph = defaultdict(set)
    for a, b in edges:
        graph[a].add(b)
        graph[b].add(a)
    return dict(graph)

def connected_components(neighbors):
    seen = set()
    def component(node):
        nodes = set([node])
        while nodes:
            node = nodes.pop()
            seen.add(node)
            nodes |= neighbors[node] - seen
            yield node
    for node in neighbors:
        if node not in seen:
            yield component(node)

def main():

    edges = [
        [10, 11],
        [11, 12],
        [12, 13],
        [13, 14],
        [14, 15],
        [15, 16],
        [16, 22],
        [12, 20],
        [20, 21],
        [21, 22],
        [22, 23],
        [23, 30],
        [30, 31],
        [31, 32],
        [32, 33],
        [33, 34],
        [34, 31],
        [31, 32],
        [21, 40],
        [40, 41],
        [41, 42],
        [42, 23],
        [15, 32],
    ]

    graph = make_graph(edges)

    keep = {}
    lose = {}
    for node, neighbors in graph.items():
        if len(neighbors) >= 3:
            keep[node] = neighbors
        else:
            lose[node] = neighbors

    link = {node: neighbors - lose.keys() for node, neighbors in lose.items()}
    lose = {node: neighbors - keep.keys() for node, neighbors in lose.items()}
    keep = {node: neighbors - lose.keys() for node, neighbors in keep.items()}

    for component in connected_components(lose):
        kept = set(node for each in component for node in link[each])
        for node in kept:
            keep[node].update(kept)
            keep[node].remove(node)

    pprint(keep)

    print()
    keep_edges = sorted(set(
        tuple(sorted((k1, k2))) for k1, ns in keep.items() for k2 in ns
    ))
    pprint(keep_edges)


if __name__ == '__main__':
    main()

[pillmuncher]

@mcl33: Weiteres Nachdenken hat mich darauf gebracht, dass kept In Zeile 67 immer nur an Sets mit entweder einem oder zwei Elementen gebunden wird. Zwei Elemente bedeutet, dass es einen Pfad zwischen diesen Elementen gibt. Ein Element bedeutet, dass es einen Pfad von einem Dreier-Knoten zu einem Endknoten gibt, der logischerweise dann kein Dreier-Knoten sein kann, weshalb man diesen Fall igorieren kann. Man kann die Zeilen 68-70 also durch das folgende ersetzen:

Code: Alles auswählen

#
        try:
            a, b = kept
        except ValueError:
            pass
        else:
            keep[a].add(b)
            keep[b].add(a)

[snafu]

@pillmuncher
Was spricht gegen ein ``if len(kept) == 2``?

[pillmuncher]

@pillmuncher
Was spricht gegen ein ``if len(kept) == 2``?

Hatte ich zuerst, aber dann fiel mir EAFP ein. Andererseits entspricht ein direkter Test wohl mehr dem "Explicit is better than implicit." Ich widerrufe also und propagiere statt dessen:

Code: Alles auswählen

#
            if len(kept) == 2:
                a, b = kept
                keep[a].add(b)
                keep[b].add(a)

[DasIch]

Die Variante ohne len() funktioniert auch wenn kept kein __len__ hat, also z.B. bei Iteratoren oder Generatoren.

[kbr]

Habe die Aufgabe einmal mit Node-Klassen umgesetzt. Der Aufbau der Datenstruktur ist etwas teuerer, dafür läuft es anschließend aber recht flott.

Code: Alles auswählen

import time
import pprint

edges = [
    [10, 11],
    [11, 12],
    [12, 13],
    [13, 14],
    [14, 15],
    [15, 16],
    [16, 22],
    [12, 20],
    [20, 21],
    [21, 22],
    [22, 23],
    [23, 30],
    [30, 31],
    [31, 32],
    [32, 33],
    [33, 34],
    [34, 31],
    [31, 32],
    [21, 40],
    [40, 41],
    [41, 42],
    [42, 23],
    [15, 32],
]

class Node(object):

    def __init__(self, id):
        self.id = id
        self.edges = 0
        self.nodes = set()
        self.walked = False

    def __str__(self):
        return "%s: %s" % (self.id, [node.id for node in self.nodes])

    def connect_threenodes(self, lessnodes):
        new_nodes = {n for n in (node.get_next_threenode(self, self) for node in self.nodes) if n}
        self.nodes -= lessnodes
        self.nodes |= new_nodes

    def get_next_threenode(self, start_node, previous_node):
        if not self.walked:
            if self.edges >= 3:
                self.nodes.add(start_node)
                return self
            self.walked = True
            for node in self.nodes:
                if not node is previous_node:
                    result = node.get_next_threenode(start_node, self)
                    if result:
                        return result
        return None


def make_node_graph(edges):
    d = {}
    for source_id, target_id in edges:
        for id in (source_id, target_id):
            if not id in d:
                d[id] = Node(id)
        d[source_id].nodes.add(d[target_id])
        d[target_id].nodes.add(d[source_id])
    nodes = set(d.values())
    for node in nodes:
        node.edges = len(node.nodes)
    return nodes


def process_node_graph(nodes):
    threenodes = {node for node in nodes if node.edges >= 3}
    lessnodes = nodes - threenodes
    for node in threenodes:
        node.connect_threenodes(lessnodes)
    return threenodes


def main():
    t1 = time.time()
    nodes = make_node_graph(edges)
    tt1 = time.time() - t1
    t2 = time.time()
    processed_nodes = process_node_graph(nodes)
    tt2 = time.time() - t2
    print(sorted((node.id, node.edges) for node in nodes))
    for node in processed_nodes:
        print(node)
    print('make_node_graph   : %s sec' % tt1)
    print('process_node_graph: %s sec' % tt2)

if __name__ == '__main__':
    main()

[snafu]

Die Variante ohne len() funktioniert auch wenn kept kein __len__ hat, also z.B. bei Iteratoren oder Generatoren.

Das ist schon klar. Der OP hat aber die zu bearbeitende Datenstruktur gezeigt und dort handelt es sich um Listen.

Rein theoretisch kann immer alles mögliche passieren. Ich bevorzuge jedoch den lesbaren Weg. Dann kracht es eben bei unsinnigen Eingaben. Und dass man einen Graphen mit Iteratoren modellieren möchte, ist IMHO so ein unsinniger Fall.

[pillmuncher]

Der OP hat aber die zu bearbeitende Datenstruktur gezeigt und dort handelt es sich um Listen.

Was mich dabei wundert, ist dass der OP geschrieben hat, es würde sich um ein numpy Array handeln. Mit numpy kenne ich mich nicht besonders aus, aber wenn man networkx dazunimmt, ginge evtl. sowas:

Code: Alles auswählen

import networkx as nx
import numpy as np
import scipy.sparse as sp

def main():

    edges = np.array([
        [10, 11],
        [11, 12],
        [12, 13],
        [13, 14],
        [14, 15],
        [15, 16],
        [16, 22],
        [12, 20],
        [20, 21],
        [21, 22],
        [22, 23],
        [23, 30],
        [30, 31],
        [31, 32],
        [32, 33],
        [33, 34],
        [34, 31],
        [31, 32],
        [21, 40],
        [40, 41],
        [41, 42],
        [42, 23],
        [15, 32],
    ])

    matrix = sp.coo_matrix((np.ones(len(edges)), edges.T)).tocsr()
    graph = nx.from_scipy_sparse_matrix(matrix)
    g2 = graph.copy()
    g3 = graph.copy()
    g2.remove_nodes_from(n for n, d in graph.degree_iter() if d != 2)
    g3.remove_nodes_from(n for n, d in graph.degree_iter() if d < 3)
    for component in nx.connected_components(g2):
        nodes = set(
            node
            for each in component
            for node in nx.all_neighbors(graph, each)
            if node in g3
        )
        if len(nodes) == 2:
            g3.add_edge(*nodes)

    pprint(sorted(sorted(edge) for edge in g3.edges()))

if __name__ == '__main__':
    main()

Ergebnis:

Code: Alles auswählen

[[12, 15],
 [12, 21],
 [15, 22],
 [15, 32],
 [21, 22],
 [21, 23],
 [22, 23],
 [23, 31],
 [31, 32]]

[pillmuncher]

Meh. Die Zeilen 35-45 kann man kürzer formulieren:

Code: Alles auswählen

#
    g2 = graph.subgraph(n for n, d in graph.degree_iter() if d == 2)
    g3 = graph.subgraph(n for n, d in graph.degree_iter() if d >= 3)
    for ns in nx.connected_components(g2):
        nodes = set(m for n in ns for m in nx.all_neighbors(graph, n))
        nodes = nodes.intersection(g3.nodes())

[kbr]

Ich hätte jetzt vermutet, dass die networkx-Lösung schneller läuft als meine handgeschriebene Node-Klasse. Aber das Gegenteil ist der Fall. Vermutlich rechnet sich bei dem gegebenen Beispiel der damit verbundene Overhead noch nicht. Hier sind die Profile-Ergebnisse:

class Node:
225 function calls (214 primitive calls) in 0.001 seconds

networkx etc:
84864 function calls (82447 primitive calls) in 0.267 seconds
kürzere Variante:
79760 function calls (78195 primitive calls) in 0.258 second

[mcl33]

Hallo zusammen,

entschuldigt bitte die späte Antwort, ich war zwei Wochen abwesend. Danke aber für den Input, ich werde mir das mal in Ruhe anschauen und ggf. weiter Fragen stellen
Vielen, vielen Dank auf jeden Fall für eure Mühe!

Michael