SCG in Action
Minimum Graph Basis
This example shows how to express
a computational problem (computing the minimum graph basis of a directed
graph) with the current SCG implementation.
Take the material from
http://www.ccs.neu.edu/home/lieber/papers/SCG-onward/onward.pdf
Take the source from onward.tex
MinBasisSize Lab: Minimum Graph Basis Size for Directed Graphs
Show predicate.
Show interfaces and their implementation for this lab.
MinBasisSizeAcyclic Lab: Minimum Graph Basis Size for Directed Acyclic Graphs
Show predicate.
Show interfaces and their implementation for this lab.
ConnectivityPreserving Lab: Strongly Connected Components Construction
Predicate:
There exists a mapping T : G(V,E) in directed graphs
to T(G) in directed acyclic graphs:
if there exists a path p from v1 in V to v2 in V then
there exists a path (possibly of length 0) from T(v1) to T(v2).
Show interfaces and their implementation for this lab.
Solution for MinBasisSizeAcyclic Lab
Show avatar for this lab.
Solution for ConnectivityPreserving Lab
Show avatar for this lab.
Solution for MinBasisSize Lab
Show avatar for this lab by composing the solutions
for the other two labs.
SCG Platform Code
Show pointer to Ahmed's code.