sepandhaghighi / pyrgg

🔧 Python Random Graph Generator
https://www.pyrgg.site
MIT License
204 stars 30 forks source link
beerpay generator gpu graph-computing graph-generation graph-generator gtgraph math mathematics python python3 script

PyRGG: Python Random Graph Generator

PyPI version Codecov built with Python3 Discord Channel

Overview

PyRGG is a user-friendly synthetic random graph generator that is written in Python and supports multiple graph file formats, such as DIMACS-Graph files. It can generate graphs of various sizes and is specifically designed to create input files for a wide range of graph-based research applications, including testing, benchmarking, and performance analysis of graph processing frameworks. PyRGG is aimed at computer scientists who are studying graph algorithms and graph processing frameworks.

Open Hub
PyPI Counter
Github Stars
Branch master dev
CI
Code Quality codebeat badge CodeFactor

Installation

PyPI

Source Code

Conda

Exe Version (Only Windows)

System Requirements

Pyrgg will likely run on a modern dual core PC. Typical configuration is:

Note that it may run on lower end equipment though good performance is not guaranteed.

Usage

Engines

PyRGG

Parameter Description
Vertices Number The total number of vertices in the graph
Min Edge Number The minimum number of edges connected to each vertex
Max Edge Number The maximum number of edges connected to each vertex
Weighted / Unweighted Specifies whether the graph is weighted or unweighted
Min Weight The minimum weight of the edges (if weighted)
Max Weight The maximum weight of the edges (if weighted)
Signed / Unsigned Specifies whether the edge weights are signed or unsigned
Directed / Undirected Specifies whether the graph is directed or undirected
Self Loop / No Self Loop Specifies whether self-loop is allowed or not
Simple / Multigraph Specifies whether the graph is a simple graph or a multigraph

Erdős–Rényi-Gilbert

Parameter Description
Vertices Number The total number of vertices in the graph
Probability The probability for edge creation between any two vertices
Directed / Undirected Specifies whether the graph is directed or undirected

Supported Formats

DIMACS

    p sp <number of vertices> <number of edges>
    a <head_1> <tail_1> <weight_1>

    .
    .
    .

    a <head_n> <tail_n> <weight_n>

CSV

    <head_1>,<tail_1>,<weight_1>

    .
    .
    .

    <head_n>,<tail_n>,<weight_n>

TSV

    <head_1>    <tail_1>    <weight_1>

    .
    .
    .

    <head_n>    <tail_n>    <weight_n>

JSON

{
    "properties": {
        "directed": true,
        "signed": true,
        "multigraph": true,
        "weighted": true,
        "self_loop": true
    },
    "graph": {
        "nodes":[
        {
            "id": 1
        },

        .
        .
        .

        {
            "id": n
        }
        ],
        "edges":[
        {
            "source": head_1,
            "target": tail_1,
            "weight": weight_1
        },

        .
        .
        .

        {
            "source": head_n,
            "target": tail_n,
            "weight": weight_n
        }
        ]
    }
}

YAML

    graph:
        edges:
        - source: head_1
        target: tail_1
        weight: weight_1

        .
        .
        .

        - source: head_n
        target: tail_n
        weight: weight_n

        nodes:
        - id: 1

        .
        .
        .

        - id: n
    properties:
        directed: true
        multigraph: true
        self_loop: true
        signed: true
        weighted: true

Weighted Edge List

    <head_1> <tail_1> <weight_1>

    .
    .
    .

    <head_n> <tail_n> <weight_n>    

ASP

    node(1).
    .
    .
    .
    node(n).
    edge(head_1,tail_1,weight_1).
    .
    .
    .
    edge(head_n,tail_n,weight_n).

Trivial Graph Format

    1
    .
    .
    .
    n
    #
    1 2 weight_1
    .
    .
    .
    n k weight_n

UCINET DL Format

    dl
    format=edgelist1
    n=<number of vertices>
    data:
    1 2 weight_1
    .
    .
    .
    n k weight_n    

Matrix Market

    %%MatrixMarket matrix coordinate real general
    <number of vertices>  <number of vertices>  <number of edges>
    <head_1>    <tail_1>    <weight_1> 
    .
    .
    .
    <head_n>    <tail_n>    <weight_n> 

Graph Line

    <head_1> <tail_1>:<weight_1> <tail_2>:<weight_2>  ... <tail_n>:<weight_n>
    <head_2> <tail_1>:<weight_1> <tail_2>:<weight_2>  ... <tail_n>:<weight_n>
    .
    .
    .
    <head_n> <tail_1>:<weight_1> <tail_2>:<weight_2>  ... <tail_n>:<weight_n>

GDF

    nodedef>name VARCHAR,label VARCHAR
    node_1,node_1_label
    node_2,node_2_label
    .
    .
    .
    node_n,node_n_label
    edgedef>node1 VARCHAR,node2 VARCHAR, weight DOUBLE
    node_1,node_2,weight_1
    node_1,node_3,weight_2
    .
    .
    .
    node_n,node_2,weight_n 

GML

    graph
    [
      multigraph 0
      directed  0
      node
      [
       id 1
       label "Node 1"
      ]
      node
      [
       id 2
       label "Node 2"
      ]
      .
      .
      .
      node
      [
       id n
       label "Node n"
      ]
      edge
      [
       source 1
       target 2
       value W1
      ]
      edge
      [
       source 2
       target 4
       value W2
      ]
      .
      .
      .
      edge
      [
       source n
       target r
       value Wn
      ]
    ]

GEXF

     <?xml version="1.0" encoding="UTF-8"?>
     <gexf xmlns="http://www.gexf.net/1.2draft" version="1.2">
         <meta lastmodifieddate="2009-03-20">
             <creator>PyRGG</creator>
             <description>File Name</description>
         </meta>
         <graph defaultedgetype="directed">
             <nodes>
                 <node id="1" label="Node 1" />
                 <node id="2" label="Node 2" />
                 ...
             </nodes>
             <edges>
                 <edge id="1" source="1" target="2" weight="400" />
                 ...
             </edges>
         </graph>
     </gexf>

Graphviz

    graph example 
        {
        node1 -- node2 [weight=W1];
        node3 -- node4 [weight=W2];
        node1 -- node3 [weight=W3];
        .
        .
        .
        }

Pickle

⚠️ Binary format

Example of Usage

Similar Works

Issues & Bug Reports

Just fill an issue and describe it. We'll check it ASAP!
or send an email to info@pyrgg.site.

You can also join our discord server

Discord Channel

Citing

If you use pyrgg in your research, please cite the JOSS paper ;-)

@article{Haghighi2017,
  doi = {10.21105/joss.00331},
  url = {https://doi.org/10.21105/joss.00331},
  year  = {2017},
  month = {sep},
  publisher = {The Open Journal},
  volume = {2},
  number = {17},
  author = {Sepand Haghighi},
  title = {Pyrgg: Python Random Graph Generator},
  journal = {The Journal of Open Source Software}
}
JOSS
Zenodo DOI

References

1- 9th DIMACS Implementation Challenge - Shortest Paths
2- Problem Based Benchmark Suite
3- MaximalClique - ASP Competition 2013
4- Pitas, Ioannis, ed. Graph-based social media analysis. Vol. 39. CRC Press, 2016.
5- Roughan, Matthew, and Jonathan Tuke. "The hitchhikers guide to sharing graph data." 2015 3rd International Conference on Future Internet of Things and Cloud. IEEE, 2015.
6- Borgatti, Stephen P., Martin G. Everett, and Linton C. Freeman. "Ucinet for Windows: Software for social network analysis." Harvard, MA: analytic technologies 6 (2002).
7- Matrix Market: File Formats
8- Social Network Visualizer
9- Adar, Eytan. "GUESS: a language and interface for graph exploration." Proceedings of the SIGCHI conference on Human Factors in computing systems. 2006.
10- Skiena, Steven S. The algorithm design manual. Springer International Publishing, 2020.
11- Chakrabarti, Deepayan, Yiping Zhan, and Christos Faloutsos. "R-MAT: A recursive model for graph mining." Proceedings of the 2004 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2004.
12- Zhong, Jianlong, and Bingsheng He. "An overview of medusa: simplified graph processing on gpus." ACM SIGPLAN Notices 47.8 (2012): 283-284.
13- Ellson, John, et al. "Graphviz and dynagraph—static and dynamic graph drawing tools." Graph drawing software. Springer, Berlin, Heidelberg, 2004. 127-148.
14- Gilbert, Edgar N. "Random graphs." The Annals of Mathematical Statistics 30.4 (1959): 1141-1144.
15- Erdős, Paul, and Alfréd Rényi. "On the strength of connectedness of a random graph." Acta Mathematica Hungarica 12.1 (1961): 261-267.

Show Your Support

Star This Repo

Give a ⭐️ if this project helped you!

Donate to Our Project

If you do like our project and we hope that you do, can you please support us? Our project is not and is never going to be working for profit. We need the money just so we can continue doing what we do ;-) .

PyRGG Donation