Implement Dijkstra algorithm

[Pierstoval]

Huy guys, this lib seems awesome, lots of work there :)

Is there any idea about implementing Dijkstra algorithm in the future?

[markrogoyski]

Graph theory is definitely something I'd like to implement and include in this library. So yes.

[Beakerboy]

How would this class be designed? How many types a Graphs are there. Here's a quick framework for a directional Graph. Each column is a node, each row is an edge.

class Graph
{

    $I = [];

    //Number of nodes
    $n = 0;

    //Number of edges
    $e = 0;
    public function addNode()
    {
        //extend the matrix by one column
        $this->n += 1;
    } 

    public function addEdge(int $source, int $target)
    {
        $this->e += 1;
        //create an array of length $n

        $A[$source] = -1;
        $A[$target] = 1;

        // Append $A to the bottom of $I;
    }
}

[Pierstoval]

@Beakerboy I'd prefer an oriented object approach like $graph->addNode(Node $node); and $graph->addEdge(Edge $edge); or similar

[markrogoyski]

I haven't put much thought into this yet, but I imagine doing something like that, with graphs being composed of vertices and edges, and then relating them somehow.. There is a lot to consider though, because there are graphs, directional graphs, multi-graphs, etc. I'll probably start a new branch for graph theory for long-term development and just start on a plane graph class and see where it goes from there.

[Pierstoval]

Plane graph (nodes+edges) are not so hard to represent, you can just, for each edge, have "startNode" and "endNode", and for nodes, "edgesStarted" and "edgesEnded" for a cool bidirectionnal relationship.

[Beakerboy]

I'm certainly no expert on Graph Theory, so from a OOP perspective, what's the advantage of having the Nodes and Edges defined as distinct objects? What operations and characteristics do that have that are independent of the Graph as a whole? The Adjacancy Matrix or Incidence Matrix would have all the info to relate the edges to the nodes.

[Pierstoval]

The OOP approach allows flexibility and allows to add new properties / overrides to the different entities, especially if you depend on interfaces and respect ISP and LSP.

[markrogoyski]

For an initial prototype I'd probably just start with a simple adjacency list data structure to represent vertices and edges and add features/abstractions as necessary as it grows in scope.