Add graph and subgraph isomorphism detection
- Dominant language
- C++
- Stars
- 413
- Forks
- 67
- Avg merge
- 7h 24m
- Merged PRs (30d)
- 53
Description
## 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.
Contributor guide
Research direction
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.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100