Πρόβλημα με C++

[Herakles]

Γεια παιδιά!Έχω ένα πρόβλημα...Προσπαθώ εδώ και μερικές μέρες να φτιάξω ένα πρόγραμμα που να διαβάζει από ένα αρχείο ένα γράφο κατευθυνόμενων ακμών το οποίο θα αποφασίζει εάν ο γράφος έχει μέσα του κύκλο ή όχι,και αν βρει να τυπώνει στο output τις ακμές που απαρτίζουν τον κύκλο.Για παράδειγμα εισάγουμε το αρχείο

File graph1.dat:

numNodes 5

numEdges 5

node n1

node n2

node n3

node n4

node n5

edge FROM n1 TO n2

edge FROM n1 TO n3

edge FROM n2 TO n4

edge FROM n3 TO n4

edge FROM n3 TO n5

 

Πιθανη υλοποίηση του προγράμματος:

#include <string>

#include <set>

#include <map>

#include <vector>

#include <limits.h>

using namespace std;

class HNode; // fwd decl

class HEdge; // fwd decl

class HGraph; // fwd decl

typedef set<HNode*> HNodePSet;

typedef set<HEdge*> HEdgePSet;

class HNode {

friend HGraph; // HGraph is the manager class: it is responsible

// for creating/deleting nodes and edges.

public:

~HNode();

const HEdgePSet& getHEdges() const;

const string& getName() const;

int getAncestors(HNodePSet& ancs) const; // return # of immed ancestors.

int getAllAncestors(HNodePSet& allAncs) const; // return # of all ancs.

int getDescendants(HNodePSet& descs) const; // return # of immed. descs.

int getAllDescendants(HNodePSet& allDecs) const; // return # all descs.

private:

// private methods include constructors (thus only the friend HGraph can create a node)

// and methods for adding/deleting incoming or outgoing edges.

// private data members may include the node name, plus sets of pointers to incoming

// and outgoing edges

};

class HEdge {

friend HGraph;

public:

~HEdge();

const HNode* getFrom() const;

const HNode* getTo() const;

...

private:

// private methods include constructors (thus only the friend HGraph can create a node)

// private data may include pointers to the 2 ends of the edge.

};

 

/** class HGraph is the manager class of HNode and HEdge objects All memory

* management is done by the HGraph object.

* See the book of

* J. Lakos: "Large Scale C++ Software Design".

*/

class HGraph {

public:

HGraph()

~HGraph();

HNode* addNode(const string& name); // add a Node for this graph

HNode* findNode(const string& name) const; // throws if not found

int removeNode(HNode* nP); // return size of _nodes afterwards

HEdge* addEdge(HNode* fromP, const HNode* to);

int removeEdge(HEdge* eP); // returns new number of edges

ostream& print(ostream& os) const;

const HNodePSet& getHNodes() const;

const HEdgePSet& getHEdges() const;

private:

// more methods here

// DATA here

};

 

Η µέθοδος HNode::getAllDescendants(my_set) «γεµίζει» το όρισµα my_set µε δείκτες σε όλους τους κόµβους που είναι απόγονοι αυτού του κόµβου. Εαν ο ίδιος ο κόµβος περιέχεται στους απογόνους του, υπάρχει κύκλος στον οποίο συµµετέχει ο κόµβος.

 

Μπορεί να βοηθήσει κανεις;Έχετε καμιά ιδέα;Μια μικρή βοήθεια θα ωφελούσε πολύ.Ευχαριστώ

[Herakles]

Κανείς;