1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
| #include "StdAfx.h"
#include "orientedgraph.h"
SquareMatrix::SquareMatrix(unsigned int _n):std::vector<int>(_n*_n, 0), n(_n){}
int& SquareMatrix::operator ()(int i, int j) { return (*this)[ (i-1)*n + j - 1 ]; }
int SquareMatrix::operator ()(int i, int j) const { return (*this)[ (i-1)*n + j - 1 ]; }
SquareMatrix SquareMatrix::operator +(const SquareMatrix& A) const {
SquareMatrix B(n);
//transform() une fonction de algorithm
std::transform(begin(), end(), A.begin(), B.begin(), std::plus<int>());
return B;
}
SquareMatrix SquareMatrix::operator *(const SquareMatrix& A) const {
SquareMatrix B(n);
for (unsigned long i=1;i<=n;i++)
for (unsigned long j=1;j<=n;j++)
for (unsigned long k=1;k<=n;k++)
B(i,j) += (*this)(i,k)*A(k,j);
//Ajout de ma part
return B;
}
void Node::addNextNode(Node* _NextNode) { NextNodes.push_back(_NextNode);}
void Node::addPreviousNode(Node* _NextNode) {PreviousNodes.push_back(_NextNode);}
void explore(std::list<Node*>& ReachableNodes) { /* A COMPLETER */}
Node::Node(const std::string& _Label) :Label(_Label){}
std::string Node::getLabel() const { return Label; }
Arc::Arc(Node* _StartNode, Node* _EndNode, double _Weight):StartNode(_StartNode), EndNode(_EndNode), Weight(_Weight){}
Node* Arc::getStartNode() const {
return StartNode;
}
Node* Arc::getEndNode() const {return EndNode;}
double Arc::getWeight() const {return Weight;}
Node* OrientedGraph::findNode(const std::string& NodeLabel) {
Node* ptr = NULL;
bool Found = false;
std::list<Node*>::iterator i = NodesList.begin(), e = NodesList.end();
while ( !Found && i!=e ) {
if ( (*i)->getLabel() == NodeLabel ) { ptr = *i; Found = true; }
i++;
}
return ptr;
}
Arc* OrientedGraph::findArc(const std::string& StartNodeLabel, const std::string& EndNodeLabel) {
Arc* ptr = NULL;
bool Found = false;
std::list<Arc*>::iterator i = ArcsList.begin(), e = ArcsList.end();
while ( !Found && i!=e ) {
if ( ((*i)->getStartNode()->getLabel() == StartNodeLabel) &&
((*i)->getEndNode()->getLabel() == EndNodeLabel) )
{
ptr = *i; Found = true;
}
i++;
}
return ptr;
}
bool OrientedGraph::addNode(const std::string& NewNodeLabel) {
if (findNode(NewNodeLabel)) {
std::cerr << NewNodeLabel << " : already used !" << std::endl; return false;
}
NodesList.push_back(new Node(NewNodeLabel));
UpToDate = false;
return true;
}
bool OrientedGraph::addArc(const std::string& StartNodeLabel, const std::string& EndNodeLabel, double Weight) {
Node* StartNode = findNode(StartNodeLabel);
if (StartNode) {
Node* EndNode = findNode(EndNodeLabel);
if (EndNode) {
ArcsList.push_back(new Arc(StartNode, EndNode, Weight));
StartNode->addNextNode(EndNode);
EndNode->addPreviousNode(StartNode);
UpToDate = false;
return true;
}
else {
std::cerr << EndNodeLabel << " : not found !" << std::endl;
return false;
}
}
else {
std::cerr << StartNodeLabel << " : not found !" << std::endl;
return false;
}
}
void OrientedGraph::computeTransitiveClosure() {
return;
}
void OrientedGraph::getReachableNodesFrom(const std::string& SourceNodeLabel,std::list<Node*>& ReachableNodes) {
return;
}
BOOL OrientedGraph::isStronglyConnected() {
return true;
}
void OrientedGraph::getMaximalStronglyConnectedComponentFrom(const std::string& SourceNodeLabel,std::list<Node*>& ConnectedNodes) {
return;
} |
Partager