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.

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)

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!

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.

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.

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

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                   

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.

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?

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.

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?

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.

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.

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.

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!

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.

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

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.