twohlix/graph_theory_php — Issue #2: Add connectedness calculations
Author: twohlix
Created: 2012-01-26 06:32:42+00:00
State: open

This gets more complicated with directed graphs.

connected($start, $end, $directed=TRUE) - have to find if a path exists between things, real adjacency matrix can speed this up

graphConnected($directred=TRUE) - works on the whole graph (first check minimum degree then do expensive stuff).

weaklyConnected($start, $end) - real adjacency matrix can speed this up. Slightly ambiguous, if a directed graph is connected between two points it is also weakly connected.

see http://en.wikipedia.org/wiki/Connected_graph for some more information