Debian Codegraph @

TODO

raw
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.