Fluent Interface to Build a Directed Cyclic Graph?

Question

I have created a set of classes to represent a directed cyclic graph for representing BPM processes, based on JUNG's DirectedSparseGraph class, which provides only basic graph manipulation methods to add and find vertices and edges.

The challenge I am facing is to create a builder that provides a fluent interface able to create a graph that includes complex branching, cycles, and multiple end nodes (see examples below).

Parallel Branches

Merging Branches

Cycles

Complex

My current implementation (see example below) is resorting to aliasing the vertex where a fork occurs (e.g., vertex "B" in Parallel Branches), and then I refer to the alias when adding a new branch to that vertex. My builder also includes something similar to allow for the merging of branches and cycles. Aliases were introduced because vertex names are not unique in BPM graphs. I want a more elegant fluent interface to quickly build graphs, free from those references.

Graph graph = GraphBuilder.newGraph()
                          .addVertex("A")
                          .edgeName("")
                          .addVertex("B", "b-fork")
                          .edgeName("")
                          .addVertex("C")
                          .edgeName("")
                          .addVertex("E")
                          .addBranch("b-fork")
                          .edgeName("")    
                          .addVertex("D")
                          .edgeName("")
                          .addVertex("F")
                          .build();

Abomination

Have you considered adding a DOT parser to your program? GraphBuilder.parse("A -> B; B -> C; B -> D;") seems more readable. – Grapefruit

@Duncan Please read the entire post. I'm not asking for the entire builder, I just want to not have a aliases, because they are not elegant. – Abomination

As you want to build a cyclic graph, but the method chain has a tree-structure, some form of aliasing seems inevitable. – Grapefruit

@Abomination Upon a second read, I think the scope is constrained enough. I think the wording at the end of your post and the lack of a specific closing question left me thinking you were after more. – Internalcombustion

@AdrianLeonhard Yes, I actually have written a DOT parser, but turned out that they are not as programmer-friendly as fluent interfaces. I also want software developers in test to be able to quickly create graphs for JUnit assertions. – Abomination

Answer 1

The problem is that the builder is a chain of methods, while you want to build a graph with cycles. You'll need to backtrack, and to do that it is necessary to refer to previous nodes either explicitely (using their label) or implictly, e.g:

    Graph graph = GraphBuilder.newGraph()
                      .addVertex("A")
                      .edgeName("")
                      .addVertex("B", "b-fork")
                      .edgeName("")
                      .addVertex("C")
                      .edgeName("")
                      .addVertex("E")

                      .goBack(2) // even worse than using label: breaks easily
                      .edgeName("")    
                      .addVertex("D")
                      .edgeName("")
                      .addVertex("F")
                      .build();

You could use a tree structure to build your graph:

    SubGraph.node("id", "label")
        .to("edgeName1", SubGraph.node("A").to("", SubGraph.node("C"))),
        .to("edgeName2", SubGraph.node("B"));

but this just delays the problem, as you will again need to refer to nodes explicitely when cycles come into play. Short of some sort of GUI or extensive ASCII-drawings there is no way to define a graph without aliases.

Personally I would recommend a DOT-style parser:

parse("a -> b -> c -> f -> e; f -> d -> b"); // "Cyclic graph"

which is both easier to read and to type.

EDIT: for the lulz: cyclic graph without aliasing:

    // do not ever do this:
    GraphBuilder.parseASCII(
            "     -->C--      \n" +         
            "    |      v     \n" +
            "A-->B      F-->E \n" + 
            "    |      ^     \n" +
            "     -->D--      \n");

Grapefruit

Nice point about backtracking, but yes it would break easily. If I were to use DOT, I would rather use text files. To represent larger graphs that string would become really long, and clunky. – Abomination

Answer 2

You could cut down on the parsing slightly by:

Graph graph = GraphBuilder.newGraph()
            .add("a,b,c,f,e")
            .add("f,d,b");

Eula

Your notation is simpler than DOT, but it doesn't capture the merging of branches into a vertex. – Abomination

unless i am missing something it does, by reusing the same name (f and b above). – Eula

I see. The second branch is completing the cycle b->c->f->d->b... The direction is not clear because it is inferred on the connections. – Abomination