Add graph and subgraph isomorphism detection
- Lingua principale
- C++
- Stelle
- 413
- Fork
- 67
- Merge medio
- 7h 24m
- PR unite (30g)
- 53
Descrizione
## Summary
Graaf has no graph or subgraph isomorphism detection.
## Current state
A search across `include/graaflib/` for "isomorphism" returns no results. There is a related historical request, [#87 "[ALGO] Graph Isomorphism"](../issues/87), which was closed without being implemented (closed due to inactivity, not as "won't do").
## Why this matters
Graph isomorphism (determining whether two graphs are structurally identical) and subgraph isomorphism (determining whether one graph's structure appears within another) are standard graph-theory operations with concrete applications: pattern/motif detection in dependency or transaction graphs, chemical structure matching, and deduplication of structurally-equivalent graph fragments. It's a well-known, distinct algorithm family that a general-purpose graph library is expected to at least partially cover, and its complete absence is a visible gap for anyone evaluating structural-comparison use cases.
## Suggested resolution
- Implement a graph isomorphism check for reasonably small/sparse graphs (e.g. a VF2-style backtracking algorithm, which is the standard practical approach and is what most comparable libraries — including Boost Graph Library — use).
- Consider whether subgraph isomorphism is in scope for the same effort or should be tracked as a follow-up, given it's a strictly harder (NP-complete) problem with different practical performance characteristics.
- Add corresponding documentation, including a clear statement of the algorithm's complexity/scalability limits so users can judge suitability for their graph sizes.
## Acceptance criteria
- [ ] Graph isomorphism detection is implemented for at least one graph type.
- [ ] Documentation added, including complexity/scalability caveats.
- [ ] Unit tests cover isomorphic graphs, non-isomorphic graphs of the same size, and graphs of different sizes.
Guida per i contributori
Apri la guida per i contributori
Direzione di ricerca
The issue is to implement graph and subgraph isomorphism detection in the graaf C++ library. Start by examining the existing graph types and algorithms in `include/graaflib/`. Research the VF2 algorithm and its typical implementation for graph isomorphism. The work involves designing and implementing a new algorithm, writing unit tests, and adding documentation about complexity and scalability. This is a significant algorithmic feature requiring deep graph theory knowledge and C++ proficiency.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Valutazione
- Stack tecnologico
- cpp
- Tipo di issue
- Funzionalità
- Difficoltà
- 5/5
- Tempo stimato
- Più di una settimana
- Stato di attività
- Attiva
- Chiarezza
- Abbastanza chiara
- Idoneità per principianti
- 25/100