/**
*
* Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
* info_at_agrum_dot_org
*
* This library is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This library 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 Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this library. If not, see .
*
*/
/** @file
* @brief Base classes for oriented graphs
*
* @author Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
*/
#ifndef GUM_DIGRAPH_H
#define GUM_DIGRAPH_H
#include
#include
#include
#include
#include
#include
#include
namespace gum {
/* ===========================================================================
*/
/* === BASE CLASS FOR MANIPULATING ALL DIRECTED GRAPHS ===
*/
/* ===========================================================================
*/
/** @class DiGraph
* @brief Base class for all oriented graphs
*
* \ingroup graph_group
*
*
* This is the base class for graphs containing directed edges (so-called
*arcs)
* *
* @par Usage example:
* @code
* // creating empty graphs
* DiGraph g1,g2;
*
* // adding nodes and arcs to g1
* NodeId i1=g1.addNode();
* NodeId i2=g1.addNode();
* NodeId i3=g1.addNode();
* g1.addArc( i1,i2 );
* g1.addArc( i1,i3 );
* g1.addArc( i2,i3 );
*
* //throw an InvalidNode
* // g1.addArc( i1+i2+i3,i1 );
*
* // copying graphs
* DiGraph g3 = g1;
* g2 = g1;
* DiGraph g4=g1;
*
* // check if a graph has no node
* if ( g1.empty() ) cerr << "graph g1 is empty" << endl;
*
* // remove all the nodes (as well as their adjacent arcs)
* g1.clear();
*
* // remove some arc
* g4.eraseArc( Arc ( i1,i3 ) );
*
* // remove node
* g2.eraseNode( i2 );
*
* // parse a graph
* for ( const auto node : g3.nodes() )
* cerr << node<< endl;
*
* for ( const auto & arc : g3.arcs())
* cerr << arc << endl;
*
* const ArcSet& a=g3.parents( 3 );
*
* for ( const auto & par : g3.parents(3))
* cerr << " - "<< par;
*
* cerr<& topologicalOrder(bool clear = true) const;
/// @}
/** checks whether there exists a directed path from \e from to \e to
*
* If from==to, this function checks if a directed cycle containing \e from
* exists.
* @param from
* @param to
* @return true if a directed path exists
*
*/
bool hasDirectedPath(const NodeId from, const NodeId to);
private:
/// The topology sequence of this Directed Graphical Model.
mutable Sequence< NodeId >* _mutableTopologicalOrder_;
/// Returns a topological order of this DAGModel.
/// @warning _mutableTopologicalOrder_ is assumed to be valid and empty
void _topologicalOrder_() const;
};
/// for friendly displaying the content of directed graphs
std::ostream& operator<<(std::ostream&, const DiGraph&);
} /* namespace gum */
#ifndef GUM_NO_INLINE
# include
#endif // GUM_NOINLINE
#endif /* GUM_DIGRAPH_H */