File: NOTES

package info (click to toggle)
cl-graph 20180131-1
  • links: PTS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 240 kB
  • sloc: lisp: 2,884; makefile: 16
file content (41 lines) | stat: -rw-r--r-- 1,424 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Notes and Tasks                                  -*- org -*-

* Notes
** simpler backend data structure
What if we only used 1 hash to hold all nodes and edges..., and what
if nodes could hold other nodes in their edge list, and edges could
hold other edges in their node list, what sort of structure would this
be?  A useful generalization of a graph?

* Tasks [4/9]
** DONE min cut
Some notes in the stuff/ directory.
** TODO breadth/depth first maps
** DONE minimum spanning tree
Prim's algorithm

** TODO minimum edge coloring
** DONE clustering coefficient
the clustering coefficient
\begin{equation*}
  C = \frac{\text{number of closed connected triples}}{\text{number of connected triples}}
\end{equation*}

** TODO measure assortativity
http://en.wikipedia.org/wiki/Assortativity

Should take an optional :key function which defaults to node degree.

** DONE random graph generators [2/2]
http://en.wikipedia.org/wiki/Random_graph

Both of the following types of random graphs
- [X] [[http://en.wikipedia.org/wiki/Edgar_Gilbert][Edgar_Gilbert]]
- [X] [[http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model][Erdos-Renyi]]

** TODO more attractive documentation
like it or not, people will initially look for pictures
- graph-dot -> images in documentation
- graph-json -> images in documentation
** TODO graph Laplacian
http://web.mit.edu/newsoffice/2013/short-algorithm-long-range-consequences-0301.html