AOEU
| Main Author: | Breggeman, Floris |
|---|---|
| Format: | info software eJournal |
| Bahasa: | eng |
| Terbitan: |
, 2020
|
| Subjects: | |
| Online Access: |
https://zenodo.org/record/3911824 |
Daftar Isi:
- The AOEU framework This is the codebase accompanying the paper “Graph Isomorphism with Pathfinding Algorithms” by Floris T. Breggeman, which is included in this repository as report/report.pdf. Its primary purpose is the development and testing of AOEU-style graph isomorphism solvers. Project Structure src: Location of all the source files. doc: Documentation of the code. work: Intended as a working directory. work/graphs contains all the graph files in the test set. results: Files containing recorded data. img: Contains images used in the reports. proposal: Contains documents related to the research proposal. report: Contains documents related to the research paper. Compiling To compile, simply clone this repository and change your working directory to the src folder, then run the following: cmake CMakeLists.txt; make After which the compiled program should be in <PROJECT ROOT>/bin/aoeu. ### If you get a compiler error related to missing libraries: This project uses C++’ std::filesystem, which has been moved out of experimental in the C++17 standard. Despite this, some systems still require it to be explicitly linked. To do so, add the following line to the bottom of CMakeLists.txt: target_link_libraries(aoeu stdc++fs) and rerun the compilation command as above. If you’re on Windows, you’re on your own. Usage aoeu <command> <options> [arguments]" Commands: - single <file> <node> <output>: run on a single node of a single graph, and output tree as dotfile. - check <file1> <file2>: check isomorphism between two graph files, return boolean. - shuffle <file1>: check isomorphism of one graph file and it’s shuffled equivalent, return boolean. - fulltest <directory>: run a full test on all files in the directory Arguments: - -h: print help text and exit. - -o <file>: write input graph as dotfile to specified location. In case of shuffle, will only write shuffled file. - -O <file> <file2>: write input graphs as dotfiles to specified locations. - -w <file>: write input graph as DIMACS to specified location. In case of shuffle, will only write shuffled file. - -W <file> <file2>: write input graphs as DIMACS to specified locations. - -r: print runtimes. - -a <algorithm>: which algorithm to use. Defaults to BFS_shadow. - -d: print debugging information - -n: don’t actually run the algorithm. Useful for converting DIMACS to .dot, and also for saving a shuffled version of a file. Any input graphs must be in the DIMACS format. Output graphs can be in both Dot and DIMACS formats. Algorithms: Currently the following algorithms are supported: BFS: standard BFS algorithm. Not recommended due to exponential memory usage. BFS_shadow: Breadth First Search algorithm with shadowtrees. Default option. DFS_shadow: Depth First Search algorithm with shadowtrees. DFS: Alias for DFS|_shadow. heuristic: Algorithm approaching BFS by using heuristics. Faster on some graphs. For a detailed explanation of all algorithms, see section 4 of the paper. Adding an algorithm Adding an algorithm is easy. The framework takes care of reading in graphs and comparing sets of trees; all one needs to add is the graph_to_tree function. Strictly speaking, an algorithm is merely a function, although I recommend making it a static member of a class for better clarity and some possibility of polymorphism. The function MUST comply with the type definition of Graph::graph_to_tree, which is: std::shared_ptr<Tree> (* graph_to_tree)(const Graph&, const std::shared_ptr<Node>&) In plain English, it takes in a graph and a shared pointer to the start node, and returns a shared pointer to a tree. Neither the graph nor the node can be modified by this process. To use the algorithm, it MUST be added to funcmap.h, which contains a mapping from string (which are passed to the runtime argument) to functions. Simply add your algorithm to the instantiation of the map variable, using whatevery string you want to name it. Generating documentation Documentation for this project was generated using doxygen. To generate documentation, simply run doxygen on <PROJECT ROOT>/src/doxygen.conf.