[ccan] [PATCH 0/7] aga: New abstract graph algorithms module

[David Gibson]

I've posted drafts of this several times before, but I think I'm now
pretty much ready to commit this.  It would be nice to have some
review first, though.

This adds a new module "aga" implementing several standard graph
algorithms across graphs that are implicitly defined by callback
functions.  This is useful because there are lots of cases where graph
algorithms are aplicable, but it's not convenient to transcribe your
program's data structures into an explicit "graph" data structure for
processing.  In addition this module allows the graph to be discovered
lazily, rather than needing to identify all possible graph nodes ahead
of time.

TODO:
  * Re-entrant versions of the algorithms which allocate their own
    temporary storage instead of requiring that the caller make room
    for it in their structures
  * Dijkstra's algorithm
  * the Bellman-Ford algorithm
  * Tarjan's strongly connected component algorithm

David Gibson (7):
  aga: Abstract Graph Algorithms
  aga: Simple test graphs
  aga: Depth first search
  aga: Breadth first search
  aga: Testcase for attempt to run concurrent algorithms
  aga: Add lazytrie testcase
  aga: Add edge costs

 ccan/aga/LICENSE                     |    1 +
 ccan/aga/_info                       |   41 ++
 ccan/aga/aga.c                       |   97 ++++
 ccan/aga/aga.h                       |  223 ++++++++
 ccan/aga/bfs.c                       |   94 ++++
 ccan/aga/dfs.c                       |   94 ++++
 ccan/aga/private.h                   |   10 +
 ccan/aga/test/api-adjacency.c        |   93 ++++
 ccan/aga/test/api-bfs.c              |  104 ++++
 ccan/aga/test/api-concurrent.c       |   52 ++
 ccan/aga/test/api-dfs.c              |  104 ++++
 ccan/aga/test/api-lazytrie-words.txt | 1000 ++++++++++++++++++++++++++++++++++
 ccan/aga/test/api-lazytrie.c         |  211 +++++++
 ccan/aga/test/chain.c                |   29 +
 ccan/aga/test/error-graph.c          |   56 ++
 ccan/aga/test/full.c                 |   52 ++
 ccan/aga/test/grid.c                 |   84 +++
 ccan/aga/test/parallel.c             |   62 +++
 ccan/aga/test/simple-graph.c         |   16 +
 ccan/aga/test/simple-graph.h         |  215 ++++++++
 ccan/aga/test/traversal1.c           |  121 ++++
 ccan/aga/test/trivial.c              |   39 ++
 22 files changed, 2798 insertions(+)
 create mode 120000 ccan/aga/LICENSE
 create mode 100644 ccan/aga/_info
 create mode 100644 ccan/aga/aga.c
 create mode 100644 ccan/aga/aga.h
 create mode 100644 ccan/aga/bfs.c
 create mode 100644 ccan/aga/dfs.c
 create mode 100644 ccan/aga/private.h
 create mode 100644 ccan/aga/test/api-adjacency.c
 create mode 100644 ccan/aga/test/api-bfs.c
 create mode 100644 ccan/aga/test/api-concurrent.c
 create mode 100644 ccan/aga/test/api-dfs.c
 create mode 100644 ccan/aga/test/api-lazytrie-words.txt
 create mode 100644 ccan/aga/test/api-lazytrie.c
 create mode 100644 ccan/aga/test/chain.c
 create mode 100644 ccan/aga/test/error-graph.c
 create mode 100644 ccan/aga/test/full.c
 create mode 100644 ccan/aga/test/grid.c
 create mode 100644 ccan/aga/test/parallel.c
 create mode 100644 ccan/aga/test/simple-graph.c
 create mode 100644 ccan/aga/test/simple-graph.h
 create mode 100644 ccan/aga/test/traversal1.c
 create mode 100644 ccan/aga/test/trivial.c

-- 
2.4.3