Wat is die mees doeltreffende grafiek datastruktuur in Python? [Gesluit]

Question

Ek moet in staat wees om 'n groot (10 ^ 7 knope) grafiek manipuleer in python. Die data wat ooreenstem met elke node / rand is minimaal, sê, 'n klein aantal snare. Wat is die mees doeltreffende, in terme van geheue en spoed , manier om dit te doen?

'n dict van dicts is meer buigsaam en makliker om te implementeer, maar ek intuïtief verwag 'n lys van lyste vinniger wees. Die lys opsie sou ook vereis dat ek die data te hou apart van die struktuur, terwyl dicts sal toelaat vir iets van die soort:

graph[I][J]["Property"]="value"

Wat sou jy voorstel?

---

Ja, ek moet 'n bietjie duideliker op wat ek bedoel met doeltreffendheid gewees het. In hierdie spesifieke geval bedoel ek dit in terme van ewetoeganklike herwinning.

laai die data in die geheue is nie 'n groot probleem. Dit is eens en vir altyd gedoen. Die tydrowende deel 'n besoek aan die nodes sodat ek die inligting kan onttrek en meet die statistieke Ek stel belang in.

Ek het nie oorweeg om elke node 'n klas (eienskappe is dieselfde vir alle nodes), maar dit lyk asof dit 'n ekstra laag van oorhoofse sal voeg? Ek het gehoop iemand sou 'n paar direkte ervaring met 'n soortgelyke geval wat hulle kan deel hê. Na alles, grafieke is een van die mees algemene abstraksies in CS.

Answer 1

Ek wil ten sterkste advokaat jy kyk na NetworkX . Dit is 'n stryd getoets oorlog perd en die eerste instrument meeste se navorsing 'tipes bereik vir wanneer hulle nodig het om ontleding van netwerk-gebaseerde data doen. Ek het grafieke met 100'e duisende rande gemanipuleer sonder probleem op 'n notaboek. Sy funksie ryk en baie maklik om te gebruik. Jy sal vind jouself fokus meer op die probleem op hande, eerder as die besonderhede in die onderliggende implementering.

Voorbeeld van Erdös-Rényi ewekansige grafiek geslag en analise

"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

visualisaties is ook eenvoudig:

Meer visualisering: http://jonschull.blogspot.com/2008/08 /graph-visualization.html

Answer 2

Hoewel hierdie vraag is nou baie oud, ek dink dit is die moeite werd om my eie luislang module vir grafiek manipulasie genoem noem grafiek-instrument . Dit is baie effektief, aangesien die datastrukture en algoritmes in C ++ geïmplementeer word, met sjabloon metaprograming, met behulp van die Boost Grafiek Biblioteek. Daarom sy prestasie (beide in geheue gebruik en runtime) is vergelykbaar met 'n suiwer C ++ biblioteek, en kan wees ordes beter as tipiese python kode, sonder om afbreuk gemak van gebruik. Ek gebruik dit self voortdurend te werk met 'n baie groot grafieke.

Answer 3

Soos reeds genoem, NetworkX is baie goed, met 'n ander opsie om igraph . Beide modules moet die meeste (indien nie alle) die analise gereedskap wat jy waarskynlik nodig is, en beide biblioteke word ook gereeld gebruik met groot netwerke.

Answer 4

'n Woordeboek kan ook bevat oorhoofse, afhangende van die werklike implementering. A hashtable bevat gewoonlik 'n paar eerste aantal beskikbare nodes om mee te begin, selfs al is jy net 'n paar van die nodes kan gebruik.

Te oordeel aan jou voorbeeld, "Eiendom", sou jy beter van 'n klas benadering vir die finale vlak en werklike eienskappe wees? Of is die name van die eienskappe te verander 'n baie van knoop tot knoop?

Ek sou sê dat dit wat "doeltreffende" beteken, hang af van baie dinge, soos:

• spoed van updates (insetsel, update, verwyder)
• spoed van ewetoeganklike herwinning
• spoed van opeenvolgende herwinning
• geheue gebruik

Ek dink dat jy sal vind dat 'n datastruktuur wat spoedige algemeen sal verteer meer geheue as een wat traag. Dit is nie altyd die geval nie, maar die meeste datastrukture lyk dit volg.

'n woordeboek kan maklik wees om te gebruik, en gee jy relatief eenvormig vinnige toegang, sal dit waarskynlik gebruik meer geheue as, soos jy voorstel, lyste. Lyste egter oor die algemeen geneig om meer oorhoofse bevat wanneer jy data in te voeg in dit, tensy hulle preallocate X knope, waarin hulle weer meer geheue gebruik.

My voorstel, in die algemeen, sou wees om net gebruik maak van die metode wat die meeste natuurlike lyk jy, en dan doen 'n "stress toets" van die stelsel, en voeg 'n aansienlike bedrag van data om dit te sien of dit 'n probleem.

Jy kan dit ook oorweeg om die toevoeging van 'n laag van onttrekking aan jou stelsel, sodat jy nie hoef te die programming interface verander as jy later op behoefte om die interne data struktuur verander.

Answer 5

Soos ek dit verstaan, ewetoeganklike is in konstante tyd vir beide dicts en lyste Python se, die verskil is dat jy net ewetoeganklike van heelgetal indekse met lyste kan doen. Ek neem aan dat jy nodig het om 'n knoop lookup deur sy etiket, so jy wil 'n dict van dicts.

Maar op die prestasie front, laai dit in die geheue kan nie 'n probleem te wees nie, maar as jy te veel gebruik jy beland uitruiling op skyf, wat die prestasie van selfs hoogs doeltreffende dicts Python se dood. Probeer om geheue gebruik af so veel as moontlik te hou. Ook, RAM is nou ongelooflik goedkoop; as jy hierdie soort ding wat 'n baie te doen, is daar geen rede om nie te hê ten minste 4 GB.

As jy wil raad oor hoe om geheue gebruik down, gee 'n paar meer inligting oor die aard van die inligting wat jy volg vir elke node.

Answer 6

Die maak van 'n klas-gebaseerde struktuur sal waarskynlik meer oorhoofse as die dict gebaseer struktuur, aangesien in python klasse eintlik gebruik dicts wanneer dit geïmplementeer word.

Answer 7

Geen twyfel NetworkX is die beste datastruktuur tot nou toe vir grafiek. Dit kom met nutsprogramme soos Helper Funksies, Datastrukture en Algoritmes, ewekansige volgorde Generators, ontwerpers, Cuthill-Mckee Bestel, Konteks Bestuurders

NetworkX is groot, want dit wowrs vir grafieke, digrawe, en multigraphs. Dit kan grafiek skryf met verskeie maniere: adjacency lys, multi line adjacency lys, Rand Lys, GEXF, GML. Dit werk met Pickle, GraphML, into, SparseGraph6 ens

Dit het implimentasie van verskeie radimade algoritmes, insluitend: Benadering, bilaterale, Boundary, Centrality, Clique, clustering, kleur, komponente, Connection, Cycles, onder leiding asikliese Grafieke, Afstand Maatreëls, oorheers Sets, Eulerian, isomorfie, Link analise, Link voorspelling, Matching, Minimum Spanning Tree, Rich Club, kortste afstande, traversal, Boom.