| 1 |
Note 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 |
|
| 14 |
1. separate external and internal attributes? |
| 15 |
2. biconn: add next_root |
| 16 |
3. DAG SSSP |
| 17 |
4. flow: Ford-Fulkerson/Edmonds-Karp/preflow-push? Floyd-Warshall variant? |
| 18 |
|
| 19 |
-- Classics -- |
| 20 |
|
| 21 |
Undirected 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 |
|
| 28 |
Digraphs |
| 29 |
- disallow_selfloops => 1? |
| 30 |
- odd-length cycle |
| 31 |
- shortest paths (bfs) |
| 32 |
- squaring a graph: for (u,v)(v,w) add (u,w) unless already there |
| 33 |
|
| 34 |
- graph union, graph difference? |
| 35 |
|
| 36 |
Various specialized graph constructors? |
| 37 |
- n-dim grid (with wraps and connectors -> wheels (webs), cones), |
| 38 |
circle, star, platonic solids, trees, etc. |