summaryrefslogtreecommitdiff
path: root/networkx/algorithms/isomorphism
Commit message (Collapse)AuthorAgeFilesLines
* codespell: pre-commit, config, typos fixed (#6662)Yaroslav Halchenko2023-05-031-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | * One ambigous typo * one more ambigous typo * [DATALAD RUNCMD] run codespell throughout === Do not change lines below === { "chain": [], "cmd": "codespell -w", "exit": 0, "extra_inputs": [], "inputs": [], "outputs": [], "pwd": "." } ^^^ Do not change lines above ^^^ For this to work -- it would require configuration files which were abandoned. See https://github.com/networkx/networkx/pull/6662 for more discussion etc. * Manual reversion of perform... "fix"
* Fix typos (#6620)Harri Nieminen2023-04-041-1/+1
|
* Fix module docstring format for ismags reference article. (#6611)Ross Barnowski2023-04-031-14/+13
| | | | | | | Improperly formatted Notes/References sections was causing a sphinx parsing error which led to a very poorly formatted html page. Fixing the numpydoc formatting for the module docstring + minor munging of the heading levels was sufficient to fix this.
* Fixed method description in ismags.py (#6600)Navya Agarwal2023-04-021-2/+2
| | | | | * Fix docstr of partition_to_color * Minor edit
* Update pre-commit (#6545)Jarrod Millman2023-03-232-11/+11
|
* Lint using Ruff (#6371)danieleades2023-02-1911-49/+42
| | | | | | | | | | | | | | | * lint and fix using ruff * add flake8-pie lints * remove useless import alias * bump version * bump deps --------- Co-authored-by: daniel.eades <daniel.eades@hotmail.com>
* Update developer requirements (#6429)Jarrod Millman2023-02-145-14/+4
| | | | | * Update developer requirements * Run linter
* Add reference to paper in vf2pp (#6373)Paula Pérez Bianchi2023-01-171-1/+7
| | | | | | | | | | | * Add warning in community doc * fix unwanted change * add reference vf2pp * Minor rst format update + refer to paper at top. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Add clique examples and deprecate helper funtions (#6186)Ross Barnowski2023-01-081-2/+4
| | | | | | | | | | | | | | | | | | | * Add examples to find_cliques docstring. Add some examples to show how to compute various quantities using the find_cliques generator. Each of these quantities currently has a dedicated function in the clique module that could be deprecated in favor of these simple expressions. * Deprecate graph_clique_number. * Deprecate graph_number_of_cliques. * Deprecate number_of_cliques. * Rm internal use of deprecated functions. * Deprecated cliques_containing_node.
* Fix link in isomorphvf2.py (#6347)Paula Pérez Bianchi2023-01-071-1/+1
| | | | | | | * Add warning in community doc * Fix broken link * reverse change from another branch
* Refactor vf2pp modules and test files (#6334)Dan Schult2023-01-0613-2229/+2142
| | | | | | | | | | | * Refactor vf2pp modules and test files * fix comment typo * MAINT: rm vf2pp_helpers pkg from package data. * remove helpers from setup.py comment Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Fix typos in the networkx codebase (#6335)Anurag Bhat2023-01-054-8/+8
| | | | | * Fix_Typos * Commit_Suggestions
* Broken link in isomorphism documentation (#6296)Paula Pérez Bianchi2023-01-031-1/+1
| | | | | * Add warning in community doc * Add new link to the doc
* Isomorphism improve documentation (#6295)Paula Pérez Bianchi2022-12-271-1/+6
| | | | | | | | | | | | | * Add warning in community doc * Add more detail to the doc entry of some functions * Update networkx/algorithms/isomorphism/isomorph.py Co-authored-by: Dan Schult <dschult@colgate.edu> * reverse change from another PR Co-authored-by: Dan Schult <dschult@colgate.edu>
* Fix bug vf2pp is isomorphic issue 6257 (#6270)reneechebbo2022-12-122-4/+10
| | | | | | * Invert the order of nodes passed to number_of_edges in _consistent_PT in feasibility.py so that the first argument is the predecessor. * Add the test provided in the issue 6257 as a unit test
* Update pytest (#6165)Jarrod Millman2022-11-011-1/+1
|
* VF2++ for Directed Graphs (#5972)Konstantinos Petridis2022-10-0410-166/+1835
| | | | | | | | | | | Modify vf2pp implementation to support directed graphs. Updates all helper functions and state/parameter objects to account for in/out degree. Includes other changes such as renaming the keyword argument from node_labels to node_label to better reflect the fact that the label kwarg expects a single value. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Add vf2pp_helpers subpackage to wheel (#5975)Ross Barnowski2022-09-111-0/+0
| | | | | * Add vf2pp_helpers to package. * Add __init__.py to vf2pp_helpers
* Switch to relative import for vf2pp_helpers. (#5973)Ross Barnowski2022-09-091-7/+5
|
* Preliminary VF2++ Implementation (#5788)Konstantinos Petridis2022-09-0613-0/+4191
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Preliminary implementation of the candidate node pair ordering of VF2++ * Removed unused lines of code * Added todos * Added demo and pseudocode for VF2++ * Pointed out a problem with the pseudocode * Initialisation of the VF2++ basis structure * Initialise the GraphMatcher * Remove useless changes * Check labels for the node ordering + demo * Code to verify the ordering * Implement the ISO feasibility check * Implement the IND feasibility * Create State class * Fixed Dan's code for the ordering * Preliminary form of the node ordering * Add visualisation * Use list comprehension for the Ti computation * Remove function * Create Unit Tests * Add labels check + update unit tests * Add pre-computation of G-labels * Remove todo * First implementation of the candidate selection * Initial version of candidate selection * Remove unnecessary files * Merge candidate selection cases into one * Create a function to incrementally update Ti and Ti_out * Unit Test for the Ti updating * Implement the Ti/Ti_out restoring * Finish the restoring of Ti and create unit test * Update test file names * Uncommented test section * Replace redundant loop with for-any * Create unit test for candidate selection using the same label for all nodes * Create unit test for candidate selection using different labels for the nodes * Update feasibility tests without the use of the state class * Create more unit tests for the feasibility checking * Provide explanation for the unit tests * First successful test of the complete ISO VF2++ algorithm (except from the buggy ordering) * Fix bug: when popping a node to climb up the DFS tree we need the previous node ordering (containing the node that we just popped) * Create a separate file for the VF2++ ISO algorithm * Delete file * Remove redundant iteration and memory use * Demo for different labels * Add benchmark for the incremental Ti updating * Remove unnecessary class * Fix bug with the ordering WOOOHOOOOO * Unit tests for the node ordering * Add unit tests for the VF2++ ISO * Fix ordering * Probablly fix logic error in ordering * Reformatted with black * Test precommit * Test precommit * Test pre commit * Testing pre commit * Update networkx/algorithms/isomorphism/tests/VF2++/test_vf2pp.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Add unit tests for vf2++ * Added vf2++ unit test * Added precheck for VF2++ * Add unit tests for the precheck * Updated the benchmarking * Updated the benchmark * Apply hooks * Add documentation for the ordering * Add documentation for the candidate selection * Added documentation for the feasibility * Added documentation for vf2++ * Separate functions for ISO feasibility * Refine unit tests * Apply hooks * Force reformat all files * Remove redundant return statements from VF2__ * Apply hooks * Apply hooks * Format * Minor changes * Add unit tests * Adjusted benchmark * Fix benchmark * Isort * Isort benchmark * Apply optimization in the candidate selection * Track matched node with pointer * Adjust benchmark * Restructure in VF2 function * Make VF2++ EXTREMELY PRETTY * Removed sorting in feasibility rules * Get rid of visited set, check mapping instead * Update networkx/algorithms/isomorphism/tests/VF2++/test_vf2pp.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Made color assignement deterministic in VF2++ unit tests * Add keyword argument in unit tests * Hoepfully fix pipeline errors * Add vf2++ unit tests for multigraphs * Add Unit tests for Feasibility * Add unit tests for feasibility on multi graphs * Finalize feasibility tests for multigraph settings * Update documentation * Remove list comprehension and boost performance * Add unit tests for both graphs and multi graphs, using same labels * Isort * Optimized precheck * Replace loop with any * Optimize multigraph chceck * Transfer except statement * Check order consistency * Cache degrees and labels from the beginning * Delete benchmark to create new * Fix precheck bug * Adjust unit tests * Add benchmark for perofmance comparison between VF2 and VF2++ * Fix Ti computing tests * Hopefully fix isort * Add benchmark for the candidate selection methods * Rename modules: lower case, remove + * Refactor VF2++ arguments * Adjust VF2++ to work with multiple node labels * Add unit tests for multiple labels * Adjust for different number of labels per node * Finish arguments of VF2++ * Add user functions * Exported the two vf2++ functions * Added underscore prefix to private functions and fixed tests * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/isomorphism/demo.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Apply suggested changes * Refactor rst files * Rm unnecessary toctree from isomorphism page. * Autodoc vf2pp module + public functions. * Rm dedicated vf2pp reference article. * Rm extra vf2pp listing from autosummaries. * Add summary of three functions to module docstring. * Make sure docstrings match their functions. * Refactor everything * Format code * Add unit test * Inline process level function in node ordering * Perform intersection first rather than last * Update networkx/algorithms/isomorphism/vf2pp_helpers/candidates.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Replace return statement with multiple operations and make it more readable * Update networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Fix multigraph bug in update_Tinout * Abstract the argmax function * Add unit test for first case of candidate selection * Create unit test for all candidate selection cases * Remove re-definition of namedtuple parameters * Update doc/reference/algorithms/isomorphism.rst Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/__init__.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Delete benchmark file * Add demo file * Create util file containing the helper functions, common across all unit tests * Fix CI/CD * Make unit tests for Ti updating specific * Remove util functions from vf2pp tests * Remove utils functions from multivf2pp tests * Remove utils functions from candidate tests * Remove utils functions from ordering checks * Remove utils functions from Ti tests * Add example in docstring * Remove unused utils functions * Separate initialization of vf2pp * Inline functions and add new abstract function for pushing to stack * Inline push to stack * Add commentsa * Separate precheck functions * Replace method with existing networkx function * Include label initialization inside parameter initializer function * Rename Tiout to Titilde * Update networkx/algorithms/isomorphism/tests/vf2pp/test_Ti_computing.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Use canonical setitem for dictionary insertions * Update networkx/algorithms/isomorphism/tests/vf2pp/test_precheck.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Remove variable assignement * Merge unit tests of vf2pp for graphs and multigraphs into the same file * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Change variable name * Update networkx/algorithms/isomorphism/vf2pp.py Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> * Re-write ordering unit tests * Rename vf2pp solver * Update networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py Co-authored-by: Dan Schult <dschult@colgate.edu> * Replace abstractified argmax function with two loops for readability * Apply final changes * Fix mistake * Update ref guide to reflect new fn names. * Update docstrings * Fix line length in module docstring * Copy updated parameter section to all 3 public fns. * Add Yields section to all_isomorphisms fn. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Update ISMAGS.analyze_symmetry docstring. (#5696)Ross Barnowski2022-06-071-5/+22
| | | | | | | | | * Update ISMAGS.analyze_symmetry docstring. Co-authored-by: Peter C Kroon <pckroon@users.noreply.github.com> * Fix formatting. Co-authored-by: Peter C Kroon <pckroon@users.noreply.github.com>
* Use isort with pre-commit to enforce import guidelines (#5659)Mridul Seth2022-06-029-10/+14
| | | | | * Add isort to pre-commit * Run isort on all python files (except __init__.py ones)
* Replace internal `close` fn with `math.isclose`. (#5224)Ross Barnowski2021-12-122-26/+16
| | | | | * Replace internal close fn with math.isclose. * Fix lines in docstring examples.
* Drop Py37 (#5143)Jarrod Millman2021-10-232-6/+6
| | | | | | | | | | | | | | | | | | | * Drop Py37 * XML serialization issue * Use math.comb Co-authored-by: Simone Gasperini <simone.gasperini2@studio.unibo.it> * Run pyupgrade --py38-plus * Run black * More documentation * Deprecate euclidean Co-authored-by: Simone Gasperini <simone.gasperini2@studio.unibo.it>
* DOC: Fix links, use DOI links, wayback machine where required (#4868)Mridul Seth2021-06-083-3/+3
| | | | | | | | | | | * Fix links, use DOI links, wayback machine where required * Add nx-guides to intersphinx mapping. * Replace external mpl link w/ intersphinx. * Update mpl intersphinx mapping. Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Update black (#4814)Jarrod Millman2021-05-181-2/+2
|
* fix typo in docstring (ismorphism -> isomorphism) (#4756)CUI Hao2021-04-242-2/+2
|
* Reenable tests (#4488)Jarrod Millman2020-12-241-1/+0
|
* DOC: Remove repeated words (#4410)Miroslav Šedivý2020-12-021-2/+2
|
* Format w/ black==20.8b1Jarrod Millman2020-10-063-9/+6
|
* Cleanup old platforms (#4202)Jarrod Millman2020-09-102-28/+3
| | | | | * Remove IronPython code * Remove Jython code
* Format python in docstrings (#4168)Jarrod Millman2020-08-199-63/+44
| | | | | | | | | | | | | | | | | | | * Format code w/ black * Format docstrings w/ black * Manual cleanup * Tell pytest to ignore planned deprecations * Don't call plt.show during testing * Another known deprecation * DOC: rm duplicate line from docstring example * Minor cleanup Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
* Remove unnecessary nx imports from doctests (#4163)Jarrod Millman2020-08-161-1/+0
| | | Co-authored-by: Dan Schult <dschult@colgate.edu>
* Add tree isomorphism (#4067)Craig Schmidt2020-08-053-0/+577
| | | | | | | | | | | | | | | | | | | | | | | | | * add code for tree isomorphism, with tests * fix typo in comment * one more typo in comments * fix some PEP8 formatting, that flake8 didn't care about * rename files as tree_isomorphism * run code through black formatter * incorporate feedback from dschult in PR4067 * fix missing import for not_implemented_for decorator * swap edge order randomly in testing routine positive_single_tree * run black on test_tree_isomorphism.py * spacing tweak to allow CI test of docs Co-authored-by: Dan Schult <dschult@colgate.edu>
* Format w/ blackJarrod Millman2020-07-1011-402/+733
|
* Remove unused imports (#3855)Alex Henrie2020-07-061-1/+1
| | | | | | | | | * Remove unused imports * remove more unused import statements found by pyflakes * move import of random outside of networkx.utils Co-authored-by: Dan Schult <dschult@colgate.edu>
* typo (#3894)Mahmut Bulut2020-04-061-1/+1
|
* Prevent KeyError on subgraph_is_monomorphic (#3798)Kang Hong Jin2020-02-012-7/+25
| | | | | | | | | | | | | | | Fixes #3775 * add test for subgraph monomorphism using edge_match * add check to make sure neighbor is in adj * fix pep8 violations * Attempt to make cacheing lookups work better in _semantic_feasibility Co-authored-by: Dan Schult <dschult@colgate.edu>
* Update string formatJarrod Millman2020-01-011-2/+1
| | | | | | | | | find -name "*py" | xargs grep -n '" % ' find -name "*py" | xargs grep -n '"\.format(' find -name "*py" | xargs grep -n "' %" find -name "*py" | xargs grep -n 'msg % ' find -name "*py" | xargs grep -n ' %d ' find -name "*py" | xargs grep -n '\.format('
* Upgrade to Py36 syntaxJarrod Millman2020-01-018-36/+32
| | | | find networkx -name \*.py -exec pyupgrade --py36-plus {} \;
* Convert %-format to fstringJarrod Millman2020-01-011-1/+0
|
* Improve test coverageJarrod Millman2019-12-311-1/+9
|
* Remove superfluous encoding informationJarrod Millman2019-11-114-4/+0
|
* Remove boiler plate from top of modulesJarrod Millman2019-11-115-22/+5
| | | | | | | | | The copyright and author stuff is not necessary, out-of-date, and inconsistent. It takes up visual space and is a pain to police everyone doing the same thing on the top of the module. Git handles authorship in a comprehensive and authoritative way. The LICENSE.txt file applies to all project code.
* Add testsJarrod Millman2019-10-241-3/+3
|
* Fix PEP8 issuesJarrod Millman2019-10-211-1/+0
|
* Deprecate is_string_likeJarrod Millman2019-10-211-16/+9
|
* Remove unused importsJarrod Millman2019-10-211-1/+0
|
* Use itertools accumulateJarrod Millman2019-10-181-3/+3
|
* Remove unused importsJarrod Millman2019-10-181-1/+2
|
View Lorry Controller Status