| | 350 | === Incidence Matrices === |
| | 351 | |
| | 352 | An incidence matrix (http://en.wikipedia.org/wiki/Incidence_matrix) is a graph data structure that relates vertices to the set of edges that connect them. This project would entail the implementation of a generic incidence matrix data structure that fits into the BGL generic graph interface. This project can include the development and definition of concepts related to graphs represented by incidence matrices (e.g., signed and bidirected graphs). Incidence matrices can also be adapted to implement hypergraphs. |
| | 353 | |
| | 354 | === Hypergraphs === |
| | 355 | |
| | 356 | A hypergraph (http://en.wikipedia.org/wiki/Hypergraph) is a generalization of graphs where an edge can connect any number of vertices (instead of exactly two). Hypergraphs can also be directed or undirected, and have their own algorithms (e.g., traversal and partitioning). This project minimally involves the definition of one hypergraph data structure and a generic traversal algorithm. This project would also involve the identification and definition of generic concepts related to hypergraphs. |
| | 357 | |
| | 358 | Note: This is a non-trivial project that requires substantial knowledge of graph theory, algorithms, and generic programming. |
| | 359 | |
| | 360 | === Implicit Graphs === |
| | 361 | |
| | 362 | Design and develop a framework for adapting functions and function objects into graphs. For example, a binary predicate function can be made to behave like an adjacency matrix, returning an "edge" if the predicate is true. This project will require a substantial amount of metaprogramming to adapt function concepts (e.g., domain, range, etc.), onto graph concepts (vertices, edges, etc.). |
| | 363 | |
| | 364 | === Closures and Reductions === |
| | 365 | |
| | 366 | Implement a suite of generic graph algorithms that computer closures and reductions on graphs. The BGL already contains a `transitive_closure` algorithm, but not (yet) a `transitive_reduction`. Other kinds of computable closures and reductions include reflexive, symmetric, and congruence. This project can also include predicates to test whether or not a graph exhibits these properties (e.g., is_symmetric). |
| | 367 | |
| | 368 | === Lattices === |
| | 369 | |
| | 370 | Define and implement a generic lattice abstraction over a graph or relation. A lattice represents relations between objects in a partially ordered set (poset). Lattices are frequently used (outside of abstract mathematics) to descibe and reason about the relations of discrete objects. One such example is ontologies. Implement algorithms over the lattice that return its minima and maxima, and compute the meet and join of elements in the lattice. |
| | 371 | |
