1 /**
2  *
3  *   Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
4  *   info_at_agrum_dot_org
5  *
6  *  This library is free software: you can redistribute it and/or modify
7  *  it under the terms of the GNU Lesser General Public License as published by
8  *  the Free Software Foundation, either version 3 of the License, or
9  *  (at your option) any later version.
10  *
11  *  This library is distributed in the hope that it will be useful,
12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  *  GNU Lesser General Public License for more details.
15  *
16  *  You should have received a copy of the GNU Lesser General Public License
17  *  along with this library.  If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 /** @file
23  * @brief Base classes for oriented graphs
24  *
25  * @author Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
26  */
27 #ifndef GUM_DIGRAPH_H
28 #define GUM_DIGRAPH_H
29 
30 #include <iostream>
31 #include <sstream>
32 #include <utility>
33 
34 #include <agrum/agrum.h>
35 #include <agrum/tools/core/sequence.h>
36 
37 #include <agrum/tools/graphs/parts/arcGraphPart.h>
38 #include <agrum/tools/graphs/parts/nodeGraphPart.h>
39 
40 namespace gum {
41 
42   /* ===========================================================================
43    */
44   /* ===           BASE CLASS FOR MANIPULATING ALL DIRECTED GRAPHS           ===
45    */
46   /* ===========================================================================
47    */
48   /** @class DiGraph
49    * @brief Base class for all oriented graphs
50    *
51    * \ingroup graph_group
52    *
53    *
54    * This is the base class for graphs containing directed edges (so-called
55    *arcs)
56    * *
57    * @par Usage example:
58    * @code
59    * // creating empty graphs
60    * DiGraph g1,g2;
61    *
62    * // adding nodes and arcs to g1
63    * NodeId i1=g1.addNode();
64    * NodeId i2=g1.addNode();
65    * NodeId i3=g1.addNode();
66    * g1.addArc( i1,i2 );
67    * g1.addArc( i1,i3 );
68    * g1.addArc( i2,i3 );
69    *
70    * //throw an InvalidNode
71    * // g1.addArc( i1+i2+i3,i1 );
72    *
73    * // copying graphs
74    * DiGraph g3 = g1;
75    * g2 = g1;
76    * DiGraph g4=g1;
77    *
78    * // check if a graph has no node
79    * if ( g1.empty() ) cerr << "graph g1 is empty" << endl;
80    *
81    * // remove all the nodes (as well as their adjacent arcs)
82    * g1.clear();
83    *
84    * // remove some arc
85    * g4.eraseArc( Arc ( i1,i3 ) );
86    *
87    * // remove node
88    * g2.eraseNode( i2 );
89    *
90    * // parse a graph
91    * for ( const auto node : g3.nodes() )
92    *   cerr << node<< endl;
93    *
94    * for ( const auto & arc : g3.arcs())
95    *   cerr << arc << endl;
96    *
97    * const ArcSet& a=g3.parents( 3 );
98    *
99    * for ( const auto & par : g3.parents(3))
100    *   cerr << "  -  "<< par;
101    *
102    * cerr<<endl;
103    *
104    * // remove all the arcs that are parent of a given node
105    * g3.eraseParents( 2 );
106    * @endcode
107    */
108   /* ===========================================================================
109    */
110   class DiGraph: public virtual NodeGraphPart, public ArcGraphPart {
111     public:
112     // ############################################################################
113     /// @name Constructors / Destructors
114     // ############################################################################
115     /// @{
116 
117     /// default constructor
118     /** @param nodes_size the size of the hash table used to store all the nodes
119      * @param nodes_resize_policy the resizing policy of this hash table
120      * @param arcs_size the size of the hash table used to store all the arcs
121      * @param arcs_resize_policy the resizing policy of this hash table */
122     explicit DiGraph(Size nodes_size          = HashTableConst::default_size,
123                      bool nodes_resize_policy = true,
124                      Size arcs_size           = HashTableConst::default_size,
125                      bool arcs_resize_policy  = true);
126 
127     /// copy constructor
128     /** @param g the DiGraph to copy */
129     DiGraph(const DiGraph& g);
130 
131     /// destructor
132     virtual ~DiGraph();
133 
134     /// @}
135 
136     // ############################################################################
137     /// @name Operators
138     // ############################################################################
139     /// @{
140 
141     /// copy operator
142     /** @param g the DiGraph to copy */
143     DiGraph& operator=(const DiGraph& g);
144 
145     /// tests whether two DiGraphs are identical (same nodes, same arcs)
146     /** @param g the DiGraph with which "this" is compared */
147     // not virtual : it is a feature !!! :)
148     bool operator==(const DiGraph& g) const;
149 
150     /// tests whether two DiGraphs are different
151     /** @param g the DiGraph with which "this" is compared */
152     // not virtual : it is a feature !!! :)
153     bool operator!=(const DiGraph& g) const;
154 
155     /// @}
156 
157     // ############################################################################
158     /// @name Accessors/Modifiers
159     // ############################################################################
160     /// @{
161 
162     /// insert a new arc into the directed graph
163     /** @param tail the id of the tail of the new inserted arc
164      * @param head the id of the head of the new inserted arc
165      * @warning if the arc already exists, nothing is done. In particular, no
166      * exception is raised.
167      * @throw InvalidNode if head or tail does not belong to the graph nodes */
168     virtual void addArc(const NodeId tail, const NodeId head);
169 
170     /// remove a node and its adjacent arcs from the graph
171     /** @param id the id of the node to be removed
172      * @warning if the node does not exist, nothing is done. In particular, no
173      * exception is raised.*/
174     virtual void eraseNode(const NodeId id);
175 
176     /// removes all the nodes and arcs from the graph
177     virtual void clear();
178 
179     /// to friendly display the content of the graph
180     virtual std::string toString() const;
181 
182     /// to friendly display the content of the graph in the DOT syntax
183     /** @param name The graph name in the dot syntax. Default is G.
184      * @return Returns a string describing the graph in the dot syntax */
185     virtual std::string toDot() const;
186 
187     /**
188      * The topological order stays the same as long as no variable or arcs are
189      * added or erased src the topology.
190      * @param clear If false returns the previously created topology.
191      * @throw InvalidDirectedCycle Raised if this DiGraph contains cycles.
192      */
193     const Sequence< NodeId >& topologicalOrder(bool clear = true) const;
194     /// @}
195 
196     /** checks whether there exists a directed path from \e from to \e to
197      *
198      * If from==to, this function checks if a directed cycle containing \e from
199      * exists.
200      * @param from
201      * @param to
202      * @return true if a directed path exists
203      *
204      */
205     bool hasDirectedPath(const NodeId from, const NodeId to);
206 
207     private:
208     /// The topology sequence of this Directed Graphical Model.
209     mutable Sequence< NodeId >* _mutableTopologicalOrder_;
210 
211     /// Returns a topological order of this DAGModel.
212     /// @warning  _mutableTopologicalOrder_ is assumed to be valid and empty
213     void _topologicalOrder_() const;
214   };
215 
216   /// for friendly displaying the content of directed graphs
217   std::ostream& operator<<(std::ostream&, const DiGraph&);
218 
219 } /* namespace gum */
220 
221 #ifndef GUM_NO_INLINE
222 #  include <agrum/tools/graphs/diGraph_inl.h>
223 #endif   // GUM_NOINLINE
224 
225 #endif /* GUM_DIGRAPH_H */
226