8207935496

Committed 08 Mar 2024 07:13PM UTC coverage: 96.58% (-0.02%) from 96.602%

Build # 8207935496

Build Type

push

github

Committed by

web-flow

Commit Message

Fix panic error at shortest paths  (#1134) (#1135)

* lint suggestion UP032

* Test of dijkstra raising IndexError

* Test Bellman Ford and A*

* fix: shortest path

(cherry picked from commit 058b0c7b1)

Co-authored-by: Julio Quintero <jequinterope@unal.edu.co>

Run Details

57 of 57 new or added lines in 1 file covered. (100.0%)

6 existing lines in 1 file now uncovered.

16802 of 17397 relevant lines covered (96.58%)

1225007.58 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.53

/src/shortest_path/all_pairs_bellman_ford.rs

// Licensed under the Apache License, Version 2.0 (the "License"); you may
// not use this file except in compliance with the License. You may obtain
// a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations
// under the License.

use rustworkx_core::dictmap::*;
use rustworkx_core::shortest_path::bellman_ford;

use std::sync::RwLock;

use pyo3::exceptions::PyIndexError;
use pyo3::prelude::*;
use pyo3::Python;

use petgraph::graph::NodeIndex;
use petgraph::prelude::*;
use petgraph::EdgeType;

use rayon::prelude::*;

use crate::iterators::{
    AllPairsPathLengthMapping, AllPairsPathMapping, PathLengthMapping, PathMapping,
};
use crate::{edge_weights_from_callable, NegativeCycle, StablePyGraph};

pub fn all_pairs_bellman_ford_path_lengths<Ty: EdgeType + Sync>(
    py: Python,
    graph: &StablePyGraph<Ty>,
    edge_cost_fn: PyObject,
) -> PyResult<AllPairsPathLengthMapping> {
    if graph.node_count() == 0 {
        return Ok(AllPairsPathLengthMapping {
            path_lengths: DictMap::new(),
        });
    } else if graph.edge_count() == 0 {
        return Ok(AllPairsPathLengthMapping {
            path_lengths: graph
                .node_indices()
                .map(|i| {
                    (
                        i.index(),
                        PathLengthMapping {
                            path_lengths: DictMap::new(),
                        },
                    )
                })
                .collect(),
        });
    }
    let edge_weights: Vec<Option<f64>> =
        edge_weights_from_callable(py, graph, &Some(edge_cost_fn), 1.0)?;
    let edge_cost = |e: EdgeIndex| -> PyResult<f64> {
        match edge_weights[e.index()] {
            Some(weight) => Ok(weight),
            None => Err(PyIndexError::new_err("No edge found for index")),
        }
    };

    let negative_cycle = RwLock::new(false);

    let node_indices: Vec<NodeIndex> = graph.node_indices().collect();
    let out_map: DictMap<usize, PathLengthMapping> = node_indices
        .into_par_iter()
        .map(|x| {
            if *negative_cycle.read().unwrap() {
                return (
                    x.index(),
                    PathLengthMapping {
                        path_lengths: DictMap::new(),
                    },
                );
            }

            let path_lengths: Option<Vec<Option<f64>>> =
                bellman_ford(graph, x, |e| edge_cost(e.id()), None).unwrap();

            if path_lengths.is_none() {
                let mut cycle = negative_cycle.write().unwrap();
                *cycle = true;
                return (
                    x.index(),
                    PathLengthMapping {
                        path_lengths: DictMap::new(),
                    },
                );
            }

            let out_map = PathLengthMapping {
                path_lengths: path_lengths
                    .unwrap()
                    .into_iter()
                    .enumerate()
                    .filter_map(|(index, opt_cost)| {
                        if index != x.index() {
                            opt_cost.map(|cost| (index, cost))
                        } else {
                            None
                        }
                    })
                    .collect(),
            };
            (x.index(), out_map)
        })
        .collect();

    if *negative_cycle.read().unwrap() {
        return Err(NegativeCycle::new_err(
            "The shortest-path is not defined because there is a negative cycle",
        ));
    }

    Ok(AllPairsPathLengthMapping {
        path_lengths: out_map,
    })
}

pub fn all_pairs_bellman_ford_shortest_paths<Ty: EdgeType + Sync>(
    py: Python,
    graph: &StablePyGraph<Ty>,
    edge_cost_fn: PyObject,
) -> PyResult<AllPairsPathMapping> {
    if graph.node_count() == 0 {
        return Ok(AllPairsPathMapping {
            paths: DictMap::new(),
        });
    } else if graph.edge_count() == 0 {
        return Ok(AllPairsPathMapping {
            paths: graph
                .node_indices()
                .map(|i| {
                    (
                        i.index(),
                        PathMapping {
                            paths: DictMap::new(),
                        },
                    )
                })
                .collect(),
        });
    }
    let edge_weights: Vec<Option<f64>> =
        edge_weights_from_callable(py, graph, &Some(edge_cost_fn), 1.0)?;
    let edge_cost = |e: EdgeIndex| -> PyResult<f64> {
        match edge_weights[e.index()] {
            Some(weight) => Ok(weight),
            None => Err(PyIndexError::new_err("No edge found for index")),
        }
    };

    let node_indices: Vec<NodeIndex> = graph.node_indices().collect();

    let negative_cycle = RwLock::new(false);

    let out_map = AllPairsPathMapping {
        paths: node_indices
            .into_par_iter()
            .map(|x| {
                if *negative_cycle.read().unwrap() {
                    return (
                        x.index(),
                        PathMapping {
                            paths: DictMap::new(),
                        },
                    );
                }

                let mut paths: DictMap<NodeIndex, Vec<NodeIndex>> =
                    DictMap::with_capacity(graph.node_count());
                let path_lengths: Option<Vec<Option<f64>>> =
                    bellman_ford(graph, x, |e| edge_cost(e.id()), Some(&mut paths)).unwrap();

                if path_lengths.is_none() {
                    let mut cycle = negative_cycle.write().unwrap();
                    *cycle = true;
                    return (
                        x.index(),
                        PathMapping {
                            paths: DictMap::new(),
                        },
                    );
                }

                let index = x.index();

                let out_paths = PathMapping {
                    paths: paths
                        .iter()
                        .filter_map(|path_mapping| {
                            let path_index = path_mapping.0.index();
                            if index != path_index {
                                Some((
                                    path_index,
                                    path_mapping.1.iter().map(|x| x.index()).collect(),
                                ))
                            } else {
                                None
                            }
                        })
                        .collect(),
                };
                (index, out_paths)
            })
            .collect(),
    };

    if *negative_cycle.read().unwrap() {
        return Err(NegativeCycle::new_err(
            "The shortest-path is not defined because there is a negative cycle",
        ));
    }

    Ok(out_map)
}

1	// Licensed under the Apache License, Version 2.0 (the "License"); you may
2	// not use this file except in compliance with the License. You may obtain
3	// a copy of the License at
4	//
5	// http://www.apache.org/licenses/LICENSE-2.0
6	//
7	// Unless required by applicable law or agreed to in writing, software
8	// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9	// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10	// License for the specific language governing permissions and limitations
11	// under the License.
12
13	use rustworkx_core::dictmap::*;
14	use rustworkx_core::shortest_path::bellman_ford;
15
16	use std::sync::RwLock;
17
18	use pyo3::exceptions::PyIndexError;
19	use pyo3::prelude::*;
20	use pyo3::Python;
21
22	use petgraph::graph::NodeIndex;
23	use petgraph::prelude::*;
24	use petgraph::EdgeType;
25
26	use rayon::prelude::*;
27
28	use crate::iterators::{
29	AllPairsPathLengthMapping, AllPairsPathMapping, PathLengthMapping, PathMapping,
30	};
31	use crate::{edge_weights_from_callable, NegativeCycle, StablePyGraph};
32
33	pub fn all_pairs_bellman_ford_path_lengths<Ty: EdgeType + Sync>(	20✔
34	py: Python,	20✔
35	graph: &StablePyGraph<Ty>,	20✔
36	edge_cost_fn: PyObject,	20✔
37	) -> PyResult<AllPairsPathLengthMapping> {	20✔
38	if graph.node_count() == 0 {	20✔
39	return Ok(AllPairsPathLengthMapping {	4✔
40	path_lengths: DictMap::new(),	4✔
41	});	4✔
42	} else if graph.edge_count() == 0 {	16✔
43	return Ok(AllPairsPathLengthMapping {	4✔
44	path_lengths: graph	4✔
45	.node_indices()	4✔
46	.map(\|i\| {	4,000✔
47	(	4,000✔
48	i.index(),	4,000✔
49	PathLengthMapping {	4,000✔
50	path_lengths: DictMap::new(),	4,000✔
51	},	4,000✔
52	)	4,000✔
53	})	4,000✔
54	.collect(),	4✔
55	});	4✔
56	}	12✔
57	let edge_weights: Vec<Option<f64>> =	12✔
58	edge_weights_from_callable(py, graph, &Some(edge_cost_fn), 1.0)?;	12✔
59	let edge_cost = \|e: EdgeIndex\| -> PyResult<f64> {	502✔
60	match edge_weights[e.index()] {	502✔
61	Some(weight) => Ok(weight),	502✔
62	None => Err(PyIndexError::new_err("No edge found for index")),	×
63	}
64	};	502✔
65
66	let negative_cycle = RwLock::new(false);	12✔
67		12✔
68	let node_indices: Vec<NodeIndex> = graph.node_indices().collect();	12✔
69	let out_map: DictMap<usize, PathLengthMapping> = node_indices	12✔
70	.into_par_iter()	12✔
71	.map(\|x\| {	60✔
72	if *negative_cycle.read().unwrap() {	60✔
73	return (	4✔
74	x.index(),	4✔
75	PathLengthMapping {	4✔
76	path_lengths: DictMap::new(),	4✔
77	},	4✔
78	);	4✔
79	}	56✔
80		56✔
81	let path_lengths: Option<Vec<Option<f64>>> =	56✔
82	bellman_ford(graph, x, \|e\| edge_cost(e.id()), None).unwrap();	502✔
83		56✔
84	if path_lengths.is_none() {	56✔
85	let mut cycle = negative_cycle.write().unwrap();	12✔
86	*cycle = true;	12✔
87	return (	12✔
88	x.index(),	12✔
89	PathLengthMapping {	12✔
90	path_lengths: DictMap::new(),	12✔
91	},	12✔
92	);	12✔
93	}	44✔
94		44✔
95	let out_map = PathLengthMapping {	44✔
96	path_lengths: path_lengths	44✔
97	.unwrap()	44✔
98	.into_iter()	44✔
99	.enumerate()	44✔
100	.filter_map(\|(index, opt_cost)\| {	264✔
101	if index != x.index() {	264✔
102	opt_cost.map(\|cost\| (index, cost))	220✔
103	} else {
104	None	44✔
105	}
106	})	264✔
107	.collect(),	44✔
108	};	44✔
109	(x.index(), out_map)	44✔
110	})	60✔
111	.collect();	12✔
112		12✔
113	if *negative_cycle.read().unwrap() {	12✔
114	return Err(NegativeCycle::new_err(	4✔
115	"The shortest-path is not defined because there is a negative cycle",	4✔
116	));	4✔
117	}	8✔
118		8✔
119	Ok(AllPairsPathLengthMapping {	8✔
120	path_lengths: out_map,	8✔
121	})	8✔
122	}	20✔
123
124	pub fn all_pairs_bellman_ford_shortest_paths<Ty: EdgeType + Sync>(	20✔
125	py: Python,	20✔
126	graph: &StablePyGraph<Ty>,	20✔
127	edge_cost_fn: PyObject,	20✔
128	) -> PyResult<AllPairsPathMapping> {	20✔
129	if graph.node_count() == 0 {	20✔
130	return Ok(AllPairsPathMapping {	4✔
131	paths: DictMap::new(),	4✔
132	});	4✔
133	} else if graph.edge_count() == 0 {	16✔
134	return Ok(AllPairsPathMapping {	4✔
135	paths: graph	4✔
136	.node_indices()	4✔
137	.map(\|i\| {	4,000✔
138	(	4,000✔
139	i.index(),	4,000✔
140	PathMapping {	4,000✔
141	paths: DictMap::new(),	4,000✔
142	},	4,000✔
143	)	4,000✔
144	})	4,000✔
145	.collect(),	4✔
146	});	4✔
147	}	12✔
148	let edge_weights: Vec<Option<f64>> =	12✔
149	edge_weights_from_callable(py, graph, &Some(edge_cost_fn), 1.0)?;	12✔
150	let edge_cost = \|e: EdgeIndex\| -> PyResult<f64> {	518✔
151	match edge_weights[e.index()] {	518✔
152	Some(weight) => Ok(weight),	518✔
153	None => Err(PyIndexError::new_err("No edge found for index")),	×
154	}
155	};	518✔
156
157	let node_indices: Vec<NodeIndex> = graph.node_indices().collect();	12✔
158		12✔
159	let negative_cycle = RwLock::new(false);	12✔
160		12✔
161	let out_map = AllPairsPathMapping {	12✔
162	paths: node_indices	12✔
163	.into_par_iter()	12✔
164	.map(\|x\| {	60✔
165	if *negative_cycle.read().unwrap() {	60✔
UNCOV 166	return (	×
UNCOV 167	x.index(),	×
UNCOV 168	PathMapping {	×
UNCOV 169	paths: DictMap::new(),	×
UNCOV 170	},	×
UNCOV 171	);	×
172	}	60✔
173		60✔
174	let mut paths: DictMap<NodeIndex, Vec<NodeIndex>> =	60✔
175	DictMap::with_capacity(graph.node_count());	60✔
176	let path_lengths: Option<Vec<Option<f64>>> =	60✔
177	bellman_ford(graph, x, \|e\| edge_cost(e.id()), Some(&mut paths)).unwrap();	518✔
178		60✔
179	if path_lengths.is_none() {	60✔
180	let mut cycle = negative_cycle.write().unwrap();	16✔
181	*cycle = true;	16✔
182	return (	16✔
183	x.index(),	16✔
184	PathMapping {	16✔
185	paths: DictMap::new(),	16✔
186	},	16✔
187	);	16✔
188	}	44✔
189		44✔
190	let index = x.index();	44✔
191		44✔
192	let out_paths = PathMapping {	44✔
193	paths: paths	44✔
194	.iter()	44✔
195	.filter_map(\|path_mapping\| {	206✔
196	let path_index = path_mapping.0.index();	206✔
197	if index != path_index {	206✔
198	Some((	162✔
199	path_index,	162✔
200	path_mapping.1.iter().map(\|x\| x.index()).collect(),	418✔
201	))	162✔
202	} else {
203	None	44✔
204	}
205	})	206✔
206	.collect(),	44✔
207	};	44✔
208	(index, out_paths)	44✔
209	})	60✔
210	.collect(),	12✔
211	};	12✔
212		12✔
213	if *negative_cycle.read().unwrap() {	12✔
214	return Err(NegativeCycle::new_err(	4✔
215	"The shortest-path is not defined because there is a negative cycle",	4✔
216	));	4✔
217	}	8✔
218		8✔
219	Ok(out_map)	8✔
220	}	20✔

Qiskit / rustworkx / 8207935496

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous