Graph theory graphs or "pentagram"

tojamrok commented 2 months ago

Proposal

Now that Mermaid uses Cytoscape.js for the Mindmap diagrams it will be possible to add support for the graph theory graphs. Something like the examples in the https://cytoscape.org/cytoscape.js-tutorial-demo/ with various automatic layouts which use Graph Theory algorithms to find the "best" layout.

In the lowest denominator, the Mindmap layout looks really neat, however for my use cases it lacks one feature: it is a tree, it cannot create loops. It would be good to be able to specify a full graph or a sequenced nodes of a connection graph, something lite the TIPC scalability architecture graph, similar to a pentagram graph, on the http://www.tipc.io/cluster.html page.

Use Cases

Graph Theory. Networking architecture.

Screenshots

Circular graph with node sequence:

Kosaraju-Tarjan strongly connected graph components (in this specific case could be done with a flowchart and subgraphs):

Pentagram with arrows and arrow labels:

Planar graphs (links do not cross):

Syntax

graph CIRCULAR
    name="full graph"
    sequence A, B, C, D, E
    A -- B
    A -- C
    A -- D
    A -- E
    B -- C
    B -- D
    B -- E
    C -- D
    C -- E
    D -- E

graph
  name="tarjan-kosaraju"
  subgraph A, B, C
  subgraph D, E
  subgraph F G
  subgraph H
  A -> B
  B -> C
  B -> A

  D -> B
  D -> C
  D -> E
  E -> D
  E -> F

  F -> B
  F -> G
  G -> F 

  H -> H
  H -> E
  H -> G

Implementation

This is a proposal which I'd love to see built into mermaid by the wonderful community.

tojamrok commented 2 months ago

For the pentagram case the cythoscape.js way is as follows:

<!DOCTYPE html>
<html>
    <head>
        <title>Cytoscape.js Example</title>
        <script src="https://cdn.jsdelivr.net/npm/cytoscape@3.23.0/dist/cytoscape.min.js"></script>
        <style>
#cy {
    width: 800px;
    height: 600px;
    border: solid 1px black;
}
        </style>
    </head>
    <body>
        <div id="cy"></div>
        <script>
            var cy = cytoscape({
                container: document.getElementById('cy'),

                elements: {
                    nodes: [
                        { "data": { "id": "n1" } },
                        { "data": { "id": "n2" } },
                        { "data": { "id": "n3" } },
                        { "data": { "id": "n4" } },
                        { "data": { "id": "n5" } }
                    ],
                    edges: [
                        { "data": { "id": "e1", "source": "n1", "target": "n2" } },
                        { "data": { "id": "e2", "source": "n1", "target": "n3" } },
                        { "data": { "id": "e3", "source": "n1", "target": "n4" } },
                        { "data": { "id": "e4", "source": "n1", "target": "n5" } },
                        { "data": { "id": "e5", "source": "n2", "target": "n3" } },
                        { "data": { "id": "e6", "source": "n2", "target": "n4" } },
                        { "data": { "id": "e7", "source": "n2", "target": "n5" } },
                        { "data": { "id": "e8", "source": "n3", "target": "n4" } },
                        { "data": { "id": "e9", "source": "n3", "target": "n5" } },
                        { "data": { "id": "e10", "source": "n4", "target": "n5" } }
                    ]
                },

                layout: {
                    name: 'circle',
                    rows: 1
                },

                style: [
                    {
                        selector: 'node',
                        style: {
                            'background-color': '#666',
                            'label': 'data(id)'
                        }
                    },
                    {
                        selector: 'edge',
                        style: {
                            'width': 2,
                            'line-color': '#ccc',
                            'target-arrow-color': '#ccc',
                            'target-arrow-shape': 'triangle'
                        }
                    }
                ]
            });
        </script>
    </body>
</html>

tojamrok commented 2 months ago

The Kosaraju-Tarjan graph can be depicted with the Cytoscape.js JSON format as follows:

<!DOCTYPE html>
<html>
    <head>
        <title>Cytoscape.js Example</title>
        <script src="https://cdn.jsdelivr.net/npm/cytoscape@3.23.0/dist/cytoscape.min.js"></script>
        <style>
#cy {
    width: 800px;
    height: 600px;
    border: solid 1px black;
}
        </style>
    </head>
    <body>
        <div id="cy"></div>
        <script>
            var cy = cytoscape({
                container: document.getElementById('cy'),

                elements: {
                    nodes: [
                        { "data": { "id": "group1", "parent": "root" } },
                        { "data": { "id": "node1", "parent": "group1" } },
                        { "data": { "id": "node2", "parent": "group1" } },
                        { "data": { "id": "node3", "parent": "group1" } },

                        { "data": { "id": "group2", "parent": "root" } },
                        { "data": { "id": "node4", "parent": "group2" } },
                        { "data": { "id": "node5", "parent": "group2" } },

                        { "data": { "id": "group3", "parent": "root" } },
                        { "data": { "id": "node6", "parent": "group3" } },
                        { "data": { "id": "node7", "parent": "group3" } },

                        { "data": { "id": "group4", "parent": "root" } },
                        { "data": { "id": "node8", "parent": "group4" } },

                    ],
                    "edges": [
                        { "data": { "id": "e1", "source": "node1", "target": "node2" } },
                        { "data": { "id": "e2", "source": "node2", "target": "node3" } },
                        { "data": { "id": "e3", "source": "node3", "target": "node1" } },

                        { "data": { "id": "e4", "source": "node4", "target": "node5" } },
                        { "data": { "id": "e5", "source": "node5", "target": "node4" } },
                        { "data": { "id": "e6", "source": "node4", "target": "node2" } },
                        { "data": { "id": "e7", "source": "node4", "target": "node3" } },

                        { "data": { "id": "e8", "source": "node6", "target": "node7" } },
                        { "data": { "id": "e9", "source": "node7", "target": "node6" } },
                        { "data": { "id": "e10", "source": "node6", "target": "node3" } },

                        { "data": { "id": "e11", "source": "node8", "target": "node5" } },
                        { "data": { "id": "e12", "source": "node8", "target": "node7" } },
                        { "data": { "id": "e13", "source": "node8", "target": "node8" } },
                    ]
                },

                layout: {
                    name: 'cose',
                    rows: 1
                },

                style: [
                    {
                        selector: 'node',
                        style: {
                            'background-color': '#666',
                            'label': 'data(id)'
                        }
                    },
                    {
                        selector: 'edge',
                        style: {
                            'width': 2,
                            'line-color': '#ccc',
                            'target-arrow-color': '#ccc',
                            'target-arrow-shape': 'triangle',
                            'curve-style': 'bezier'
                        }
                    },
                    {
                        selector: 'node[parent]',
                        style: {
                            'background-color': 'lightblue',
                            'border-width': 2,
                            'border-color': 'blue',
                            'shape': 'rectangle'
                        }
                    }
                ]
            });
        </script>
    </body>
</html>

mermaid-js / mermaid