<strong>Computing Concept: </strong>
<blockquote>Let TSG(v, w) and TSG(w, z) be transfer subgraphs in G = (V, E) of depth d1 and d2, respectively. We let + denote the sequential composition of two transfer subgraphs. TSG(v, z) = TSG(v, w) + TSG(w, z).</blockquote>
It is clear that the composite transfer subgraph TSG(v, z) has a starting vertex v, ending vertex z, depth d1 + d2, and the set of its arcs is the union of the sets of arcs of TSG(v, w) and TSG(w, z).
<blockquote>Let TSG(v, w) and TSG(w, z) be transfer subgraphs in G = (V, E) of depth d1 and d2, respectively. We let + denote the sequential composition of two transfer subgraphs. TSG(v, z) = TSG(v, w) + TSG(w, z).</blockquote>
It is clear that the composite transfer subgraph TSG(v, z) has a starting vertex v, ending vertex z, depth d1 + d2, and the set of its arcs is the union of the sets of arcs of TSG(v, w) and TSG(w, z).
Let G = (V, E). Let TSG_Container(i) be the collection of transfer subgraphs in G of depth i, where i >= 0. TSG_Container(0) contains the trivial transfer subgraph of depth 0 and empty set of arcs. We adopt the representation you have used in your implementation to demonstrate the composition of simple paths:
<pre title=”representation of TSG containers” class=”lang:default decode:true”>// define the type for the TSG containers
// this definition corresponds to what you have already used
typedef map< int, vector<tsgTYPE> > container_t;
<pre title=”representation of TSG containers” class=”lang:default decode:true”>// define the type for the TSG containers
// this definition corresponds to what you have already used
typedef map< int, vector<tsgTYPE> > container_t;
// declare the containers
container_t STGcontainers;
</pre>
container_t STGcontainers;
</pre>
<strong>
Undefined TSG</strong>
Undefined TSG</strong>
In the previous blog, we have introduced a default constructor for tsgTYPE class and vUNDEFINED was introduced. An undefined TSG is simply tsgTYPE(vUNDEFINED, vUNDEFINED). It can be also obtained by creating a TSG object using the default constructor.
<strong>A Simple Algorithm</strong>
Finding all the combinations of starting and ending vertices in the TSG containers, held in your map representations, is a daunting challenge. We adopt “don’t care” strategy and combine any two transfer subgraphs and produce the resulting transfer subgraph if the rules of sequential composition (see above) apply; <em>otherwise </em>the resulting transfer subgraph is <em>undefined</em>.
<pre class=”lang:default decode:true ” title=”The Algorithm- Inductive step k+1″ >// create an instance of an undefined TSG
// for later comparisons
// for later comparisons
tsgTYPE undefined_tsg;
// declare the map of containers
container_t STGcontainers;
container_t STGcontainers;
// suppose that TSG subgraphs of depth 1, 2, …., k (k > 0) have been generated
// produce TSG subgraphs of depth k + 1
// produce TSG subgraphs of depth k + 1
for (int i = 1; i <= k; i++)
{
vector<tsgTYPE> NextContainer;
for each tsgx in the vector retrieved from STGContainers[i]
{
for each tsgy in the vector retrieved from STGContainers[k+1-i]
{
tsgTYPE newTSG;
newTSG = tsgx + tsgy;
if (newTSG != undefined_tsg)
NextContainer.push_back(newTSG);
}
}
}</pre>The proof of correctness follows directly from TSG definitions and the implementation of new operators on transfer subgraphs: operator= (assignment), binary operator+ (composition), checking for equality == and inequality !=. These operators shall be defined for tsgTYPE class. Accordingly, the new specification of tsgTYPE class becomes:
{
vector<tsgTYPE> NextContainer;
for each tsgx in the vector retrieved from STGContainers[i]
{
for each tsgy in the vector retrieved from STGContainers[k+1-i]
{
tsgTYPE newTSG;
newTSG = tsgx + tsgy;
if (newTSG != undefined_tsg)
NextContainer.push_back(newTSG);
}
}
}</pre>The proof of correctness follows directly from TSG definitions and the implementation of new operators on transfer subgraphs: operator= (assignment), binary operator+ (composition), checking for equality == and inequality !=. These operators shall be defined for tsgTYPE class. Accordingly, the new specification of tsgTYPE class becomes:
<pre class=”lang:default mark:27-40 decode:true ” title=”new specification of TSGs” >
class tsgTYPE
{
private:
VKEY _v; // starting vertex
VKEY _w; // ending vertex
ESET_TYPE E; // set of arcs of TSG(v, w)
static VSET_TYPE _V;
unsigned int _depth; // the length of the longest path in TSG(v, w)
{
private:
VKEY _v; // starting vertex
VKEY _w; // ending vertex
ESET_TYPE E; // set of arcs of TSG(v, w)
static VSET_TYPE _V;
unsigned int _depth; // the length of the longest path in TSG(v, w)
public:
// basic constructors
// other constructors may be added later for convenience
tsgTYPE() { _v = _w = vUNDEFINED; }
tsgTYPE(VKEY v, VKEY w) { _v =v; _w = w;}
// getters and setters
void setArcs(ESET_TYPE E) { _E = E; }
void setStartingVertex(VKEY v) { _v = v; }
void setEndingVertex(VKEY w) { _w = w; }
void setDepth(unsigned int d} { _depth = d; }
VKEY getStartingVertex() const { return _v; }
VKEY getEndingVertex() const { return _w;}
ESET_TYPE getArcs() const { return _E}
unsigned int getDepth() const ( return _depth; }
// basic constructors
// other constructors may be added later for convenience
tsgTYPE() { _v = _w = vUNDEFINED; }
tsgTYPE(VKEY v, VKEY w) { _v =v; _w = w;}
// getters and setters
void setArcs(ESET_TYPE E) { _E = E; }
void setStartingVertex(VKEY v) { _v = v; }
void setEndingVertex(VKEY w) { _w = w; }
void setDepth(unsigned int d} { _depth = d; }
VKEY getStartingVertex() const { return _v; }
VKEY getEndingVertex() const { return _w;}
ESET_TYPE getArcs() const { return _E}
unsigned int getDepth() const ( return _depth; }
// static member function
static void vertex_universe(VSET_TYPE V);// Added functionality is specified below
// copy constructor
tsgTYPE(const tsgTYPE& rhs);
// overloading of the assignment operator
tsgTYPE& operator=(const tsgTYPE& rhs);
// overloading of the + operator (composition)
tsgTYPE operator+(const tsgTYPE& rhs) const;
// overloading of operators: == and !=
bool operator==(const tsgTYPE& rhs) const;
bool operator!=(const tsgTYPE& rhs) const;
// destructor
~tsgTYPE();
};
</pre>
static void vertex_universe(VSET_TYPE V);// Added functionality is specified below
// copy constructor
tsgTYPE(const tsgTYPE& rhs);
// overloading of the assignment operator
tsgTYPE& operator=(const tsgTYPE& rhs);
// overloading of the + operator (composition)
tsgTYPE operator+(const tsgTYPE& rhs) const;
// overloading of operators: == and !=
bool operator==(const tsgTYPE& rhs) const;
bool operator!=(const tsgTYPE& rhs) const;
// destructor
~tsgTYPE();
};
</pre>