search

hzhan0607 / cusp-library

Automatically exported from code.google.com/p/cusp-library
Apache License 2.0
0 stars 0 forks source link

design and implement cusp::graph::induced_subgraph #41

Open GoogleCodeExporter opened 8 years ago

GoogleCodeExporter commented 8 years ago 
Proposed function signature:

template <typename Matrix1,
          typename Array1,
          typename Matrix2>
size_t induced_subgraph(const Matrix1& G,
                        const Array1& stencil,
                              Matrix2& S);

Assumptions:
 G is an NxN matrix
 stencil is an array with length N whose value_type is convertible to bool
 S can be .resize()-ed to hold the induced subgraph

Semantics:
 Returns K, where K is the number of true values in stencil
 S will be a KxK matrix
 The valid vertices of G will be mapped to [0,K) in order
 For each edge (i,j) in G where (stencil[i] && stencil[j]) is true the edge (M[i],M[j]) will exist in S, where M is the mapping above

Possible extensions:

template <typename Matrix1,
          typename Array1,
          typename Matrix2,
          typename Array2>
size_t induced_subgraph(const Matrix1& G,
                        const Array1& stencil,
                              Matrix2& S,
                              Array2& map);

Here output array map stores the mapping from S vertices to G vertices.  Note 
this is not the mapping mentioned in the Semantics section above.

Original issue reported on code.google.com by wnbell on 29 Oct 2010 at 5:27

GoogleCodeExporter commented 8 years ago

Original comment by wnbell on 14 Feb 2011 at 6:46

GoogleCodeExporter commented 8 years ago

Original comment by wnbell on 5 Feb 2012 at 1:08