41 #ifndef BPP_GRAPH_DAGRAPHIMPL_H
42 #define BPP_GRAPH_DAGRAPHIMPL_H
49 #include "../Exceptions.h"
50 #include "../Numeric/VectorTools.h"
56 template<
class GraphImpl>
249 template<
class GraphImpl>
257 template<
class GraphImpl>
260 return isValid_ || validate_();
264 template<
class GraphImpl>
270 std::unique_ptr<Graph::NodeIterator> allIt = allNodesIterator();
273 for ( ; !allIt->end(); allIt->next())
275 if (getNumberOfFathers(**allIt) == 0)
287 template<
class GraphImpl>
290 return GraphImpl::isLeaf(node);
293 template<
class GraphImpl>
296 return GraphImpl::getNumberOfIncomingNeighbors(node) >= 1;
299 template<
class GraphImpl>
302 return getIncomingNeighbors(node);
305 template<
class GraphImpl>
308 return GraphImpl::getNumberOfIncomingNeighbors(node);
311 template<
class GraphImpl>
314 GraphImpl::link(fatherNode, node);
315 topologyHasChanged_();
319 template<
class GraphImpl>
322 GraphImpl::link(fatherNode, node, edge);
323 topologyHasChanged_();
327 template<
class GraphImpl>
330 std::vector<Graph::NodeId> fathers = getFathers(node);
331 for (std::vector<Graph::NodeId>::iterator currFather = fathers.begin(); currFather != fathers.end(); currFather++)
333 removeFather(node, *currFather);
338 template<
class GraphImpl>
341 if (getNumberOfIncomingNeighbors(node) == 1)
344 GraphImpl::unlink(father, node);
347 template<
class GraphImpl>
350 std::vector<Graph::NodeId> foundLeaves;
351 fillListOfLeaves_(node, foundLeaves);
356 template<
class GraphImpl>
359 const std::vector<Graph::NodeId> sons = getSons(startingNode);
362 for (std::vector<Graph::NodeId>::const_iterator currNeighbor = sons.begin(); currNeighbor != sons.end(); currNeighbor++)
364 fillListOfLeaves_(*currNeighbor, foundLeaves);
369 foundLeaves.push_back(startingNode);
373 template<
class GraphImpl>
377 throw Exception(
"DAGraphImpl<GraphImpl>: The DAG must be rooted.");
380 template<
class GraphImpl>
384 throw Exception(
"DAGraphImpl<GraphImpl>: The DAG is not valid.");
388 template<
class GraphImpl>
391 isValid_ = GraphImpl::isDA();
395 template<
class GraphImpl>
402 template<
class GraphImpl>
405 return GraphImpl::getOutgoingNeighbors(node);
408 template<
class GraphImpl>
411 return GraphImpl::getNumberOfOutgoingNeighbors(node);
414 template<
class GraphImpl>
417 GraphImpl::link(node, sonNode);
418 topologyHasChanged_();
421 template<
class GraphImpl>
424 GraphImpl::link(node, sonNode, edge);
425 topologyHasChanged_();
429 template<
class GraphImpl>
432 std::vector<Graph::NodeId> sons = getSons(node);
433 for (std::vector<Graph::NodeId>::iterator currSon = sons.begin(); currSon != sons.end(); currSon++)
435 removeSon(node, *currSon);
441 template<
class GraphImpl>
444 GraphImpl::unlink(node, son);
448 template<
class GraphImpl>
451 GraphImpl::setRoot(newRoot);
454 if (isRooted() && isValid())
455 propagateDirection_(newRoot);
458 GraphImpl::orientate();
464 template<
class GraphImpl>
467 std::vector<Graph::NodeId> vFat = getFathers(node);
470 propagateDirection_(fat);
475 GraphImpl::switchNodes(fat, node);
480 template<
class GraphImpl>
484 std::vector<Graph::EdgeId> metNodes;
485 fillSubtreeMetNodes_(metNodes, localRoot);
489 template<
class GraphImpl>
493 std::vector<Graph::EdgeId> metEdges;
494 fillSubtreeMetEdges_(metEdges, localRoot);
499 template<
class GraphImpl>
502 metNodes.push_back(localRoot);
503 std::vector<Graph::NodeId> sons = GraphImpl::getOutgoingNeighbors(localRoot);
504 for (std::vector<Graph::NodeId>::iterator currSon = sons.begin(); currSon != sons.end(); currSon++)
506 fillSubtreeMetNodes_(metNodes, *currSon);
510 template<
class GraphImpl>
513 std::vector<Graph::EdgeId> edgesToSons = GraphImpl::getOutgoingEdges(localRoot);
514 for (std::vector<Graph::EdgeId>::iterator currEdgeToSon = edgesToSons.begin(); currEdgeToSon != edgesToSons.end(); currEdgeToSon++)
516 metEdges.push_back(*currEdgeToSon);
517 fillSubtreeMetEdges_(metEdges, GraphImpl::getBottom(*currEdgeToSon));
void fillSubtreeMetEdges_(std::vector< Graph::EdgeId > &metEdges, Graph::NodeId localRoot) const
std::vector< Graph::NodeId > getFathers(Graph::NodeId nodeid) const
std::vector< Graph::NodeId > getSons(Graph::NodeId node) const
std::vector< Graph::NodeId > getBelowNodes(Graph::NodeId localRoot) const
std::vector< Graph::NodeId > removeSons(Graph::NodeId node)
bool isLeaf(Graph::NodeId node) const
void removeFather(Graph::NodeId node, Graph::NodeId father)
void orientGraphFrom_(std::set< Graph::NodeId > &metNodes, Graph::NodeId localRoot)
size_t getNumberOfSons(Graph::NodeId node) const
Get the number of sons node.
std::vector< Graph::EdgeId > getBelowEdges(Graph::NodeId localRoot) const
void addFather(Graph::NodeId node, Graph::NodeId father)
void addSon(Graph::NodeId node, Graph::NodeId sonNode)
bool hasFather(Graph::NodeId node) const
void rootAt(Graph::NodeId newRoot)
void propagateDirection_(Graph::NodeId node)
void removeSon(Graph::NodeId node, Graph::NodeId son)
std::vector< Graph::NodeId > getLeavesUnderNode(Graph::NodeId node) const
void fillSubtreeMetNodes_(std::vector< Graph::NodeId > &metNodes, Graph::NodeId localRoot) const
std::vector< Graph::NodeId > removeFathers(Graph::NodeId node)
void mustBeValid_() const
void mustBeRooted_() const
virtual void topologyHasChanged_() const
void fillListOfLeaves_(Graph::NodeId startingNode, std::vector< Graph::NodeId > &foundLeaves) const
size_t getNumberOfFathers(Graph::NodeId node) const
Get the number of fathers nodes.
Exception base class. Overload exception constructor (to control the exceptions mechanism)....
DAGraphImpl< GlobalGraph > DAGlobalGraph