Graph-tool: Difference between revisions

Revision as of 12:23, 10 August 2015

Latest revision as of 01:03, 4 August 2025

(48 intermediate revisions by 30 users not shown)

Line 1:

{{Third-party|date=January 2021}}

{{Infobox software

| name = graph-tool

| title = Graph Tool

| logo = [[File:Graph-tool-logo.png|250px]]

| screenshot = <!-- [[File: ]] -->

| caption =

| collapsible =

| author =

| developer = [[Tiago de PaulaP. Peixoto]]

| released = <!-- {{Start date|YYYY|MM|DD|df=yes/no}} -->

| discontinued =

| latest release version = 2.2.3645

| latest release date = {{Start date and age|20152022|0105|0822|df=yes/no}}

| latest preview version =

| latest preview date = <!-- {{Start date and age|YYYY|MM|DD|df=yes/no}} -->

| frequently updated = <!-- DO NOT include this parameter unless you know what it does -->

| programming language = [[Python (programming language)|Python]], [[C++]]

| operating system = [[Cross-platformOS X]], [[Linux]]

| platform =

| size =

Line 22 ⟶ 23:

| status =

| genre = [[Software library]]

| license = [[GPLLGPL]]

| website = {{URL|graph-tool.skewed.de}}

}}

'''graph-tool''' is a [[Python (programming language)|Python]] module for manipulation and statistical analysis of [[Graph (discrete mathematics)|graphs]] (a.k.a.AKA [[Network theory|networks]]). The core data structures and algorithms of graph-tool are implemented in [[C++]], making extensive use of [[metaprogramming]], based heavily on the [[Boost Graph Library]]. This type of approach can confer a level of performance which is comparable (both in memory usage and computation time) to that of a pure [[C++]] library, which can be several orders of magnitude better than pure Python.<ref>[http://graph-tool.skewed.de/performance Graph-tool performance comparison], Graph-tool</ref> Many algorithms are implemented in parallel using [[OpenMP]], which provides increased performance on [[Multi-core processor|multi-core]] architectures.

Furthermore, many algorithms are implemented in parallel using [[OpenMP]], which provides increased performance on [[Multi-core processor|multi-core]] architectures, without degrading the performance on single-core machines.

== Features ==

* Creation and manipulation of [[Directed graph|directed]] or [[Graph (discrete mathematics)|undirected graphs]].

* Association of arbitrary information to the vertices, edges or even the graph itself, by means of property maps.

* Filter vertices and/or edges "on the fly", such that they appear to have been removed.

Line 36 ⟶ 35:

* Convenient and powerful [[graph drawing]] based on [[cairo (graphics)|cairo]] or [[Graphviz]].

* Support for typical statistical measurements: degree/property histogram, combined degree/property histogram, vertex-vertex correlations, [[assortativity]], average vertex-vertex [[shortest path]], etc.

* Support for several graph-theoretical algorithms: such as [[graph isomorphism]], [[Subgraph isomorphism problem|subgraph isomormismisomorphism]], [[minimum spanning tree]], [[Connected component (graph theory)|connected components]], [[Dominator (graph theory)|dominator]] tree, [[maximum flow]], etc.

* Support for several [[centrality]] measures.

* Support for [[clustering coefficient]]s, as well as [[network motif]] statistics and [[community structure]] detection.

Line 42 ⟶ 41:

* Support for well-established network models: [[preferential attachment|Price]], [[Barabási–Albert model|Barabási-Albert]], Geometric Networks, Multidimensional [[lattice graph]], etc.

==SuitabiltySuitability==

Graph-tool can be used to work with very large graphs {{clarify|date=January 2021 |reason= Be more precise? Size of graph you can use depends strongly on context.}} in a variety of contexts, including simulation of [[epithelium|cellular tissue]],<ref>Bruno Monier et al, "Apico-basal forces exerted by apoptotic cells drive epithelium folding", Nature, 2015 [http://www.nature.com/nature/journal/vaop/ncurrent/full/nature14152.html]</ref> [[data mining]],<ref>Ma, Shuai, et al. "Distributed graph pattern matching." Proceedings of the 21st international conference on World Wide Web. ACM, 2012. [http://dl.acm.org/citation.cfm?id=2187963]</ref><ref>Ma, Shuai, et al. "Capturing topology in graph pattern matching." Proceedings of the VLDB Endowment 5.4 (2011): 310-321. [http://dl.acm.org/citation.cfm?id=2095690]</ref> analysis of [[Social network theoryanalysis|analysis of social networks]],<ref>Janssen, E., M. A. T. T. Hurshman, and N. A. U. Z. E. R. Kalyaniwalla. "Model selection for social networks using graphlets." Internet Mathematics (2012). [http://www.mathstat.dal.ca/~janssen/papers/Graphlets.pdf]</ref><ref>Asadi, Hirad Cyrus. Design and implementation of a middleware for data analysis of social networks. Diss. M Sc thesis report, KTH School of Computer Science and Communication, Stockholm, Sweden, 2007. [http://www.student.nada.kth.se/~hias02/xjobb-en.pdf] {{Webarchive|url=https://web.archive.org/web/20150122120734/http://www.student.nada.kth.se/~hias02/xjobb-en.pdf |date=2015-01-22 }}</ref> analysis of [[Peer-to-Peerpeer|P2P]] systems,<ref>Teresniak, Sven, et al. "Information-Retrieval in einem P2P-Netz mit Small-World-Eigenschaften Simulation und Evaluation des SemPIR-Modells."[http://asv.informatik.uni-leipzig.de/thesis/thesis_document/25/masterarbeit.pdf] {{Webarchive|url=https://web.archive.org/web/20150122120956/http://asv.informatik.uni-leipzig.de/thesis/thesis_document/25/masterarbeit.pdf |date=2015-01-22 }}</ref> large-scale modeling of [[Agent-based model|agent-based systems]],<ref>Hamacher, Kay, and Stefan Katzenbeisser. "Public security: simulations need to replace conventional wisdom." Proceedings of the 2011 workshop on New security paradigms workshop. ACM, 2011. [http://dl.acm.org/citation.cfm?id=2073288]</ref> theoretical assessment and modeling of network [[Clustering coefficient|clustering]],<ref>Abdo, Alexandre H., and A. P. S. de Moura. "Clustering as a measure of the local topology of networks." arXiv preprint physics/0605235 (2006). [https://arxiv.org/abs/physics/0605235]</ref> large-scale [[call graph]] analysis,<ref>Narayan, Ganesh, K. Gopinath, and V. Sridhar. "Structure and interpretation of computer programs." Theoretical Aspects of Software Engineering, 2008. TASE'08. 2nd IFIP/IEEE International Symposium on. IEEE, 2008. [https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4549888]</ref> and analysis of the brain's [[Connectome]].<ref>Gerhard, Stephan, et al. "The connectome viewer toolkit: an open source framework to manage, analyze, and visualize connectomes." Frontiers in neuroinformatics 5 (2011). [https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3112315/]</ref>

study of academic [[Genealogy tree]]s,<ref>Miyahara, Edson Kiyohiro, Jesus P. Mena-Chalco, and Roberto M. Cesar-Jr. "Genealogia Acadêmica Lattes." [http://www.linux.ime.usp.br/~edsonkm/mac499/download/monografia.pdf]</ref> theoretical assessment and modeling of network [[Clustering coefficient|clustering]],<ref>Abdo, Alexandre H., and A. P. S. de Moura. "Clustering as a measure of the local topology of networks." arXiv preprint physics/0605235 (2006). [http://arxiv.org/abs/physics/0605235]</ref> large-scale [[call graph]] analysis,<ref>Narayan, Ganesh, K. Gopinath, and V. Sridhar. "Structure and interpretation of computer programs." Theoretical Aspects of Software Engineering, 2008. TASE'08. 2nd IFIP/IEEE International Symposium on. IEEE, 2008. [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4549888]</ref><ref>Campos, José Creissac, et al. "GUIsurfer: A Reverse Engineering Framework for User Interface Software." [http://cdn.intechopen.com/pdfs/30511/InTech-Guisurfer_a_reverse_engineering_framework_for_user_interface_software.pdf]</ref> and analysis of the brain's [[Connectome]].<ref>Gerhard, Stephan, et al. "The connectome viewer toolkit: an open source framework to manage, analyze, and visualize connectomes." Frontiers in neuroinformatics 5 (2011). [http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3112315/]</ref>

==References==

{{Reflist|230em}}

==External links==

{{Portal|Free and open-source software}}

* {{official website|http://graph-tool.skewed.de/}}

* [http://nethedz.org/blog/2011/07/installing-graphtool-on-snowleopard Installing on MacOS Snow Leopard]

* [https://pypi.python.org/pypi/graph-tool PyPi entry]

* [http://www.ohloh.net/p/graph-tool Ohloh entry]

* [http://plus.google.com/u/0/b/113703414224138555067/ Google+ page]

{{Portal|Free software}}

{{DEFAULTSORT:graph-tool}}