Click here to Skip to main content
Click here to Skip to main content

GraphSynth - Design, Implement, and Test Graph Grammars

, 21 Nov 2006 CPOL
Rate this:
Please Sign up or sign in to vote.
GraphSynth is the first publicly available approach to creating graph grammars.
Sample Image - GraphSynth.jpg

Introduction

Graph transformation systems, or graph grammars, are a branch of graph theory research that rigorously defines mathematical operations such as addition and intersection in graphs. Mathematicians have developed the foundations of this research, and engineering design researchers have appropriated the concept to formalize the creation of complex engineering systems. Electric circuits, truss structures, and chemical processes are just a few of the artifacts of engineering design that are easily represented by graphs. When viewing the artifact as a graph constructed from an initial simpler graph that describes the problem, one needs to develop a set of rules to capture the valid transformations that can occur.

Rules and graphs in GraphSynth are stored in an XML format and are loaded into the program and instantiated as define graph object: nodes and arcs. Grammar rules are essentially constructed of two elements: application conditions (that, if met, are valid transitions in the state-space tree), and application instructions (how the graph is to be altered). These two elements are each represented as a graph: the conditional, recognition, or left-hand-side graph; and the application or right-hand-side graph.

Background

For a detailed description including some of the text found here, go to graphsynth.com.

Using the Code

Within the source files of GraphSynth, you will find the details for classes like grammarRule.cs and ruleSet.cs are stored in the project named Representation. The other main projects are Generation, GraphLayout, Evaluation, Guidance, Application_UI_and_Search. This final one, is the main one, the ".exe" is found in its bin directory. The other projects compile to DLLs. The authors of GraphSynth theorize that the division of representation, generation, evaluation, and guidance is useful in almost all computational synthesis methods. The representation is formulated by the programmer of the computational design method to capture the forms or attributes of the design space.

Other than these in GraphSynth, the project named GraphLayout contains custom layout algorithms that the researcher may write for their resulting graphs. Within the Application_UI_and_Search project, there is folder called MainFormsAndSettings which includes start up routines, and the display forms. The one file called searchProcess.cs not included in the directory is likely where a researcher would write their main search routine. In fact, in each project the ".cs" file not included in a subdirectory is open to modification. These are searchProcess.cs, inheritedGraphClasses.cs, graphLayout.cs, GetToOptimum.cs, and EvaluateSwirls.cs. The latter two are for the facetious example presented in the searchProcess.cs file. These should be studied and then deleted. They merely offer an example of how the projects are intended to interact. For a particular application, one would create their own evaluation methods, and thus there are no general methods that can be provided for this. For guidance strategies, there are currently no such methods for graph synthesis. Our current research is developing a number of these. In the meantime, GraphSynth can be used to synthesize graphs, either through user-guided or random decisions. Future updates will include guidance methods, and thus a full optimization procedure can be made to design optimal graph topologies.

Points of Interest

This work is part of an ongoing National Science Foundation funded research project. We have decided that C# offered the most powerful and easy approach to creating graph grammars. In the two years since our research has begun, we have borrowed from a number of CodeProject projects: most notably Netron (which is no longer available, but a version of it is compiled in this) and the properties Bag by Tony Allowatt.

History

  • Since GraphSynth 1.5.0.0 (October 31st, 2006)
    • Generation separated into its own DLL
    • candidate.undoLastRule fixed.
    • User Choose fixed.
    • New layout to user choose. Now the last rule that has been applied can be undone.
    • RuleSet number fixed.
    • Introduced new static class in Representation: SearchIO. This is intended to be the way in which various functions communicate with the main process and the search process controller.
    • These help files have been improved to reflect the changes. See new section at the bottom of Search Process
  • Since GraphSynth 1.1.2.1 (September 5th, 2006)
    • Separate DLLs! The biggest change is to make future updates and sharing of functions easier. There are now separate DLLs for various parts of the code.
    • In the Recognize-Choose-Apply Cycle, the cycle limit exit is moved from the end of the process (after apply) to the very beginning of the process (see new flowchart on the generation page.
    • Print command added – graphs can now be sent to the printer (Courtesy of Chaitanya Vempati).
    • “Confirm each user choose” fixed (was false when it meant true).
    • New Improved Graph Layout functions and DLL
      • Stop layout menu item removed
      • Netron Spring embedder sped up
      • Custom layout buttons
        • Only first three public methods under graphLayout will appear in list.
      • New keyboard shortcuts
      • Default layout added to global setting for this as well
    • Properties window divorces from main when graph window maximized
    • Fixed redraw problem by forcing Netron to redraw at key points in the code.
    • Switched order of output and input directories in global settings
    • Sped up printing to side bar text box
      • Output box now prints downward
      • Introduce consoleWriter in Representation DLL
      • Starts writing to splash screen
    • A warning is added in saving a rule if arc in K are accidentally connected up in opposite ways from L to R
    • Arc.othernode checks both to and from in case the node is not even known to arc
    • Terminate request honored after R, C and A
    • Candidate’s recipe and performance parameters set to public
    • RCA now void with since redundant that candidate is passed
  • Since GraphSynth 1.0.2.1 (July 14th, 2006)
    • The main change is the ability to edit settings within GraphSynth
    • A prompt for settings occurs at the onset if no settings file is found
    • Rule set has additional settings for how the Generation process will proceed
    • It is now possible to specify as many as 10 default rulesets compared to the previous 3
  • Since GraphSynth 0.0.0.0
    • Too numerous to list. GraphSynth started in January of 2005

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

mattica

United States United States
No Biography provided

Comments and Discussions

 
QuestionNice! what about license? PinmemberWin32nipuh6-May-07 20:59 
GeneralInteresting, but... PinmemberColin Angus Mackay22-Nov-06 4:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 21 Nov 2006
Article Copyright 2006 by mattica
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid