OKlibrary  0.2.1.6
RandomGraphs.hpp File Reference

Plans regarding generation of (general) random graphs. More...

Go to the source code of this file.


Detailed Description

Plans regarding generation of (general) random graphs.

Todo:
Implementation
  • First we need an overview on the existing generators for random (general) graphs.
  • One general method is to construct a random adjacency matrix or a random incidence matrix.
  • In the Maxima graphs-module we have:
    1. random_bipartite_graph
    2. random_digraph
    3. random_regular_graph
    4. random_graph
    5. random_graph1
    6. random_tournament (complete digraphs)
    7. random_tree
    It seems only (simple) graphs are generated.
  • In Sage:
    1. RandomBarabasiAlbert
    2. RandomDirectedGN
    3. RandomDirectedGNC
    4. RandomDirectedGNR
    5. RandomGNM
    6. RandomGNP
    7. RandomHolmeKim
    8. RandomLobster
    9. RandomNewmanWattsStrogatz
    10. RandomRegular
    11. RandomShell
    12. RandomTreePowerlaw
    It seems only (simple) graphs are generated.
Todo:
Overview on theoretical possibilities
  • We need an overview on the models studied in the theory of random graphs.
  • We are especially interested in random multigraphs!
    1. These could be obtained by taking the union of random graphs.
    2. Again, the natural alternative is to consider random matrices.
    3. Or one consider any given graph, and multiplies each edge in a random way.

Definition in file RandomGraphs.hpp.