Graph data structure library for Rust.

Overview

petgraph

Graph data structure library. Supports Rust 1.41 and later.

Please read the API documentation here

build_status crates gitter

Crate feature flags:

  • graphmap (default) enable GraphMap.
  • stable_graph (default) enable StableGraph.
  • matrix_graph (default) enable MatrixGraph.
  • serde-1 (optional) enable serialization for Graph, StableGraph using serde 1.0. Requires Rust version as required by serde.

Recent Changes

See RELEASES for a list of changes. The minimum supported rust version will only change on major releases.

License

Dual-licensed to be compatible with the Rust project.

Licensed under the Apache License, Version 2.0 http://www.apache.org/licenses/LICENSE-2.0 or the MIT license http://opensource.org/licenses/MIT, at your option. This file may not be copied, modified, or distributed except according to those terms.

Comments
  • Add adjacency matrix implementation

    Add adjacency matrix implementation

    Equivalent to #120, implements #28.

    This pull-request adds a MatrixGraph structure which implements all graph traits using a dense adjacency matrix for its underlying structure.

    The matrix itself is represented as a flat array where each entry is an edge. The size of the array varies, depending on the graph being directed (~V^2) or undirected (V*(V+1)/2). See below for more details.

    Directed Graph:

    Layout is a flattened 2D array, where (i, j) maps to an array index i * capacity + j.

     0  1  2  3
     4  5  6  7
     8  9 10 11
    12 13 14 15
    

    The node capacity is greater than the number of nodes, and is maintained to a power of two, reducing the number of resizes that need to happen as they involve O(V) buffer copies.

    Undirected Graph:

    Layout is a lower triangular matrix, where the array indices are mapped like this:

    0
    1 2
    3 4 5
    6 7 8 9
    

    Resizing this type of matrix is at worst a Vec resize.

    Traits:

    • [x] Default
    • [x] Clone
    • [x] GraphBase
    • [x] GraphProp
    • [x] IntoNeighborsDirected
    • [x] IntoNodeIdentifiers
    • [x] IntoNodeReferences
    • [x] IntoNeighbors
    • [x] IntoEdges
    • [x] IntoEdgeReferences
    • [x] Visitable
    • [x] GetAdjacencyMatrix
    • [x] NodeCount
    • [x] NodeIndexable
    • [x] NodeCompactIndexable
    • [x] Data
    • [x] Build

    Questions:

    • [x] Any suggestions for better naming are welcome. ~Maybe something like AdjacencyMatrixGraph would work? (Although it is much more verbose.)~ Settled on MatrixGraph.

    Misc:

    • Edge weights are directly stored in the matrix, which whould probably appear clearly in the doc because the underlying array could get quite large if the user isn't careful.
    • Parallel edges are not supported but aren't too difficult to support, although the iterators are a bit tricky to get right.
    • To support the Build trait, the add_node impl method should return an Option<NodeIndex>, returning None if the edge already exists, as parallel edges aren't currently supported. This is entirely feasible and I'll get to this when I have some time on my hands, but that may not be before closing this PR.
    opened by jmcomets 23
  • Add A* pathfinding algorithm

    Add A* pathfinding algorithm

    Summary

    I've written the current A* to return the full path from start to finish, unlike the Dijkstra that simply computes all costs, stopping if the goal is found. Additionally, I could add in the computed cost of the path.

    I've added a test that validates a basic usage, although there should be a proof that the heuristic drives the pathfinding.

    Performance-wise, the tracking of previous nodes to later rebuild the path from start to finish adds on the Dijkstra's performance cost, otherwise it's roughly equivalent.

    Sidenotes

    Some work could be done to allow more flexibility in terms of data-structures used by the algorithm, as it currently requires that node IDs be Eq + Hash when we could have another version only requiring Ord which would use trees instead of hashmaps.

    Questions

    • [x] Should the path returned be the list of node IDs or the actual edge IDs?
    • [x] Should the pathfinding algorithms be reworked to share some common "flexible" interface?
    • [ ] Should there be bench tests on the A* vs the Dijkstra when H(x) = 0 to measure the cost of tracking the path?

    (fixes #138)

    opened by jmcomets 18
  • Some thoughts and ideas related to Graph.

    Some thoughts and ideas related to Graph.

    During my use of Graph in dsp-chain I've run into a few issues for which there don't yet seem to be any easy work-arounds and often I find myself resorting to unsafe code when there is probably a nicer solution possible within Graph's API. Most instances revolve around gaining simultaneous mutable access to multiple different nodes/edges at once. Just thought I'd share some of these issues along with some thoughts and ideas on how they might be addressed.

    Access to incoming edges

    I've noticed that Graph provides two main methods for iterating over edges of a given node:

    • edges: provides an iterator over the outgoing edges paired with their respective node indices.
    • edges_both: provides an iterator over all edges paired with their respective node indices.

    Here are some thoughts that came to mind:

    • Perhaps edges could take a Direction argument so that a user may iterate over either direction, rather than only Outgoing?
    • Perhaps it would be useful to provide edges_mut and edges_both_mut variations?
    • Maybe edges_undirected (instead of edges_both) would be more consistent with neighbors_undirected and find_edge_undirected?

    Simultaneous mutable access to a node and its edges.

    There are a few variations on this problem, the two that I've run into are:

    • Needing both mutable access to a node weight and immutable access to its incoming edge weights simultaneously.
    • Needing both immutable access to a node weight and mutable access to its outgoing edge weights simultaneously.

    The exact use case within dsp-chain is: (during a reverse dfs) each node must be able to read from each of its incoming edge's buffers so that it may sum them to its own buffer. Once it has rendered its own buffer, it then writes the result to each of its outgoing edges' buffers. This must all be achieved without allocating any new intermediate buffers.

    In the API's current state I'm unsure of how to get around this without unsafe code. I imagine it should be possible to expose a safe interface to this use-case so that the above examples look something like:

    // Mutable access to a node weight and immutable access to its incoming edge weights simultaneously.
    graph.node_mut_with_edges(node_idx, pg::Incoming, |node_weight_mut, edge_weights| {
        for edge_weight in edge_weights {
            // do stuff with node_weight_mut and edge_weight....
        }
    })
    
    // Immutable access to a node weight and mutable access to its outgoing edge weights simultaneously.
    graph.node_with_edges_mut(node_idx, pg::Outgoing, |node_weight, edge_weights_mut| {
        for edge_weight_mut in edge_weights_mut {
            // do stuff with node_weight and edge_weight_mut...
        }
    });
    

    Pair indexing

    It would be nice to be able to index into the graph twice at once, i.e. perhaps by allowing indexing the Graph with tuples.

    let (a_weight, b_weight) = &mut graph[(a, b)];
    

    I noticed that you have a private index_twice function in the graph module already - perhaps there's a reason you've avoided exposing it? I guess one problem with this is that the returned references are always either 1. both immutable or 2. both mutable, without exposing an option for combinations of the two.

    Anyway, apologies for the lengthy issue! These are currently things I'm dodging with unsafe, but just thought I'd come to the source, share my experience and perhaps land a nicer solution closer to home - let me know your thoughts when you get a chance :) Also, if there are already nice solutions to any of the above that I might have missed, please feel free to share!

    opened by mitchmindtree 18
  • attempt to clarify index documentation

    attempt to clarify index documentation

    It seemed to be that "Send and Sync" safety isn't directly particularly related to the use of indices, so I moved that up. It's true that "The Graph is a regular rust collection" is saying that it has indices, but this seemed like a reasonable overview for the introductory section.

    On first reading, I wondered if "Pros and Cons of Indices" was about this particular Graph (as opposed to other kinds of graphs in the crate). After I re-read a few times, I realized this was an attempt to draw attention to when you would or would not want to use indices. I've adjusted the section headings and some formatting, which I think makes it more clear.

    opened by ultrasaurus 15
  • Use a double linked list for free nodes in stable_graph

    Use a double linked list for free nodes in stable_graph

    Fixes #412. The previous implementation of extend_with_edges was copied directly from graph and misbehaved.

    In a stable graph the function may have to create nodes corresponding to previously-deleted indices. To do that it has to remove the node from the free_node list, and doing that would have required traversing the list to find the previous node in the chain and modify the pointers.

    Instead, I upgraded the free_node list to a doubly linked list using the unused "input edge" field in node.next[1] for the backwards pointer, in addition to the existing forward pointer in node.next[0]. This allows for removing nodes from the free_node list in constant time.

    The drawback of this are the additional node indexing operation required each time we have to update the backwards pointer, but I compared the benchmarks and saw no significant difference.

    Benchmark comparison
    name                                       master ns/iter  fix ns/iter  diff ns/iter  diff %  speedup
    add_100_edges_to_self                      406             400                    -6  -1.48%   x 1.01
    add_100_nodes                              18,629          19,368                739   3.97%   x 0.96
    add_5_edges_for_each_of_100_nodes          1,003           995                    -8  -0.80%   x 1.01
    add_adjacent_edges                         26,117          26,150                 33   0.13%   x 1.00
    add_edges_from_root                        26,115          26,305                190   0.73%   x 0.99
    bench_add_edge                             381             381                     0   0.00%   x 1.00
    bench_inser                                4               4                       0   0.00%   x 1.00
    bench_remove                               167             167                     0   0.00%   x 1.00
    bigger_edges_in                            34              34                      0   0.00%   x 1.00
    bigger_edges_out                           37              37                      0   0.00%   x 1.00
    bigger_neighbors_in                        34              34                      0   0.00%   x 1.00
    bigger_neighbors_out                       31              31                      0   0.00%   x 1.00
    bigger_sccs                                4,888           4,923                  35   0.72%   x 0.99
    connected_components_full_dir_bench        545             545                     0   0.00%   x 1.00
    connected_components_full_undir_bench      353             352                    -1  -0.28%   x 1.00
    connected_components_petersen_dir_bench    256             256                     0   0.00%   x 1.00
    connected_components_petersen_undir_bench  202             189                   -13  -6.44%   x 1.07
    connected_components_praust_dir_bench      766             736                   -30  -3.92%   x 1.04
    connected_components_praust_undir_bench    426             455                    29   6.81%   x 0.94
    dijkstra_bench                             1,668,548       1,662,203          -6,345  -0.38%   x 1.00
    full_edges_default                         7               7                       0   0.00%   x 1.00
    full_edges_in                              13              13                      0   0.00%   x 1.00
    full_edges_in                              7               7                       0   0.00%   x 1.00
    full_edges_out                             12              12                      0   0.00%   x 1.00
    full_edges_out                             20              20                      0   0.00%   x 1.00
    full_iso_bench                             1,210           1,209                  -1  -0.08%   x 1.00
    full_neighbors_in                          13              13                      0   0.00%   x 1.00
    full_neighbors_out                         12              12                      0   0.00%   x 1.00
    full_sccs                                  935             935                     0   0.00%   x 1.00
    graph_map                                  192             194                     2   1.04%   x 0.99
    is_cyclic_undirected_full_dir_bench        63              65                      2   3.17%   x 0.97
    is_cyclic_undirected_full_undir_bench      63              65                      2   3.17%   x 0.97
    is_cyclic_undirected_petersen_dir_bench    103             105                     2   1.94%   x 0.98
    is_cyclic_undirected_petersen_undir_bench  116             117                     1   0.86%   x 0.99
    is_cyclic_undirected_praust_dir_bench      99              101                     2   2.02%   x 0.98
    is_cyclic_undirected_praust_undir_bench    98              99                      1   1.02%   x 0.99
    k_shortest_path_bench                      6,097,948       6,110,103          12,155   0.20%   x 1.00
    min_spanning_tree_full_dir_bench           317             328                    11   3.47%   x 0.97
    min_spanning_tree_full_undir_bench         213             225                    12   5.63%   x 0.95
    min_spanning_tree_petersen_dir_bench       164             173                     9   5.49%   x 0.95
    min_spanning_tree_petersen_undir_bench     126             141                    15  11.90%   x 0.89
    min_spanning_tree_praust_dir_bench         327             331                     4   1.22%   x 0.99
    min_spanning_tree_praust_undir_bench       209             215                     6   2.87%   x 0.97
    neighbors_default                          7               7                       0   0.00%   x 1.00
    neighbors_in                               8               8                       0   0.00%   x 1.00
    neighbors_out                              5               5                       0   0.00%   x 1.00
    petersen_iso_bench                         937             942                     5   0.53%   x 0.99
    petersen_undir_iso_bench                   709             698                   -11  -1.55%   x 1.02
    praust_dir_no_iso_bench                    728,082         721,312            -6,770  -0.93%   x 1.01
    praust_undir_no_iso_bench                  746,227         747,843             1,616   0.22%   x 1.00
    sccs_graph                                 2,211           2,288                  77   3.48%   x 0.97
    sccs_stable_graph                          2,119           2,113                  -6  -0.28%   x 1.00
    stable_graph_map                           242             240                    -2  -0.83%   x 1.01
    stable_graph_retain_edges                  245             245                     0   0.00%   x 1.00
    stable_graph_retain_nodes                  41              41                      0   0.00%   x 1.00
    
    opened by ABorgna 14
  • Add a versatile dfs visitor

    Add a versatile dfs visitor

    See also http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/depth_first_search.html

    DFS(G)                                      -                                     
      for each vertex u in V                    -                                 
        color[u] := WHITE                       initialize vertex u               
        p[u] = u                                -                                 
      end for                                   -                                 
      time := 0                                 -                                 
      if there is a starting vertex s           -                                 
        call DFS-VISIT(G, s)                    start vertex s                    
      for each vertex u in V                    -                                 
        if color[u] = WHITE                     -                                 
          call DFS-VISIT(G, u)                  start vertex u                    
      end for                                   -                                 
      return (p,d_time,f_time)                  -                                 
                                                -                                 
    DFS-VISIT(G, u)                             -                                 
      color[u] := GRAY                          discover vertex u                 
      d_time[u] := time := time + 1             -                                 
      for each v in Adj[u]                      examine edge (u,v)                
        if (color[v] = WHITE)                   -                                 
          p[v] = u                              (u,v) is a tree edge              
          call DFS-VISIT(G, v)                  -                                 
        else if (color[v] = GRAY)               -                                 
          ...                                   (u,v) is a back edge              
        else if (color[v] = BLACK)              -                                 
          ...                                   (u,v) is a cross or forward edge  
        ...                                     -                                 
      end for                                   finish edge (u,v)                 
      color[u] := BLACK                         -                                 
      f_time[u] := time := time + 1             finish vertex u                   
    
    
    enhancement help wanted 
    opened by bluss 14
  • is_isomorphic/is_isomorphic_matching stack overflows on large graphs.

    is_isomorphic/is_isomorphic_matching stack overflows on large graphs.

    I couldn't figure out how to replicate other than to use my crate Chelone. I have a binary in the crate that checks the equality of two Turtle documents. This implementation hashes the RDF graph converts into a Graph and calls algo::is_isomorphic. Using the test/data/manifest.ttl file which is a large file containing 4344 nodes and 2172 edges.

    Steps To Reproduce

    cargo run --bin is_equal tests/data/manifest.ttl tests/data/manifest.ttl
    

    Actual Results

    thread 'main' has overflowed its stack
    fatal runtime error: stack overflow
    [1]    5969 abort      cargo run --bin is_equal tests/data/manifest.ttl tests/data/manifest.ttl
    

    Expected Results

    To not stack overflow.

    bug 
    opened by XAMPPRocky 13
  • IntoNodeIdentifiers/References is bounded on immutable refs in NodeFiltered

    IntoNodeIdentifiers/References is bounded on immutable refs in NodeFiltered

    https://docs.rs/petgraph/0.4.4/petgraph/visit/struct.NodeFiltered.html

    For example, the following fails if tree: &mut StableGraph<_, usize>, but works if tree: &StableGraph<_, usize>:

    let end_index = EdgeIndex::<u32>::end();
    
    let dead_leaf_inds: Vec<_> = NodeFiltered::from_fn(tree, |node_ind| {
        tree.edges_directed(node_ind, Outgoing)
            .any(|edge_ref| edge_ref.id() == end_index)
      }).node_identifiers().collect();
    

    Error:

    no method named `node_identifiers` found for type `petgraph::visit::NodeFiltered<&mut petgraph::prelude::StableGraph<_, usize>, [[email protected]:265:52: 268:4 tree:_, end_index:_]>` in the current scope
    the method `node_identifiers` exists but the following trait bounds were not satisfied: `petgraph::visit::NodeFiltered<&mut petgraph::prelude::StableGraph<_, usize>, [[email protected]:265:52: 268:4 tree:_, end_index:_]> : petgraph::visit::IntoNodeIdentifiers`, `&mut petgraph::prelude::StableGraph<_, usize> : petgraph::visit::IntoNodeIdentifiers`
    

    Is there any reason why the tree ref needs to be immutable here?

    opened by ghost 12
  • Transitive reduction of directected acyclic graphs

    Transitive reduction of directected acyclic graphs

    Here is an implementation of the transitive reduction and closure of directed acyclic graphs. The source of the algorithm is On the calculation of transitive reduction-closure of orders by Habib, Morvan and Rampon.

    Scope

    The fact that it is limited to directed acyclic graphs is "normal" because transitive reduction is not well defined on graphs with a cycle. You can still define a set of minimal transitive reductions on cyclic graphs, though, and to obtain one, the algorithm is as follows:

    • condense the graph
    • on each scc component, an algorithm exists in linear time to compute a reduction
    • use the algorithm of the implemented in this PR on the condensation
    • combine the results of the two above steps in a transitive reduction of the original graph.

    Therefore, if someone wants to extend petgraph to have transitive reduction for all directed graphs, then this algo will likely be reused and this is not a waste of time.

    Why is the PR so big ?

    The algorithm needs a very specific data structure: an adjacency list where the nodes and each successor lists are toposorted. Practically speaking, this means that you have to copy the graph to sort it, so the size of the copy should be a small as possible. (Same apply for the result) So I added a new graph datastructure, adj::List which is just an adjacency list (only successors, no predecessors, like Graph). I implemented all the traits I could for this data structure, and this is why the pull request is so big.

    Why are there no node weights on adj::List ?

    I have been bitten several times in the past by the following "shortcoming" of petgraph: I want to use EdgeFiltered on a graph to visit it, but also change the node weights while visiting it. But creating an EdgeFiltered borrows the graph, so it is impossible. The underlying problem is that one cannot borrow the weights separately from the nodes. For the case of adj::List, I thought we could add something like

    impl<N, E, W, Ix:IndexType> DataMap for (W, List<E, Ix>)
    where W: Index<Ix, Output = N> {
    ...
    }
    

    ie you carry the graph and node weights separately, but by the magic of traits, a pair of these can be used as a fully-fledged graph.


    The PR is in good shape, but some small things could get some improvements. I would like you to confirm your interest in this work before I invest more time in it, though.

    opened by symphorien 11
  • (Stable)Graph are not PartialEq

    (Stable)Graph are not PartialEq

    Because Node and Edge are not PartialEq, it is not possible to compare graphs straightforwardly, as far as I know. I assume common traits aren’t implemented for Node and Edge because it would limit the genericity of the weight types (related, @bluss in https://github.com/bluss/petgraph/issues/37#issuecomment-250997896). What would be required (e.g., Rust features, code in this crate, library user code, etc.) to support PartialEq (Stable)Graph values?

    opened by sanmai-NL 11
  • Pub edges_undirected

    Pub edges_undirected

    This PR makes Graph::edges_undirected and StableGraph::edges_undirected public. I didn't find any reason that they are private. Also modified misleading doc on edges to match its actual behavior.

    opened by zimond 10
  • Status of this crate

    Status of this crate

    First, thanks for the amazing library, I really appreciate your hard work!

    What is the status of this crate from the maintainers' POV? The last issue that has been commented/closed by maintainers is #497, which was 6 months ago, and that issue had a PR sent with it. Other questions/reports in issues haven't been answered by then. I know that you're not obliged to answer everything that's going on in issues, but at least confirming bug reports and responding to feature requests can be helpful for the issue authors.

    opened by m-spitfire 2
  • The trait bounds in `extend_with_edges` (`From<Dummy>` is not implemented for `NodeIndex`)

    The trait bounds in `extend_with_edges` (`From` is not implemented for `NodeIndex`)

    Test Case

    use petgraph::graph::Graph;
    use petgraph::dot::{Dot, Config};
    
    #[derive(Copy, Clone, Debug, Default)]
    struct Dummy(usize);
    
    fn main() {
        let d1 = Dummy(1);
        let d2 = Dummy(2);
        let d3 = Dummy(3);
        let d4 = Dummy(4);
        let mut graph = Graph::<Dummy, ()>::new();
    
        graph.extend_with_edges(&[(d3, d1), (d3, d2), (d1, d4)]);
    
        println!("{:?}", Dot::with_config(&graph, &[Config::EdgeNoLabel]));
    }
    

    Steps To Reproduce

    Just run the above example: Playground

    Actual Results

    error[[E0277]](https://doc.rust-lang.org/stable/error-index.html#E0277): the trait bound `NodeIndex: From<Dummy>` is not satisfied
        --> src/main.rs:14:29
         |
    14   |     graph.extend_with_edges(&[(d3, d1), (d3, d2), (d1, d4)]);
         |           ----------------- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `From<Dummy>` is not implemented for `NodeIndex`
         |           |
         |           required by a bound introduced by this call
         |
         = help: the trait `From<Ix>` is implemented for `NodeIndex<Ix>`
         = note: required for `Dummy` to implement `Into<NodeIndex>`
    note: required by a bound in `Graph::<N, E, Ty, Ix>::extend_with_edges`
        --> /playground/.cargo/registry/src/github.com-1ecc6299db9ec823/petgraph-0.6.2/src/graph_impl/mod.rs:1332:51
         |
    1332 |         <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
         |                                                   ^^^^^^^^^^^^^^^^^^^ required by this bound in `Graph::<N, E, Ty, Ix>::extend_with_edges`
    

    Expected Results

    The documentation for extend_with_edges says that the nodes are inserted automatically to match the edges. But above example doesn't compile due to trait bounds. However when you insert nodes beforehand the extend_with_edges compiles fine and correct:

    use petgraph::graph::Graph;
    use petgraph::dot::{Dot, Config};
    
    #[derive(Copy, Clone, Debug, Default)]
    struct Dummy(usize);
    
    fn main() {
        let d1 = Dummy(1);
        let d2 = Dummy(2);
        let d3 = Dummy(3);
        let d4 = Dummy(4);
        let mut graph = Graph::<Dummy, ()>::new();
    
        let n1 = graph.add_node(d1);
        let n2 = graph.add_node(d2);
        let n3 = graph.add_node(d3);
        let n4 = graph.add_node(d4);
        graph.extend_with_edges(&[(n3, n1), (n3, n2), (n1, n4)]);
    
        println!("{:?}", Dot::with_config(&graph, &[Config::EdgeNoLabel]));
    }
    

    I'm sorry if I misunderstood any trait bounds for the function, I tried to understand the core of petgraph by reading the source code, but I was lost during the process.

    opened by m-spitfire 0
  • Algorithm Artifacts & Playback Functionality

    Algorithm Artifacts & Playback Functionality

    I am currently experimenting with algorithms for VLSI placement and routing. Along with them I am developing an application that lets me visualise the algorithm's progress

    https://user-images.githubusercontent.com/20277283/208407991-14cca304-1ea7-416d-9c91-2deaabec9229.mp4

    The yellow nodes represent nodes in the open set and the red nodes represent nodes in the closed set (A* algorithms). The olive nodes are the path solution.

    The way I am able to achieve this is by returning a Vector<StackItem>

    where StackItem is defined as:

    pub enum StackItem<T: GridNode>{
        Add(GridNodePosition, T),
        Remove(GridNodePosition, T),
        Move(GridNodePosition, GridNodePosition, T),
        BatchAdd(HashMap<GridNodePosition, T>),
        BatchRemove(HashMap<GridNodePosition, T>),
    }
    

    This allows me to visualise not only the path but also any algorithm artifacts and makes debugging very easy. The other thing I can do is I can play back and forth the solution and in the future I want to add the functionality to manually modify parts of the solution and rerun the routing algorithm from that partial solution

    I would love to use petgraph but I don't want to lose the functionality I already implemented. Would this be something that you would interested seeing in petgraph as well. I am happy to spearhead the effort if you are willing to accept the a merge request!

    opened by giannissc 0
  • Feature request: reverse() for [Di]GraphMap

    Feature request: reverse() for [Di]GraphMap

    Summary

    DiGraph.reverse() is nice in some situations; being able to do DiGraphMap.reverse() would be great when the node identities are more complex (e.g. Point's rather than indices).

    Motivation

    What does adding this feature enable that isn't possible without it?

    It avoids manually extracting the edges, reversing their endpoints and creating a new graph.

    Does it improve performance?

    Perhaps, if it can be done more efficiently.

    Turn dynamic checks into statically enforced properties?

    No.

    Explain why this feature should be implemented.

    Details

    • What code needs to change? New traits? Which modules?

    • Is this a new graph algorithm? Include links to papers, Wikipedia, or other implementations of this algorithm that exist.

    • Are you willing to implement this yourself? Mentor someone else and help them implement it?

    Perhaps, certainly if the trivial obvious version is sufficient.

    opened by rbtcollins 0
  • Question: astar heuristic function

    Question: astar heuristic function

    Hi there, I'm new to Rust programing and petgraph... I'm trying to implement a program that emulates google maps path search and I'm having some problems trying to implement the heuristic function into astar. I read these examples:

    • https://timothy.hobbs.cz/rust-play/petgraph_review.html
    • https://docs.rs/petgraph/latest/petgraph/algo/astar/fn.astar.html

    But in any of these examples there is an heuristic function example that use a function that satisfy my needs. So I decided to implement and impl class than can be use as an heuristic function.... But... when i tried to run it, the compiler throw an error that say that it need a function not a method.

    Can anyone help me understanding how to implement this type of heuristic function in a properly way?

    My code:

    use petgraph::graph::Graph;
    use petgraph::graph::EdgeReference;
    use petgraph::algo::astar;
    use petgraph::graph::NodeIndex;
    
    #[derive(Debug)]
    struct Nodo {
        id: u32,
        latitud: f32,
        longitud: f32
    }
    
    #[derive(Debug)]
    struct Via {
        distancia: f32
    }
    
    struct Rutas {
        grafo: Graph<Nodo, Via>,
        latitud_inicial: f32,
        longitud_inicial: f32
    }
    
    impl Rutas {
    
        pub fn add_node(&mut self, nodo: Nodo) -> NodeIndex {
    
            self.grafo.add_node(nodo)
        
        }
    
        pub fn add_edge(&mut self, nodo_1: NodeIndex, nodo_2: NodeIndex, via: Via) {
    
            self.grafo.add_edge(nodo_1, nodo_2, via);
    
        }
    
        pub fn set_coordinates(&mut self, nodo_objetivo: NodeIndex) {
    
            self.latitud_inicial = self.grafo[nodo_objetivo].latitud;
            self.longitud_inicial = self.grafo[nodo_objetivo].longitud;
    
        }
    
        pub fn compute_heuristic_distance(&mut self, nodo_busqueda: NodeIndex) -> f32 {
    
            /*
            
            x: longitud
            y: latitud
            
            */
    
            let latitud_busqueda = self.grafo[nodo_busqueda].latitud;
            let longitud_busqueda = self.grafo[nodo_busqueda].longitud;
    
            let dx = self.longitud_inicial - longitud_busqueda;
            let dy = self.latitud_inicial - latitud_busqueda;
    
            //println!("SELF {} {}", self.latitud_inicial, self.longitud_inicial);
            //println!("INPUT {} {}", latitud_busqueda, longitud_busqueda);
    
            (dx * dx + dy * dy).sqrt()
    
        }
    
    }
    
    fn get_distances(er : EdgeReference<Via>) -> f32 {
    
        er.weight().distancia
    
    }
    
    fn main() {
    
        let rutas_esqueleto : Graph<Nodo, Via> = Graph::new();
    
        //let mut lista_nodos: HashMap<NodeIndex, Nodo> = HashMap::new(); /*¿HasMap para almacenar los nodos? Aumentaria la memoria usada pero podria ser una opcion viable para evitar el borrow check*/
    
        let mut rutas = Rutas{grafo: rutas_esqueleto, latitud_inicial: -9999.0, longitud_inicial: -9999.0};
    
        let punto1 = rutas.add_node(Nodo{id: 1, latitud: 1.1, longitud: 1.2});
        let punto2 = rutas.add_node(Nodo{id: 2, latitud: 2.1, longitud: 2.2});
        let punto3 = rutas.add_node(Nodo{id: 3, latitud: 3.1, longitud: 3.2});
        let punto4 = rutas.add_node(Nodo{id: 4, latitud: 4.1, longitud: 4.2});
    
        rutas.add_edge(punto1, punto2, Via{distancia: 2.3});
        rutas.add_edge(punto2, punto3, Via{distancia: 5.0});
        rutas.add_edge(punto2, punto4, Via{distancia: 5.0});
    
        rutas.set_coordinates(punto3); 
        
        let (cost, path) = astar(
                &rutas.grafo,
                punto1,
                |n| n == punto3,
                get_distances,
                rutas.compute_heuristic_distance 
            ).unwrap();
    
        
        for node_ix in path.iter() {
            println!("{:?}", rutas.node_weight(*node_ix).unwrap());
        
    }
    

    Error:

    error[E0615]: attempted to take value of method compute_heuristic_distance on type Rutas --> src/main.rs:99:19 | 99 | rutas.compute_heuristic_distance | ^^^^^^^^^^^^^^^^^^^^^^^^^^ method, not a field | help: use parentheses to call the method | 99 | rutas.compute_heuristic_distance(_) | +++

    For more information about this error, try rustc --explain E0615. error: could not compile fast_rusting_routes due to previous error

    Thank you for your time :D

    opened by guicalare 1
  • Floyd-Warshall implementation doesn't work on undirected graphs.

    Floyd-Warshall implementation doesn't work on undirected graphs.

    use petgraph::{graph::{UnGraph, NodeIndex}, algo::floyd_warshall::floyd_warshall}; // 0.6.2
    
    fn main() {
        let mut g: UnGraph<(), ()> = UnGraph::new_undirected();
        let n1 = g.add_node(());
        let n2 = g.add_node(());
        g.add_edge(n1, n2, ());
        println!("{:?}", floyd_warshall(&g, |_| 1));
    }
    

    outputs Ok({(NodeIndex(0), NodeIndex(0)): 0, (NodeIndex(1), NodeIndex(0)): 2147483647, (NodeIndex(1), NodeIndex(1)): 0, (NodeIndex(0), NodeIndex(1)): 1})

    I expect the distance from node 1 to node 0 to be 1 rather than the max integer.

    opened by cryslith 1
Simple but powerful graph library for Rust

Graphlib Graphlib is a simple and powerful Rust graph library. This library attempts to provide a generic api for building, mutating and iterating ove

Purple Protocol 177 Nov 22, 2022
Rust library for of graph ensembles

Rust library for random graph ensembles Minimal Rust version: 1.55.0 Implements simple sampling and monte carlo (or rather markov-) steps, that can be

Yannick Feld 2 Dec 14, 2022
🦀 Rust Graph Routing runtime for Apollo Federation 🚀

Apollo Router The Apollo Router is a configurable, high-performance graph router for a federated graph. Getting started Follow the quickstart tutorial

Apollo GraphQL 502 Jan 8, 2023
Graph API client writen in Rust

graph-rs Now available on stable Rust at crates.io graph-rs-sdk = "0.1.0" 0.1.0 and above use stable Rust. Anything before 0.1.0 uses nightly Rust. M

Sean Reeise 56 Jan 3, 2023
A Graph implemented using nothing but `Vec`s in rust

VecGraph A Graph implemented using nothing but Vecs in rust. Details The graph is implemented using two Vecs: nodes and edges. nodes stores "nodes". w

null 1 Jan 27, 2022
GraphScope: A One-Stop Large-Scale Graph Computing System from Alibaba

A One-Stop Large-Scale Graph Computing System from Alibaba GraphScope is a unified distributed graph computing platform that provides a one-stop envir

Alibaba 2.2k Jan 1, 2023
A simple and elegant, pipewire graph editor

pw-viz A simple and elegant, pipewire graph editor This is still a WIP, node layouting is kinda jank at the moment. Installation A compiled binary is

null 180 Dec 27, 2022
A graph crate with simplicity in mind

A graph crate with simplicity in mind. Prepona aims to be simple to use (for users of the crate) and develop further (for contributors). Nearly every

Mohamad Amin Rayej 80 Dec 15, 2022
Simple, performant graph generator for Feynman diagrams* ⚛️

Feynman diagram generator ⚛️ A simple generator of "Feynman diagram" permutations (as defined by problem 781). Incrementally builds isomorphically uni

eugene huang 3 Jan 1, 2023
Theorem relational dependencies automatic extraction and visualization as a graph for Lean4.

Lean Graph Interactive visualization of dependencies for any theorem/definitions in your Lean project. How to use In your browser: lean-graph.com Or r

Patrik Číhal 8 Jan 3, 2024
svgcleaner could help you to clean up your SVG files from the unnecessary data.

svgcleaner svgcleaner helps you clean up your SVG files, keeping them free from unnecessary data. Table of Contents Purpose Goals Alternatives Charts

Evgeniy Reizner 1.5k Jan 9, 2023
Compact, efficient data structures in contiguous byte arrays

Sokoban Compact, efficient data structures in contiguous byte arrays. Benchmarks Based on simple benchmarks, the naive performance of Sokoban data str

Ellipsis Labs 75 Jun 5, 2023
The library provides basic functions to work with Graphviz dot lang from rust code.

Description The library provides the basic access to the graphs in graphviz format with ability to import into or export from it. Base examples: Parse

Boris 28 Dec 16, 2022
Generic framebuffer implementation in Rust for use with embedded-graphics library

Fraramebuffer implementation for Rust's Embedded-graphics Framebuffer approach helps to deal with display flickering when you update multiple parts of

Bernard Kobos 9 Nov 29, 2022
An SVG rendering library.

resvg resvg is an SVG rendering library. Purpose resvg can be used as a Rust library, a C library and as a CLI application to render SVG files based o

Evgeniy Reizner 1.8k Jan 7, 2023
Library for Rubik's cube applications.

Rubik Master cube-demo3.mov Do you like to solve Rubik's cube? I do. As a cuber and programmer, I want to build a toolset to build applications like S

Akira Hayakawa 12 Nov 3, 2022
Sub-pixel precision light spot rendering library for astronomy and video tracking applications.

Planetarium Sub-pixel precision light spot rendering library for astronomy and video tracking applications. Example usage use planetarium::{Canvas, Sp

Sergey Kvachonok 5 Mar 27, 2022
Small, lightweight and fast library for rendering text with wgpu.

wgpu-text wgpu-text is a wrapper over glyph-brush for fast and easy text rendering in wgpu. This project was inspired by and is similar to wgpu_glyph,

Leon 20 Nov 30, 2022
Python library for embedding large graphs in 2D space, using force-directed layouts.

Graph Force A python/rust library for embedding graphs in 2D space, using force-directed layouts. Installation pip install graph_force Usage The first

Niko Abeler 159 Dec 29, 2022