Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

map_vertex violates invariants if two vertices map to the same new one. #31

Closed
maurer opened this issue Mar 13, 2015 · 0 comments
Closed

map_vertex violates invariants if two vertices map to the same new one. #31

maurer opened this issue Mar 13, 2015 · 0 comments

Comments

@maurer
Copy link

maurer commented Mar 13, 2015

See this SCC contraction code for an example of how I ran into this.

Either the documentation surrounding map_vertex should be changed to document that it is unsafe to map vertices to the same value, or values for new vertices need to be somehow loaded in the implementation. Most likely, this would necessitate switching from a map to a fold, and essentially rebuilding the whole thing, but I suspect that the map is essentially already doing this.
@backtracking backtracking mentioned this issue Aug 30, 2023
Merged
avsm pushed a commit to ocaml/opam-repository that referenced this issue Aug 31, 2023
@backtracking
[new release] ocamlgraph (2 packages) (2.1.0)
8359556 
CHANGES:

  - ❗ OCamlGraph now requires OCaml >= 4.08
  - ❗ [Traverse]: fixed [Dfs.fold] and [Dfs.fold_component],
    which were not implementing a proper DFS
  - [Classic]: new functions [cycle] and [grid]
  - [Eulerian]: Eulerian paths (new module)
  - [Components]: strong articulation points (see functors [Connectivity]
    and [BiConnectivity]) (Timothy Bourke)
  - [Dominator]: non-trivial dominators (Timothy Bourke)
  - backtracking/ocamlgraph#31: fixed documentation of [map_vertex]: the supplied function
    must be injective
  - backtracking/ocamlgraph#110: ensure that map_vertex applies the function only once per vertex
nberth pushed a commit to nberth/opam-repository that referenced this issue Jun 18, 2024
@backtracking @nberth
[new release] ocamlgraph (2 packages) (2.1.0)
964fb22 
CHANGES:

  - ❗ OCamlGraph now requires OCaml >= 4.08
  - ❗ [Traverse]: fixed [Dfs.fold] and [Dfs.fold_component],
    which were not implementing a proper DFS
  - [Classic]: new functions [cycle] and [grid]
  - [Eulerian]: Eulerian paths (new module)
  - [Components]: strong articulation points (see functors [Connectivity]
    and [BiConnectivity]) (Timothy Bourke)
  - [Dominator]: non-trivial dominators (Timothy Bourke)
  - backtracking/ocamlgraph#31: fixed documentation of [map_vertex]: the supplied function
    must be injective
  - backtracking/ocamlgraph#110: ensure that map_vertex applies the function only once per vertex
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@maurer