Anfänger: Graphentheorie

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
KomplexKompliziert
User
Beiträge: 20
Registriert: Freitag 29. Juni 2012, 09:05

Hallo zusammen!
Ich bin kompletter Neuanfänger in Python. Ich möchte mir mittels Adjazenzmatrix/Adjazenzliste einen Graphen grafisch veranschaulichen. Alle Beispiele, die ich bisher gefunden habe, verstehe ich irgendwie nicht, bzw. sind meines Erachtens für mein Problem zu kompliziert. Ich habe einen Graphen mit 4 Knoten und 6 Kanten und habe die Adjazenzliste erstellt:

Code: Alles auswählen

Adjazenzliste ={"A":["A","B","C"],"B":["C"],"C":["D"],"D":["A"]}
Wie kann ich dieses jetzt graphisch veranschaulichen (Länge=Gewichte der Kanten sind erstmal frei wählbar)?

Bin für jede Hilfe dankbar!!
BlackJack

@KomplexKompliziert: `networkx` ist eine Python-Bibliothek um mit Graphen in Python zu arbeiten. Da gibt es IIRC auch verschiedene Backends zur grafischen Darstellung. Eines davon ist GraphViz. Dafür alleine gibt es auch Python-Anbindungen.

Edit: `networkx` verwendet `matplotlib` zum erstellen der Grafik. Kleines Programm um ein Fenster mit dem Graphen anzuzeigen und ohne auf externe Programme wie GraphViz zum platzieren der Knoten zurück zu greifen:

Code: Alles auswählen

import networkx as nx
from matplotlib import pylab


def main():
    graph = nx.Graph({'A': ['A', 'B', 'C'], 'B': ['C'], 'C': ['D'], 'D': ['A']})
    nx.draw(graph)
    pylab.show()
    

if __name__ == '__main__':
    main()
KomplexKompliziert
User
Beiträge: 20
Registriert: Freitag 29. Juni 2012, 09:05

Super vielen Dank! Jetzt bin ich allerdings zu blöd, das Paket networkx zu installieren. Wie geht das denn?
lunar

@KomplexKompliziert: Dokumentation, rechte Seite oben…
BlackJack

@KomplexKompliziert: Also in meinem Fall hat ein simples ``sudo apt-get install python-networkx`` gereicht. ;-)

Keine Ahnung wie weit man mit `easy_install` oder `pip` unter Windows kommt. Es gibt da ja noch `numpy`, `scipy`, und `matplotlib` als Abhängigkeiten. Die Dokumentation hat einen Abschnitt Installing.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Wenn es Dir eher um Graphentheorie an sich geht, kann ich Dir auch Rocs empfehlen. Das ist zwar nur (?) in JavaScript prorammierbar, aber evtl. reicht Dir das ja auch.
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
Benutzeravatar
/me
User
Beiträge: 3561
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

BlackJack hat geschrieben:Keine Ahnung wie weit man mit `easy_install` oder `pip` unter Windows kommt. Es gibt da ja noch `numpy`, `scipy`, und `matplotlib` als Abhängigkeiten. Die Dokumentation hat einen Abschnitt Installing.
Irgendwie geht es. Ich habe hier auf einem Windows-Rechner mit Python 2.7 networkx in der Version 1.7rc1 installiert. Ich weiß nicht mehr wie ich die Installation vorgenommen habe, aber wenn ich das geschafft habe kann es ja nicht so kompliziert sein. :D
KomplexKompliziert
User
Beiträge: 20
Registriert: Freitag 29. Juni 2012, 09:05

Also ich bin wirklich zu doof dazu, ich hab das mal mit diesem französischen Youtube-Video (http://www.youtube.com/watch?v=qXzurFUg7fY) probiert aber bei mir kommt dann immer diese Fehlermeldung:

Code: Alles auswählen

C:\Python27\Scripts>easy_install networkx
Searching for networkx
Reading http://pypi.python.org/simple/networkx/
Download error: [Errno 10060] Ein Verbindungsversuch ist fehlgeschlagen, da die
Gegenstelle nach einer bestimmten Zeitspanne nicht richtig reagiert hat, oder di
e hergestellte Verbindung war fehlerhaft, da der verbundene Host nicht reagiert
hat -- Some packages may not be found!
Couldn't find index page for 'networkx' (maybe misspelled?)
Scanning index of all packages (this may take a while)
Reading http://pypi.python.org/simple/
Download error: [Errno 10060] Ein Verbindungsversuch ist fehlgeschlagen, da die
Gegenstelle nach einer bestimmten Zeitspanne nicht richtig reagiert hat, oder di
e hergestellte Verbindung war fehlerhaft, da der verbundene Host nicht reagiert
hat -- Some packages may not be found!
No local packages or download links found for networkx
Best match: None
Traceback (most recent call last):
  File "C:\Python27\Scripts\easy_install-script.py", line 8, in <module>
    load_entry_point('setuptools==0.6c11', 'console_scripts', 'easy_install')()
  File "C:\Python27\lib\site-packages\setuptools\command\easy_install.py", line
1712, in main
    with_ei_usage(lambda:
  File "C:\Python27\lib\site-packages\setuptools\command\easy_install.py", line
1700, in with_ei_usage
    return f()
  File "C:\Python27\lib\site-packages\setuptools\command\easy_install.py", line
1716, in <lambda>
    distclass=DistributionWithoutHelpCommands, **kw
  File "C:\Python27\lib\distutils\core.py", line 152, in setup
    dist.run_commands()
  File "C:\Python27\lib\distutils\dist.py", line 953, in run_commands
    self.run_command(cmd)
  File "C:\Python27\lib\distutils\dist.py", line 972, in run_command
    cmd_obj.run()
  File "C:\Python27\lib\site-packages\setuptools\command\easy_install.py", line
211, in run
    self.easy_install(spec, not self.no_deps)
  File "C:\Python27\lib\site-packages\setuptools\command\easy_install.py", line
434, in easy_install
    self.local_index
  File "C:\Python27\lib\site-packages\setuptools\package_index.py", line 475, in
 fetch_distribution
    return dist.clone(location=self.download(dist.location, tmpdir))
AttributeError: 'NoneType' object has no attribute 'clone'
Jetzt hab ich noch diesen Link http://networkx.lanl.gov/install.html hier durchgeschaut, aber da verstehe ich schon gar nichts:
1. Ich hab mir das zip-file runter geladen und entpackt
Download the source (tar.gz or zip file).
2. Was muss ich bei "Unpack and change directory to networkx-“version” genau machen?
3. Run “python setup.py install” to build and install. Wo muss ich das ausführen? In der DOS-Konsole (wie im Video) oder in der Python 'Command Line' ?
BlackJack

@KomplexKompliziert: Bei dem `easy_install`-Versuch war ganz offensichtlich `pypi.python.org` nicht erreichbar. Entweder war das gerade down, oder Deine Netzwerkeinstellungen blockieren den Zugriff.
KomplexKompliziert
User
Beiträge: 20
Registriert: Freitag 29. Juni 2012, 09:05

Was müsste ich dann da machen? Ich habe bei Firefox jetzt mal die Seite zugelassen (also unter Einstellungen Ausnahme hinzufügen). Aber das bringt auch nichts und auf die Internetseite komme ich ganz normal. Kann mir jemand entweder erklären, wie ich das mit dem Dos-Fenster hinkriege oder mit dem anderen Weg?
deets

@snafu: Das ist HTTP. Das sollte ja klappen. Was auch immer da schief geht, daran denke ich haengt's nicht.
deets

@KomplexKompliziert

Was du im FireFox machst ist voellig irrelevant fuer die Kommandozeile. Und auf ebenjener musst du im uebrigen auch das "python setup.py install" ausfuehren - recht einfach daran zu erkennen, das der Befehl mit "python" beginnt, oder?
KomplexKompliziert
User
Beiträge: 20
Registriert: Freitag 29. Juni 2012, 09:05

Hab mal Firewall und Virenschutz ausgestellt- funktioniert aber immer noch nicht. Noch ein Vorschlag?
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Nutzt du einen Proxy?
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Antworten