xc
Public Member Functions | Protected Member Functions | Friends | List of all members

Graph that uses an array to store its vertices. More...

#include <ArrayGraph.h>

Inheritance diagram for XC::ArrayGraph:
Inheritance graph
[legend]
Collaboration diagram for XC::ArrayGraph:
Collaboration graph
[legend]

Public Member Functions

 ArrayGraph (int arraySize)
 Constructor. More...
 
virtual ~ArrayGraph (void)
 Destructor.
 
virtual bool addVertex (const Vertex &vertexPtr)
 Add a vertex to the graph. More...
 
virtual int addEdge (int vertexTag, int otherVertexTag)
 Add an edge to the graph. More...
 
virtual VertexgetVertexPtr (int vertexTag)
 Return a pointer to the vertex identified by the tag. More...
 
virtual const VertexgetVertexPtr (int vertexTag) const
 Return a const pointer to the vertex identified by the tag. More...
 
virtual VertexItergetVertices (void)
 A method which first invokes {reset()} on the graphs ArrayVertexIter and then returns a reference to this iter. More...
 
int getNumVertex (void) const
 Return the number of vertices in the graph, returns numVertex.
 
int getNumEdge (void) const
 A method to return the number of edges in the graph.
 
virtual void Print (std::ostream &s) const
 Print the graph. More...
 
- Public Member Functions inherited from XC::Graph
 Graph (int numVertices=32)
 Constructor. More...
 
 Graph (const Graph &other)
 Copy constructor.
 
Graphoperator= (const Graph &other)
 Assignment operator.
 
virtual bool addVertex (const Vertex &vertexPtr, bool checkAdjacency=true)
 Appends a vertex to the graph. More...
 
virtual int getFreeTag (void)
 Returns the siguiente identifier (tag) libre.
 
virtual bool removeVertex (int tag, bool removeEdgeFlag=true)
 Removes from the graph the vertex identified by the tag being passed as parameter. More...
 
const VertexBuscaRef (int ref) const
 
void getBand (int &, int &) const
 Returns the ends of the bandwidth.
 
int getVertexDiffMaxima (void) const
 Returns the maximum (positive) of the difference between vertices indexes. More...
 
int getVertexDiffExtrema (void) const
 Returns the extreme (positive or negative) of the difference between vertices indexes. More...
 
virtual int merge (Graph &other)
 Mezcla los dos grafos.
 
virtual void Print (std::ostream &os, int flag=0) const
 Prints the graph.
 
int sendSelf (Communicator &)
 Sends object through the communicator argument.
 
int recvSelf (const Communicator &)
 Receives object through the communicator argument.
 
- Public Member Functions inherited from XC::MovableObject
 MovableObject (int classTag, int dbTag)
 Constructor. More...
 
 MovableObject (int classTag)
 Constructor. More...
 
 MovableObject (const MovableObject &)
 Copy constructor. Doesn't copy the dbTag.
 
MovableObjectoperator= (const MovableObject &)
 Assignment operator. Doesn't copy the dbTag.
 
int getClassTag (void) const
 Return the class identifier.
 
int getDbTag (void) const
 Return the object identifier in the database.
 
int getDbTag (Communicator &)
 Return the object identifier in the database.
 
void setDbTag (int dbTag)
 Sets the object identifier in the database.
 
void setDbTag (Communicator &)
 Sets the object identifier in the database if not already set. More...
 
virtual int setParameter (const std::vector< std::string > &argv, Parameter &param)
 Sets the value param to the parameter argv.
 
virtual int updateParameter (int parameterID, Information &info)
 Updates the parameter identified by parameterID with info.
 
virtual int activateParameter (int parameterID)
 Activates the parameter identified by parameterID.
 
virtual int setVariable (const std::string &variable, Information &)
 Set the value of the variable idenfified by var.
 
virtual int getVariable (const std::string &variable, Information &)
 Return the value of the variable idenfified by var.
 
- Public Member Functions inherited from XC::DistributedBase
 DistributedBase (void)
 Constructor.
 
virtual ~DistributedBase (void)
 Destructor.
 
virtual DbTagDatagetDbTagData (void) const
 Returns a vector to store class dbTags.
 
const int & getDbTagDataPos (const int &i) const
 Returns the data at the i-th position.
 
void setDbTagDataPos (const int &i, const int &v)
 Sets the data at the i-th position.
 
void inicComm (const int &dataSize) const
 Initializes communication.
 

Protected Member Functions

int getArraySize (void) const
 Return the size of the graphs array.
 
 ArrayGraph (const ArrayGraph &)
 
ArrayGraphoperator= (const ArrayGraph &)
 
- Protected Member Functions inherited from XC::Graph
void inic (const size_t &)
 
void copy (const Graph &other)
 
int sendData (Communicator &)
 Send object members through the communicator argument.
 
int recvData (const Communicator &)
 Receives object members through the communicator argument.
 

Friends

class ArrayVertexIter
 
std::ostream & operator<< (std::ostream &, const ArrayGraph &)
 

Additional Inherited Members

- Protected Attributes inherited from XC::Graph
ArrayOfTaggedObjects myVertices
 
VertexIter theVertexIter
 
int numEdge
 
int nextFreeTag
 

Detailed Description

Graph that uses an array to store its vertices.

ArrayGraph is a subtype of Graph. The vertices for this type of graph are held in a simple array data structure whose initial size is specified at construction. This size can increase if needed. The array storage scheme is more efficient than a List storage scheme in terms of accessing the vertices; in very large problems where memory is limited this type of scheme may have problems getting enough contiguous meory in which case a List might be a better choice. { There is a question as to whether or not the public methods should be declared as virtual. Good OOP programming would have all methods declared as virtual, however as subclasses cannot gain access to the private member data there does not seem to be much point in declaring them, except for the destructor, virtual in this instance.}

Constructor & Destructor Documentation

◆ ArrayGraph()

XC::ArrayGraph::ArrayGraph ( int  arraySize)

Constructor.

To construct an empty ArrayGraph. Creates a Vertex ** array, {theVertices} of size arraySize and sets the number of vertices, numVertex, and number of edges numEdge to \(0\). If it fails to get an array of appropriate size it sets its arraySize to \(0\); subclasses can check if successful construction by invoking the protected member function getArraySize().

Member Function Documentation

◆ addEdge()

int XC::ArrayGraph::addEdge ( int  vertexTag,
int  otherVertexTag 
)
virtual

Add an edge to the graph.

Causes the graph to add an edge {(vertexTag,otherVertexTag)} to the graph. A check is first made to see if vertices with tags given by {vertexTag} and {otherVertexTag} exist in the graph. If they do not exist a $-1$ is returned, otherwise the method invokes {addEdge()} on each of the corresponding vertices in the graph. Returns $0$ if successful, a negative number if not.

Reimplemented from XC::Graph.

◆ addVertex()

bool XC::ArrayGraph::addVertex ( const Vertex vrt)
virtual

Add a vertex to the graph.

Method to add a vertex to the graph. If the adjacency list of the vertex is not empty the graph will first check to see all vertices in the the the vertices adjacency list exist in the graph before the vertex is added. It then checks if it needs a new_ array and if so creates one, i.e. if the {arraySize} $=$ {numVertex} it creates a new_ array, whose size is double the original and copies the pointers to the vertices, before invoking {delete()} on the old array. It now tries to add the vertex in the array at location {vertexTag}. If this fails it adds at the first empty location it comes to. Returns a 0 if successful addition, a $-1$ otherwise and a message to cerr explaining the problem.

◆ getVertexPtr() [1/2]

XC::Vertex * XC::ArrayGraph::getVertexPtr ( int  vertexTag)
virtual

Return a pointer to the vertex identified by the tag.

A method which returns a pointer to the vertex whose tag is given by vertexTag. The method first looks at location {vertexTag} for the vertex, otherwise it must search through the array until it finds the vertex it is looking for. If no such vertex exists in the graph $0$ is returned.

Reimplemented from XC::Graph.

◆ getVertexPtr() [2/2]

const XC::Vertex * XC::ArrayGraph::getVertexPtr ( int  vertexTag) const
virtual

Return a const pointer to the vertex identified by the tag.

A method which returns a const pointer to the vertex whose tag is given by vertexTag. The method first looks at location {vertexTag} for the vertex, otherwise it must search through the array until it finds the vertex it is looking for. If no such vertex exists in the graph $0$ is returned.

Reimplemented from XC::Graph.

◆ getVertices()

XC::VertexIter & XC::ArrayGraph::getVertices ( void  )
virtual

A method which first invokes {reset()} on the graphs ArrayVertexIter and then returns a reference to this iter.

Reimplemented from XC::Graph.

◆ Print()

void XC::ArrayGraph::Print ( std::ostream &  s) const
virtual

Print the graph.

A method to print the graph. It first prints out numVertex and numEdge and then on each newline prints the vertexTag and the edges for that vertex. It does this by going through theVertices array and invoking Print() on each non-zero pointer.


The documentation for this class was generated from the following files: