networkx und Zeichenkodierung

[nezzcarth]

Hallo

ich bastel gerade ein wenig mit networkx herum, und versuche mittels der Funktion read_gml eine gml Datei (die ich zuvor aus einer dot/graphivz Datei per gv2gml gewonnen habe) zu lesen. Dabei tritt folgender Fehler auf:

(python 3.4; networkx 1.9-1)

Code: Alles auswählen

Traceback (most recent call last):
  File "./nx_test.py", line 37, in <module>
    main()
  File "./nx_test.py", line 31, in main
    tmp = nx.read_gml('./ha.gml')
  File "<string>", line 2, in read_gml
  File "/usr/lib/python3.4/site-packages/networkx/utils/decorators.py", line 220, in _open_file
    result = func(*new_args, **kwargs)
  File "/usr/lib/python3.4/site-packages/networkx/readwrite/gml.py", line 125, in read_gml
    G = parse_gml(lines, relabel=relabel)
  File "/usr/lib/python3.4/site-packages/networkx/readwrite/gml.py", line 174, in parse_gml
    data = "".join(lines)
  File "/usr/lib/python3.4/site-packages/networkx/readwrite/gml.py", line 124, in <genexpr>
    lines = (unescape(line.decode('ascii')) for line in path)
UnicodeDecodeError: 'ascii' codec can't decode byte 0xc3 in position 29: ordinal not in range(128)

Der Aufruf erfolgt einfach nur durch folgende Zeile:

Code: Alles auswählen

tmp = nx.read_gml('./ha.gml')

Das Problem ist wohl, dass die GML diverse Sonderzeichen enthält, die Funktion 'read_gml' aber inhärent auf ascii ausgerichtet ist. Habe ich irgendeine Chance, diese Funktion zu verwenden, ohne auf die Sonderzeichen verzichten zu müssen?

Vielen Dank für's lesen

[Hellstorm]

Also so wie das dort geschrieben steht (The GML specification says that files should be ASCII encoded, with any extended ASCII characters (iso8859-1) appearing as HTML character entities) scheint das Problem ja eher deine GML-Datei zu sein, die dann nicht standardmäßig ist (Wer auch immer sich sowas ausdenkt, haben wir 1970...?).

Kannst du dir nicht ein separates Skript schreiben, welches die GML-Datei einliest und alle Nicht-ASCII-Zeichen in HTML escaped?

Ansonsten ist ja das Problem schon im Quellcode:

Code: Alles auswählen

lines = (unescape(line.decode('ascii')) for line in path)

D.h. da wird ja alles außer ASCII verworfen. Du könntest das natürlich verändern (ascii nach utf-8 oder iso-8859-1 ersetzen), aber wer weiß, an welchen anderen Stellen das noch Probleme gibt. Deswegen würde ich eher die GML-Datei konvertieren.

[nezzcarth]

Danke für die Antwort. Dass alles außer ASCII verworfen wird, hatte ich versucht in meiner Nachricht mit 'inhärent auf ascii' ausgerichtet, und der Verlinkung auf den Source zum Ausdruck zu bringen Meine Hoffnung war, dass jemand vielleicht einen Tipp weiß, mit dem man das umgehen kann.

Das mit dem Escapen wollte ich eigentlich vermeiden, hab's aber dann gemacht. Nun beschwert er sich allerdings, dass es kein 'unichr' gibt; scheinbar ist das Paket also noch nicht ganz python 3 kompatibel :/

Ich sollte also wohl von GML Abstand nehmen und mir ein anderes Format suchen, scheint mir ...

[Hellstorm]

Danke für die Antwort. Dass alles außer ASCII verworfen wird, hatte ich versucht in meiner Nachricht mit 'inhärent auf ascii' ausgerichtet, und der Verlinkung auf den Source zum Ausdruck zu bringen Meine Hoffnung war, dass jemand vielleicht einen Tipp weiß, mit dem man das umgehen kann.

Hatte das schon verstanden, aber mir kam es halt so vor, als ob das zu tief darin verankert ist. Ansonsten versuch doch mal den Quelltext von Networkx zu verändern, wie ich das geschrieben habe. Entweder funktioniert es oder nicht.

[BlackJack]

@Hellstorm: Wir haben nicht die 70er aber mit GML ein Format das Mitte der 90er entstanden ist. Und dafür halte ich ASCII-only für nicht so ungewöhnlich und das HTML-Named-Entities für ISO-8859-1-Zeichen vorgesehen wurden, sogar für ziemlich Fortschrittlich.

Das Problem sehe ich jedenfalls nicht bei NetworkX sondern beim Programm das diese Dateien erzeugt hat. Die entsprechen ganz offensichtlich nicht der Spezifikation.

[nezzcarth]

@BlackJack:
Danke auch für deine Einschätzung.

Code: Alles auswählen

Traceback (most recent call last):
  File "./nx_test.py", line 38, in <module>
    main()
  File "./nx_test.py", line 32, in main
    tmp = nx.read_gml('./ha.gml')
  File "<string>", line 2, in read_gml
  File "/usr/lib/python3.4/site-packages/networkx/utils/decorators.py", line 220, in _open_file
    result = func(*new_args, **kwargs)
  File "/usr/lib/python3.4/site-packages/networkx/readwrite/gml.py", line 125, in read_gml
    G = parse_gml(lines, relabel=relabel)
  File "/usr/lib/python3.4/site-packages/networkx/readwrite/gml.py", line 174, in parse_gml
    data = "".join(lines)
  File "/usr/lib/python3.4/site-packages/networkx/readwrite/gml.py", line 124, in <genexpr>
    lines = (unescape(line.decode('ascii')) for line in path)
  File "/usr/lib/python3.4/site-packages/networkx/readwrite/gml.py", line 79, in unescape
    return re.sub("&#?\w+;", fixup, text)
  File "/usr/lib/python3.4/re.py", line 175, in sub
    return _compile(pattern, flags).sub(repl, string, count)
  File "/usr/lib/python3.4/site-packages/networkx/readwrite/gml.py", line 75, in fixup
    text = unichr(htmlentitydefs.name2codepoint[text[1:-1]])
NameError: name 'unichr' is not defined

Das liegt deiner Ansicht nach auch eher an der Eingabe-Datei? Dachte halt, weil sich da über unichr beschwert wird, dass es irgendein python 3-bezogenes Problem sein könnte.

Ich denke, ich werde dem ganzen noch mal auf den Zahn fühlen. Die Ausgangsdatei habe ich in Dot per Hand erstellt, weil ich mit dem Format am vertrautestens bin; mit Dateiformaten für Graphen habe ich mich vorher noch nie befasst und kann daher noch nicht gut einschätzen, was man da nimmt (dürfte auch Anwendungszweck bezogen sein). Entsprechend hatte ich dann geschaut, welche Konverter es für Formate, die networkx als Austauschformate führt, gibt (read_dot habe ich ebenfalls entdeckt, aber wegen der Abhängigkeit von pygraphviz kann ich das unter Python 3 nicht verwenden). Dann habe ich es mit gv2gml aus dem Graphviz-Paket nach gml konvertiert. Am naheliegendsten dürfte wohl sein, dass ich irgendwo in der Ausgangsdatei geschlampt habe (leider hat gv2gml sich auch nicht beschwert, sodass ich das hätte merken können).

Danke jedenfalls für eure Antworten

[BlackJack]

@nezzcarth: `unichr()` ist eindeutig ein Problem von NetworkX. Die Funktion gibt es in Python 3 nicht mehr, bzw. heisst sie dort `chr()`, denn das alte `chr()` aus Python 2 macht keinen Sinn mehr wenn Zeichenketten grundsätzlich Unicode sind. Könnte man bei NetworkX als Bug melden wenn das in den aktuellen Quelltext noch so drin steht.

Bei meinem Graphviz ist gar kein gv2gml dabei, dafür aber ein gv2gxl. Ist ja interessant.

[nezzcarth]

@nezzcarth: `unichr()` ist eindeutig ein Problem von NetworkX. Die Funktion gibt es in Python 3 nicht mehr, bzw. heisst sie dort `chr()`, denn das alte `chr()` aus Python 2 macht keinen Sinn mehr wenn Zeichenketten grundsätzlich Unicode sind. Könnte man bei NetworkX als Bug melden wenn das in den aktuellen Quelltext noch so drin steht.

Bei meinem Graphviz ist gar kein gv2gml dabei, dafür aber ein gv2gxl. Ist ja interessant.

@BlackJack:
Sieht ganz danach aus, als wäre das noch in drin: https://github.com/networkx/networkx/bl ... .py#L67-75
Da ich das Paket allerdings gerade erst heute getestet hab' und mich evtl. nicht gut genug auskenne, um das einschätzen zu können, trau' ich mich noch nicht recht, das zu melden

gv2gxl ist in "meinem" GraphViz auch enthalten, leider versteht NetworkX dieses Format nicht

[nezzcarth]

Ich hab' die Ausgangsdatei nun mit Unterstützung einiger regulärer Ausdrücke in's GEXF-Format konvertiert. So kann NetworkX sie zumindest schon mal lesen, und ich habe die Möglichkeit, das ggf. in ein anderes Format zu überführen. Generell erscheint mir aber die Fülle von Formaten, um Graphen zu speichern etwas unübersichtlich. Ich habe (für eine Art Spiel/Simulation) einen ungerichteten Graph. Ich würde gerne sowohl zu Knoten, als auch zu Kanten gerne ergänzende Daten hinterlegen (Bezeichner, falls möglich auch Spezifizierung von verschiedenen Typen von Knoten und Kanten, um das im Programm zu verwenden. Manche Formate scheinen auch Informationen zur grafischen Darstellung speichern zu können; das ist für mich aber völlig irrelevant). Kann man da irgendein Format, das NetworkX versteht empfehlen?

[BlackJack]

@nezzcarth: Ich würde da eher von deinem Programm ausgehen wie das diese Daten speichern soll, beziehungsweise wie das den Graphen intern repräsentiert. Daraus kannst Du dann ja einen Graphen mit NetworkX erstellen.

[nezzcarth]

@nezzcarth: Ich würde da eher von deinem Programm ausgehen wie das diese Daten speichern soll, beziehungsweise wie das den Graphen intern repräsentiert. Daraus kannst Du dann ja einen Graphen mit NetworkX erstellen.

Möglicherweise habe ich das noch richtig durchdrungen, und sehe das etwas zu einfach. Im Prinzip geht es darum, dass ich versuche sowas ähnliches wie eine Landkarte darzustellen, wobei jeder Knoten ein "Land" und jede Kante eine "Grenze" ist. Diese möchte ich extern einlesen (damit sie austauschbar ist), um dann damit mit meinem Programm zu arbeiten. Entsprechend hatte ich gedacht, dass ich als Repräsentation eben ein Graph-Objekt des NetworkX Moduls nehme, um dann z.B. Routen und sowas zu berechnen. Aber vielleicht habe ich das Paket bisher auch noch nicht richtig verstanden; ich werde mir deinen Einwand noch mal durch den Kopf gehen lassen

[BlackJack]

@nezzcarth: Man kann als Knoten jedes Objekt verwenden das sich auch als Schlüssel in Wörterbüchern verwenden lässt, und man kann beliebige Objekte als Werte an Kanten anfügen. Die Dokumentation dazu: What to use as nodes and edges.

Das heisst wenn Du in Deiner Anwendung einen Datentyp hast der ein Land repräsentiert und der als Schlüssel in Wörterbüchern verwendbar ist, dann kann man direkt diese Länder-Objekte verwenden. Und falls Grenzen/Grenzübergänge auch als Objekte dargestellt werden, dann kannst Du diese Objekte an die Kanten ”heften”.

[nezzcarth]

@BlackJack:
Ich habe das Probelm, dass ich versuche einen (optionalen) Regelmechanismus eines Rollenspielsystems umzusetzen, der den Preis und die Verfügbarkeit von Produkten regelt; ich möchte ungern den Boardbetreiber in die Situation bringen, sich mit irgendwelchen Urheberrechtskram auseinandersetzen zu müssenn und daher auf eine zu detailierte Beschreibung verzichten.

Im Prinzip funktioniert es so, dass die Spielwelt in verschiedene Handelszonen unterteilt wird, denen Waren, die dort produziert werden zugeordnet sind. Der Preis und die Verfügbarkeit eines Produkts in einer anderen als der Herstellungszone berechnet sich dann anhand der Anzahl der Grenzübetritte vom Herstellungs- zum Verkaufsort (wobei Handelszonen verschiedene Merkmale zugeordnet werden, die noch mal Einflüsse haben, etwa, ob es sich um ein Land oder Meergebiet handelt und der Transport daher mit verschiedenen Fahrzeugen erfolgen muss; da weiß ich zum Beispiel nicht, ob ich das an die Handelszonen "heften" soll, oder an die Grenzen.). Meine Überlegung war, dass man soetwas mit einem Graphen gut abbilden kann; liege ich richtig? Ich habe gedacht, dass ich den Graph, der die Handelszonen und die Grenzen zwischen ihnen vorhält extern in irgendeinem geeigneten Format ablege. Fraglich wäre dann eben, ob ich die ganzen Zusatzinformationen auch in dieselbe Datei stecke, oder in eine zweite. Die Waren würde ich erst mal weglassen wollen, aber in einer eventuellen weiteren Ausbaustufe müssten die ja auch irgendwo abgelegt werden.

Ich dachte, dass ich als Knoten einen String nehme, der ein Kürzel für die jeweilige Zone ist, und die weiteren Informationen in den Attributen diesen Knoten ablege. Ich bin leider in solchen Designfragen oft etwas unschlüssig. Falls jemand einen anderen Vorschlag hat, nehme ich den gerne an.

[nezzcarth]

Nun habe ich mal versucht, die Daten in JSON abzulegen. Zu Test-/Illustrationszwecken habe statt der 'Original'-Daten die Nordsee-Region genommen. Das sieht so aus:

Code: Alles auswählen

{
    "BEL": {
        "LABEL": "Belgien",
        "BORDERS": ["DEU", "FRA", "NLD", "NS"],
        "SEA": false
        },  
    
    "DEU": {
        "LABEL": "Deutschland",
        "BORDERS": ["DNK", "NLD", "NS"],
        "SEA": false
    },
    
    "DNK": {
        "LABEL": "Dänemark",
        "BORDERS": ["DEU", "NS"],
        "SEA": false
    },
    
    "FRA": {
        "LABEL": "Frankreich",
        "BORDERS": ["BEL", "DEU", "NS"],
        "SEA": false
    },
    
    "GBR": {
        "LABEL": "Großbritannien",
        "BORDERS": ["NS"],
        "SEA": false
    },
    
    "NLD": {
        "LABEL": "Niederlande",
        "BORDERS": ["DEU", "NS"],
        "SEA": false
    },
    
    "NOR": {
        "LABEL": "Norwegen",
        "BORDERS": ["NS"],
        "SEA": false
    },
    
    "NS" : {
        "LABEL": "Nordsee",
        "BORDERS": ["DNK", "DEU", "NLD"],
        "SEA": true
    }
}

Die Funktion die die Daten einliest und in einem Graph-Objekt ablegt, sieht so aus

(python 3.4)

Code: Alles auswählen

def read_trade_zone_file(file_name):
    try:
        with open(file_name, 'r') as f:
            try:
                tz_tmp = json.load(f)
            except ValueError:
                print("'{}' is no valid JSON file.".format(file_name))
                sys.exit(1)
    except FileNotFoundError:
        print("File '{}' not found.".format(file_name))
        sys.exit(1)
    trade_zones = nx.Graph()
    trade_zones.add_nodes_from(tz_tmp.items())
    for trade_zone in trade_zones.nodes():
        for border in trade_zones.node[trade_zone]['BORDERS']:
            sea = trade_zones.node[trade_zone]['SEA'] or trade_zones.node[border]['SEA']
            trade_zones.add_edge(trade_zone, border, SEA=sea)
    return trade_zones

Allerdings bin ich mir noch immer unsicher, ob man das so machen sollte; insb. verschachtelte Dictionaries finde ich ja eigentlich nicht so nett.
Gibt es da einen eleganteren Weg?

[nezzcarth]

Ich habe den oben gewählten Ansatz bisher im wesentlichen weiter verfolgt. Im Prinzip geht es ja darum die günstigste Route zwischen zwei Knoten zu finden. Da sich aber nicht alle Faktoren, die da hinein spielen implementieren lassen, gebe ich die günstigste(n) aus, sowie alle weiteren, die maximal eine Kante mehr enthalten (evtl. finde ich noch ein Modell nachdem man diesen Wert berechnen könnte, statt ihn einfach fix auf 1 zu setzen). Die "Günstigkeit" bemisst sich an einem möglichst geringen Preis (für jeden Grenzübertritt wird, abhängig von einigen Faktoren ein prozentualer Aufschlag errechnet) und einer möglich hohen Verbreitung (die für jeden Grenzübertritt sinkt, für See- und Landgrenzen jeweils unterschiedlich). Ich dachte mir, dass ich dies durch einen gewichteten Graphen ausdrücken kann.

Mein Problem ist, dass ich zwei "Metriken" habe, die sich auch noch umgekehrt verhalten (das eine sollte maximiert, das andere minimiert werden) und nicht weiß, wie ich das in einem einzelnen Wert, den ich als Kantengewicht verwende, erfassen kann. Hat da Jemand eine Idee? Bin für jede Antwort dankbar

(Ein Ansatz wäre ja, zwei verschiedene Werte zu nehmen und von diesen dann einfach das arithmetische Mittel zu bilden; aber ich bin unsicher, ob man das mathematisch "erlaubt" (im Sinne von sinnvoll) ist und man da nicht mehr berücksichtigen müsste)