Since the weight matrix is actually the transpose of the weight matrix (sbromberger/SimpleWeightedGraphs.jl#65 (comment)), the wrong value is being read in the current implementation:

julia> s = SimpleWeightedDiGraph([1,2,1], [2,1,2], [1,1,1])
{2, 2} directed simple Int64 graph with Int64 weights     

julia> get_weight(s,1,2)
2

Which is wrong because the weight of the Edge 1 => 2 is 1, not 2. This occurs because, get_weight is calling s.weights[2,1]. However, the weights field is not transposed.

The kruskal_mst function may contain some logic that the prim_mst function lacks. When I supply a SimpleWeightedGraph as input, the kruskal_mst function returns a vector of SimpleWeightedEdge. By contrast, the prim_mst function returns a vector of SimpleEdge instead. The behavior of kruskal_mst seems more beneficial, to me. Here is a small example:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.7.1 (2021-12-22)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> using Graphs, SimpleWeightedGraphs

julia> A=[0 7 0 5 0 0 0;0 0 8 0 7 0 0;0 0 0 0 5 0 0;0 0 0 0 18 6 0;0 0 0 0 0 8 9; 0 0 0 0 0 0 11;0 0 0 0 0 0 0]
7×7 Matrix{Int64}:
 0  7  0  5   0  0   0
 0  0  8  0   7  0   0
 0  0  0  0   5  0   0
 0  0  0  0  18  6   0
 0  0  0  0   0  8   9
 0  0  0  0   0  0  11
 0  0  0  0   0  0   0

julia> kruskal_mst(SimpleWeightedGraph(A + A'))
6-element Vector{SimpleWeightedEdge{Int64, Int64}}:
 Edge 1 => 4 with weight 5
 Edge 3 => 5 with weight 5
 Edge 4 => 6 with weight 6
 Edge 1 => 2 with weight 7
 Edge 2 => 5 with weight 7
 Edge 5 => 7 with weight 9

julia> prim_mst(SimpleWeightedGraph(A + A'))
6-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 5 => 3
 Edge 1 => 4
 Edge 2 => 5
 Edge 4 => 6
 Edge 5 => 7

See sbromberger/SimpleWeightedGraphs.jl#56

The laplacian_matrix function for SimpleWeightedDigraph uses dir=:out as default for the dir parameter. This contrasts with the definition in Graphs.jl where dir=:both is the default for directed graphs.

While I may agree that dir=:out could be a saner default, the problem is that the documentation of the function is only present in the Graphs package and mentions that the default is dir=:both for directed graphs. After looking at the doc at the REPL, the user may expect the default to be dir=:both when it is in fact dir=:out for SimpleWeightedDigraph.

See the following example for SimpleWeightedGraphs v1.3.0:

using SimpleWeightedGraphs
using Graphs

g = SimpleWeightedDiGraph(3)
add_edge!(g, 1, 2, 0.5)
get_weight(g, 1, 2) # gives 0.0 instead of 0.5
get_weight(g, 2, 1) # gives 0.5 instead of 0.0

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!

Hi there!

To create a weighted graph we should issue this command: g = SimpleWeightedGraph(sources, destinations, weights). In addition to distance between edges, I want to asign their time also. That is, having a graph that its weight are both distance and time. I only want to do so, because at some point I need to query the time of some edges, and if I on;y construct the graph based on the distances, I cannot find out the time of a specific edge.

So, three questions:
1- Is is possible to have two ways of assigning weights to a graph?
2- Is there any better way?
3- How to iterate ove edges? I did for (i,j) in edges(g) and it did not work, which kind of make sense to me, but I don't know how to iterate.

Thanks!

See sbromberger/SimpleWeightedGraphs.jl#45

See sbromberger/SimpleWeightedGraphs.jl#65

It is unclear how well self-loops are supported in Graphs.jl, but that should not prevent us from supporting them here. For now, I stated in the documentation that they are not properly handled, because of a few issues that were raised over the years and never closed in the original package:

• sbromberger/SimpleWeightedGraphs.jl#38
• sbromberger/SimpleWeightedGraphs.jl#53

What do you think?

See sbromberger/SimpleWeightedGraphs.jl#38

julia> using SimpleWeightedGraphs
julia> g = SimpleWeightedGraph([1,2,1], [2,1,2], [1,1,1]; combine = +)
julia> edges(g)
ERROR: UndefVarError: edges not defined
Stacktrace:
 [1] top-level scope
   @ REPL[3]:1

I'm not sure if I'm doing something wrong (edges seems to be implemented in simpleweightedgraph.jl) but I can't seem to iterate through the edges of a graph.

See sbromberger/SimpleWeightedGraphs.jl#53

At the moment, inneighbors allocates for SimpleWeightedDiGraph (see #14 (comment))

See sbromberger/SimpleWeightedGraphs.jl#71

See this conversation

This seems to be mostly equivalent to a sparse matrix (I mentioned slower access of weights, but using binary search, I think it should be same complexity than for a sparse matrix)
You can get back the sparse matrix by simply:

• collecting the weights in the order found in the adjacency list
• concatenating the outneighbors adjacency lists
• computing the cumulative degrees of the vertices.

As shown in the discussion, the benefit obtained by iterating simultaneously weights and vertices can be also achieved with the sparse matrix implementation, although it seems a bit slower.

The proposed implementation is by storing tuples in the adjacency lists, but it might be better to store in some aside adjacency list to avoid the penalty cost of accessing tuple when considering only neighbors. (we can still zip through both lists at the same time).

At this point, I think the bigger drawback will be the linear cost for generating the weight matrix, all other computations should be asymptotically equivalent.
I think we need some benchmarking to find the best implementation, by considering both the access of a single weight and the access of weights when iterating neighbors.

As of today the repo still uses Travis for CI, is that a problem? I feel like GH Actions are simpler to use.

https://discourse.julialang.org/t/pagerank-for-weighted-graphs-in-julia/101076/4

Description of bug
When creating an edge induced subgraph of a SimpleWeightedGraph with weights different from one, these weights are not preserved. This is in contrast to a vertex induced subgraph, where this works correctly.

How to reproduce
Detail steps to reproduce the behavior.

Expected behavior

julia> g = SimpleWeightedGraph([0 2; 2 0])
{2, 1} undirected simple Int64 graph with Int64 weights

julia> weights(g)
2×2 SparseArrays.SparseMatrixCSC{Int64, Int64} with 2 stored entries:
 ⋅  2
 2  ⋅

# vertex induced subgraph
julia> weights(first(induced_subgraph(g, [1,2])))
2×2 SparseArrays.SparseMatrixCSC{Int64, Int64} with 2 stored entries:
 ⋅  2
 2  ⋅

# edge induced subgraph
julia> weights(first(induced_subgraph(g, [Edge(1,2)])))
2×2 SparseArrays.SparseMatrixCSC{Int64, Int64} with 2 stored entries:
 ⋅  1
 1  ⋅

The entries in the last spare matrix should also be two, but have been set to the default value of 1.

Version information
Julia: v1.8
Graphs.jl: v1.7.4
SimpleWeightedGraphs: v1.2.1

Additional context
src/overrides.jl contains a specialized version of induced_subgraph for vertex lists, but not for edge list - so we probably have to implement that.

I had a distance matrix (in csv format) with 50 million edges that I needed to convert into a SimpleWeightedGraph. My first approach was to construct the graph edge-by-edge using the add_edge!(v1, v2, weight) function, however this approach would have taken hours or even days to complete the graph.

In an effort to quickly compute the graph, I used the SimpleWeightedGraph(sources, destinations, weights) constructor. This approach was able to complete the graph in less than one minute.

I am suggesting a documentation change to address the speed of the add_edge!(v1, v2, weight) function and the constructor.

Thank you,
Alexander

See sbromberger/SimpleWeightedGraphs.jl#42

See sbromberger/SimpleWeightedGraphs.jl#41

Following this Discourse thread, it would be nice to document some essential methods of the package, such as weight(e::SimpleWeightedEdge)
cc @etiennedeg

Is there a reason why get_weight does not take an AbstractEdge as second argument? I see how the AbstractSimpleWeightedEdge is supposed to contain that information, but when I get my edges from some other source, it is a bit strange to always have to write get_weight(g, src(e), dst(e)).

See sbromberger/SimpleWeightedGraphs.jl#64

See sbromberger/SimpleWeightedGraphs.jl#69

See sbromberger/SimpleWeightedGraphs.jl#43

The MWE is modified from the test:

using Graphs, SimpleWeightedGraphs

g = SimpleWeightedGraph(3)
add_edge!(g, 1, 2, 0.5)
add_edge!(g, 2, 3, 0.8)
add_edge!(g, 1, 3, 2.0)
a_star(g, 1, 3)

and the return does not match the actual edge weight

2-element Vector{SimpleWeightedEdge{Int64, Float64}}:
 Edge 1 => 2 with weight 1.0  # should be 0.5
 Edge 2 => 3 with weight 1.0  # should be 0.8

Querying the weight using SimpleWeightedGraphs.weight on the vector returned by a_star would give the default weight 1.0, which can be observed by running SimpleWeightedGraphs.weight(a_star(g, 1, 3)[1]) == 1.0.

I've tried to create a samll graph and was wondering why it does not allow me to assign a weight parameter??

sources = rand(1:6, 10)
destinations = rand( 1:6, 10)
weights = 0.2.*rand(1:6, 10)

g = SimpleWeightedGraph(sources, destinations, weights)

Let's assume I could create a weighted graph, I've read the documentation and didn't find any command to be able to find the distance (or time--if it weighted based on time) between two nodes. Do you aware of any?

Thanks a lot for the package!

Hi all,

When I want to create a graph out of an excel file, the Julia returns an Error ArgumentError: row indices I[k] must satisfy 1 <= I[k] <= m

Net_data_file = "C:/Data/Network.csv"
Net_df        = CSV.read(joinpath(Net_data_file), DataFrames.DataFrame)

start_node = Net_df.from
end_node   = Net_df.tos
distance   = Net_df.distance
time       = Net_df.speed

g = SimpleWeightedDiGraph(start_node, end_node, distance)

Is there any command that would fix it?