Program Listing for File BaseGraph.h#
↰ Return to documentation for file (src/midend/programAnalysis/OpenAnalysis/Utils/BaseGraph.h)
// $Id: BaseGraph.h,v 1.3 2008/01/08 02:56:40 dquinlan Exp $
// -*-C++-*-
// * BeginRiceCopyright *****************************************************
//
// Copyright ((c)) 2002, Rice University
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// * Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// * Neither the name of Rice University (RICE) nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// This software is provided by RICE and contributors "as is" and any
// express or implied warranties, including, but not limited to, the
// implied warranties of merchantability and fitness for a particular
// purpose are disclaimed. In no event shall RICE or contributors be
// liable for any direct, indirect, incidental, special, exemplary, or
// consequential damages (including, but not limited to, procurement of
// substitute goods or services; loss of use, data, or profits; or
// business interruption) however caused and on any theory of liability,
// whether in contract, strict liability, or tort (including negligence
// or otherwise) arising in any way out of the use of this software, even
// if advised of the possibility of such damage.
//
// ******************************************************* EndRiceCopyright *
// Best seen in 120-column wide window (or print in landscape mode).
//--------------------------------------------------------------------------------------------------------------------
// This file is part of Mint.
// Arun Chauhan (achauhan@cs.rice.edu), Dept of Computer Science, Rice University, 2001.
//--------------------------------------------------------------------------------------------------------------------
#ifndef BaseGraph_H
#define BaseGraph_H
// standard headers
#include <iostream>
using ::std::ostream;
// STL headers
#include <list>
#include <set>
// Mint headers
#include "Iterator.h"
#include "Exception.h"
namespace std {
using namespace ::std;
}
//--------------------------------------------------------------------------------------------------------------------
// BaseGraph
//--------------------------------------------------------------------------------------------------------------------
class BaseGraph {
public:
class Node;
class Edge;
class DFSIterator;
class BFSIterator;
class NodesIterator;
class BiDirNodesIterator;
class EdgesIterator;
friend class DFSIterator;
friend class BFSIterator;
friend class NodesIterator;
friend class BiDirNodesIterator;
friend class EdgesIterator;
//------------------------------------------------------------------------------------------------------------------
class EmptyEdge : public Exception {
public:
EmptyEdge () {}
~EmptyEdge () {}
void report (std::ostream& o) const { o << "E! Adding a null edge to a graph." << std::endl; }
};
//------------------------------------------------------------------------------------------------------------------
class DuplicateEdge : public Exception {
public:
DuplicateEdge (BaseGraph::Edge* e) { offending_edge = e; }
~DuplicateEdge () {}
void report (std::ostream& o) const;
private:
BaseGraph::Edge* offending_edge;
};
//------------------------------------------------------------------------------------------------------------------
class NonexistentEdge : public Exception {
public:
NonexistentEdge (BaseGraph::Edge* e) { offending_edge = e; }
~NonexistentEdge () {}
void report (std::ostream& o) const { o << "E! Removing a non-existent edge from a graph." << std::endl; }
private:
BaseGraph::Edge* offending_edge;
};
//------------------------------------------------------------------------------------------------------------------
class EdgeInUse : public Exception {
public:
EdgeInUse (BaseGraph::Edge* e) { offending_edge = e; }
~EdgeInUse () {}
void report (std::ostream& o) const { o << "E! Adding an edge that is already a part of another graph." << std::endl; }
private:
BaseGraph::Edge* offending_edge;
};
//------------------------------------------------------------------------------------------------------------------
class EmptyNode : public Exception {
public:
EmptyNode () {}
~EmptyNode () {}
void report (std::ostream& o) const { o << "E! Adding a null node to a graph." << std::endl; }
};
//------------------------------------------------------------------------------------------------------------------
class DuplicateNode : public Exception {
public:
DuplicateNode (BaseGraph::Node* n) { offending_node = n; }
~DuplicateNode () {}
void report (std::ostream& o) const { o << "E! Adding a duplicate node to a graph." << std::endl; }
private:
BaseGraph::Node* offending_node;
};
//------------------------------------------------------------------------------------------------------------------
class NonexistentNode : public Exception {
public:
NonexistentNode (BaseGraph::Node* n) { offending_node = n; }
~NonexistentNode () {}
void report (std::ostream& o) const { o << "E! Removing a non-existent node from a graph." << std::endl; }
private:
BaseGraph::Node* offending_node;
};
//------------------------------------------------------------------------------------------------------------------
class NodeInUse : public Exception {
public:
NodeInUse (BaseGraph::Node* n) { offending_node = n; }
~NodeInUse () {}
void report (std::ostream& o) const { o << "E! Addiing a node that is already a part of another graph." << std::endl; }
private:
BaseGraph::Node* offending_node;
};
//------------------------------------------------------------------------------------------------------------------
class DeletingRootOfNonSingletonGraph : public Exception {
public:
DeletingRootOfNonSingletonGraph (BaseGraph::Node* n) { offending_node = n; }
~DeletingRootOfNonSingletonGraph () {}
void report (std::ostream& o) const { o << "E! Deleting the root node of a non-singleton graph." << std::endl; }
private:
BaseGraph::Node* offending_node;
};
//------------------------------------------------------------------------------------------------------------------
class Node {
public:
Node () { dfs_succ = bfs_succ = 0; in_use = false; }
virtual ~Node () { dfs_succ = NULL; bfs_succ = NULL; }
virtual void dump (std::ostream& os) { os << this; }
protected:
bool in_use;
Node* dfs_succ;
Node* bfs_succ;
friend class BaseGraph;
friend class BaseGraph::DFSIterator;
friend class BaseGraph::BFSIterator;
};
//------------------------------------------------------------------------------------------------------------------
class Edge {
public:
Edge (Node* _n1, Node* _n2) { n1 = _n1; n2 = _n2; in_use = false; }
virtual ~Edge () { n1 = NULL; n2 = NULL; }
virtual void dump (std::ostream& os) { os << this; }
protected:
bool in_use;
Node* n1;
Node* n2;
friend class BaseGraph;
friend class BaseGraph::DFSIterator;
friend class BaseGraph::BFSIterator;
friend class BaseGraph::DuplicateEdge;
};
//------------------------------------------------------------------------------------------------------------------
class DFSIterator : public Iterator {
public:
DFSIterator (BaseGraph& g);
~DFSIterator () {}
void operator++ () { if (p != 0) p = p->dfs_succ; std::cerr << "advance " << p << std::endl; }
operator bool () { return (p != 0); }
protected:
Node* p;
};
//------------------------------------------------------------------------------------------------------------------
class BFSIterator : public Iterator {
public:
BFSIterator (BaseGraph& g);
~BFSIterator () {}
void operator++ () { if (p != 0) p = p->bfs_succ; }
operator bool () { return (p != 0); }
protected:
Node* p;
};
//------------------------------------------------------------------------------------------------------------------
class NodesIterator : public Iterator {
public:
NodesIterator (BaseGraph& g) { gr = &g; iter = gr->node_set.begin(); }
~NodesIterator () {}
void operator++ () { ++iter; }
operator bool () { return (iter != gr->node_set.end()); }
protected:
std::set<Node*>::iterator iter;
BaseGraph* gr;
};
//------------------------------------------------------------------------------------------------------------------
class BiDirNodesIterator : public Iterator {
public:
enum dirType { Forward, Reverse };
// Default to forward direction if client doesn't specify the direction.
BiDirNodesIterator (BaseGraph& g) { dir = Forward; iter = gr->node_set.begin(); }
BiDirNodesIterator (BaseGraph& g, dirType d) {
gr = &g; dir = d;
if (dir == Forward)
iter = gr->node_set.begin();
else {
iter = gr->node_set.end();
iter--;
pre_begin = gr->node_set.begin();
--pre_begin;
}
}
~BiDirNodesIterator () {}
void operator++ () { ++iter; }
void operator-- () { --iter; }
operator bool () {
if (dir == Forward)
return iter != gr->node_set.end();
else {
return iter != pre_begin;
}
}
protected:
std::set<Node*>::iterator iter;
std::set<Node*>::iterator pre_begin;
BaseGraph* gr;
dirType dir;
};
//------------------------------------------------------------------------------------------------------------------
class EdgesIterator : public Iterator {
public:
EdgesIterator (BaseGraph& g) { gr = &g; iter = gr->edge_set.begin(); }
~EdgesIterator () {}
void operator++ () { ++iter; }
operator bool () { return (iter != gr->edge_set.end()); }
protected:
std::set<Edge*>::iterator iter;
BaseGraph* gr;
};
//------------------------------------------------------------------------------------------------------------------
BaseGraph () { root_node = 0; }
BaseGraph (Node* root) { root_node = 0; add(root); }
virtual ~BaseGraph ();
Node* root () { return root_node; }
void set_root (Node* n) { root_node = n; }
int num_nodes () { return node_set.size(); }
int num_edges () { return edge_set.size(); }
bool isempty () { return (root_node == 0); }
void dump (std::ostream&);
protected:
std::set<Node*> node_set; // the set of all the graph nodes
std::set<Edge*> edge_set; // the set of all the graph edges
Node* root_node; // the root node
bool DFS_needed, BFS_needed; // has a DFS / BFS been done on this graph?
#if __cplusplus < 201103L
void add (Edge* e) throw (DuplicateEdge, EdgeInUse, EmptyEdge,
DuplicateNode, NodeInUse, EmptyNode);
void add (Node* n) throw (DuplicateNode, NodeInUse, EmptyNode);
void remove (Edge* e) throw (NonexistentEdge, EmptyEdge);
void remove (Node* n) throw (NonexistentNode, DeletingRootOfNonSingletonGraph, EmptyNode);
#else
void add (Edge* e);
void add (Node* n);
void remove (Edge* e);
void remove (Node* n);
#endif
virtual Node* create_DFS_links (Node* start_node) = 0;
virtual Node* create_BFS_links (Node* start_node) = 0;
};
//--------------------------------------------------------------------------------------------------------------------
#endif