graph.h

Go to the documentation of this file.

/////////////////////////////////////////////////////////////////////////////
///
/// @file graph.h
///
/// A directed graph class and some algorithms.
/// This file contains the definition of a class that represents
/// a directed graph with a limited number of operations on the graph,
/// optimized for the particular application.
/// This specific definition is a simple wrapper for the class "diGraph"
/// borrowed from the CHomP package.
///
/// @author Pawel Pilarczyk
///
/////////////////////////////////////////////////////////////////////////////

// Copyright (C) 1997-2010 by Pawel Pilarczyk.
//
// This file is part of my research software package.  This is free software;
// you can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation;
// either version 2 of the License, or (at your option) any later version.
//
// This software is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License along
// with this software; see the file "license.txt".  If not, write to the
// Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// Started on December 22, 2008. Last revision: December 22, 2008.


#ifndef _FINRESDYN_GRAPH_H_
#define _FINRESDYN_GRAPH_H_


// include some standard C++ header files
#include <iostream>
#include <vector>

// include selected header files from the CHomP library
#include "chomp/struct/digraph.h"
#include "chomp/struct/bitfield.h"


// --------------------------------------------------
// ---------------- the graph class -----------------
// --------------------------------------------------

/// A directed graph class with some algorithms built-in.
/// This class defines a directed graph which is optimized
/// for the particular application in this project.
/// It supports a very limited number of operations,
/// but these operations are very fast. This class also implements
/// a few algorithms necessary in this project.
/// This particular implementation is a wrapper for the class "diGraph"
/// available in the CHomP software package.
/// Note: The default constructor, destructor and assignment operator
/// are good for this class, so none are defined.
class Graph
{
public:
        /// Adds a vertex.
        void addVertex (void);

        /// Adds an edge starting at the last vertex.
        /// Note: The range of the target vertex number is not verified.
        void addEdge (int target);

        /// Returns the number of vertices.
        int countVertices (void) const;

        /// Returns the number of edges.
        int countEdges (void) const;

        /// Counts the number of edges leaving the given vertex.
        int countEdges (int vertex) const;
        
        /// Retrieves the given edge that leaves the given vertex.
        int getEdge (int vertex, int i) const;

        /// Verifies if the graph is strongly connected.
        bool checkStronglyConnected () const;

        /// Verifies if the graph is aperiodic.
        bool checkAperiodic () const;

private:
        /// The underlying graph object.
        chomp::homology::diGraph<> g;

}; /* class Graph */

// --------------------------------------------------

inline void Graph::addVertex (void)
{
        g. addVertex ();
        return;
} /* Graph::addVertex */

inline void Graph::addEdge (int target)
{
        g. addEdge (target);
        return;
} /* Graph::addEdge */

inline int Graph::countVertices (void) const
{
        return g. countVertices ();
} /* Graph::countVertices */

inline int Graph::countEdges (void) const
{
        return g. countEdges ();
} /* Graph::countEdges */

inline int Graph::countEdges (int vertex) const
{
        return g. countEdges (vertex);
} /* Graph::countEdges */

inline int Graph::getEdge (int vertex, int i) const
{
        return g. getEdge (vertex, i);
} /* Graph::getEdge */

// --------------------------------------------------

/// This function uses Tarjan's algorithm (as described in the Wikipedia)
/// for the computation of strongly connected components
/// in order to determine whether the given graph is strongly connected.
/// Tha advantage of this approach over the one described in Cormen's
/// textbook is that the transposed graph need not be computed.
inline bool Graph::checkStronglyConnected () const
{
        chomp::homology::dummyArray compVertices, compEnds;
        int n = chomp::homology::SCC_Tarjan (g, compVertices, compEnds);
        return ((n == 1) && (compEnds [0] == g. countVertices ()));
} /* Graph::checkStronglyConnected */

inline bool Graph::checkAperiodic () const
{
        int period = chomp::homology::computePeriod (g);
        return (period == 1);
} /* Graph::checkAperiodic */


#endif // _FINRESDYN_GRAPH_H_