CODEWITHSUNDEEP
algorithmgraph
csguy
csguy

Reputation: 1474

Easiest way to generate an undirected graph’s adjacency list?

The closest thing I could find was this: https://csacademy.com/app/graph_editor/

But it doesn’t randomly generate a graph. I’m looking to generate an adjacency list for 1000+ node graph.

Ex. {0, 2, 3}, {1, 5}, ...

Any help would be appreciated.

Upvotes: 1

Views: 2987

Answers (2)

kaya3
kaya3

Reputation: 51063

There are various models for generating random graphs with particular statistical properties. You've said in the comments that the distribution doesn't really matter for your use-case, so a simple model to use is the one which includes each potential edge with some fixed probability, independent of whether other edges are included. This distribution is usually called G(n, p) where n is the number of nodes, and p is the probability of an edge being included.

The algorithm to generate a graph from G(n, p) is straightforward:

  • Initialise a graph with n nodes and no edges.
  • For each (unordered/ordered) pair of nodes u, v:
    • Generate a random real number in the range [0, 1].
    • If this number is less than p, add the edge u-v to the graph.

The choice between unordered pairs and ordered pairs depends on whether you want an undirected or directed graph respectively.

Since you want an adjacency list, the "initialise" step will be to create a list containing n empty lists, and the "add edge" step will add v to u's (and u to v's list, if the graph should be undirected).

Here's an example implementation in Python:

from random import random
from itertools import product, combinations

def random_graph(n, p, *, directed=False):
    nodes = range(n)
    adj_list = [[] for i in nodes]
    possible_edges = product(nodes, repeat=2) if directed else combinations(nodes, 2)
    for u, v in possible_edges:
        if random() < p:
            adj_list[u].append(v)
            if not directed:
                adj_list[v].append(u)
    return adj_list

Examples:

>>> random_graph(4, 0.5)
[[1, 2, 3],
 [0, 3],
 [0],
 [0, 1]]
>>> random_graph(5, 0.25, directed=True)
[[0, 2, 4],
 [1, 4],
 [0, 1, 2, 3],
 [1],
 [1, 2]]

Upvotes: 2

ardenit
ardenit

Reputation: 3890

If you want to generate a random graph with N nodes and M edges, the easiest way is the following algorithm:

Let list be a list of all pairs (0, 1), ...., (0, N-1), (1, 2), ...., (N-2, N-1): all S = (N - 1) * N / 2 possible edges. Then you need to generate a random subset of this list, with size M.

  • Generate a random number x0 from 0 to S-1
  • Swap elements on indices x0 and S-1
  • Generate a random number x1 from 0 to S-2
  • Swap elements on indices x1 and S-2
  • (repeat until you generate M numbers)

Last M elements in the list will form a random subset of edges. Then you can just add them in your graph and create adjacency lists as you want.

Upvotes: 1

Related Questions