Outline graph interfaces

[cole-k]

• Make one overall graphs interface that is directed and weighted
  • require that instances implement some common methods like cost ( vertex -- cost ), neighbors ( vertex -- neighbors ), etc.
  • refer to path-finding for an example of use (this will look like the (astar) private tuple).
• Make separate class instances for the various types of classes (weighted vs. unweighted)
  • e.g. for unweighted graphs, implement cost by always returning 1

[kwshi]

FYI, here's some excerpt from the built-in sequences vocabulary that might hint at how to define generic interfaces:

MIXIN: sequence

GENERIC: length ( seq -- n ) flushable
GENERIC: set-length ( n seq -- )
GENERIC: nth ( n seq -- elt ) flushable
GENERIC: set-nth ( elt n seq -- )
GENERIC: new-sequence ( len seq -- newseq ) flushable
GENERIC: new-resizable ( len seq -- newseq ) flushable
GENERIC: like ( seq exemplar -- newseq ) flushable
GENERIC: clone-like ( seq exemplar -- newseq ) flushable

M: sequence lengthen 2dup length > [ set-length ] [ 2drop ] if ; inline
M: sequence shorten 2dup length < [ set-length ] [ 2drop ] if ; inline

: empty? ( seq -- ? ) length 0 = ; inline

: if-empty ( ..a seq quot1: ( ..a -- ..b ) quot2: ( ..a seq -- ..b ) -- ..b )
    [ dup empty? ] [ [ drop ] prepose ] [ ] tri* if ; inline

[kwshi]

Proposed vocabulary organization:

• graph-theory for generic graph interface
• graph-theory.directed for algorithms specific to directed graphs
• graph-theory.undirected for algs specific to undirected graphs (e.g. minimum spanning tree)
• graph-theory.unweighted, graph-theory.weighted, etc.

[nandeeka]

Extension Ideas:

• Number of nodes
• Number of edges
• Add/remove edge
• For a given vertex, get all neighbors
• etc.

[kwshi]

Help page on naming conventions, for reference: (help page "Conventions")