juliagraphs/graphs.jl

An optimized graphs package for the Julia programming language

graphs.jl's Issues

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

broken documentation links in the README

The link https://juliagraphs.org/Graphs.jl/dev/ is broken

[Port] Add JuliaFormatter template

See sbromberger/LightGraphs.jl#1592

[Port] Inconsistency about weights

See sbromberger/LightGraphs.jl#1519

Transfer issues from LightGraphs.jl

It's a pity to lose all the information contained in the open and closed issues of the old repo.

https://github.com/sbromberger/LightGraphs.jl/issues

[Port] [BUG] `a_star` fails on `SimpleWeightedDiGraph`

See sbromberger/LightGraphs.jl#1579

[BUG] Can't add vertices to a `MetaDiGraph`

Run this,

using LightGraphs, MetaGraphs, SimpleGraphs

g = MetaDiGraph()

add_vertex!(g.graph)
add_edge!(g,1,1)

and then make a new session swapping LightGraphs for Graphs.jl
you should get the following error:

ERROR: LoadError: MethodError: no method matching add_vertex!(::LightGraphs.SimpleGraphs.SimpleDiGraph{Int64})
Closest candidates are:
  add_vertex!(::SimpleDiGraph{T}) where T at /home/caseykneale/.julia/packages/Graphs/Mih78/src/SimpleGraphs/simpledigraph.jl:449
  add_vertex!(::Graphs.SimpleGraphs.SimpleGraph{T}) where T at /home/caseykneale/.julia/packages/Graphs/Mih78/src/SimpleGraphs/simplegraph.jl:526

[Port] `strongly_connected_components` and `strongly_connected_components_kosaraju` run in quadratic time

See sbromberger/LightGraphs.jl#1560

[Port] Graph transitivity

See sbromberger/LightGraphs.jl#1556

[BUG] Intermittently failing tests for `label_propagation` on mac OS

Examples of failing tests here and here

[Port] Performance of `diameter`

See sbromberger/LightGraphs.jl#1516

Standardized output for shortest path algorithms

At the moment, a_star returns a list of edges, while dijkstra_shortest_paths returns a custom state object. Would it make sense to have homogeneous outputs, at least for the single-source case?

[Port] [BUG] `Experimental.Traversals.topological_sort` not working for non-connected sub-graphs

See sbromberger/LightGraphs.jl#1565

[Port] [BUG] `mincut` gives incorrect results for some `SimpleGraph`s

See sbromberger/LightGraphs.jl#1589

[Port] A function that finds all simple paths

See sbromberger/LightGraphs.jl#1521

[Port] [BUG] `adjacency_matrix` fails for `SimpleGraph` with self-loops (Julia 1.7)

See sbromberger/LightGraphs.jl#1594

[Port] [BUG] `has_isomorph` doesn't work with `MetaDiGraph`s

See sbromberger/LightGraphs.jl#1503

[Port] [BUG] `merge_vertices` does not merge vertices of `star_graph` correctly

See sbromberger/LightGraphs.jl#1586

Standardized interface for graph modification

I understand why the Graphs.jl interface doesn't require the possibility of graph modification. However, wouldn't it be nice to specify at least the desired names add/rem_vertex/edge! in case people decide to implement them?

This could help standardize algorithms that include graph operations such as contractions (see #79)

"Undirected" mode for shortest paths with directed graphs

This is a repost of this issue on the old repo.

---

Hi,
This is a follow up of this discussion.
Is there a way to efficiently find shortest paths in a directed graph while ignoring the direction of the edges ? (so without casting to a directed graph)
R seems to have an "undirected" mode for this.

---

Having thought more on this, better than a keyword in functions, it would be practical to have a new graph type that would be a wrapper around a directed graph, with redefinition of accessers to make it an undirected graph (a sort of graph view). This would avoid the heavy conversion to an undirected graph.

[Port] Add a function api `random_geometric_graph`

See sbromberger/LightGraphs.jl#1509

Non-deterministic test failure in closness centrality

I saw this once on my mac running single threaded

 Testing Running tests...
Parallel.Closeness: Test Failed at /Users/viral/.julia/packages/Graphs/mjncd/test/parallel/centrality/closeness.jl:14
  Expression: tz ≈ [0.75, 0.4444444444444444, 0.3333333333333333, 0.0]
   Evaluated: [0.75, 0.4444444444444444, 0.3333333333333333, NaN] ≈ [0.75, 0.4444444444444444, 0.3333333333333333, 0.0]
Stacktrace:
 [1] macro expansion
   @ ~/.julia/packages/Graphs/mjncd/test/parallel/centrality/closeness.jl:14 [inlined]
 [2] macro expansion
   @ /Users/julia/buildbot/worker/package_macos64/build/usr/share/julia/stdlib/v1.6/Test/src/Test.jl:1151 [inlined]
 [3] top-level scope
   @ ~/.julia/packages/Graphs/mjncd/test/parallel/centrality/closeness.jl:2

And see it in CI too: https://github.com/JuliaGraphs/Graphs.jl/runs/3931288326

[Port] `eigs` in documentation of laplacian and adjacency spectrum

See sbromberger/LightGraphs.jl#1494

[Port] Add widest / maximum capacity path algorithm

See sbromberger/LightGraphs.jl#1557

[BUG] `biconnected_components` loses some edges - should we return only vertices ?

This is a repost of this issue, I think it deserves discussion on whether we should return edges instead of vertices.

Summary :

start=[1,1,2,2,2,3,4,4,5,5,7,7,8,8,9,9,10,10,12,12,1,2,3]
destination=[2,4,4,5,3,5,7,8,7,8,9,10,9,10,11,12,12,13,13,11,11,12,13]

graph_s=SimpleWeightedGraph(start,destination,collect(1:23))

bi_components= biconnected_components(graph_s)

graph_s has 23 edges, but only 19 are returned in the unique biconnected component.

etienneINSA : The error is here : the edge is added only if state.low[v] > state.depth[w], whereas it should be always added to the stack. I can make a PR, but I have an interrogation: Why do we return the biconnected components by their edges? As the subgraphs are induced, this is more easily defined by the vertices. Is there a good reason to do that, or would it be too breaking to change this behavior?

Explore leveraging GraphBLAS kernels to speed up Graphs.jl

We may be able to accelerate some of the kernels within Graphs.jl using https://github.com/JuliaSparse/SuiteSparseGraphBLAS.jl.

cc @wimmerer

[Port] Use `ismutable` in `johnson_shortest_paths`

See sbromberger/LightGraphs.jl#1597

[Port] Add `topological_sort_by_dfs` to documentation

See sbromberger/LightGraphs.jl#1566

Refresh icon

Hi graphers! (graphistes?) Thank you for your efforts in migrating, maintaining, and updating this package, which so many of us find useful.

As a very minor contribution, here are some suggestions for a refreshed icon.

I noticed an oddity with the current icon. For some reason it's slightly transparent, which explains the subdued appearance when used with GitHub's Dark Mode.

The current icon also uses the OG Julia duotone colour design, which was replaced by single colours sometime around v1.2.

[Port] Add a generator for directed configuration model

See sbromberger/LightGraphs.jl#1553

[Port] Ambiguity in Barabási–Albert possibly worth investigating

See sbromberger/LightGraphs.jl#1534

Edge Betweenness Centrality

At the moment, there is no function to calculate the edge betweenness centrality of a graph.

I have an implementation for undirected/unweighted graphs, at least.

Should I do a PR for this?

https://github.com/J-C-Q/Introduction-to-Network-Science/blob/0b83582a49e8833314fe8453b19643549d127d89/edge_betweenness_centrality.jl

Suggestion: Hierarchical structure for documentation

The current documentation has many sections in the menu on the left, but hardly any subsections. I feel like this doesn't help navigation, and I would prefer a more hierarchical approach (like the one from networkx. Does anyone agree?

[Port] Fallback for all edge operations

For an edge operation f, define both f(g, src(e), dst(e)) and f(g, e) on abstract graphs

See sbromberger/LightGraphs.jl#1287

Squash does not work correctly for AbstractGraph

The way the squash is currently implemented is by either calling SimpleGraph{T}(g) or SimpleDiGraph{T}(g) for some integer type T. This fails if g is a subtype of AbstractGraph for which these functions are not implemented. There are multiple ways to solve this:

1. Restrict squash to SimpleGraph and SimpleDiGraph and leave the implementation of that function for other graph types open.
2. Ensure that the constructors SimpleGraph{T}(g) or SimpleDiGraph{T}(g) work for for any kind of g::AbstractGraph.
3. Require that subtypes of any kind of graph type SomeGraph <: AbstractGraph implement a constructor SomeGraph{T}(g) and adjust squash accordingly.

In my opinion, 1. is the way to go. 2. could lead to some information (such as metadata) being thrown away by squash which is probably not what the user wants. 3. would make the interface more complicated and would make existing packages not correspond to the interface anymore.

`is_cyclic` for undirected graphs

Issue previously open at #1518 for LightGraphs.jl.

The is_cyclic function in LightGraphs.jl works well for directed graphs but for undirected graphs returns true for any nonempty graph. The usual definition for undirected graphs is that cycles don't contain repeated links, so 1->2->1 is not considered a cycle (absent multiple edges.)

Useful for me because I want a function that will test whether an (undirected) network is a tree and easiest way to check that is to confirm the graph is acyclic+connected

Consistent approach to graph direction

In traversals we use dir=[:in,:out] to tell functions to use in or out neighbors. We should probably have a more systematic approach based on a type like ReverseGraph{G} <: AbstractGraph. This came up in #36 where you have a symmetry in the algorithm that is invariant to the direction.

Mark parallel algorithms as experimental

A parallel BFS non-deterministic issue in #9
https://github.com/JuliaGraphs/Graphs.jl/pull/9/checks?check_run_id=3932016414#step:6:227

Trace says this is where the test fails: https://github.com/JuliaGraphs/Graphs.jl/blob/master/src/Parallel/traversals/gdistances.jl#L67

The test failed in the parallel gdistances test.

[Port] Modularity for bipartite graphs

See sbromberger/LightGraphs.jl#1541

Minors and contraction

It would be nice to have support for graph minors, at list for SimpleGraphs and possibly even in the interface by defining something like contract_edge!(g, s, d)

[Port] Update Plotting Documentation

See sbromberger/LightGraphs.jl#1580

[Port] [BUG] `random_configuration_model(n::T, ks::Vector{T})` fails when `T` is not `Int64`

See sbromberger/LightGraphs.jl#1577

[Port] [BUG] Intermittently-failing tests in `Parallel.Closeness`

See sbromberger/LightGraphs.jl#1555

[Port] [BUG] `yen_k_shortest_paths` with `k=2` returns same path twice

See sbromberger/LightGraphs.jl#1505

Common interface for graphs with metadata

Hey!

There has been some talk recently about adding better support for graph metadata, so here's an issue to centralize our discussions. First of all, here are the packages that I'm aware of that deal with vertex- & edge-level attributes:

• https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl
• https://github.com/JuliaGraphs/MetaGraphs.jl
• https://github.com/simonschoelly/SimpleValueGraphs.jl @simonschoelly
• https://github.com/JuliaGraphs/MetaGraphsNext.jl @bramtayl

One idea would be to design a common interface extending AbstractGraph to work with metadata. I'm aware that the four packages above are very different, and that the case of edge weights probably deserves special treatment. On the other hand, agreeing on a common set of names for functions would bring clear benefits:

• User-friendliness would increase significantly, as well as ease of documentation
• Switching between meta-graph implementations would be instantaneous. This is sometimes necessary to improve performance
• Compatibility with downstream packages such as https://github.com/JuliaGraphs/GraphDataFrameBridge.jl would be a non-issue
• The same goes with upstream packages such as https://github.com/JuliaGraphs/GraphIO.jl or https://github.com/JuliaGraphs/SNAPDatasets.jl

As food for thought, here are a few past discussions on this topic:

• https://discourse.julialang.org/t/creating-a-weighted-graph/41241/17
• https://discourse.julialang.org/t/retworkx-new-high-performance-python-graph-library/71109/5

What is your take on this?

1.5 silently dropped julia 1.3 support

If I interpret the logs correctly, it looks like 1.3 isn't supported anymore:
https://github.com/JuliaPlots/Makie.jl/runs/4753606377?check_suite_focus=true#step:6:284
Was this on purpose?

`period` function does not work correctly for abstract directed graphs

Currently the period functions seems to work only for SimpleDiGraph. It should either be restricted to that type or implemented in a way that works with other directed AbstractGraph.

How to reproduce:

julia> using Graphs, SimpleWeightedGraphs

julia> g = cycle_digraph(4)
{4, 4} directed simple Int64 graph

julia> gw = SimpleWeightedDiGraph(g)
{4, 4} directed simple Int64 graph with Float64 weights

julia> period(g)
4

julia> period(gw)
ERROR: MethodError: no method matching difference(::SimpleWeightedDiGraph{Int64, Float64}, ::SimpleDiGraph{Int64})
Closest candidates are:
  difference(::T, ::T) where T<:AbstractGraph at ~/.julia/dev/Graphs/src/operators.jl:196
Stacktrace:
 [1] period(::Type{IsDirected{SimpleWeightedDiGraph{Int64, Float64}}}, g::SimpleWeightedDiGraph{Int64, Float64})
   @ Graphs ~/.julia/dev/Graphs/src/connectivity.jl:503
 [2] period(g::SimpleWeightedDiGraph{Int64, Float64})
   @ Graphs ~/.julia/packages/SimpleTraits/l1ZsK/src/SimpleTraits.jl:331
 [3] top-level scope
   @ REPL[20]:1

[Port] Proposal: relax restriction on vertex IDs

See sbromberger/LightGraphs.jl#1572

[Port] Preserve vertex labels after deleting a vertex

See sbromberger/LightGraphs.jl#1587

[Port] [Contributing] Wilson's, loop erased walks, and normalization constants (Kirchoff/Tutte)

See sbromberger/LightGraphs.jl#1571