• Home
  • History
  • Annotate
Name Date Size #Lines LOC

..03-May-2022-

.github/H03-May-2022-5528

benches/H03-May-2022-872714

src/H03-May-2022-14,92710,489

tests/H03-May-2022-4,7784,015

.cargo-checksum.jsonH A D03-May-202289 11

.cargo_vcs_info.jsonH A D23-May-202074 65

.gitignoreH A D22-Dec-201941 43

.travis.ymlH A D23-May-2020777 3533

CONTRIBUTING.rstH A D22-Dec-20193.3 KiB12879

Cargo.tomlH A D23-May-20201.9 KiB7865

Cargo.toml.orig-cargoH A D23-May-20201.4 KiB6548

LICENSE-APACHEH A D22-Dec-201910.6 KiB202169

LICENSE-MITH A D22-Dec-20191 KiB2622

MakefileH A D22-Dec-2019982 3923

README.rstH A D23-May-202013.2 KiB417290

custom.cssH A D22-Dec-2019533 2620

graph-example.dotH A D22-Dec-2019222 1614

README.rst

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