It's about time to start adding stable/beta tags for others relying on this library and make sure we adhere to semantic versioning.

This is mostly an administrative task. We should think about which version we're starting at (IMHO the current state is somewhere near v0.5, but we're actually lacking any previous tags) and make sure to provide a changelog that includes breaks in backwards compatibility.

Possibly also consider tagging some older beta releases?

After merging #22 not paying enough attention we need to make sure how to merge PRs.

I personally don't care about my commit messages but as I wrote in http://build2be.com/content/do-we-need-git-squash-and-thus-forced-pushes squashing is an ok workflow.

Cherry picking on the other hand is too much of a burden regarding PRs. Github provides a nice workflow regarding merging providing a 'delete branch' in the end.

So let's do the squash workflow:

• evaluate all tasks from the issue
• check the code
• squash the branch
• merge the PR
• delete the branch

@clue what do you think?

I somehow needed to do

$ git diff
diff --git a/lib/Fhaculty/Graph/Loader/UmlClassDiagram.php b/lib/Fhaculty/Graph/Loader/UmlClassDiagram.php
index 63e5035..2d15650 100644
--- a/lib/Fhaculty/Graph/Loader/UmlClassDiagram.php
+++ b/lib/Fhaculty/Graph/Loader/UmlClassDiagram.php
@@ -65,7 +65,7 @@ class UmlClassDiagram extends Base
         } else {
             $reflection = new ReflectionClass($class);
         }
-        $vertex = $this->graph->createVertex($class);
+        $vertex = $this->graph->createVertex($class, TRUE);

         $parent = $reflection->getParentClass();
         if ($parent) {

I feeded it with get_declared_classes();

  $loader = new UmlClassDiagram();
  try {
    foreach ($classes as $class) {
      $loader->createVertexClass($class);
    }
  }
  catch (Exception $exc) {
    return $exc->getMessage();
  }

My test environment is a little tricky so I was wondering how we test this easier.

BTW awesome UML generator.

• http://build2be.com/content/views-core-awesome-uml-route
• http://build2be.com/content/graphviz-blockstorageunittest

Current Dijkstra implementation is very slow.

I tried running it on graph which contains ~100 edges and it ran ~1s. Other implementations are 100x faster.

http://en.wikipedia.org/wiki/Complement_graph
http://reference.wolfram.com/mathematica/ref/GraphComplement.html
http://www.xatlantis.ch/examples/graph_example.html
http://www.mathcove.net/petersen/lessons/get-lesson?les=37

I have code like this:

$graph = new \Fhaculty\Graph\Graph();
$v1 = $graph->createVertex(1);
$v2 = $graph->createVertex(2);
$v5 = $graph->createVertex(5);
$v6 = $graph->createVertex(6);

$v1->createEdge($v2)->setWeight(4);
$v2->createEdge($v5)->setWeight(4);
$v5->createEdge($v6)->setWeight(4);

$alg = new \Fhaculty\Graph\Algorithm\ShortestPath\Dijkstra($v1);
echo $graph;
var_dump($alg->getDistance($v6));

it has output as excepted:

graph G {
  1 -- 2 [label=4]
  2 -- 5 [label=4]
  5 -- 6 [label=4]
}
int(12)

but if I change sequence of creating vertices

$v1 = $graph->createVertex(1);
$v2 = $graph->createVertex(2);
$v6 = $graph->createVertex(6);  // this vertex was created as last
$v5 = $graph->createVertex(5);

// other code is the same

I get this output:

graph G {
  1 -- 2 [label=4]
  2 -- 5 [label=4]
  5 -- 6 [label=4]
}

And distance isn't count because maximum execution time exceeded.

Graph is the same in both cases, so result has to be same too.

In several issues we run into particular graphviz related issues. These should probably not belong to graph repo perse.

• #96
• #92
• clue/graph-uml#23 (related)

What we could do is move this to graph-uml but that library still tries to become graphviz independent.

Maybe graphviz repo is ok? https://packagist.org/search/?q=graphviz has some hits so maybe not the best name.

Trying to grasp what a Graph or Set or UmlClassDiagram is hard to get as these lacks class level documentation.

I'm esp. interested in code examples for each class.

I hope to use this Component to replace mine used for http://drupal.org/project/graphapi.

Walk::factoryFromVertices($vertices,$by=Edge::ORDER_FIFO,$desc=false)

How about return $this value in
https://github.com/clue/graph/blob/master/src/Vertex.php#L380
(fluent interface) ?

you must include license text for MIT license

As UML is not related to Graph data we should move it out of Graph project

We need to support any widespread import/export format in order to be able to add a layer of persistence.

Comparing GraphML, GXL, TGF, GML, DGML and XGMML, GraphML seems to have a good support in other graph libraries and editors and seems sufficiently easy to implement. It's XML-based, widespread, supports mixed graphs, nested graphs and can be easily extended with custom attributes.

http://en.wikipedia.org/wiki/GraphML

We currently have several classes that are concerned with creating / building graphs from certain parameters or input graphs:

• Algorithm\ResidualGraph
• Algorithm\TransposeGraph
• Loader\CompleteGraph
• Future ComplementGraph (see #60)
• Possibly some others

IMHO both Algorithm and Loader are bad descriptions and do not quite describe their responsibility. As a first step, I'd vote for grouping these in a new Builder (or similar) namespace. In the future we should work out a decent API (interface).

Refs #120.

This project should be split into several smaller components in order to simplify code reuse and avoid having to pull in unrelated files.

This raises a couple of questions though:

Which components should be split?
This is mainly smaller library size vs. lots of libraries
Fine grained splitting might be useful, however splitting classes like Dijkstra to its own library might be confusing. Perhaps keep all shortest path algorithms as "graph-algo-shortestpath"?
For now, we should probably NOT split the whole library, but only those parts where it's useful. (Also refs #24)
At some point in time we will probably need something like a "graph-datastructure" base library.

Preserve history?
Assuming we split the UmlClassDiagram, I suppose we should keep its history in the new repo? What about previous versions / renames? Once it's been moved to a separate repo, the relevant classes should be deleted from this main project (and thus preserve its history both here and in the new repo).
Consensus? Best practice?

Where to move to?
Once we start adding a bunch of libraries, we should consider adding it to a github organization. I've created a "fhaculty" organization mirroring the current namespace. Moving everything is going to incur BC breaks and will likely confuse people, so this is not an immediate option.

BC breaks?
Should not be an issue: New split libraries should be reference via composer.json in this project and paths should be unchanged for the first release. Add entry to CHANGELOG. Besides this library being considered beta, this should not break.

Meta data?
Like said above, each new split library should be referenced in this project's composer.json. Also, each new split library should get its own set of meta files, including:

• composer.json
• Add to packagist
• Unit tests
• Travis config

Any thoughts?

Base classes (Graph, Vertex and Edge) should not be polluted with algorithm definitions. Tight coupling should be avoided, the algorithms already live in the Algorithm namespace, so there's no need to bloat the API and duplicate methods.

Quite obviously, this will break BC, so make sure to properly document in CHANGELOG.md.

Eventually, this should simplify extending the base classes (ticket #26).

Support native cloning of Graph, Vertex and Edge.

As it works right now, you can set a edges weight as NULL, FLOAT, INT but I need to more than one weight on an edge. In other words i need to set an edges weight to an array or an stdClass object.

I also need to set a vertexes data to an array/object.

How hard is this for you to implement? Maybe even adding a new property to each called "data" so you do not have to change the current functionality.

We do have algorithms but we should have some transformers which test for an algorithm then apply a solution to validate that algorithm.

For example http://thejit.org has a space tree so we must supply it a tree. But what if our structure is only a DAG or worse a Cyclic Graph?

It's not hard to transform a DAG into a tree as I did http://drupalcode.org/project/thejit.git/blob/refs/heads/7.x-1.x:/modules/thejit_spacetree/thejit_spacetree.module#l368

• Are there more use cases?
• Is this different from exporters?

Its use has been a source of confusion and once #48 is completed, is it of very little use anyway.

The current classes in the Loader sub-namespace are pretty much useless and should be removed from this library. They haven't received any updates in years, lack any sort of documentation or tests and use a proprietary format.

Note that the CompleteGraph loader doesn't quite fit in there and will probably be moved to a separate namespace (see #116). Update: Postponed for now.

As a first step, I'd vote to split off the namespace into a separate composer package. Any input on naming is welcome. Perhaps something like graphp/plain?

Refs #120.

While trying to fix #36 it seems we need something like a cluster class for graphviz to add local attributes for the cluster like

• title
• defaults for the contained elements like node, edge and graph

We do have a group concept for vertices but their group needs attributes. We can call this a subgraph but that would mean the users of Graph must create these.

A group is just tagging vertice with a belongs to relation.

Kan we call this class Group?

This is probably not the right place to mention this but I couldn't find any other way to ask this.

My company is currently developing a prototype for a game app. The php backend should be able to do some graph searches. We are wondering how and if we could use this library in a commercial project?

As Graph.php is fairly new to me it's a good idea to checkout our coverage.

Ie #25 misses tests.

See #103.

We should support attaching arbitrary data to vertices and edges.

Implementing a setDataKey($key, $value) and getDataKey($key) is actually quite easy. But things to be considered:

• Maybe implement ArrayAccess so that data can easily be set as $vertex[$key] = $value. While this may be appealing at first, how should we iterate over data set? Implementing Iterator to support foreach ($vertexOrEdge as $key => $value) { ... } should be okay, but it's a bit ambiguous.
• Consider what to do when drawing the graph, importing and exporting graph files. For the mean time perhaps just ignore any additional data? But in the long term...?

Goal: Stabilizing the core graph library (plain Graph, Vertices and Edges)

This ticket serves as a placeholder / meta-issue to link related tickets to.

For the reference: This is essentially a resurrection of #25.

In #36 a commented on the record structure which allows for 'deep' edge snap points.

Using tailport and headport for an edge we can do this.

digraph {

  node [
    shape=record
  ];

  source [
    label="<f0> left |<middle> middle |<f2> right"
    shape=record
  ]

  target [
    label="<f0> left |<f1> middle |<right> right"
    shape=record
  ]

  source -> target [
    tailport = middle
    headport = right
    taillabel = source
    label = middle
    headlabel = target
  ]

}

Having a vertex label like

node [shape=record];
struct1 [label="<f0> left | <f1> middle | <f2> right"];
another

we can connect an edge to f1 like this

a -> struct1:f1

Using portpos like

a -> struct1:f1:nw;

is even worse.

AFAIK we don't have support for this.

Defining this as a Layout is not an option either?

XREF

• record : http://www.graphviz.org/content/node-shapes#record
• portpos : http://www.graphviz.org/content/attrs#kportPos

Now that all components have been split off into separate packages under the graphp organization, we should eventually also move this repository.

Things to consider:

• Does this involve any BC breaks? What about consumers of this package?
• Should we rename this package to the "graphp" vendor?
• If so, what package name should we assign?

I'd like to migrate previous issues, PR, among with all watchers and stargazers, so forking does not seem to be an option.

Any input would be much appreciated!

A lot of our algorithms would benefit from a dedicated Result interface, which saves the intermediary result for further operations. Also, passing its arguments to the createResult() method instead of the constructor allows for a much cleaner design by interchanging the actual algorithm implementation (via dependency injection).

For example, calling the following code always calculates the whole algorithm and then only returns a subset of its results:

$alg = new EdmondsKarp($va, $vb);
$max1 = $alg->getFlowMax();
$max2 = $alg->getFlowMax();

Instead, I'd like to propose something like this, which makes it clear when the actual algorithm runs:

$alg = new EdmondsKarp();
$result = $alg->createResult($va, $vb);
$max1 = $result->getFlowMax();
$max2 = $result->getFlowMax();

This applies to at least MaxFlow, MaximumMatching, MinimumCostFlow, MinimumSpanningTree, ShortestPath, TravelingSalesmanProblem and perhaps a few others.

I'm opening this one as a way to discuss this concept and also to link the first batch of PRs against. I'd love to get some feedback!

Some thoughts:

• Ticket #114 will remove all mathematical properties from the Vertex and Edge classes, such as weight, balance etc. and will use general purpose Attributes instead.
• This means that the Vertex ID will be the only property remaining that is not being stored in the Attributes. Arguably, this might cause confusion and limits how this library can be used.
• Also, the way the Vertex ID is currently implemented, requires it to be unique within the whole graph. Among others, this means that we can not create an exact clone of the vertex within the same graph (see #58).
• The Vertex ID is often used as an index for arrays / maps. Because of this, it can only be set during construction time and can not be changed later on.

As an alternative, we should consider if dropping the Vertex ID altogether could be an option.

• Most use cases can probably store an arbitrary identifier (or any number thereof) in the Attributes instead
• I'm not sure if enforcing a unique key constraint is actually needed anywhere and even if so: is this necessarily part of this library?

Trying to

echo $edge;

a single edge is not an option right now.

Should we add this?

We should provide an algorithm for cycle detection that works for both directed and undirected (and mixed) graphs.

Consider basing it on #8.

Besides merely detecting cycles, it would be nice to also return Cycle instances, similar to how DetectNegativeCycle works.

http://en.wikipedia.org/wiki/Cycle_%28graph_theory%29#Cycle_detection

I'd like to integrate with https://travis-ci.org/ so my pull requests are tested immediately.

Yesterday I managed to locally testing which is an improvement :)

What do you think?

In my class diagrams I have unnecessary links cluttering the display

How can I remove these? Use an algorithm?

Although not directly asked for, issue 4 mentioned the need for a topological sorting algorithm to be used to resolve dependencies.

It's a well-covered subject, sufficiently easy to implement and could potentially also be used as a base for the (to-be-implemented) cycle detection.

http://en.wikipedia.org/wiki/Topological_sorting
http://drupal.org/node/1762204#comment-7049472

While working on #13 I wanted to add a test for Multigraph like

     * is it working for multigraph.
     *
     * @see http://en.wikipedia.org/wiki/Multigraph
     */
    public function testGraphMultigraph() {
        $graph = new Graph();
        $graph->createVertex("A")->createEdgeTo($graph->createVertex("B"));
        $graph->getVertex("A")->createEdgeTo($graph->createVertex("B"));

        $alg = new TopologicalSort($graph);

        $tsl = array_keys($alg->getVertices());
        $this->assertSame(array('A', 'B'), $tsl);
    }

but we do not have Multigraph support right? Are there reasons not to add Multigraph support?

Also refs #54.

The abstract algorithm base classes are pretty much useless and make up for an awkward API (see also #94).

We should work towards updating the API of all algorithm implementations currently using the base classes and eventually remove the base classes.

Obviously, this involves quite a big BC break and will likely take some time until all algorithms are updated.

Goal: Stabilizing the core graph library (plain Graph, Vertices and Edges)

The current set of algorithms is certainly what sets this library apart from other existing graph libraries. However, they're also a constant source of changes, issues and BC breaks. Also, quite a few users of this library probably won't even use a single algorithm.

As such, I'd like to split of the whole Algorithm namespace into a separate package. This is a short-term solution to this problem. Ideally, we should consider splitting this package into even more dedicated packages. This will add quite some maintenance overhead, so I'd like to postpone this until there's an actual demand.

The suggested package name would be "graphp/algorithms". Any input is welcome!

[Edit: axed] Marking this ticket as "blocked", as there are quite a few PRs and issues that need review first. Splitting this off now means that we should migrate all outstanding PRs and issues over.

Any input is very much appreciated!

Refs #120.

In #106 I noted a missing end of file newline.

Are there more CS test we should add?

Depends on #120.

When generating a Graph its name always is 'G' (in svg output it's the title sometimes showed as a web browser tooltip)

The code https://github.com/clue/graph/blob/master/lib/Fhaculty/Graph/GraphViz.php#L285

        $script = ($directed ? 'di':'') . 'graph G {' . self::EOL;

could render a proper ID as defined in http://www.graphviz.org/content/dot-language

Trouble is where to set its name as this has no relation to the graph layout.

Ie adding a label layout attribute like

        $script .= ' label = "Awesome graph"' . self::EOL;

adds a label to the output.

Can we do better?

Relates to #84 + #40

As a side note in #6 we need to set some attributes when defining the Graph for later rendering. We have covered this for Vertice and Edge but not for Graph.

Why not mimic the GraphViz way to set global aka Graph level stuff?

$viz->setLayout(GraphViz::LAYOUT_VERTEX, 'style', 'filled');

This way we can define general Vertice and Edge attributes in one go.

Using the current factory methods Graph::createVertex() and Vertex::createEdge() it's quite difficult to use e.g. an sub class of EdgeDirected there. We should actively encourage extending the base classes and perhaps at some point in time consider removing the create*() methods.

Its definition is ambiguous: the current implementation considers a Graph with no vertices as empty, whereas the common (ymmv) interpretation is to check for the number of edges instead.

Once #48 is merged, it should be trivially easy to replace all existing calls to explicitly check for either $graph->getVertices()->isEmpty() or $graph->getEdges()->isEmpty() instead.

While working on some issues trying to generate a top down UML I ran into

$graphviz = new GraphViz($graph);
$graphviz->setFormat('svg');
// This is broken
$graphviz->setLayout( GraphViz::LAYOUT_GRAPH, 'rankdir', 'TB');

which calls

$this->graph->setLayout($layout, $value);

giving
PHP Fatal error: Call to undefined method Fhaculty\Graph\Graph::setLayout() in /.../vendor/clue/graph/lib/Fhaculty/Graph/GraphViz.php on line 179

composer/installed.json

    {
        "name": "clue/graph",
        "version": "dev-master",
        "version_normalized": "9999999-dev",
        "source": {
            "type": "git",
            "url": "https://github.com/clue/graph.git",
            "reference": "52fc5d877e0a577543cb491b2fe3a543bc28d668"
        },

I tried to understand but failed.

GraphViz and GraphML have already been split off and are now distributed as independent packages. So should the TGF exporter.

The suggested package name would be "graphp/tgf". Any input is welcome!

Refs #120