Generate the set of unique useful architectures with a perfect matching-based approach.
Matlab Python
Switch branches/tags
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

README (pm-architectures-project)

GitHub release GitHub contributors


Generate the set of unique useful architectures with a perfect matching-based approach.

readme image


open ex_md161635_CaseStudy1


Many elements of this project are discussed in the following papers. Please cite them if you use the project.

  • DR Herber, T Guo, JT Allison. Enumeration of Architectures with Perfect Matchings. Journal of Mechanical Design, 139(5), p. 051403, May 2017. [PDF]
    • Abstract: In this article, a class of architecture design problems is explored with perfect matchings (PMs). A perfect matching in a graph is a set of edges such that every vertex is present in exactly one edge. The perfect matching approach has many desirable properties such as complete design space coverage. Improving on the pure perfect matching approach, a tree search algorithm is developed that more efficiently covers the same design space. The effect of specific network structure constraints (NSCs) and colored graph isomorphisms on the desired design space is demonstrated. This is accomplished by determining all unique feasible graphs for a select number of architecture problems, explicitly demonstrating the specific challenges of architecture design. With this methodology, it is possible to enumerate all possible architectures for moderate scale-systems, providing both a viable solution technique for certain problems and a rich data set for the development of more capable generative methods and other design studies.
  • DR Herber, JT Allison. Enhancements to the Perfect Matching-based Tree Algorithm for Generating Architectures. Technical report, Engineering System Design Lab, UIUC-ESDL-2017-02, Urbana, IL, USA, Dec. 2017. [URL] [PDF]
    • Abstract: In this report, a number of enhancements to the perfect matching-based tree algorithm for generating the set of unique, feasible architectures are discussed. The original algorithm was developed to generate a set of colored graphs covering the graph structure space defined by (C,R,P) and various additional network structure constraints. The proposed enhancements either more efficiently cover the same graph structure space or allow additional network structure constraints to be defined. The seven enhancements in this report are replicate ordering, avoiding loops, avoiding multi-edges, avoiding line-connectivity constraints, checking for saturated subgraphs, enumerating subcatalogs, and alternative tree traversal strategies. Some theory, implementation details, and examples are provided for each enhancement.

External Includes

  • See INSTALL_PM_Architectures_Project.m for more information
  • MATLAB File Exchange Submission IDs (10922, 23629, 29438, 40397, 44673, 47246)
  • Python (Python 3.5, numpy package, igraph package), optional depending on isomorphism checking option

General Information


Project Links