# Random graphs, fully-connected graphs

**URL:** <https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445>\
**Category:** Graphs\
**Tags:** lightgraphs, graphs\
**Created:** [May 30, 2020, 12:01am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445 "2020-05-30T00:01:36Z")\
**Posts on this page:** 18\
**Page:** 1

<div class="post-metadata">

**Author:** ![erlebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/erlebach/32/12973_2.png) [@erlebach](https://discourse.julialang.org/u/erlebach)\
**Post date:** [May 30, 2020, 12:01am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/1 "2020-05-30T00:01:36Z")

</div>

Hi,  
How does one create a fully connected graph with LightGraphs.jl? I looked at the documentation and did not see an obvious function.

A second equation is how to create a random graph with p percent of the edges?  
I did find a function that allowed me to create a graph with Nv vertices and Ne edges, so I could create the conversion. But I assume there is a built-in function that can duplicate the desired functionality.

A third question would be how to create a network such that connections between a point and neighbors do not extend beyond a specified distance. Again, one can create the appropriate routine, but an efficient implementation might already be a part of the library.

Thanks.

Gordon

---

<div class="post-metadata">

**Author:** ![dilumaluthge](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dilumaluthge/32/29283_2.png) [@dilumaluthge](https://discourse.julialang.org/u/dilumaluthge)\
**Post date:** [May 30, 2020, 12:23am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/2 "2020-05-30T00:23:51Z")

</div>

@anon94023334 ^

---

<div class="post-metadata">

**Author:** ![erlebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/erlebach/32/12973_2.png) [@erlebach](https://discourse.julialang.org/u/erlebach)\
**Post date:** [May 30, 2020, 1:29am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/3 "2020-05-30T01:29:40Z")

</div>

@dilumaluthge: I cannot see the reply! Or are you referring to somebody who might know the answer? If so, thanks!

---

<div class="post-metadata">

**Author:** ![dilumaluthge](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dilumaluthge/32/29283_2.png) [@dilumaluthge](https://discourse.julialang.org/u/dilumaluthge)\
**Post date:** [May 30, 2020, 1:31am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/4 "2020-05-30T01:31:16Z")

</div>

I’m just pinging Seth, who can probably answer these questions. I myself do not know the answers to these questions.

---

<div class="post-metadata">

**Author:** ![erlebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/erlebach/32/12973_2.png) [@erlebach](https://discourse.julialang.org/u/erlebach)\
**Post date:** [May 30, 2020, 2:44am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/5 "2020-05-30T02:44:52Z")

</div>

I looked at the source code of LightGraphs and did not find what I was looking for. But then I found SpecialGraphs.jl, which has the function CompleteGraph, which computes an all-to-all connection. Interesting that since one needs to implement the required Interface to LightGraphs to gets its functionality, that these SpecialGraphs try to find alternative shortcuts to implement this interface when the graph has special structure. A CompleteGraph has special structure. I will try it out.

Thanks for the motivation.

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [May 30, 2020, 3:45am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/6 "2020-05-30T03:45:48Z")

</div>

> How does one create a fully connected graph with LightGraphs.jl? I looked at the documentation and did not see an obvious function.

Do you mean a complete graph? If you’re on 1.3.x, use `complete_graph(n)`. If on master, use `SimpleGraph(LightGraphs.Generators.Complete(n))`.

> A second equation is how to create a random graph with p percent of the edges?

Use `erdos_renyi()` if on 1.3.x, or `SimpleGraphs(LightGraphs.Generators.ErdosRenyi())` on master. `ne` can be calculated via `p*nv*(nv-1) ÷ 2` for an undirected graph, so you could also do `SimpleGraph(nv, p * nv * (nv - 1) ÷ 2)`.

> A third question would be how to create a network such that connections between a point and neighbors do not extend beyond a specified distance.

What do you mean by “distance”? SimpleGraphs are unweighted (that is, default weight is 1). If “distance” means “weight”, then you can probably do this using `SimpleWeightedGraphs` and just bound the weight matrix.

---

<div class="post-metadata">

**Author:** ![erlebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/erlebach/32/12973_2.png) [@erlebach](https://discourse.julialang.org/u/erlebach)\
**Post date:** [May 30, 2020, 4:20am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/7 "2020-05-30T04:20:51Z")

</div>

Thanks! I do not understand the 1.3x versus master comment. I am on Julia 1.4x. While waiting for your response, I came across SpecialGraphs and used cg = SpecialGraphs.CompleteGraph(nverts). I assume both approach generate the same results since they both implement the desired interface?

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [May 30, 2020, 4:30am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/8 "2020-05-30T04:30:16Z")

</div>

I don’t know anything about SpecialGraphs, so I can’t comment.

1.3.x is the current stable version of LightGraphs. If you did a `Pkg.add` then this is what you’re using. If you did a `Pkg.dev`, then you’re on master, which has some major API changes.

If `complete_graph()` works without any warnings, then you’re on 1.3.x.

---

<div class="post-metadata">

**Author:** ![erlebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/erlebach/32/12973_2.png) [@erlebach](https://discourse.julialang.org/u/erlebach)\
**Post date:** [May 30, 2020, 4:46am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/9 "2020-05-30T04:46:44Z")

</div>

Ok, great. I will stick with what I have, but look forward to trying Pkg.dev in the near future. Has the documentation been updated for the master? When is the expected release date (give or take a few months.) Thanks.

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [May 30, 2020, 5:27am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/10 "2020-05-30T05:27:42Z")

</div>

Documentation is in progress, but the docstrings are up to date. Release is expected later this summer.

---

<div class="post-metadata">

**Author:** ![Igor\_Douven](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/igor_douven/32/8433_2.png) [@Igor\_Douven](https://discourse.julialang.org/u/Igor_Douven)\
**Post date:** [May 30, 2020, 10:27am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/11 "2020-05-30T10:27:22Z")

</div>

I switched to master yesterday and had to replace a couple of occurrences of `erdos_renyi()` in my code. This comment now made me a bit uncertain. Shouldn’t `erdos_renyi(N, p)` become something like `LightGraphs.SimpleGraph(LightGraphs.Generators.ErdosRenyi(N, round(Int, p * nv * (nv - 1) / 2)))`, or `LightGraphs.SimpleGraph(LightGraphs.Generators.ErdosRenyi(N, round(Int, binomial(N, 2)*p)))`? So basically divide by 2 what you are suggesting? I may well be wrong though – just checking.

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [May 30, 2020, 4:11pm UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/12 "2020-05-30T16:11:15Z")

</div>

No, you’re right. If you use the `ErdosRenyi` generator with a `SimpleDiGraph` then you’ll want to NOT divide by 2. But since a SimpleGraph has undirected edges, you’ll need to divide by two. I’ll fix my previous reply. Thanks.

---

<div class="post-metadata">

**Author:** ![Igor\_Douven](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/igor_douven/32/8433_2.png) [@Igor\_Douven](https://discourse.julialang.org/u/Igor_Douven)\
**Post date:** [May 30, 2020, 4:25pm UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/13 "2020-05-30T16:25:45Z")

</div>

Thanks for the clarification!

---

<div class="post-metadata">

**Author:** ![erlebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/erlebach/32/12973_2.png) [@erlebach](https://discourse.julialang.org/u/erlebach)\
**Post date:** [May 31, 2020, 2:05am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/14 "2020-05-31T02:05:14Z")

</div>

Can a node link to itself in LightGraphs?

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [May 31, 2020, 2:17am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/15 "2020-05-31T02:17:53Z")

</div>

In general, yes; but some algorithms don’t like self-loops too much. Specifically, shortest-path calculations might have an issue. It’s not really supported for anything beyond representing a structure.

---

<div class="post-metadata">

**Author:** ![erlebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/erlebach/32/12973_2.png) [@erlebach](https://discourse.julialang.org/u/erlebach)\
**Post date:** [May 31, 2020, 2:35am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/16 "2020-05-31T02:35:27Z")

</div>

Do you know anything about SIR models? That is why I need it. Of course, I am not working in the most optimized fashion, I know.

Here is another question. I defined a graph with 10 nodes and 7 edges. I would like to add additional edges with `add_edges(graph, src, dst)` . When printing the edges, I notice that existing edges are overwritten as opposed to new edges created. That was unexpected. Is this what you’d expect? Here is what I did:

```julia
nedges = 7
nverts = 10

dg = DiGraph(nverts, nedges)

for i in 1:nverts
    add_edge!(dg, i, i) # self-links
end

```

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [May 31, 2020, 4:05am UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/17 "2020-05-31T04:05:41Z")

</div>

> When printing the edges, I notice that existing edges are overwritten as opposed to new edges created.

I don’t know what you mean. Self-loops are not created by default, so they will not “overwrite” anything when you create them, since there’s nothing to overwrite:

```julia
julia> g = DiGraph(10, 7)
{10, 7} directed simple Int64 graph

julia> collect(edges(g))
7-element Array{LightGraphs.SimpleGraphsCore.SimpleEdge{Int64},1}:
 Edge 4 => 1
 Edge 4 => 3
 Edge 6 => 2
 Edge 6 => 5
 Edge 7 => 1
 Edge 7 => 4
 Edge 9 => 8

julia> for i in vertices(g)
           add_edge!(g, i, i)
       end

julia> collect(edges(g))
17-element Array{LightGraphs.SimpleGraphsCore.SimpleEdge{Int64},1}:
 Edge 1 => 1
 Edge 2 => 2
 Edge 3 => 3
 Edge 4 => 1
 Edge 4 => 3
 Edge 4 => 4
 Edge 5 => 5
 Edge 6 => 2
 Edge 6 => 5
 Edge 6 => 6
 Edge 7 => 1
 Edge 7 => 4
 Edge 7 => 7
 Edge 8 => 8
 Edge 9 => 8
 Edge 9 => 9
 Edge 10 => 10

```

---

<div class="post-metadata">

**Author:** ![erlebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/erlebach/32/12973_2.png) [@erlebach](https://discourse.julialang.org/u/erlebach)\
**Post date:** [May 31, 2020, 2:47pm UTC](https://discourse.julialang.org/t/random-graphs-fully-connected-graphs/40445/18 "2020-05-31T14:47:00Z")

</div>

I was obviously mistaken. I rewrote a mwe this morning, and you are obviously correct. Thank you for your help.

```julia
using LightGraphs

nedges = 3
nverts = 5

# Create a directed graph
dg = DiGraph(nverts, nedges)

#List the edges
println("\n----> Graph edges, no self-connections")
for (i,e) in enumerate(edges(dg))
    println("Edge $i) #, src/dst: ", src(e), ", ", dst(e))
end

for i in 1:nverts
    add_edge!(dg, i, i)
end

println("\n----> Added self-edges")
for (i,e) in enumerate(edges(dg))
    println("Edge $i) #, src/dst: ", src(e), ", ", dst(e))
end

```

with output:

```julia
----> Graph edges, no self-connections
Edge 1) #, src/dst: 2, 1
Edge 2) #, src/dst: 3, 1
Edge 3) #, src/dst: 5, 4

----> Added self-edges
Edge 1) #, src/dst: 1, 1
Edge 2) #, src/dst: 2, 1
Edge 3) #, src/dst: 2, 2
Edge 4) #, src/dst: 3, 1
Edge 5) #, src/dst: 3, 3
Edge 6) #, src/dst: 4, 4
Edge 7) #, src/dst: 5, 4
Edge 8) #, src/dst: 5, 5

```