Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
  • Dec 05 04:35
    Palladinium edited #523
  • Dec 05 04:35
    Palladinium opened #523
  • Dec 03 20:13
    fgvieira commented #299
  • Nov 26 07:55
    TheButlah commented #324
  • Nov 26 07:55
    TheButlah commented #324
  • Nov 26 07:36
    TheButlah commented #324
  • Nov 16 16:48
    fgvieira opened #522
  • Nov 04 18:07
    NickHu opened #521
  • Nov 02 16:47
    barkincavdaroglu opened #520
  • Oct 30 10:18
    donRumata03 opened #519
  • Oct 29 16:06
    starovoid closed #473
  • Oct 26 10:32
    NickHu synchronize #480
  • Oct 26 10:31
    NickHu synchronize #480
  • Oct 13 21:06
    jonesmartins opened #518
  • Oct 11 03:55
    chaosprint commented #370
  • Oct 09 14:08
    teuron closed #375
  • Oct 09 14:08
    teuron synchronize #375
  • Oct 09 14:02
    teuron synchronize #375
  • Oct 09 00:58
    jianshu93 opened #517
  • Oct 08 20:45
    jujhar16 opened #516
Anton Kochkov
@XVilka
Congratulations!
Good job :thumbsup:
bluss
@bluss:matrix.org
[m]
thanks @aborgna, that's cool
mako yass
@makoConstruct

Howdy, I had an idea, wondering if this is a thing or if anyone could say it's not worth trying:
Would it improve performance to sort the vertices in a CSR graph according to a large number of small, count limited breadth-first searches, for instance, where each one starts at random origins then goes out for a few steps until it's covered enough vertices to fill a cache line. This would make it so that more vertices than usual would end up being close in memory to their immediate neighbor vertices.

This might improve cache coherence a bit, in some cases (and workloads) it could improve it a lot, for instance, you had a part of the graph that was long chain of vertices (each degree 2), in that case they'd all end up being arranged in the vertex array to be in exactly the same sequence as they are in the chain. I'd expect it to work pretty well for directed tree-shaped graphs too.

1 reply
aborgna
@aborgna:matrix.org
[m]
Hi! That's an intriguing idea :) Do you know if it has been explored elsewhere?
I'm away from my pc these days, but it would be fun to experiment a bit with it and some benchmarks.
mako yass
@makoConstruct
I do not know. It had a glance around and couldn't see anything, although I vaguely remember seeing mention, somewhere, of sorting vertices according to a single breadth first search. Which seems like it would only help cache adjacency for the chosen root vertex, and by keeping edges with the same origin vertex together
Anton Kochkov
@XVilka
I just thought, we could attract more users and contributors to petgraph if allow the integration with nascent Rust ML frameworks for the GNN (Graph Neural Networks or Geometrical Neural Networks). Good example is how it's done in Julia:
  • There is a popular FluxML machine and deep learning framework for Julia
  • There is a GeometricFlux.jl library for FluxML that allows to build GNN on top of the JuliaGraphs
  • There is a JuliaGraphs framework which is very popular in Julia community.
Wojciech Niedźwiedź
@Niedzwiedzw
heyy
I have a tree structure
a pointer map to be exact
I have succesfully built it but now I'd like to list all the possible paths from root to end
John Austin
@Kleptine
A question came up while working on a new graph implementation:
  • Why is petgraph::Direction repr(usize)?
bluss
@bluss:matrix.org
[m]
@Kleptine: Probably an old decision that can be revisited. The reason is that because it is used as an index (something[direction as usize]).
Wojciech Niedźwiedź
@Niedzwiedzw
my question still stands :(
still haven't solved it
mako yass
@makoConstruct
@Niedzwiedzw Hopefully this is enough to explain it but something like this would work:
struct BackLink { node:node, back:Option<Rc<BackLink>> }
fn consider(this:node, coming_from:Option<Rc<BackLink>>, puts_results:&mut Vec<Vec<node>>) { ... }
where consider is a recursive function that, when it reaches an end (a node that has no neighbors aside from the one in the backlink), uses the backlinks to assemble the path, which it then puts in puts_results. consider is called on the root node, and once that call returns, all of the paths will be listed in puts_results.
I can report to this chat that I've implemented CSR++, a concurrent, mutable version of CSR. You can find the repo of you really want to but I wont link it until it's non-horrible.
alex
@alex:memoryandthought.me
[m]
Hey folks, I need to traverse a DAG topologically but with the ability to prune as I go. Specificaly, if a particular node doesn't match a condition I want to discard it and all of it's children. Is there any equivalent of visit::depth_first_search for topological traversals?
mako yass
@makoConstruct
What are the methods for constructing a Csr? They seem inadequate. I came across from_sorted_edges, the problem with this is that there's no way to get it to build nodes that have no edges. Unless you're using reflexive edges to mean that (haven't looked at the code), but some people need actual reflexive edges, so I hope it doesn't work like that.
In my CSR++ implementation, the construction function signature is from_iters(nodes: impl Iterator<Item=(K, V)>, edges: impl Iterator<Item=(K,K,E)>);
(K is an external key, distinct from the nodes' internal index. V is node weights and E is edge weights.)
mako yass
@makoConstruct
Alright, here it is https://github.com/makoConstruct/graph_shrine
Basically, it's CSR but segmented and more amenable to edits.
Egor Starovoitov
@PrototypeRailGun
Hi! I recently created pull-request #468, but it failed the Rustfmt check. Can you tell me what I should fix in order to pass this test?
aborgna
@aborgna:matrix.org
[m]
Hi, it seems there are some whitespace & import ordering issues. You can fix them automatically with cargo fmt
Egor Starovoitov
@PrototypeRailGun
Thanks!
highway900
@highway900
Hi everyone! I would like to collect all the connected components into different subgraphs (e.g. to find largest connected component), I have had a look inside connected_componentsat UnionFindbut I am honestly a bit lost how I might achieve this. Am I going the right direction with the api? Is there another or better way to achieve this?
bluss
@bluss:matrix.org
[m]
@highway900: I guess it's algorithmically overkill, but wouldn't kosaraju_scc give you all connected components for an undirected graph
highway900
@highway900
@bluss:matrix.org thanks.
Egor Starovoitov
@PrototypeRailGun
Hi! What do you think about algorithms for calculating bridges and articulation points of simple undirected graphs? I would like to add these algorithms to petgraph.
mako yass
@makoConstruct
This message was deleted
@PrototypeRailGun I'm very interested in those. I'm probably going to need them for identifying key landmarks in my web of trust DB. What's the distinction between bridges and articulation points?
Egor Starovoitov
@PrototypeRailGun
@makoConstruct Bridge is an edge, the removal of which leads to an increase in the number of connectivity components, and an articulation point is a vertex with a similar property. I am glad that you are interested in these algorithms, and I will start implementing them soon.
mako yass
@makoConstruct
ah right
mako yass
@makoConstruct
I guess I'd only need articulation points
highway900
@highway900

I have an issue which is likely my fault but I cannot figure out. When using extend_with_edges or from_edges I get different behavior from seemingly the same type...

    let edges_from_collect = edges
        .iter()
        .map(|(x, y)| (*x as i32, *y as i32))
        .collect::<Vec<(i32, i32)>>();
    let edges_vec = vec![(0, 1), (1, 2)];
    let edges_array = &[(0, 1), (1, 2)];

    let mut g0 = UnGraph::<i32, f64>::from_edges(edges_vec);
    let mut g1: UnGraph<i32, f64> = UnGraph::new_undirected();
    g1.extend_with_edges(edges_from_collect);

In this example edges is simply a vec of (usize, usize) (maybe not and ideal cast but serves for this example)
The problem is that both extend_with_edges or from_edgeswill not work when I use my constructed vec from the collect the resulting types from both edges_from_collect and edges_vec is by my understanding the same Vec<(i32, i32)>, yet rust complains that the traitFrom<i32>is not satisfied when I useedges_from_collect. The explicitedges_vec` work no problem...? What am I missing here? Cheers.

highway900
@highway900
I am encountering a stack overflow issue when using tarjan_scc on a graph with >210000 nodes. One of the islands I'm assuming the largest (not sure of this size yet) causes the stack overflow. Is this a known limitation? I noticed that f in this case is of type &[usize] and it looks like the stack overflow is caused here.
 let mut _tscc = TarjanScc::new();
 _tscc.run(self, |f| {
     println!("{:?}", f.len());
 });
chaosprint
@chaosprint:matrix.org
[m]
hey guys, I am curious how is it going with the no_std pr. I found it on the gh repo for a while.
aborgna
@aborgna:matrix.org
[m]
Hi. I pushed a change to fix support for rust 1.41.
indexmap 1.8 dropped support for it, and because it was a minor semver bump cargo picked it anyway.
It's probably a good idea to bump our MSRV in the next release, but for now I'll publish a 0.6.1 hotfix with this
Btw I've been missing this last time because I'm writing my phd thesis, and I'll probably continue like that until July :/
aborgna
@aborgna:matrix.org
[m]
:point_up: Edit: It's probably a good idea to bump our MSRV in the next release, but for now I'll publish a 0.6.1 hotfix with the fix
bluss
@bluss:matrix.org
[m]

I'm sorry, yeah it's not easy to know how to handle growing Rust versions. indexmap by itself is also tracking hashbrown's new releases.

that sounds great aborgna best of luck with the thesis :)

Vince Knight
@drvinceknight
Hello, can I ask if there is any guidance available about citing petgragph?
iouae
@iouae
Hello there. Looking for an adequate way to update all current edges on in-memory graph. Instead of using iteration along all edges one per one, replace old weights with new ones per single action. Any thoughts?
David
@yenicelik
hey guys, im wondering if it's possible to filter out all nodes with a certain degree (degree 1), from the graph?
dougpowers
@dougpowers
I'm having issues compiling petgraph 0.6.2 on WSL2 Debian. It's complaining that IndexGraph and IndexSet are both short one generic argument. It compiles fine on Windows, so I'm a little lost.
1 reply
cwfitzgerald
@cwfitzgerald:matrix.org
[m]
Hey! Are petgraph::StableGraph's edges kept in insertion order - i.e. if I add a bunch of directed edges away from node A, when I iterate the edges will I get them back in the same order I added them?
cwfitzgerald
@cwfitzgerald:matrix.org
[m]
I believe the answer is yes - the edges seem to form a linked list of all edges added to the node
aborgna
@aborgna:matrix.org
[m]
cwfitzgerald: The edges are iterated in index order. Since StableGraph preserves the indices, new additions may come before older edges if there are available holes:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=4c799bd7a4cc0642dffbc49b5bbd8c60
1 reply
cwfitzgerald
@cwfitzgerald:matrix.org
[m]
aborgna: just expanded the example - it seems to always be inverse insertion order? https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=d3dc35565f028912087719465f2a7439