math-php
math-php copied to clipboard
Implement Dijkstra algorithm
Huy guys, this lib seems awesome, lots of work there :)
Is there any idea about implementing Dijkstra algorithm in the future?
Graph theory is definitely something I'd like to implement and include in this library. So yes.
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;
}
}
@Beakerboy I'd prefer an oriented object approach like $graph->addNode(Node $node);
and
$graph->addEdge(Edge $edge);
or similar
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.
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.
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.
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.
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.