30 #ifndef _D_DIGRAPH_HPP
31 #define _D_DIGRAPH_HPP
33 #include "Core/include/DBaseObject.h"
63 template <
class NodeT =
size_t,
class WeightT =
size_t>
67 typedef WeightT WeightType;
135 inline bool operator==(
const Diedge &rhs)
const
144 inline bool operator!=(
const Diedge &rhs)
const
146 return !this->operator==(rhs);
149 inline bool operator<(
const Diedge &rhs)
const
151 return weight > rhs.weight;
154 virtual void printSelf(ostream &os = std::cout,
string s =
"")
const
165 template <
class NodeT,
class WeightT>
169 if (e1.size() != e2.size())
173 typename vector<DiedgeT>::const_iterator it1 = e1.begin(), it2 = e2.begin();
175 for (; it1 != e1.end() && it2 != e2.end(); it1++, it2++) {
176 if ((*it1) != (*it2))
178 if (it1->weight != it2->weight)
197 template <
class NodeT =
size_t,
class WeightT =
size_t>
203 typedef NodeT NodeType;
204 typedef WeightT NodeWeightType;
205 typedef std::map<NodeT, WeightT> NodeValuesType;
206 typedef set<NodeT> NodeListType;
209 typedef WeightT DiedgeWeightType;
211 typedef std::vector<Diedge<NodeT, WeightT>> DiedgeListType;
212 typedef std::vector<size_t> NodeDiedgesType;
213 typedef std::map<NodeT, NodeDiedgesType> NodeDiedgeListType;
218 NodeValuesType nodeValues;
219 DiedgeListType edges;
220 NodeDiedgeListType nodeEdgeList;
231 :
BaseObject(
"Digraph"), edgeNbr(rhs.edgeNbr), nodes(rhs.nodes),
232 nodeValues(rhs.nodeValues), edges(rhs.edges),
233 nodeEdgeList(rhs.nodeEdgeList), oriented(rhs.oriented)
246 nodeValues = rhs.nodeValues;
248 nodeEdgeList = rhs.nodeEdgeList;
249 edgeNbr = rhs.edgeNbr;
250 oriented = rhs.oriented;
260 nodeEdgeList.clear();
272 void addNode(
const NodeT &ind,
const WeightT &val)
275 nodeValues[ind] = val;
283 typename DiedgeListType::iterator foundEdge =
284 find(edges.begin(), edges.end(), e);
285 if (foundEdge != edges.end())
286 return foundEdge - edges.begin();
315 nodeEdgeList[e.
source].push_back(edgeNbr);
316 nodeEdgeList[e.
target].push_back(edgeNbr);
330 void addEdge(
const NodeT src,
const NodeT targ, WeightT weight = 0,
331 bool checkIfExists =
true)
341 DiedgeListType sEdges = edges;
343 sort(sEdges.begin(), sEdges.end());
345 sort(sEdges.rbegin(), sEdges.rend());
349 nodeEdgeList.clear();
352 for (
typename DiedgeListType::const_iterator it = sEdges.begin();
353 it != sEdges.end(); it++)
382 void removeNode(
const NodeT ind)
384 typename NodeListType::iterator fNode = nodes.find(ind);
385 if (fNode != nodes.end())
390 void removeNodeEdge(
const NodeT node,
const size_t edgeIndex)
392 typename NodeDiedgeListType::iterator nEdges = nodeEdgeList.find(node);
393 if (nEdges == nodeEdgeList.end())
396 NodeDiedgesType &eList = nEdges->second;
398 typename NodeDiedgesType::iterator ei =
399 find(eList.begin(), eList.end(), edgeIndex);
400 if (ei != eList.end())
410 typename NodeDiedgeListType::iterator fNodeEdges =
411 nodeEdgeList.find(node);
412 if (fNodeEdges == nodeEdgeList.end())
415 NodeDiedgesType &nedges = fNodeEdges->second;
416 for (NodeDiedgesType::iterator it = nedges.begin(); it != nedges.end();
420 removeNodeEdge(e.
target, *it);
422 removeNodeEdge(e.
source, *it);
433 if (
index >= edges.size())
448 typename DiedgeListType::iterator foundEdge =
449 find(edges.begin(), edges.end(),
DiedgeType(src, targ));
450 if (foundEdge == edges.end())
461 typename DiedgeListType::iterator foundEdge =
462 find(edges.begin(), edges.end(), edge);
463 if (foundEdge == edges.end())
477 size_t nb_edges = edges.size();
480 if (e.
weight > EdgeThreshold)
493 size_t nb_edges = edges.size();
496 if (e.
weight < EdgeThreshold)
503 const NodeListType &
getNodes()
const
508 const DiedgeListType &
getEdges()
const
530 NodeListType &getNodes()
566 typename NodeDiedgeListType::iterator it = nodeEdgeList.find(node);
567 if (it != nodeEdgeList.end())
570 return vector<size_t>();
584 virtual void printSelf(ostream &os = std::cout,
string s =
"")
const
586 os << s <<
"Number of nodes: " << nodes.size() << endl;
587 os << s <<
"Number of edges: " << edges.size() << endl;
588 os << s <<
"Oriented: " << (oriented ?
"true" :
"false") << endl;
589 os << s <<
"Edges: " << endl <<
"source-target (weight) " << endl;
591 string s2 = s +
"\t";
592 for (
typename DiedgeListType::const_iterator it = edges.begin();
593 it != edges.end(); it++)
594 if ((*it).isActive())
595 (*it).printSelf(os, s2);
607 map<NodeT, NodeT> lookup;
608 set<NodeT> nodeList(nodes);
610 while (!nodeList.empty()) {
611 propagateLabel(*(nodeList.begin()), *(nodeList.begin()), lookup,
618 void propagateLabel(
const NodeT ind,
const NodeT lbl,
619 map<NodeT, NodeT> &lookup, set<NodeT> &nList)
const
621 typename NodeListType::iterator foundNode = nList.find(ind);
622 if (foundNode == nList.end())
626 nList.erase(foundNode);
628 const NodeDiedgesType &nEdges = nodeEdgeList.at(ind);
630 for (
typename NodeDiedgesType::const_iterator it = nEdges.begin();
631 it != nEdges.end(); it++) {
632 const DiedgeType &e = edges[*it];
634 propagateLabel(e.source, lbl, lookup, nList);
635 else if (e.target != ind)
636 propagateLabel(e.target, lbl, lookup, nList);
647 template <
class digraphT>
650 typedef typename digraphT::NodeType NodeType;
651 typedef typename digraphT::DiedgeType DiedgeType;
652 typedef typename digraphT::DiedgeListType DiedgeListType;
653 typedef typename digraphT::NodeDiedgesType NodeDiedgesType;
654 typedef typename digraphT::NodeDiedgeListType NodeDiedgeListType;
656 std::set<NodeType> visitedNodes;
657 std::priority_queue<DiedgeType> pq;
660 const DiedgeListType & edges = graph.
getEdges();
661 const NodeDiedgeListType &nodeEdgeList = graph.
getNodeEdges();
663 NodeType curNode = (*nodeEdgeList.begin()).first;
664 visitedNodes.insert(curNode);
666 const NodeDiedgesType &nodeEdges = nodeEdgeList.at(curNode);
667 for (
typename NodeDiedgesType::const_iterator it = nodeEdges.begin();
668 it != nodeEdges.end(); it++)
671 while (!pq.empty()) {
672 DiedgeType edge = pq.top();
675 if (visitedNodes.find(edge.source) == visitedNodes.end())
676 curNode = edge.source;
677 else if (visitedNodes.find(edge.target) == visitedNodes.end())
678 curNode = edge.target;
682 mst.addEdge(edge,
false);
683 visitedNodes.insert(curNode);
684 NodeDiedgesType
const &nodeEdges = nodeEdgeList.at(curNode);
685 for (
typename NodeDiedgesType::const_iterator it = nodeEdges.begin();
686 it != nodeEdges.end(); it++)
Base Smil Object.
Definition: DBaseObject.h:52
Non-oriented edge.
Definition: DDigraph.hpp:65
Diedge(const Diedge &rhs)
Copy constructor.
Definition: DDigraph.hpp:83
Diedge(NodeT a, NodeT b, WeightT w=1)
Constructor using two nodes and an optional weight (default 1).
Definition: DDigraph.hpp:77
WeightT weight
Edge weight/value.
Definition: DDigraph.hpp:110
bool isActive() const
Check if the edge is active.
Definition: DDigraph.hpp:120
void desactivate()
Deactivate the Edge.
Definition: DDigraph.hpp:128
NodeT source
Source node.
Definition: DDigraph.hpp:106
NodeT target
Target node.
Definition: DDigraph.hpp:108
Diedge & operator=(const Diedge &rhs)
Copy an edge.
Definition: DDigraph.hpp:97
Diedge()
Default constructor.
Definition: DDigraph.hpp:71
Non-oriented Digraph.
Definition: DDigraph.hpp:199
NodeDiedgesType getNodeEdges(const size_t &node)
getNodeEdges() - Get a map containing the edges linked to a given node
Definition: DDigraph.hpp:564
void removeHighEdges(DiedgeWeightType EdgeThreshold)
removeHighEdges() - remove edges whose weight are greater then some threshold
Definition: DDigraph.hpp:475
void addNode(const NodeT &ind)
Add a node given its index.
Definition: DDigraph.hpp:266
size_t getEdgeNbr()
getEdgeNbr() -
Definition: DDigraph.hpp:376
map< NodeT, NodeT > labelizeNodes() const
labelizeNodes() - Labelize the nodes.
Definition: DDigraph.hpp:605
NodeDiedgeListType & getNodeEdges()
getNodeEdges()-
Definition: DDigraph.hpp:556
void addNode(const NodeT &ind, const WeightT &val)
Add a node given its index and its optional value.
Definition: DDigraph.hpp:272
void removeLowEdges(DiedgeWeightType EdgeThreshold)
removeHighEdges() - remove edges whose weight are lesser then some threshold
Definition: DDigraph.hpp:491
DiedgeListType & getEdges()
getEdges() - Get a vector containing the graph edges
Definition: DDigraph.hpp:540
NodeListType & getNodes()
getNodes() - get the list of nodes
Definition: DDigraph.hpp:530
void removeEdge(const NodeT src, const NodeT targ)
Find and remove an edge linking src to targ.
Definition: DDigraph.hpp:446
Digraph(const Digraph &rhs)
Copy constructor.
Definition: DDigraph.hpp:230
DigraphType clone()
clone() -
Definition: DDigraph.hpp:360
DigraphType computeMST()
computeMST() - Compute the Minimum Spanning Tree graph
Definition: DDigraph.hpp:576
virtual void printSelf(ostream &os=std::cout, string s="") const
printSelf() -
Definition: DDigraph.hpp:584
size_t getNodeNbr()
getNodeNbr() -
Definition: DDigraph.hpp:368
void removeEdge(const size_t index)
Remove an edge.
Definition: DDigraph.hpp:431
void removeEdge(const DiedgeType &edge)
Remove a given edge.
Definition: DDigraph.hpp:459
int findEdge(const NodeT &src, const NodeT &targ)
findEdge() - Find an edge by its nodes - return its index
Definition: DDigraph.hpp:294
void addEdge(const NodeT src, const NodeT targ, WeightT weight=0, bool checkIfExists=true)
Add an edge to the graph given two nodes src and targ and an optional weight.
Definition: DDigraph.hpp:330
void sortEdges(bool reverse=false)
Sort edges (by weight as defined by the operator < of class Edge)
Definition: DDigraph.hpp:339
void clear()
Clear graph content.
Definition: DDigraph.hpp:255
void removeNodeEdges(const NodeT node)
Remove all edges linked to the node nodeIndex.
Definition: DDigraph.hpp:408
NodeValuesType & getNodeValues()
getNodeValues() -
Definition: DDigraph.hpp:548
int findEdge(const DiedgeType &e)
findEdge() - Find an edge by its content - return its index
Definition: DDigraph.hpp:281
void addEdge(const DiedgeType &e, bool checkIfExists=true)
Add an edge to the graph.
Definition: DDigraph.hpp:306
Digraph()
Default constructor.
Definition: DDigraph.hpp:225
NodeEdgeListType & getNodeEdges()
getNodeEdges()-
Definition: DGraph.hpp:550
EdgeListType & getEdges()
getEdges() - Get a vector containing the graph edges
Definition: DGraph.hpp:534
NodeValuesType & getNodeValues()
getNodeValues() -
Definition: DGraph.hpp:542
digraphT digraphMST(const digraphT &graph)
graphMST() - create a Mininum Spanning Tree
Definition: DDigraph.hpp:648
bool operator==(const vector< Diedge< NodeT, WeightT >> &e1, const vector< Diedge< NodeT, WeightT >> &e2)
Check if two vectors of edges are equal.
Definition: DDigraph.hpp:166
graphT graphMST(const graphT &graph)
graphMST() - create a Mininum Spanning Tree
Definition: DGraph.hpp:641