chomp::homology::PredecessorsCycle Class Reference

A helper class for determining a cycle that realizes the minimum. More...

#include <digraph.h>

Public Member Functions
	PredecessorsCycle ()
	The default constructor. More...
void	add (int_t vertex, int_t predecessor, int_t stage)
	Adds a predecessor information for the given vertex at the given stage (path progression length). More...
template<class VectorType >
void	getCycle (VectorType &cycle) const
	Fills in a vector with a cycle that realizes the minimum, using the push_back method to add the consecutive vertices. More...

Protected Attributes
chomp::homology::multitable< chomp::homology::multitable< int_t > >	pred
	The array of predecessors at each stage. More...
int_t	searchStart
	The vertex number to start back-tracing the cycle from. More...
int_t	compSize
	The size of the component with the cycle to search. More...

Detailed Description

A helper class for determining a cycle that realizes the minimum.

Definition at line 3294 of file digraph.h.

Constructor & Destructor Documentation

PredecessorsCycle()

chomp::homology::PredecessorsCycle::PredecessorsCycle ( )

inline

The default constructor.

Definition at line 3326 of file digraph.h.

                                            :
        searchStart (-1), compSize (0)
{
        return;
} /* PredecessorsCycle::PredecessorsCycle */

Member Function Documentation

add()

void chomp::homology::PredecessorsCycle::add ( int_t  vertex, int_t  predecessor, int_t  stage  )

inline

Adds a predecessor information for the given vertex at the given stage (path progression length).

If called with stage == -n then this means that the minimizing vertex at stage n is provided (to trace back the cycle from) with the component size.

Definition at line 3332 of file digraph.h.

{
        if (stage >= 0)
        {
                pred [stage] [vertex] = predecessor;
        }
        else
        {
                searchStart = vertex;
                compSize = -stage;
        }
        return;
} /* PredecessorsCycle::add */

References compSize, pred, and searchStart.

getCycle()

template<class VectorType >

void chomp::homology::PredecessorsCycle::getCycle ( VectorType &  cycle ) const

inline

Fills in a vector with a cycle that realizes the minimum, using the push_back method to add the consecutive vertices.

Definition at line 3348 of file digraph.h.

{
        // return no cycle if no information is available
        if ((searchStart < 0) || (compSize <= 0))
                return;
 
        // search for a cycle and return the first cycle found;
        // not a very efficient way: just store the path in a vector
        // and check if the newly added vertes is already there
        int_t current (searchStart);
        std::vector<int_t> path;
        for (int_t stage = compSize; stage >= 0; -- stage)
        {
                for (size_t n = 0; n < path. size (); ++ n)
                {
                        if (path [n] == current)
                        {
                                for (size_t m = path. size ();
                                        m > n; -- m)
                                {
                                        cycle. push_back (path [m - 1]);
                                }
                                return;
                        }
                }
                path. push_back (current);
                current = pred [stage] [current];
        }
        return;
} /* PredecessorsCycle::getCycle */

References compSize, pred, and searchStart.

Member Data Documentation

compSize

int_t chomp::homology::PredecessorsCycle::compSize

protected

The size of the component with the cycle to search.

Definition at line 3322 of file digraph.h.

Referenced by add(), and getCycle().

pred

chomp::homology::multitable<chomp::homology::multitable<int_t> > chomp::homology::PredecessorsCycle::pred

protected

The array of predecessors at each stage.

The first index to the array is the stage, the second index is the vertex number, and the entry is the predecessor number.

Definition at line 3316 of file digraph.h.

Referenced by add(), and getCycle().

searchStart

int_t chomp::homology::PredecessorsCycle::searchStart

protected

The vertex number to start back-tracing the cycle from.

Definition at line 3319 of file digraph.h.

Referenced by add(), and getCycle().

---

The documentation for this class was generated from the following file:

• chomp/struct/digraph.h