bobluppes / bobluppes/graaf

Add graph and subgraph isomorphism detection

Aperta
#338 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub
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

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.