A groovy dsl for creating and traversing graphs. Graphs can be extended with types and plugins which allows developers to create the desired behavior and values for their algorithm.
There are two entry points into the dsl: The graph method, and BaseScript.
BaseScript is a transformation which allows developers to change the base
script class for the current script. By changing the script to DslScript a
new Graph becomes the delegate of the script.
#!/usr/bin/env groovy
@Grab(group='com.github.moaxcp', module='graph-dsl', version='latest.revision')
import graph.*
@groovy.transform.BaseScript DslScript script
plugin 'graphviz'
edge 'A', 'B'
assert graph.vertices.keySet() == ['A', 'B'] as Set
assert graph.edges.size() == 1
assert graph.edges.first() == new Edge(from:'A', to:'B')
image 'images/base-script-method.png'
This example of a graph creates two vertices named 'step1' and 'step2' as well as an edge between them. The basic graph structure is held in a map of named Vertex objects and a set of Edge objects. Each Edge contains the names of the two vertices it connects.
The same graph can be created using the graph method.
The entry-point to the dsl is the Graph.graph(Closure) method. This method
applies the closure to a new Graph object and returns it.
#!/usr/bin/env groovy
@Grab(group='com.github.moaxcp', module='graph-dsl', version='latest.revision')
import graph.*
import static graph.Graph.*
def graph = graph {
edge 'A', 'B'
}
assert graph.vertices.keySet() == ['A', 'B'] as Set
assert graph.edges.size() == 1
assert graph.edges.first() == new Edge(from:'A', to:'B')
graph.plugin 'graphviz'
graph.image 'images/graph-method.png'
There are a few rules the dsl follows:
- All referenced vertices are created if they don't exist.
- If an edge or vertex already exists it will be reused by an operation.
- Type can be changed at any time if the type is compatible with the current graph structure.
- Plugins can be applied at any time.
- Vertices and edges are always Maps.
All traversal methods start at a root vertex and traverse the graph. A closure is called on each "visit" which can modify the graph in some way. The following examples create a graph and perform a traversal.
type 'directed-graph'
plugin 'graphviz'
vertex('A') {
connectsTo('B') {
connectsTo('C')
connectsTo('D')
}
connectsFrom('D') {
connectsTo('C')
connectsTo('E')
}
connectsTo('E')
}
snapshot()
eachBfs('A') { vertex ->
vertex.fillcolor = 'green'
vertex.style = 'filled'
snapshot()
}
gif 'images/breadth-first-traversal.gif'
type 'directed-graph'
plugin 'graphviz'
vertex('A') {
connectsTo('B') {
connectsTo('C')
connectsTo('D')
}
connectsFrom('D') {
connectsTo('C')
connectsTo('E')
}
connectsTo('E')
}
snapshot()
preOrder('A') { vertex ->
vertex.fillcolor = 'green'
vertex.style = 'filled'
snapshot()
CONTINUE
}
gif 'images/pre-order-traversal.gif'
type 'directed-graph'
plugin 'graphviz'
vertex('A') {
connectsTo('B') {
connectsTo('C')
connectsTo('D')
}
connectsFrom('D') {
connectsTo('C')
connectsTo('E')
}
connectsTo('E')
}
snapshot()
postOrder('A') { vertex ->
vertex.fillcolor = 'green'
vertex.style = 'filled'
snapshot()
CONTINUE
}
gif 'images/post-order-traversal.gif'
Note: This is the DAG created by the java gradle plugin
type 'directed-graph'
plugin 'graphviz'
edge 'compileJava', 'classes'
edge 'processResources', 'classes'
vertex('classes') {
connectsTo 'javadoc'
connectsTo('compileTestJava') {
connectsTo('testClasses') {
connectsFrom('processTestResources')
connectsTo('test') {
connectsFrom 'classes'
connectsTo('check') {
connectsTo 'build'
}
}
}
}
connectsTo('jar') {
connectsTo 'uploadArchives'
connectsTo('assemble') {
connectsTo 'build'
}
}
}
snapshot()
reversePostOrder('build') { vertex ->
vertex.fillcolor = 'green'
vertex.style = 'filled'
snapshot()
CONTINUE
}
gif 'images/reverse-post-order-traversal.gif'
This example classifies edges and colors them by type. The closure takes the arguments from, to, and type. These arguments can be used to modify the graph. In this example the edges are colored and labeled with the type.
type 'directed-graph'
plugin 'graphviz'
vertex('A') {
connectsTo('B') {
connectsTo 'C'
connectsTo('D') {
connectsTo 'A'
connectsFrom 'A'
connectsTo 'C'
connectsTo 'E'
}
}
}
vertex('F') {
connectsTo('G') {
connectsTo 'D'
}
}
snapshot()
classifyEdges('A') {Object from, Object to, EdgeType type ->
edge(from, to) {
switch(type) {
case EdgeType.TREE_EDGE:
color = 'green'
snapshot()
label = 'tree'
break
case EdgeType.BACK_EDGE:
color = 'red'
snapshot()
label = 'back'
break
case EdgeType.FORWARD_EDGE:
color = 'grey'
snapshot()
label = 'forward'
break
case EdgeType.CROSS_EDGE:
color = 'blue'
snapshot()
label = 'cross'
break
}
}
snapshot()
CONTINUE
}
snapshot(4)
gif 'images/edge-classification.gif', 500
Connected component visits each vertex supplying the root vertex for the component. The closure parameters are the root vertex key and the current vertex.
plugin 'graphviz'
vertex('A') {
connectsTo('B') {
connectsTo 'C'
}
connectsTo 'C'
}
vertex('Z') {
connectsTo('X') {
connectsTo('Y')
}
connectsTo('W') {
connectsTo 'X'
}
}
vertex 'J'
def colors = ['A':'yellow', 'Z':'green', J:'blue']
snapshot()
connectedComponent('A') { root, vertex ->
vertex.fillcolor = colors[(root)]
vertex.style = 'filled'
snapshot()
CONTINUE
}
gif 'images/connected-component-undirected.gif'
type 'directed-graph'
plugin 'graphviz'
vertex('A') {
connectsTo('B') {
connectsTo 'C'
}
connectsTo 'C'
}
vertex('Z') {
connectsTo('X') {
connectsTo('Y')
}
connectsTo('W') {
connectsTo 'X'
}
}
vertex 'J'
def colors = ['A': 'yellow', 'Z': 'green', J: 'blue']
snapshot()
connectedComponent('A') { root, vertex ->
vertex.fillcolor = colors[(root)]
vertex.style = 'filled'
snapshot()
CONTINUE
}
gif 'images/connected-component-directed.gif'
The Default behavior of a graph is undirected. These graphs have a set of edges
where only one edge can connect any two vertices. An undirected graph can be
changed to a directed graph at any time using the type method.
//lots of code
type 'directed-graph'
//lots of codeThere are functional search methods built on the depthFirstTraversal and breadthFirstTraversal method. These methods
follow the standard names in groovy: each, find, inject, findAll, collect. The methods can specify which type of
search to perform such as eachBfs or eachDfs.
eachBfs {
println it.id
}
def vertex = findBfs {
it.id == 'A'
}
def bfsOrder = collectBfs {
it.id
}Note: These methods are not yet implemented for depth first traversal. The depth first search methods will be the defaults when a search type is not specified.
Vertex keys are used to refer to a Vertex in the dsl. Keys can be any object which implements equals and hashCode.
Since Edge and Vertex are maps, all of the syntax for maps apply to them. In a dsl closure assignments create and entry in the Edge or Vertex.
edge('A', 'B') {
label = 'edge label'
}
vertex('step1') {
label = 'first step in process'
}If non dsl entries are used in a dsl method they are added to the object.
edge('A', 'B', [weight:10]) //weight is a non dsl entry
vertex('step1', [connectsTo:step1, color:'red']) //color is a non dsl entryTypes can be changed with the type methods.
type 'directed-graph'
type graph.type.DirectedGraphTypeA graph's type determines specific behavior. A type can change a normal graph to an directed-graph. It can add wieght to the graph. It can change the graph to a DAG. Developers can make their own type and apply it to a graph. Types can:
- replace all edges and vertices
- add methods to the edge and vertex dsl
- change the data structures used by the graph
- add constraints to the structure of the graph
The type of a graph may be changed at any time. An undirected-graph may be changed to a directed-graph which can be changed back to an undirected-graph.
type 'directed-graph'The DirectedGraphType changes the behavior of a graph to that of a directed graph. In a directed graph edges become directional. Only two edges can exist between any two vertices. In that case, the edges need to go in opposite directions.
Traversal methods will only follow out edges from a vertex.
type 'weighted-graph'WeightedGraphType is an undirected graph where edges can have weight. Traversal methods follow edges with the least weight.
Edges can be assigned weight within the dsl.
type 'weighted-graph'
edge 'A', 'B', [weight:10]
edge ('A', 'B') { weight = 10 }type 'weighted-directed-graph'WeightedDirectedGraphType is a directed graph where edges can have weight. Traversal methods follow edges with the least weight.
Plugins may be applied with the plugin methods.
plugin 'graphviz'
plugin graph.plugin.GraphVizGraphviz is a graph visualization toolset. The project provides a dsl called dot for visualizing graphs. The graphviz plugin provides methods to create dot strings, BufferedImages and to view the graph. Edge and Vertex attributes will be used as dot attributes.
type 'directed-graph'
plugin 'graphviz'
vertex('A') {
connectsTo('B') {
connectsTo 'C', 'D'
}
connectsTo('D') {
connectsTo 'C'
connectsTo 'E'
}
connectsFrom 'D'
}
vertex 'F', [connectsTo:'G']
edge 'G', 'D'
image 'images/graphviz.png'
Follow this guide to install git.
https://git-scm.com/book/en/v2/Getting-Started-Installing-Git
clone the project from github.
git clone https://github.com/moaxcp/graph-dsl.git
The project uses gradle for the build system. Using gradlew, you do not need to install gradle to build the project.
./gradlew build
All contributions are welcome. Please submit a pull request to the develop branch in github.
Even if you are just learning groovy there are many ways to contribute.
- Fix a codenarc issue. See codenarc report
- Add/fix groovydoc
- create a wiki page
- create a plugin
- add a graph algorithm
If there are any issues contact me moaxcp@gmail.com.
- graphviz pluging can now create gifs
- connectsFrom now works for undirected graphs
- closure in vertex and edge methods now delegate to objects for code completion
- vertex.key has been renamed to vertex.id
- edge.one has been renamed to edge.from
- edge.two has been renamed to edge.to
-
Switched to using reckon gradle plugin. This is an opinionated version similar to gradle-gitflow but there is no need to use gitflow
-
Stopped using gitflow and simply use master with tagged versions for releases
-
removed NameSpec for naming vertices and all associated methods.
-
Traversal methods are now in TraversalDsl trait
-
depthFirstSearchis now split inprotected void addVertex(Vertex vertex) { }to two methods
preOrder, andpostOrder -
breadthFirstSearchhas been simplified -
added new traversals
classifyEdges,connectedComponent -
Can now change key of vertex by assigning property in vertex method closures
-
Can now change one or two of edge by assigning property in edge method closures
Adding graphviz plugin.
Vertices and edges are now maps. Closures in entries are not resolved as was the case when dynamic properties were set.
Example
edge.weight = { queue.size() }
assert edge.weight == 10 //in 0.22.0 would call the closure. In this release the closure is returned.#102 Switch from name to key
In this release Vertex.name has been repalced with Vertex.key. The key may be any object that implements equals and hashCode.
This release represents a major change in how graphs are typed. Additional functionality is no only added through a Type. Type is the delegate of a Graph. A graph's type provides additional methods and can change any aspect of how a graph works. Types provide a graph with edges and vertices. They define the EdgeSpec and VertexSpec which means a type may add new methods to the dsl for building edges and vertices.
- upgraded to gradle 4.2
- replaced plugins with type
- edges and vertices can now add properties dynamically. This removes the need for traits.
Adding DslScript which can be used with @BaseScript to make a new Graph object the delegate of the current script.
- #91 Plugins should be called Type
This change adds names for types of graphs and plugins. Instead of the developers needing to import and use classes they can simply use a name.
type 'directed-graph'
plugin 'edge-map'
- #93 NameSpec and ConfigSpec
- runnerCode can no longer be set in map parameters to vertex and edge methods
This release includes a major refactor in how graphs are built. Configurations for vertex and edge methods have been
refactored to use NameSpec and ConfigSpec object. A NameSpec is a wrapper for a string. It represents the name of
something. A ConfigSpec is a wrapper around a map and closure. It represents the configuration for something. NameSpec
and ConfigSpec are a common interface for graph types to share. VertexSpec and EdgeSpec are now controlled by the graph
type. Types can add new properties and methods for use in a ConfigSpec. An example of this is connectsFrom in a
directed graph. connectsFrom can only be used after applying DirectedGraphPlugin. Graph types can override methods
like connectsTo and connectsFrom to perform checks before adding edges. This will be important when the DAG type is
added.
For the first time packages have been introduced to the project.
- plugin
- these are plugins which add functionality not related to specific types of graphs
- trait
- these are traits which can be used on vertices and edges
- type
- these are types of graphs and related classes
Factories for EdgeSpec and VertexSpec are now used by Graph. This allows plugins to add new behavior to the edge and vertex methods. New attributes and methods can be added to the ConfigSpec used in these methods. DirectedGraphPlugin uses this to add connectsFrom to the map and closure in the ConfigSpec.
- #82 Methods that take vertex names should also take VertexNameSpec
- #84 Configure gradle to fail for codenarc violations and jacoc verification
- #87 TraversalSpec should return VertexNameSpec when property or method is missing
- #85 Traversal methods should accept a root param
- #80 Removed sonarqube since it no longer supports groovy
- #78 Changed edgesFirst and edgesSecond in dsl to connectsTo and connectsFrom.
- #77 renameOne and renameTwo in edge methods will not add extra vertex objects to the graph.
This release combines fixes for a few issues on github.
- #75 Vertex.name, Edge.one, and Edge.two is now @PackageScope. This only affects code that is @CompileStatic for now due to GROOVY-3010.
- #74Vertices and edges may now be deleted. A vertex cannot be deleted if there are edges referencing it.
- #73 Added EdgeWeightPlugin. This plugin adds the Weight trait to each edge. Traversal methods are ordered by edge weight.
There were also several other changes that were not an issue on github:
Updated gradle to 3.5. Refactored gradle script to use the plugins closure when possible. gradle-gitflow does not work with the closure because it is not in the gradle repository. This is another reason to update the plugin. Spock was also updated to 1.1.
Added edgeTraits and vertexTraits. These methods will ensure traits are applied to current and future edges and vertices.
Added tests to provide more code coverage in jacoco.
Added more usage details to README.md
Just as in 0.13.0, where the config closure was removed from VertexSpec, this release removes the config closure from EdgeSpec. Traits can be added and configured for an Edge all within the same closure.
graph.with {
edge (step1, step2) {
traits Mapping
message = "hello from edge between $one and $two"
queue = [] as LinkedList
traits Weight
weight { queue.size() }
}
}As in 0.13.0 this represents a major step in finalizing the edge api.
This release removes the need for the config closure when creating a vertex. It is now possible to apply traits and configure them all within the closure passed to vertex methods.
graph.with {
vertex step1 {
traits Mapping
message = 'hello from step1'
queue = [] as LinkedList
traits Weight
weight { queue.size() }
}
}This change represents a major step in finalizing the vertex api.
This release introduces a new way of creating a Vertex. The new methods allow vertices to be created without using strings for names. Vertices can now be added with the following syntax.
graph.with {
vertex step1
vertex step2(traits:Mapping)
vertex step3 {
traits Mapping
config {
label = 'step3'
}
}
vertex step4(traits:Mapping) {
config {
label = 'step4'
}
}
}This was achieve by adding propertyMissing and methodMissing to Graph which return a VertexSpec. A vertex(VertexSpec) method was added to allow this syntax.
Removing connectsTo from VertexSpec and replacing it with edgesFirst and edgesSecond. This helps in creating directed graphs using the vertex methods. It also helps when creating vertices first then applying the DirectedGraphPlugin.
Publishing of gh-pages was still broken. This release fixed the issue. Also added reports to gh-pages so we can now view test results, code coverage, and static analysis.
Fixed publishing of gh-pages.
Release to maven central for 0.10.0 failed. Upgraded gradle-nexus-staging-plugin which fixed the problem.
This release features breadth first search methods. These are methods that follow the standard collection methods that come with groovy: eachBfs, findBfs, findAllBfs, injectBfs, and collectBfs. There are two overrides for each. The first takes a closure and starts at the first vertex in the vertices map. The second can specify the root to start at in the breadth first traversal. Here is a short example using findBfs:
findBfs {
it.work > 0
}Finds the first vertex with work > 0
findBfs('step4') {
it.work > 0
}Finds the first vertex with work > 0 starting at step4.
Added reversePostOrder to DirectedGraphPlugin. This will allow a DirectedGraph to perform a closure on each vertex in reverse post order (topological order). Also added reversePostOrderSort which returns the vertex names in reverse post order of a graph.
DirectedGraphPlugin was reorganized making it possible to javadoc methods dynamically added to the graph. The methods added are static in DirectedGraphPlugin. They are added to Graph's metaClass using method pointers while currying the graph param to the apply method. This could be used in future plugins.
- fixing publishing of javadoc and groovydoc. gh-pages branch must exist.
- Automatically publishing javadoc and groovydoc to gh-pages.
This is a major update to the api. It focuses on the edge and vertex methods in Graph. These methods
provide developers with the flexibility to create and configure the objects as they see fit. All edge
and vertex methods return the object which allows the object to be configured with the << operator.
The methods use *Spec objects to store specifications for the edge or vertex and then applies it to the
graph. See the groovydoc for more details.
- upgraded to groovy-2.4.10
- Adding edge and vertex methods to Graph which provides many new ways to manipulate a graph.
- Vertices can be renamed and edges can be moved to different vertices.
- Anytime a vertex is referenced it will be created.
- Added support for classifying edges. This can be used to detect cycles in a graph.
- Added test coverage.
- Added javadoc.
- fixed issue with logging when optimizations are turned off
- updating gradle to 3.4.1
- fixed many codenarc issues
- added support for breadth first traversal
- Added warning when optimizations are turned off
- Adjusting retry time for nexus-staging-plugin
- Fixed vertex and edge methods so they can modify existing objects
- Added entry point to dsl though graph method
- Added trait key to vertex and edge map. This makes it easier to add a single trait.
- Following suggestions from #5 to fix nexus release issue
- Adding fix for closeAndPromoteRepository
- Switched from maven-publish to maven plugin
- Fixes for maven-publish plugin.
- Artifacts publish to nexus automatically
- Added delegate support for Edges and Vertices
- Added VertexMapPlugin and EdgeMapPlugin
- Optimized codenarc configuration using the ruleset method.
- Updated gradle to version 3.3.
- Added Plugin interface for all Plugins to implement.
- Added plugins property to Graph which contains all plugins applied to the Graph.
- Adde DirectedGraph plugin which converts a Graph into a DirectedGraph.
sonarqube.com doesn't seem to show any issues for groovy projects. This release adds codenarc support for local development. This allows developers to view issues right away without worrying about sonar.
- Changed travis.sh so master gets published to sonar instead of develop.
- initial plugin support
- DirectedGraph plugin
- Support for vertices, edges, and depth first traversal
The license can be found in the LICENSE file.
MIT License
Copyright (c) 2017 John Mercier