1

I'm often tasked with relatively complex flows that my employers will want to experiment with in regards to the amount of steps and their order. I'm a contractor and when my work is handed over to another developer, I'd like to ship something that is easy to understand quickly - and a flow with 10+ steps is quite the mouthful. So I've written a prototype that takes a homemade JSON data structure, which allows for

  1. Executing that data structure with a state object passed to all conditions and continuing through the true-path of the flowchart.
  2. Turning the data structure into a graph that can be visualized, like the example below.

Flowchart

The supported types are: Condition, Step/State and Terminate.

I've seen various flowchart designers out there and were wondering if it would make sense to implement at subset of their data structure, so the flowcharts can be changed in both code and a visual designer. Perhaps it would allow for the flowcharts to be executed in other programming languages, since my own implementation is made in TypeScript only.

Are there any standard for flowchart data structures, and/or are there any defacto standard tool for editing flowcharts that needs to also be executed?

This is the prototype. Please note that it is very, very much just a prototype!

import { inspect } from "util"
import { Graph, json, alg } from "graphlib"
import * as fs from "fs"

let predicates = {
    isSomeCondition2: () => false,
    IsCvrActive: () => false,
    shouldContactCustomerService: () => false,
    canDeliverProduct: () => true,
    isChangingSupplier: () => true,
    isSomeCondition: () => true,
    isReceipt: () => false
}

let flow =
{
    type: "Flow", name: "Primary flow", nodes: [
        { type: "Step", name: "Enter CVR" },
        {
            type: "Condition", name: "Is CVR Active?", predicateKey: "IsCvrActive",
            right: {
                type: "Step", name: "CVR is inactive",
                left: { type: "Terminate", name: "Terminate (inactive cvr)" }
            }
        },
        {
            type: "Condition", name: "Should contact customer service?", predicateKey: "shouldContactCustomerService",
            left: {
                type: "Step", name: "Contact customer service",
                left: { type: "Terminate", name: "Terminate (contact customer service)" }
            }
        },
        {
            type: "Condition", name: "Can deliver product?", predicateKey: "canDeliverProduct",
            right: {
                type: "Step", name: "Cannot deliver product",
                left: { type: "Terminate", name: "Terminate (cannot deliver product)" }
            }
        },
        {
            type: "Condition", name: "DataHub has PODs for CVR?", predicateKey: "isChangingSupplier",
            left: { type: "Flow", name: "Switch provider", nodes: [
                { type: "Step", name: "Power destination addresses" }
            ]},
            right: { type: "Flow", name: "Relocation", nodes: [
                { type: "Step", name: "Enter address" },
                { type: "Step", name: "Enter POD" },
                { type: "Step", name: "Enter estimated annual volume" },
                { type: "Step", name: "Enter latest meter reading" }
            ]}
        },
        { type: "Step", name: "First payment" },
        {
            type: "Condition", name: "What receipt?", predicateKey: "isReceipt",
            left: { type: "Step", name: "Receipt1" },
            right: { type: "Step", name: "Receipt2" }
        }]
}

let start = new Date()

//console.log("== EVALUATED")
//let evaluatedFlow = evaluateFlow(flow)
//console.log(evaluatedFlow)

var i = 0;

let graph = traverseFlow(flow)

console.log("PARENT Is this a condition?")
console.log(graph.parent('Is this a condition?'));

console.log("PARENT Enter CVR")
console.log(graph.parent('Enter CVR'));

console.log("== GRAPH")
var graphJson = json.write(graph)
fs.writeFileSync("./graph.html", writeHtml(graphJson));
//console.log(inspect(graphJson, { showHidden: false, depth: null }))

console.log("== MINIMUM STEPS")
//let minimumSteps = findMinimumSteps(graph)
//console.log(minimumSteps)

let end = <any>new Date() - <any>start
console.info("\n\nExecution time: %dms", end)

function findMinimumSteps(graph: Graph) {
    let root = graph.sources()[0]
    let sinks = graph.sinks().filter(node => graph.node(node).type !== "Terminate")
    let dijkstraResult = alg.dijkstra(graph, root, e => graph.node(e.w).type === "Condition" ? 0 : 1)
    console.log("=== DIJSKTRA")
    console.log(dijkstraResult)
    let shortestPath = sinks
        .map(node => dijkstraResult[node])
        .reduce((a, b) => a.distance < b.distance ? a : b)
    return shortestPath.distance + 1
}

function traverseFlow(flow: any, graph?: Graph, parent?: any): Graph {
    graph = graph || new Graph({ compound: true })
    let sinks = parent ? [parent.name] : graph.sinks()

    flow.nodes
        .map(createFlowGraph)
        .forEach((subGraph: Graph) => {

            subGraph.nodes().forEach(node => {
                graph.setNode(node, subGraph.node(node))
                let parentFlow = subGraph.parent(node) || flow.name
                if(graph.node(parentFlow)) {
                    graph.setParent(node, parentFlow)
                }
            })
            subGraph.edges().forEach(edge => graph.setEdge(edge, subGraph.edge(edge)))

            sinks.forEach(outNode => {
                let label = graph.node(outNode)
                if (label.type !== "Terminate" && label.type !== "Flow")
                    subGraph.sources().forEach(inNode => {
                        if(subGraph.node(inNode).type !== "Flow")
                            graph.setEdge(outNode, inNode, { label: label.type === "Condition" ? conditionLabel(label, inNode) : undefined })
                    })
            })

            let unconnectedConditions = subGraph.filterNodes(n =>
                subGraph.node(n).type === "Condition" && (subGraph.outEdges(n) || []).length === 1).nodes()

            sinks = subGraph.sinks().filter(node => subGraph.node(node).type !== "Flow").concat(unconnectedConditions)
        })

    return graph
}

function createFlowGraph(root: any): Graph {
    let graph = new Graph({ compound: true })
    traverseBinaryNode(graph, root)
    return graph
}

function conditionLabel(condition: any, node: any) {
    let { left, right } = condition

    if(left && left.type === "Flow")
        left = left.nodes[0]

    if(right && right.type === "Flow")
        right = right.nodes[0]

    if(left && left.name === node)
        return true

    if(right && right.name === node)
        return false

    return !!condition.right
}

function traverseBinaryNode(g: Graph, node: any, parent?: any) {

    if(node.type === "Flow")
        g.setNode(node.name, (<any>Object).assign({}, node, {  label: node.name, clusterLabelPos: 'top', style: 'fill: #fff' }))
    else
        g.setNode(node.name, (<any>Object).assign({}, node))

    if (node.type === "Flow")
        traverseFlow(node, g, parent)

    if (node.left)
        traverseBinaryNode(g, node.left, node)

    if (node.right)
        traverseBinaryNode(g, node.right, node)

    if (parent && node.type !== "Flow")
        g.setEdge(parent.name, node.name, { label: parent.type === "Condition" ? conditionLabel(parent, node.name) : undefined })
}

function evaluateFlow(flow: any) {
    let steps = []
    for (let node of flow.nodes) {
        if (!evaluateNode(node, steps))
            break
    }
    return steps
}

function evaluateNode(node: any, steps: any[]) {
    steps.push(node)

    switch (node.type) {
        case "Condition": {
            if (predicates[node.predicateKey]())
                return evaluateNode(node.left, steps)
            else if (node.right)
                return evaluateNode(node.right, steps)

            // Continue to the next binary tree in the flow
            return true
        }
        case "Step": {
            if (node.left)
                return evaluateNode(node.left, steps)

            // Continue to the next binary tree in the flow
            return true
        }
        case "Terminate": {
            // Stop evaluating the flow
            return false
        }
    }

    throw Error("Unknown node type")
}

function writeHtml(graphJson) {
    return `
    <!doctype html>
    <html>
        <head></head>
        <body>
        <script src="https://d3js.org/d3.v4.min.js"></script>
        <script src="https://dagrejs.github.io/project/dagre-d3/latest/dagre-d3.js"></script>


        <style id="css">
        /* This sets the color for "TK" nodes to a light blue green. */
        g.type-TK > rect {
          fill: #00ffd0;
        }

        text {
          font-weight: 300;
          font-family: "Helvetica Neue", Helvetica, Arial, sans-serf;
          font-size: 14px;
        }

        .node rect {
          stroke: #999;
          fill: #fff;
          stroke-width: 1.5px;
        }

        .edgePath path {
          stroke: #333;
          stroke-width: 1.5px;
        }

        .clusters rect {
            fill: #00ffd0;
            stroke: #999;
            stroke-width: 1.5px;
          }

        </style>

        <svg id="svg-canvas" width=3000 height=3000></svg>


        <script>
// Here we"re setting nodeclass, which is used by our custom drawNodes function
// below.
var g = dagreD3.graphlib.json.read(JSON.parse(\`${JSON.stringify(graphJson, null, 2)}\`)).setGraph({})

// Create the renderer
var render = new dagreD3.render();

// Set up an SVG group so that we can translate the final graph.
var svg = d3.select("svg"),
    svgGroup = svg.append("g");

// Run the renderer. This is what draws the final graph.
render(d3.select("svg g"), g);

// Center the graph
var xCenterOffset = (svg.attr("width") - g.graph().width) / 2;
svgGroup.attr("transform", "translate(" + xCenterOffset + ", 20)");
svg.attr("height", g.graph().height + 40);

        </script>

        </body>
    </html>
    `
}

First do npm install graphlib then run with tsc file.ts && node file.js, then open graph.html

5
  • 1
    I'm sorry you feel that way. I've talked to other developers who says there are defacto ways to do this, unfortunately we're not in contact anymore. I'm sure there are great answers to this question.
    – Jan Sommer
    Oct 19, 2018 at 14:02
  • Why would there be a "standard" for flowchart data structures? Data structures are implementations. There isn't a standard for flowchart data structures for the same reason that compilers don't have a standard for how they are implemented, even though the language being implemented usually does have a standard. The compiler writer is free to implement the compiler any way he sees fit, so long as he conforms to the language standard. There are things like Abstract Syntax Trees, but that concept occurs at a higher level (hence the word "abstract"). Oct 19, 2018 at 14:14
  • 1
    That's too bad. I'm trying to build something that other developers would love to work with, and is thus asking for help. If there's no standard, so be it, but perhaps someone who's better than me at this have an opinion?
    – Jan Sommer
    Oct 19, 2018 at 14:18
  • 2
    Have a look here: xpdl.org and here: en.wikipedia.org/wiki/XPDL Oct 19, 2018 at 14:36

1 Answer 1

1

Business Process Model and Notation (BPMN) is a graphical representation for specifying business processes in a business process model.

enter image description here

Example of a Business Process Model and Notation for a process with a normal flow. From Wikipedia.

The XML Process Definition Language (XPDL) is a format standardized by the Workflow Management Coalition (WfMC) to interchange business process definitions between different workflow products.

XPDL is currently the best file format for exchange of BPMN diagrams; it has been designed specifically to store all aspects of a BPMN diagram. XPDL contains elements to hold graphical information, such as the X and Y position of the nodes, as well as executable aspects which would be used to run a process.

Further Reading
XML Process Definition Language (XPDL) on Wikipedia
XPDL 2.2 Website dedicated to the WfMC's XPDL specification
Business Process Model and Notation (BPMN) on Wikipedia

1
  • This is excellent. Not going to implement this, since it's too advanced, but should someone ask why I made something that's been made a million times before, I'd say that there's nothing non-proprietary that's simple enough for flowcharts. It seems like there's room for something simpler, compared to XPDL.
    – Jan Sommer
    Oct 21, 2018 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.