Isis 3.0 Programmer Reference
Back | Home
ControlGraph.cpp
1 #include "IsisDebug.h"
2 #include "ControlGraph.h"
3 
4 #include <iostream>
5 #include <utility>
6 
7 #include <QHash>
8 #include <QMap>
9 #include <QString>
10 #include <QVector>
11 #include <QQueue>
12 #include <QPair>
13 
14 #include "ControlMeasure.h"
15 #include "ControlPoint.h"
16 #include "GroupedStatistics.h"
17 #include "ControlNet.h"
18 #include "IException.h"
19 #include "IString.h"
20 
21 
22 
23 namespace Isis {
24 
31  cnet = someControlNet;
32  cubeIdToIndexHash = NULL;
33  cubeIndexToIdHash = NULL;
34  graph = NULL;
36 
37  // cubeIdToIndexHash provides a way of assigning unique sequential indices
38  // to all of the Cube Serial numbers in the ControlNet, while
39  // cubeIndexToIdHash prvides a way to get the Cube Serial numbers back.
42  cubeIdToIndexHash->reserve(cnet->GetNumPoints() / 5);
43  cubeIndexToIdHash->reserve(cnet->GetNumPoints() / 5);
44 
46 
48 
49  if (islands->size())
50  connected = false;
51  else
52  connected = true;
53  }
54 
55 
62  cnet = other.cnet;
63 
64  cubeIdToIndexHash = NULL;
65  cubeIndexToIdHash = NULL;
66  graph = NULL;
67  islands = NULL;
68 
72  *other.graph);
73  islands = new QVector< QVector< int > >(*other.islands);
74 
75  connected = other.connected;
76  }
77 
78 
83  cnet = NULL;
84 
85  if (cubeIdToIndexHash) {
86  delete cubeIdToIndexHash;
87  cubeIdToIndexHash = NULL;
88  }
89 
90  if (cubeIndexToIdHash) {
91  delete cubeIndexToIdHash;
92  cubeIndexToIdHash = NULL;
93  }
94 
95  if (graph) {
96  delete graph;
97  graph = NULL;
98  }
99 
100  if (islands) {
101  delete islands;
102  islands = NULL;
103  }
104  }
105 
106 
109  return connected;
110  }
111 
112 
118  return islands->size();
119  }
120 
121 
128  const {
129  if (connected) {
130  QString msg = "\n\nGetCubesOnIsland called on connected graph with no "
131  "islands!!!\n\n";
132  throw IException(IException::Programmer, msg.toStdString(), _FILEINFO_);
133  }
134 
135  ASSERT(islands->size() != 0);
136 
137  if (island < 0 || island >= islands->size()) {
138  QString msg = "\n\nA list of cubes was requested from island " +
139  QString::number(island) + "\nbut that island does not exist!!!"
140  "\n\nThere are " + QString::number(islands->size()) + " islands "
141  "numbered from 0 to " + QString::number(islands->size() - 1) + "\n\n";
142  throw IException(IException::Programmer, msg.toStdString(), _FILEINFO_);
143  }
144 
145  QVector< QString > cubeList;
146  for (int i = 0; i < (*islands)[island].size(); i++) {
147  cubeList.push_back(cubeIndexToIdHash->value((*islands)[island][i]));
148  }
149 
150  return cubeList;
151  }
152 
153 
158  QVector< QString > cubeList;
159 
160  // for each key in the cubeIdToIndexHash add the key to a vector
162  while (i != cubeIdToIndexHash->constEnd()) {
163  cubeList.push_back(i.key());
164  i++;
165  }
166 
167  return cubeList;
168  }
169 
170 
177  CubeSerialNumber) const {
178  return graph->find(cubeIdToIndexHash->value(CubeSerialNumber)).value()
179  .second;
180  }
181 
182 
187  if (this == &other)
188  return *this;
189 
190  if (cubeIdToIndexHash) {
191  delete cubeIdToIndexHash;
192  cubeIdToIndexHash = NULL;
193  }
194  if (cubeIndexToIdHash) {
195  delete cubeIndexToIdHash;
196  cubeIndexToIdHash = NULL;
197  }
198  if (graph) {
199  delete graph;
200  graph = NULL;
201  }
202  if (islands) {
203  delete islands;
204  islands = NULL;
205  }
206 
207  cnet = other.cnet;
208  connected = other.connected;
209 
213  *other.graph);
214  islands = new QVector< QVector< int > >(*other.islands);
215 
216  return *this;
217  }
218 
219 
224  // index assigned to last hashed cube (-1 means empty hash table)
225  int cubeIndex = -1;
226 
227  // whats about to happen is this:
228  //
229  // for all ControlPoints in the given ControlNet
230  // for each ControlMeasure (cube) in the ControlPoint
231  // for all the other ControlMeasures (other cubes) in the ControlPoint
232  // add connection from previous for loops cube to this for loops cube
233  //
234  // along the way as we encounter new cubes they are hashed. Also, for all
235  // the measures encountered be the middle for loop statistics are saved.
236 
237  for (int cpIndex = 0; cpIndex < cnet->GetNumPoints(); cpIndex++) {
238  if (!(*cnet)[cpIndex]->IsIgnored()) {
239  // use a reference for the current ControlPoint for clearity
240  const ControlPoint &curCtrlPoint = *(*cnet)[cpIndex];
241  for (int cmIndex = 0; cmIndex < curCtrlPoint.GetNumMeasures(); cmIndex++) {
242  // get current cube's serial number and hash if new
243  QString curCube = curCtrlPoint[cmIndex]->GetCubeSerialNumber();
244  if (!cubeIdToIndexHash->contains(curCube)) {
245  cubeIdToIndexHash->insert(curCube, ++cubeIndex);
246  cubeIndexToIdHash->insert(cubeIndex, curCube);
247  }
248  int curCubeIndex = cubeIdToIndexHash->value(curCube);
249 
251  >::iterator graphIterator = graph->find(curCubeIndex);
252 
253  // look for adjacent cubes
254  for (int cmIndex2 = 0; cmIndex2 < curCtrlPoint.GetNumMeasures(); cmIndex2++) {
255  if (cmIndex2 != cmIndex) {
256  // get adjacent cube's serial number and hash if new
257  QString adjacentCube = curCtrlPoint[cmIndex2]->GetCubeSerialNumber();
258  if (!cubeIdToIndexHash->contains(adjacentCube)) {
259  cubeIdToIndexHash->insert(adjacentCube, ++cubeIndex);
260  cubeIndexToIdHash->insert(cubeIndex, adjacentCube);
261  }
262  int adjCubeIndex = cubeIdToIndexHash->value(adjacentCube);
263 
264  // add a connection from the current cube to the adjacent cube
265  if (graphIterator != graph->end()) {
266  graphIterator.value().first.AddConnection(adjCubeIndex, cpIndex,
267  cmIndex2);
268  }
269  else {
270  AdjacentCubeList newCubeList(adjCubeIndex, cpIndex, cmIndex2);
271  GroupedStatistics cmStats;
272  graph->insert(curCubeIndex, qMakePair(newCubeList, cmStats));
273  }
274  }
275  } // of for all measures in cp
276 
277  // save off statistics
278  if (graphIterator != graph->end()) {
279  QVector< QString > dataNames(cnet->GetPoint(cpIndex)->
280  GetMeasure(cmIndex)->GetMeasureDataNames());
281 
282  for (int i = 0; i < dataNames.size(); i++)
283  graphIterator.value().second.AddStatistic(dataNames[i],
284  cnet->GetPoint(cpIndex)->GetMeasure(cmIndex)->
285  GetMeasureData(dataNames[i]));
286  } // of saving statistics
287  } // of for all measures in cp
288  } // of if not an igrored point
289  } // of for all ControlPoints in net
290  } // of HashCubesAndPopulateGraph
291 
292 
298  // assume subgraphs exist! (check assumption at the very end of the method)
299 
300  // A search list has a value for every cube, which defaults to false.
301  // A breadth-first search is used to test connectivity and works by setting
302  // each cubes cooresponding search list value to true as it is visited.
303  // At the end of the first round the true entries make up the first
304  // subgragh. As they are added to the first subgraph they are removed from
305  // the search list. The remaining false entries must have the breadth-first
306  // search done on them to determine the next subgraph(s). This process
307  // continues until all entries in the search list are true (until all cubes
308  // have been visited)
309  QMap< int, bool > searchList;
310  for (int i = 0; i < graph->size(); i++)
311  searchList.insert(i, false);
312 
313  // For each subgraph keep a list of the cubes in the subgraph. This is
314  // represented by a 2d vector where the inner vectors are cubes within a
315  // subgraph and the outer vector is a list of subgraphs
317 
318  // keeps track of which itteration of the breadth-first search we are on and
319  // thus also which subgraph we are currently populating
320  int subgraphIndex = -1;
321 
322  while (searchList.size()) {
323  // create a new subgraph
324  subgraphIndex++;
325  islands->push_back(QVector< int >());
326 
327  // The queue used for breadth-first searching
328  QQueue< int > q;
329 
330  // visit the first cube
331  searchList.begin().value() = true;
332  q.enqueue(searchList.begin().key());
333 
334  // visit all cubes possible using the breadth-first approach
335  while (q.size()) {
336  int curVertex(q.dequeue());
337  QVector< int > adjacentVertices = graph->find(curVertex).value().first
338  .GetAdjacentCubes();
339 
340  for (int i = 0; i < adjacentVertices.size(); i++) {
341  const int &curNeighbor = adjacentVertices[i];
342 
343  ASSERT(searchList.find(curNeighbor) != searchList.end());
344 
345  if (!searchList.find(curNeighbor).value()) {
346  searchList.find(curNeighbor).value() = true;
347  q.enqueue(curNeighbor);
348  }
349  }
350  } // end of breadth-first search
351 
352  // add all true entries to the current subgraph
353  QMap< int, bool >::iterator i = searchList.begin();
354  while (i != searchList.end()) {
355  if (i.value()) {
356  (*islands)[subgraphIndex].push_back(i.key());
357  }
358  i++;
359  }
360 
361  // remove all the true entries from the search list
362  for (int i = 0; i < (*islands)[subgraphIndex].size(); i++) {
363  searchList.remove((*islands)[subgraphIndex][i]);
364  }
365  }
366 
367  // if there was only ever one subgraph created then the initial assumption
368  // was wrong! There are no islands at all - this is a connected graph!
369  if (subgraphIndex == 0) {
370  islands->clear();
371  }
372  }
373 
374 
386  const int &cpIndex, const int &cmIndex) {
387  connections = NULL;
388 
389  QVector< QPair< int, int > > firstEdge;
390  firstEdge.push_back(qMakePair(cpIndex, cmIndex));
392  connections->insert(cubeIndex, firstEdge);
393  }
394 
395 
402  other) {
403  connections = NULL;
404  connections = new QMap< int, QVector< QPair< int, int > > >(
405  *other.connections);
406  }
407 
408 
411  if (connections) {
412  delete connections;
413  connections = NULL;
414  }
415  }
416 
417 
422  // vector of adjacent cubes to be returned
423  QVector< int > adjacentCubes;
424 
425  if (!connections)
426  return adjacentCubes;
427 
428  QMap< int, QVector< QPair< int, int > > >::const_iterator i =
429  connections->constBegin();
430  while (i != connections->constEnd()) {
431  adjacentCubes.push_back(i.key());
432  i++;
433  }
434 
435  return adjacentCubes;
436  }
437 
438 
449  const int &cpIndex, const int &cmIndex) {
450  QMap< int, QVector< QPair< int, int > > >::iterator i =
451  connections->find(cubeIndex);
452 
453  // if the cube already exists in our list then just add another edge to it.
454  // otherwise we need to add the cube as well.
455  if (i != connections->end()) {
456  i.value().push_back(qMakePair(cpIndex, cmIndex));
457  }
458  else {
459  QVector< QPair< int, int > > firstEdge;
460  firstEdge.push_back(qMakePair(cpIndex, cmIndex));
461  connections->insert(cubeIndex, firstEdge);
462  }
463  }
464 
465 
470  const AdjacentCubeList &other) {
471  if (connections) {
472  delete connections;
473  connections = NULL;
474  }
475 
476  connections = new QMap< int, QVector< QPair< int, int > > >(
477  *other.connections);
478 
479  return *this;
480  }
481 }
~ControlGraph()
Destruct a ControlGraph.
Unless noted otherwise, the portions of Isis written by the USGS are public domain.
const GroupedStatistics & GetMeasureStats(const QString &CubeSerialNumber) const
AdjacentCubeList(const int &cubeIndex, const int &cpIndex, const int &cmIndex)
Construct a new AdjacentCubeList given one initial adjacent connection.
Grouped Statistics.
void HashCubesAndPopulateGraph()
int GetNumPoints() const
Return the number of control points in the network.
ControlGraph(ControlNet *someControlNet)
construct a ControlGraph given a ControlNet
This error is for when a programmer made an API call that was illegal.
Definition: IException.h:154
ControlNet * cnet
ControlNet to make a graph from.
Definition: ControlGraph.h:80
~AdjacentCubeList()
destruct an AdjacentCubeList
bool connected
Stores the state of the graphs connectivity so that connectivity must only be calculated once...
Definition: ControlGraph.h:101
a control network
Definition: ControlNet.h:207
Unless noted otherwise, the portions of Isis written by the USGS are public domain.
QHash< int, QString > * cubeIndexToIdHash
Used to get a cube serial number from an index.
Definition: ControlGraph.h:86
const QVector< QString > GetCubesOnIsland(const int &island) const
#define _FILEINFO_
Macro for the filename and line number.
Definition: IException.h:38
const QVector< QString > GetCubeList() const
A single control point.
Definition: ControlPoint.h:339
bool IsConnected() const
Returns true if this ControlGraph is connected or false otherwise.
QMap< int, QVector< QPair< int, int > > > * connections
stores all edges or connections for an adjacent cube
Definition: ControlGraph.h:134
int GetIslandCount() const
There can be 0 islands or 2 or more islands.
const QVector< int > GetAdjacentCubes() const
ControlGraph & operator=(const ControlGraph &other)
AdjacentCubeList & operator=(const AdjacentCubeList &other)
QHash< QString, int > * cubeIdToIndexHash
Used to get an index from a cube serial number.
Definition: ControlGraph.h:83
void CalculateIslands()
Determines whether or not islands exist and calculates what they are if present.
Isis exception class.
Definition: IException.h:99
QVector< QVector< int > > * islands
Stores a list of islands which are themselves a list of cube indices.
Definition: ControlGraph.h:104
QMap< int, QPair< AdjacentCubeList, GroupedStatistics > > * graph
THE GRAPH!! It is a map of cube indices to a pair.
Definition: ControlGraph.h:95
Control Graph nested class.
Definition: ControlGraph.h:120
Control Network statistics and connectivity.
Definition: ControlGraph.h:57
void AddConnection(const int &cubeIndex, const int &cpIndex, const int &cmIndex)
Adds a connection to an AdjacentCubeList.
const ControlMeasure * GetMeasure(QString serialNumber) const
Get a control measure based on its cube&#39;s serial number.

U.S. Department of the Interior | U.S. Geological Survey
ISIS | Privacy & Disclaimers | Astrogeology Research Program
To contact us, please post comments and questions on the ISIS Support Center
File Modified: 07/12/2023 23:16:18