1Note that these are possibilities, not plans nor promises. 2 3- graph periphery: the subgraph of graph center vertices 4- finding the shortest cycle: easy for directed (*), but how about undirected? 5 (*) http://www.cs.auckland.ac.nz/~ute/220ft/graphalg/node14.html 6 do a BFS, when sees an already seen vertex, a cycle of length of at most 7 twice the current depth of the BFS has been found; no cycles => V + 1 (Inf) 8- bipartite aka 2-colourable: again, BFS: 9 http://www.cs.auckland.ac.nz/~ute/220ft/graphalg/node15.html 10- Eulerian circuit: Fleury's algorithm: 11 http://planetmath.org/encyclopedia/FleurysAlgorithm.html 12- could_be_isomorphic() - go second degree? 13 141. separate external and internal attributes? 152. biconn: add next_root 163. DAG SSSP 174. flow: Ford-Fulkerson/Edmonds-Karp/preflow-push? Floyd-Warshall variant? 18 19-- Classics -- 20 21Undirected graphs 22- connectivity 23 - given two vertices are they on a cycle 24 - find_all_paths($u, $v)? 25 - find_all_cycles()? NP-complete; equivalent to finding all Hamiltonians 26- Euler tour 27- bipartite matching: Hopcroft - Kraft 28- 2-colorability (see above) 29- planarity 30 31Digraphs 32- disallow_selfloops => 1? 33- odd-length cycle 34- shortest paths (bfs) 35- squaring a graph: for (u,v)(v,w) add (u,w) unless already there 36 37- graph union, graph difference? 38 39Various specialized graph constructors? 40- n-dim grid (with wraps and connectors -> wheels (webs), cones), 41 circle, star, platonic solids, trees, etc. 42