Edge-weighted graphs compatible with Graphs.jl.
See the documentation for a tutorial.
Edge-weighted graphs compatible with Graphs.jl
Home Page: http://juliagraphs.org/SimpleWeightedGraphs.jl/
License: Other
Edge-weighted graphs compatible with Graphs.jl.
See the documentation for a tutorial.
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
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!
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:
What do you think?
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.
At the moment, inneighbors
allocates for SimpleWeightedDiGraph
(see #14 (comment))
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:
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.
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
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))
.
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?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.