v4.0 Spectrum Release

This release includes many changes from the previous version to the point that it is challenging to summarize. Many of the changes are described in a recent conference paper [PDF]. There have been many changes to the options (opts) and network structure constraint (NSC) structures so please see PMA_DefaultOpts.m and PMA_DefaultNSC.m. Reviewing the Examples folder may also be helpful. The release is based on commit 95ac70b.

Summary of Changes

• New graph enumeration algorithms
  • Added v10 algorithm which is a breadth-first search implementation of v8 (b4a6f7e, 79a97bc)
  • Added v11 algorithms based on the touched vertex promotion enhancement (13ed289, 6d57b60)
  • Added v12 algorithms which utilize NSC.multiedgeA to limit the number of multiedges and loops during the graph generation process (b1bcedd, 9d09ccc)
  • Changed default algorithm to v12DFS (95ac70b)
  • Updated analysis versions (d0137f1, 74c8524, 085aab7, 9d09ccc)
  • Updated stochastic versions (b9517ad, 6913b24)
  • Fixed issue in PMA_TreeSaveGraphs.m when the number of preallocated graphs was not large enough (d73be8a)
• Major improvements, fixes, and additional features to labeled graph isomorphism checking methods
  • Now a single function combining the matlab and python versions as well as PMA_IsoBFS.m into PMA_RemoveIsoLabeledGraphs.m (1c84354)
  • Additional simple graph invariant checks and improved implementations (b4a6f7e, 1c84354, 79a97bc, 085aab7, 034b843, 5091d6b)
  • Fixed issues when checking isomorphisms for labeled multigraphs (1c84354, 41f5429, 9d09ccc)
  • Added py-networkx option but is not generally faster than py-igraph (1c84354, d73be8a)
• Major improvements, fixes, and additional features to subcatalog specification and generation
  • Added v1 subcatalog generation method which allows for ports bounds (P.min and P.max) and additional NSCs on the subcatalogs (6d57b60)
  • Added v2 subcatalog generation method which allows for linear penalty and linear satisfaction constraints (085aab7, 5091d6b)
  • Added custom subcatalog constraints for specific graph classes (6d57b60, 085aab7, 085aab7)
  • Subcatalogs are now sorted by the total number of ports to reduce average total computation time (6d57b60)
  • Both graph generation and isomorphism checking for each subcatalog is now done with the same job reducing computation time (6d57b60)
  • Bug fixes (5091d6b, b1bcedd)
• Updates to network structure constraints methods
  • Moved NSC checks to a separate function named PMA_CheckNSCFeasibility.m (a7ac593, 6d57b60)
  • Changed the names of many NSC fields so see PMA_DefaultNSC.m (6d57b60, b1bcedd)
  • Changed how NSC.loops works so that you can specify if loops are allowed or not without it being overwritten in
    PMA_ExpandPossibleAdj.m (6d57b60)
  • Added PMA_Check4PathWithIntermediate.m which checks if there exists a path between a defined start and end node that contains a specified intermediate node (b1bcedd)
  • Bug fixes (0b2e600, b9517ad, b4a6f7e, d73be8a, 8326d71, e84b2e1)
• New plotting features, changes, and fixes
  • Added color library feature in PMA_LabelColors.m (bea0de7) and custom coloring function (41f5429)
  • Added optional randomizer to the ordering of the graphs in the plot function (b1bcedd)
  • Added optional replicate numbers in plots (034b843)
  • Changed PMA_PlotTreeEnumerate.m to show what edge was added, sort the tree graph, and other improvements (d0137f1)
  • Changed default plot function type to matlab (034b843)
  • Bug fixes (ca667b9, 74c8524)
• New examples
  • Added many OEIS examples with a standardized method for evaluating them (41f5429, 8d74a09, 085aab7, b1bcedd, 5091d6b, 58151e1, bea0de7, ca667b9)
  • Added patterns examples (a9149cb)
• Dependency updates
  • Added MFX 52301 to replace existing perfect matching functions (f5ef2b1)
  • Added MFX 68575 which includes a faster implementation of base2dec (58151e1)
  • Removed MFX 44673 (ca667b9)
  • Added PMA_changem.m to remove a toolbox dependency (bea0de7)
• Mex files for the different graph enumeration algorithms are now generated during installation (ca667b9, 5620d6e, 58151e1, 13ed289)
• Changed PMA_ParallelToggle.m to allow more ways to control parallel pool creation (1c84354, 0b2e600, b9517ad, b1bcedd)
• Fixed bug in PMA_SortAsPerfectMatching.m where the data type was too small (int8 -> int16) but some previous (old) examples now run out of memory on certain configurations (085aab7)
• Performance improvements to many subfunctions (41f5429, 58151e1, a9149cb, f5ef2b1, b9517ad, b1bcedd, 4dbc5b1, a7ac593)
• New helper functions for connected components bins (79a97bc), cycle detection (4dbc5b1), parent pointers (74c8524), and decimal labels (58151e1)
• Fixed issues some issues with generating structured graphs but not all methods are working at the time of release (b780435)

v3.0 Structured Release

This release includes the ability to enumerate problems where the graphs of interest contain structured components. The release is based on commit 316d23c.

Summary of Changes

• Added ability to handle graphs with structured components (cb4c1f1)
  • Added ability to define structured components with NSC.S in UniqueUsefulGraphs.m (f249f35)
  • Added Structured_SimpleCheckConnections.m to create the required data for the simple checks (316d23c)
  • Added isomorphism checking functions for structured graphs (316d23c)
• Updates to the labeled graph isomorphism checking methods
  • Added additional simple checks to RemovedColoredIsosMatlab.m (and Python), and there is a large reduction in isomorphism checking computation time in some cases (f249f35)
  • Added parallelization of python isomorphism checking method (only utilized with subcatalogs) (76b6f9d)
  • Fixed bug in RemovedColoredIsosPython.m when two graphs were reported as different but were actually the same (3e37761)
  • Changed the outputs from RemovedColoredIsosPython and RemovedColoredIsosMatlab to be the same (removed method-specific fields) (3e37761)
• Added line-connectivity constraint checks (76b6f9d)
• Changed plotTreeEnumerate.m and TreeEnumerateCreatev1Analysis.m for the new inputs and updated style (633f778)
• Added new implementation of the suspension example in MD-16-1635 which is much faster than the previous example (76b6f9d)
• Added consistent ordering to the outputted graphs, and see Test_ConsistentOrdering (3e37761)
• Fixed bugs (316d23c, 76b6f9d, fdcd683, 3e37761)

v2.0 Enhancements Release

This release includes a number of enhancements including more efficient generation of the graphs and new NSCs. The release is based on commit 4650d0b.

Summary of Changes

• Added a number of enhancements described in PDF (7d8c14d and 191b833). Major bug fix in (944be52).
  • Performance increase varies but can be more than 30x
• Added win64 mex versions for tree_v1 and tree_v8 (944be52)
  • Initial tests indicate up to 6x performance increase between non-mex version
• Added NSC defaults to DefaultNSC.m (af24a87)
• Added opts.subcatalogfun for custom filtering of subcatalogs (944be52)
• Fixed the creation of the connected components graph adjacency matrix in GenerateFeasibleGraphs (7d8c14d)
  • Note that this increases the number of unique graphs for some of the examples. Potential increase is only possible in examples with both loops and multi-edges present in feasible graphs.
• Changed the Graphs structure to be a true structure (previously a cell array of structures) (ed74a75)
• Changed how NSC.counts works, can now provide a boolean vector with the same length as P that indicates if individual component types should have a unique number of connections (8509525)
• Changed implementation of SortAsPerfectMatching and InversePerfectMatchings (4650d0b)
• Changed the method for generating unique numbers given a string using a base 36 system (af24a87)
  • This approach is guaranteed to be unique for the strings '0' to '2GOSA7PA2GW' or 1-10 character uppercase strings
• Changed NSC.necessary to NSC.M (7d8c14d and 1b0889a)
• Changed the names of some opts (6073de6)
• Fixed ExpandPossibleAdj to handle nonsymmetric A matrix (7d8c14d)

v1.1 First Minor Release Post IDETC2016-60212

This release is the first minor release after the initial code developed for the IDETC2016-60212 paper. The release is based on commit d042e89.

Summary of Changes

• Added license file (1b77ae8)
• Added default options (see DefaultOpts.m) (19e4438)
• Added in Matlab isomorphism checking method (opts.isomethod) (only available in 2016b and there is a bug in the internal MATLAB function that requires a manual fix, also the Matlab method is SLOW) (19e4438)
• Added ReorderCRP.m function that reorders {C,R,P} to a more favorable ordering for enumeration (more information to come, simply do not utilize this function if you want to maintain the user-defined ordering) (19e4438)
• Changed install script to use try and catch statements and will report if a feature is available or not (19e4438)
• Changed detectiso_func3.py to detectiso_func4.py and is now faster (19e4438)
• Fixed InitialPortIsoFilter.m to correctly sort edges first (edges with larger port numbers first), and then perform the unique row check to remove guaranteed port isomorphisms (19e4438)

v1.0 IDETC2016 Release

This release is the code developed for the IDETC2016-60212 paper. The release is based on commit bd0cc3f.