1
2petgraph
3========
4
5Graph data structure library. Known to support Rust 1.37 and later.
6
7Please read the `API documentation here`__
8
9__ https://docs.rs/petgraph/
10
11|build_status|_ |crates|_
12
13.. |build_status| image:: https://travis-ci.org/petgraph/petgraph.svg?branch=master
14.. _build_status: https://travis-ci.org/petgraph/petgraph
15
16.. |crates| image:: http://meritbadge.herokuapp.com/petgraph
17.. _crates: https://crates.io/crates/petgraph
18
19Crate feature flags:
20
21- ``graphmap`` (default) enable ``GraphMap``.
22- ``stable_graph`` (default) enable ``StableGraph``.
23- ``matrix_graph`` (default) enable ``MatrixGraph``.
24- ``serde-1`` (optional) enable serialization for ``Graph, StableGraph`` using
25 serde 1.0. Requires Rust version as required by serde.
26
27Recent Changes
28--------------
29
30- 0.5.0
31
32 - Upgrade to Rust 2018 edition
33 - Fix clippy warnings and unify code formatting
34 - Improved and enhanced documentation
35 - Update dependencies including modern quickcheck
36 - Numerous bugfixes and refactorings
37 - Added ``MatrixGraph`` implementation
38 - Added ``InfoEdges`` and ``InfoEdgesDirected``
39
40- 0.4.13
41
42 - Fix clippy warnings by @jonasbb
43 - Add docs for ``Csr`` by @ksadorf
44 - Fix conflict with new stable method ``find_map`` in new Rust
45
46- 0.4.12
47
48 - Newtype ``Time`` now also implements ``Hash``
49 - Documentation updates for ``Frozen``.
50
51- 0.4.11
52
53 - Fix ``petgraph::graph::NodeReferences`` to be publicly visible
54 - Small doc typo and code style files by @shepmaster and @waywardmonkeys
55 - Fix a future compat warning with pointer casts
56
57- 0.4.10
58
59 - Add graph trait ``IntoEdgesDirected``
60 - Update dependencies
61
62- 0.4.9
63
64 - Fix ``bellman_ford`` to work correctly with undirected graphs (#152) by
65 @carrutstick
66 - Performance improvements for ``Graph, Stablegraph``'s ``.map()``.
67
68- 0.4.8
69
70 - ``StableGraph`` learned new methods nearing parity with ``Graph``. Note
71 that the ``StableGraph`` methods preserve index stability even in the batch
72 removal methods like ``filter_map`` and ``retain_edges``.
73
74 + Added ``.filter_map()``, which maps associated node and edge data
75 + Added ``.retain_edges()``, ``.edge_indices()`` and ``.clear_edges()``
76
77 - Existing ``Graph`` iterators gained some trait impls:
78
79 + ``.node_indices(), .edge_indices()`` are ``ExactSizeIterator``
80 + ``.node_references()`` is now
81 ``DoubleEndedIterator + ExactSizeIterator``.
82 + ``.edge_references()`` is now ``ExactSizeIterator``.
83
84 - Implemented ``From<StableGraph>`` for ``Graph``.
85
86- 0.4.7
87
88 - New algorithm by @jmcomets: A* search algorithm in ``petgraph::algo::astar``
89 - One ``StableGraph`` bug fix whose patch was supposed to be in the previous
90 version:
91
92 + ``add_edge(m, n, _)`` now properly always panics if nodes m or n don't
93 exist in the graph.
94
95- 0.4.6
96
97 - New optional crate feature: ``"serde-1"``, which enables serialization
98 for ``Graph`` and ``StableGraph`` using serde.
99 - Add methods ``new``, ``add_node`` to ``Csr`` by @jmcomets
100 - Add indexing with ``[]`` by node index, ``NodeCompactIndexable`` for
101 ``Csr`` by @jmcomets
102 - Amend doc for ``GraphMap::into_graph`` (it has a case where it can panic)
103 - Add implementation of ``From<Graph>`` for ``StableGraph``.
104 - Add implementation of ``IntoNodeReferences`` for ``&StableGraph``.
105 - Add method ``StableGraph::map`` that maps associated data
106 - Add method ``StableGraph::find_edge_undirected``
107 - Many ``StableGraph`` bug fixes involving node vacancies (holes left by
108 deletions):
109
110 + ``neighbors(n)`` and similar neighbor and edge iterator methods now
111 handle n being a vacancy properly. (This produces an empty iterator.)
112 + ``find_edge(m, n)`` now handles m being a vacancy correctly too
113 + ``StableGraph::node_bound`` was fixed for empty graphs and returns 0
114
115 - Add implementation of ``DoubleEndedIterator`` to ``Graph, StableGraph``'s
116 edge references iterators.
117 - Debug output for ``Graph`` now shows node and edge count. ``Graph, StableGraph``
118 show nothing for the edges list if it's empty (no label).
119 - ``Arbitrary`` implementation for ``StableGraph`` now can produce graphs with
120 vacancies (used by quickcheck)
121
122- 0.4.5
123
124 - Fix ``max`` ambiguity error with current rust nightly by @daboross (#153)
125
126- 0.4.4
127
128 - Add ``GraphMap::all_edges_mut()`` iterator by @Binero
129 - Add ``StableGraph::retain_nodes`` by @Rupsbant
130 - Add ``StableGraph::index_twice_mut`` by @christolliday
131
132- 0.4.3
133
134 - Add crate categories
135
136- 0.4.2
137
138 - Move the ``visit.rs`` file due to changed rules for a module’s directory
139 ownership in Rust, resolving a future compat warning.
140 - The error types ``Cycle, NegativeCycle`` now implement ``PartialEq``.
141
142- 0.4.1
143
144 - Add new algorithm ``simple_fast`` for computing dominators in a control-flow
145 graph.
146
147- 0.4.0
148
149 - Breaking changes in ``Graph``:
150
151 - ``Graph::edges`` and the other edges methods now return an iterator of
152 edge references
153
154 - Other breaking changes:
155
156 - ``toposort`` now returns an error if the graph had a cycle.
157 - ``is_cyclic_directed`` no longer takes a dfs space argument. It is
158 now recursive.
159 - ``scc`` was renamed to ``kosaraju_scc``.
160 - ``min_spanning_tree`` now returns an iterator that needs to be
161 made into a specific graph type deliberately.
162 - ``dijkstra`` now uses the ``IntoEdges`` trait.
163 - ``NodeIndexable`` changed its method signatures.
164 - ``IntoExternals`` was removed, and many other smaller adjustments
165 in graph traits. ``NodeId`` must now implement ``PartialEq``, for example.
166 - ``DfsIter, BfsIter`` were removed in favour of a more general approach
167 with the ``Walker`` trait and its iterator conversion.
168
169 - New features:
170
171 - New graph traits, for example ``IntoEdges`` which returns
172 an iterator of edge references. Everything implements the graph traits
173 much more consistently.
174 - Traits for associated data access and building graphs: ``DataMap``,
175 ``Build, Create, FromElements``.
176 - Graph adaptors: ``EdgeFiltered``. ``Filtered`` was renamed to ``NodeFiltered``.
177 - New algorithms: bellman-ford
178 - New graph: compressed sparse row (``Csr``).
179 - ``GraphMap`` implements ``NodeIndexable``.
180 - ``Dot`` was generalized
181
182- 0.3.2
183
184 - Add ``depth_first_search``, a recursive dfs visitor that emits discovery,
185 finishing and edge classification events.
186 - Add graph adaptor ``Filtered``.
187 - impl ``Debug, NodeIndexable`` for ``Reversed``.
188
189- 0.3.1
190
191 - Add ``.edges(), .edges_directed()`` to ``StableGraph``. Note that these
192 differ from ``Graph``, because this is the signature they will all use
193 in the future.
194 - Add ``.update_edge()`` to ``StableGraph``.
195 - Add reexports of common items in ``stable_graph`` module (for example
196 ``NodeIndex``).
197 - Minor performance improvements to graph iteration
198 - Improved docs for ``visit`` module.
199
200- 0.3.0
201
202 - Overhaul all graph visitor traits so that they use the ``IntoIterator``
203 style. This makes them composable.
204
205 - Multiple graph algorithms use new visitor traits.
206 - **Help is welcome to port more algorithms (and create new graph traits in
207 the process)!**
208
209 - ``GraphMap`` can now have directed edges. ``GraphMap::new`` is now generic
210 in the edge type. ``DiGraphMap`` and ``UnGraphMap`` are new type aliases.
211 - Add type aliases ``DiGraph, UnGraph, StableDiGraph, StableUnGraph``
212 - ``GraphMap`` is based on the indexmap crate. Deterministic iteration
213 order, faster iteration, no side tables needed to convert to ``Graph``.
214 - Improved docs for a lot of types and functions.
215 - Add graph visitor ``DfsPostOrder``
216 - ``Dfs`` gained new methods ``from_parts`` and ``reset``.
217 - New algo ``has_path_connecting``.
218 - New algo ``tarjan_scc``, a second scc implementation.
219 - Document traversal order in ``Dfs, DfsPostOrder, scc, tarjan_scc``.
220 - Optional graph visitor workspace reuse in ``has_path_connecting``,
221 ``is_cyclic_directed, toposort``.
222 - Improved ``Debug`` formatting for ``Graph, StableGraph``.
223 - Add a prelude module
224 - ``GraphMap`` now has a method ``.into_graph()`` that makes a ``Graph``.
225 - ``Graph::retain_nodes, retain_edges`` now expose the self graph only
226 as wrapped in ``Frozen``, so that weights can be mutated but the
227 graph structure not.
228 - Enable ``StableGraph`` by default
229 - Add method ``Graph::contains_edge``.
230 - Renamed ``EdgeDirection`` → ``Direction``.
231 - Remove ``SubTopo``.
232 - Require Rust 1.12 or later
233
234- 0.2.10
235
236 - Fix compilation with rust nightly
237
238- 0.2.9
239
240 - Fix a bug in SubTopo (#81)
241
242- 0.2.8
243
244 - Add Graph methods reserve_nodes, reserve_edges, reserve_exact_nodes,
245 reserve_exact_edges, shrink_to_fit_edges, shrink_to_fit_nodes, shrink_to_fit
246
247- 0.2.7
248
249 - Update URLs
250
251- 0.2.6
252
253 - Fix warning about type parameter defaults (no functional change)
254
255- 0.2.5
256
257 - Add SubTopo, a topo walker for the subgraph reachable from a starting point.
258 - Add condensation, which forms the graph of a graph’s strongly connected
259 components.
260
261- 0.2.4
262
263 - Fix an algorithm error in scc (#61). This time we have a test that
264 crosschecks the result of the algorithm vs another implementation, for
265 greater confidence in its correctness.
266
267- 0.2.3
268
269 - Require Rust 1.6: Due to changes in how rust uses type parameter defaults.
270 - Implement Graph::clone_from.
271
272- 0.2.2
273
274 - Require Rust 1.5
275 - ``Dot`` passes on the alternate flag to node and edge label formatting
276 - Add ``Clone`` impl for some iterators
277 - Document edge iteration order for ``Graph::neighbors``
278 - Add *experimental feature* ``StableGraph``, using feature flag ``stable_graph``
279
280- 0.2.1
281
282 - Add algorithm ``is_isomorphic_matching``
283
284- 0.2.0
285
286 - New Features
287
288 - Add Graph::neighbors().detach() to step edges without borrowing.
289 This is more general than, and replaces now deprecated
290 walk_edges_directed. (#39)
291 - Implement Default for Graph, GraphMap
292 - Add method EdgeDirection::opposite()
293
294 - Breaking changes
295
296 - Graph::neighbors() for undirected graphs and Graph::neighbors_undirected
297 for any graph now visit self loop edges once, not twice. (#31)
298 - Renamed Graph::without_edges to Graph::externals
299 - Removed Graph::edges_both
300 - GraphMap::add_edge now returns ``Option<E>``
301 - Element type of ``GraphMap<N, E>::all_edges()`` changed to ``(N, N, &E)``
302
303 - Minor breaking changes
304
305 - IntoWeightedEdge changed a type parameter to associated type
306 - IndexType is now an unsafe trait
307 - Removed IndexType::{one, zero}, use method new instead.
308 - Removed MinScored
309 - Ptr moved to the graphmap module.
310 - Directed, Undirected are now void enums.
311 - Fields of graphmap::Edges are now private (#19)
312
313- 0.1.18
314
315 - Fix bug on calling GraphMap::add_edge with existing edge (#35)
316
317- 0.1.17
318
319 - Add Graph::capacity(), GraphMap::capacity()
320 - Fix bug in Graph::reverse()
321 - Graph and GraphMap have `quickcheck::Arbitrary` implementations,
322 if optional feature `check` is enabled.
323
324- 0.1.16
325
326 - Add Graph::node_indices(), Graph::edge_indices()
327 - Add Graph::retain_nodes(), Graph::retain_edges()
328 - Add Graph::extend_with_edges(), Graph::from_edges()
329 - Add functions petgraph::graph::{edge_index, node_index};
330 - Add GraphMap::extend(), GraphMap::from_edges()
331 - Add petgraph::dot::Dot for simple graphviz dot output
332
333- 0.1.15
334
335 - Add Graph::clear_edges()
336 - Add Graph::edge_endpoints()
337 - Add Graph::map() and Graph::filter_map()
338
339- 0.1.14
340
341 - Add new topological order visitor Topo
342 - New graph traits NeighborsDirected, Externals, Revisitable
343
344- 0.1.13
345
346 - Add iterator GraphMap::all_edges
347
348- 0.1.12
349
350 - Fix an algorithm error in scc (#14)
351
352- 0.1.11
353
354 - Update for well-formedness warnings (Rust RFC 1214), adding
355 new lifetime bounds on NeighborIter and Dfs, impact should be minimal.
356
357- 0.1.10
358
359 - Fix bug in WalkEdges::next_neighbor()
360
361- 0.1.9
362
363 - Fix Dfs/Bfs for a rustc bugfix that disallowed them
364 - Add method next_neighbor() to WalkEdges
365
366- 0.1.8
367
368 - Add Graph::walk_edges_directed()
369 - Add Graph::index_twice_mut()
370
371- 0.1.7
372
373 - Add Graph::edges_directed()
374
375- 0.1.6
376
377 - Add Graph::node_weights_mut and Graph::edge_weights_mut
378
379- 0.1.4
380
381 - Add back DfsIter, BfsIter
382
383License
384-------
385
386Dual-licensed to be compatible with the Rust project.
387
388Licensed under the Apache License, Version 2.0
389http://www.apache.org/licenses/LICENSE-2.0 or the MIT license
390http://opensource.org/licenses/MIT, at your
391option. This file may not be copied, modified, or distributed
392except according to those terms.
393
394
395