twohlix / graph_theory_php Goto Github PK

Add maximum degree and minimum degree support.

Curious: for directed graphs should I track maximum inDegree and maximum outDegree as well as minimum inDegree and minimum outDegree? or do those numbers even matter?

http://en.wikipedia.org/wiki/Degree_(graph_theory)

Add in degree sequencing, basically get a list of all the degrees and sort them in descending order

Curious about digraphs, is there an indegree sequence and an outdegree sequence?

Degree sequence is pretty cool as it allows for checking on the validity of a graph (sum of degree sequence must be even for valid graphs).

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

Add in graph regularity

If all vertices have the same degree (aka the same # of neighbors) a graph is regular.
Simple check: if maxDegree == minDegree then the graph is regular. Otherwise its not

perhaps this should be a helper that takes an instantiated graph object.

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