/*
* $Revision: 2615 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2012-07-16 14:23:36 +0200 (Mo, 16. Jul 2012) $
***************************************************************/
/** \file
* \brief Pure declaration header, find template implementation in
* Graph.h
*
* Declaration of NodeElement, EdgeElement, and Graph classes.
*
* \author Carsten Gutwenger
*
* \par License:
* This file is part of the Open Graph Drawing Framework (OGDF).
*
* \par
* Copyright (C)
* See README.txt in the root directory of the OGDF installation for details.
*
* \par
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* Version 2 or 3 as published by the Free Software Foundation;
* see the file LICENSE.txt included in the packaging of this file
* for details.
*
* \par
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* \par
* You should have received a copy of the GNU General Public
* License along with this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
* \see http://www.gnu.org/copyleft/gpl.html
***************************************************************/
#ifdef _MSC_VER
#pragma once
#endif
#ifndef OGDF_GRAPH_D_H
#define OGDF_GRAPH_D_H
#include "List.h"
namespace ogdf {
//
// in embedded graphs, adjacency lists are given in clockwise order.
//
class OGDF_EXPORT Graph;
class OGDF_EXPORT NodeElement;
class OGDF_EXPORT EdgeElement;
class OGDF_EXPORT AdjElement;
class OGDF_EXPORT FaceElement;
class OGDF_EXPORT GraphListBase;
class OGDF_EXPORT ClusterElement;
//! The base class for objects used by graphs like nodes, edges, etc.
/**
* Such graph objects are maintained in list (see GraphList),
* and \a GraphElement basically provides a next and previous pointer
* for these objects.
*/
class OGDF_EXPORT GraphElement {
friend class Graph;
friend class GraphListBase;
protected:
GraphElement *m_next; //!< The successor in the list.
GraphElement *m_prev; //!< The predecessor in the list.
OGDF_NEW_DELETE
}; // class GraphElement
//! Base class for GraphElement lists.
class OGDF_EXPORT GraphListBase {
protected:
GraphElement *m_head; //!< Pointer to the first element in the list.
GraphElement *m_tail; //!< Pointer to the last element in the list.
public:
//! Constructs an empty list.
GraphListBase() { m_head = m_tail = 0; }
// destruction
~GraphListBase() { }
//! Adds element \a pX at the end of the list.
void pushBack(GraphElement *pX) {
pX->m_next = 0;
pX->m_prev = m_tail;
if (m_head)
m_tail = m_tail->m_next = pX;
else
m_tail = m_head = pX;
}
//! Inserts element \a pX after element \a pY.
void insertAfter(GraphElement *pX, GraphElement *pY) {
pX->m_prev = pY;
GraphElement *pYnext = pX->m_next = pY->m_next;
pY->m_next = pX;
if (pYnext) pYnext->m_prev = pX;
else m_tail = pX;
}
//! Inserts element \a pX before element \a pY.
void insertBefore(GraphElement *pX, GraphElement *pY) {
pX->m_next = pY;
GraphElement *pYprev = pX->m_prev = pY->m_prev;
pY->m_prev = pX;
if (pYprev) pYprev->m_next = pX;
else m_head = pX;
}
//! Removes element \a pX from the list.
void del(GraphElement *pX) {
GraphElement *pxPrev = pX->m_prev, *pxNext = pX->m_next;
if (pxPrev)
pxPrev->m_next = pxNext;
else
m_head = pxNext;
if (pxNext)
pxNext->m_prev = pxPrev;
else
m_tail = pxPrev;
}
//! Sorts the list according to \a newOrder.
template
void sort(const LIST &newOrder) {
GraphElement *pPred = 0;
typename LIST::const_iterator it = newOrder.begin();
if (!it.valid()) return;
m_head = *it;
for(; it.valid(); ++it) {
GraphElement *p = *it;
if ((p->m_prev = pPred) != 0) pPred->m_next = p;
pPred = p;
}
(m_tail = pPred)->m_next = 0;
}
//! Reverses the order of the list elements.
void reverse() {
GraphElement *pX = m_head;
m_head = m_tail;
m_tail = pX;
while(pX) {
GraphElement *pY = pX->m_next;
pX->m_next = pX->m_prev;
pX = pX->m_prev = pY;
}
}
//! Exchanges the positions of \a pX and \a pY in the list.
void swap(GraphElement *pX, GraphElement *pY) {
if (pX->m_next == pY) {
pX->m_next = pY->m_next;
pY->m_prev = pX->m_prev;
pY->m_next = pX;
pX->m_prev = pY;
} else if(pY->m_next == pX) {
pY->m_next = pX->m_next;
pX->m_prev = pY->m_prev;
pX->m_next = pY;
pY->m_prev = pX;
} else {
::swap(pX->m_next,pY->m_next);
::swap(pX->m_prev,pY->m_prev);
}
if(pX->m_prev)
pX->m_prev->m_next = pX;
else
m_head = pX;
if(pX->m_next)
pX->m_next->m_prev = pX;
else
m_tail = pX;
if(pY->m_prev)
pY->m_prev->m_next = pY;
else
m_head = pY;
if(pY->m_next)
pY->m_next->m_prev = pY;
else
m_tail = pY;
OGDF_ASSERT(consistencyCheck());
}
//! Checks consistency of graph list.
bool consistencyCheck() {
if (m_head == 0) {
return (m_tail == 0);
} else if (m_tail == 0) {
return false;
} else {
if (m_head->m_prev != 0)
return false;
if (m_tail->m_next != 0)
return false;
GraphElement *pX = m_head;
for(; pX; pX = pX->m_next) {
if (pX->m_prev) {
if (pX->m_prev->m_next != pX)
return false;
} else if(pX != m_head)
return false;
if (pX->m_next) {
if (pX->m_next->m_prev != pX)
return false;
} else if (pX != m_tail)
return false;
}
}
return true;
}
OGDF_NEW_DELETE
}; // class GraphListBase
//! Lists of graph objects (like nodes, edges, etc.).
/**
* The template type \a T must be a class derived from GraphElement.
*/
template class GraphList : protected GraphListBase {
public:
//! Constructs an empty list.
GraphList() { }
// destruction (deletes all elements)
~GraphList() {
if (m_head)
OGDF_ALLOCATOR::deallocateList(sizeof(T), m_head,m_tail);
}
//! Returns the first element in the list.
T *begin () const { return (T *)m_head; }
//! Returns the last element in the list.
T *rbegin() const { return (T *)m_tail; }
//! Returns true iff the list is empty.
bool empty() { return m_head; }
//! Adds element \a pX at the end of the list.
void pushBack(T *pX) {
GraphListBase::pushBack(pX);
}
//! Inserts element \a pX after element \a pY.
void insertAfter(T *pX, T *pY) {
GraphListBase::insertAfter(pX,pY);
}
//! Inserts element \a pX before element \a pY.
void insertBefore(T *pX, T *pY) {
GraphListBase::insertBefore(pX,pY);
}
//! Moves element \a pX to list \a L and inserts it before or after \a pY.
void move(T *pX, GraphList &L, T *pY, Direction dir) {
GraphListBase::del(pX);
if (dir == after)
L.insertAfter(pX,pY);
else
L.insertBefore(pX,pY);
}
//! Moves element \a pX to list \a L and inserts it at the end.
void move(T *pX, GraphList &L) {
GraphListBase::del(pX);
L.pushBack(pX);
}
//! Moves element \a pX from its current position to a position after \a pY.
void moveAfter(T *pX, T *pY){
GraphListBase::del(pX);
insertAfter(pX,pY);
}
//! Moves element \a pX from its current position to a position before \a pY.
void moveBefore(T *pX, T *pY){
GraphListBase::del(pX);
insertBefore(pX,pY);
}
//! Removes element \a pX from the list and deletes it.
void del(T *pX) {
GraphListBase::del(pX);
delete pX;
}
//! Only removes element \a pX from the list; does not delete it.
void delPure(T *pX) {
GraphListBase::del(pX);
}
//! Removes all elements from the list and deletes them.
void clear() {
if (m_head) {
OGDF_ALLOCATOR::deallocateList(sizeof(T),m_head,m_tail);
m_head = m_tail = 0;
}
}
//! Sorts all elements according to \a newOrder.
template
void sort(const T_LIST &newOrder) {
GraphListBase::sort(newOrder);
}
//! Reverses the order of the list elements.
void reverse() {
GraphListBase::reverse();
}
//! Exchanges the positions of \a pX and \a pY in the list.
void swap(T *pX, T *pY) {
GraphListBase::swap(pX,pY);
}
//! Checks consistency of graph list; returns true if ok.
bool consistencyCheck() {
return GraphListBase::consistencyCheck();
}
OGDF_NEW_DELETE
}; // class GraphList
typedef NodeElement *node; //!< The type of nodes.
typedef EdgeElement *edge; //!< The type of edges.
typedef AdjElement *adjEntry; //!< The type of adjacency entries.
//! Class for adjacency list elements.
/**
* Adjacency list elements represent the occurrence of an edges in
* the adjacency list of a node.
*/
class OGDF_EXPORT AdjElement : private GraphElement {
friend class Graph;
friend class GraphListBase;
friend class GraphList;
AdjElement *m_twin; //!< The corresponding adjacency entry (same edge)
edge m_edge; //!< The associated edge.
node m_node; //!< The node whose adjacency list contains this entry.
int m_id; //!< The (unique) index of the adjacency entry.
//! Constructs an adjacency element for a given node.
AdjElement(node v) : m_node(v) { }
//! Constructs an adjacency entry for a given edge and index.
AdjElement(edge e, int id) : m_edge(e), m_id(id) { }
public:
//! Returns the edge associated with this adjacency entry.
edge theEdge() const { return m_edge; }
//! Conversion to edge.
operator edge() const { return m_edge; }
//! Returns the node whose adjacency list contains this element.
node theNode() const { return m_node; }
//! Returns the corresponding adjacency element associated with the same edge.
adjEntry twin() const { return m_twin; }
//! Returns the associated node of the corresponding adjacency entry (shorthand for twin()->theNode()).
node twinNode() const { return m_twin->m_node; }
//! Returns the index of this adjacency element.
int index() const { return m_id; }
// traversing faces in clockwise (resp. counter-clockwise) order
// (if face is an interior face)
//! Returns the clockwise successor in face. Use faceCycleSucc instead!
adjEntry clockwiseFaceSucc() const { return m_twin->cyclicPred(); }
//! Returns the clockwise predecessor in face. Use faceCycleSucc instead!
adjEntry clockwiseFacePred() const { return cyclicSucc()->m_twin; }
//! Returns the counter-clockwise successor in face.
adjEntry counterClockwiseFaceSucc() const { return m_twin->cyclicSucc(); }
//! Returns the counter-clockwise predecessor in face.
adjEntry counterClockwiseFacePred() const { return cyclicPred()->m_twin; }
// default is traversing faces in clockwise order
//! Returns the cyclic successor in face.
adjEntry faceCycleSucc() const { return clockwiseFaceSucc(); }
//! Returns the cyclic predecessor in face.
adjEntry faceCyclePred() const { return clockwiseFacePred(); }
//! Returns the successor in the adjacency list.
adjEntry succ() const { return (adjEntry)m_next; }
//! Returns the predecessor in the adjacency list.
adjEntry pred() const { return (adjEntry)m_prev; }
//! Returns the cyclic successor in the adjacency list.
adjEntry cyclicSucc() const;
//! Returns the cyclic predecessor in the adjacency list.
adjEntry cyclicPred() const;
#ifdef OGDF_DEBUG
const Graph *graphOf() const;
#endif
OGDF_NEW_DELETE
}; // class AdjElement
//! Class for the representation of nodes.
class OGDF_EXPORT NodeElement : private GraphElement {
friend class Graph;
friend class GraphList;
GraphList m_adjEdges; //!< The adjacency list of the node.
int m_indeg; //!< The indegree of the node.
int m_outdeg; //!< The outdegree of the node.
int m_id; //!< The (unique) index of the node.
#ifdef OGDF_DEBUG
// we store the graph containing this node for debugging purposes
const Graph *m_pGraph; //!< The graph containg this node (debug only).
#endif
// construction
#ifdef OGDF_DEBUG
//! Constructs a node element with index \a id.
/**
* \remarks The parameter \a pGraph is only passed in a debug build.
* It is used, e.g., by NodeArray for checking if a node belongs to
* the correct graph.
*/
NodeElement(const Graph *pGraph, int id) :
m_indeg(0), m_outdeg(0), m_id(id), m_pGraph(pGraph) { }
#else
NodeElement(int id) : m_indeg(0), m_outdeg(0), m_id(id) { }
#endif
public:
//! Returns the (unique) node index.
int index() const { return m_id; }
//! Returns the indegree of the node.
int indeg() const { return m_indeg; }
//! Returns the outdegree of the node.
int outdeg() const { return m_outdeg; }
//! Returns the degree of the node (indegree + outdegree).
int degree() const { return m_indeg + m_outdeg; }
//! Returns the first entry in the adjaceny list.
adjEntry firstAdj() const { return m_adjEdges.begin(); }
//! Returns the last entry in the adjacency list.
adjEntry lastAdj () const { return m_adjEdges.rbegin(); }
//! Returns the successor in the list of all nodes.
node succ() const { return (node)m_next; }
//! Returns the predecessor in the list of all nodes.
node pred() const { return (node)m_prev; }
#ifdef OGDF_DEBUG
//! Returns the graph containing this node (debug only).
const Graph *graphOf() const { return m_pGraph; }
#endif
OGDF_NEW_DELETE
}; // class NodeElement
inline adjEntry AdjElement::cyclicSucc() const
{
return (m_next) ? (adjEntry)m_next : m_node->firstAdj();
}
inline adjEntry AdjElement::cyclicPred() const
{
return (m_prev) ? (adjEntry)m_prev : m_node->lastAdj();
}
inline bool test_forall_adj_edges(adjEntry &adj, edge &e)
{
if (adj) { e = adj->theEdge(); return true; }
else return false;
}
//! Class for the representation of edges.
class OGDF_EXPORT EdgeElement : private GraphElement {
friend class Graph;
friend class GraphList;
node m_src; //!< The source node of the edge.
node m_tgt; //!< The target node of the edge.
AdjElement *m_adjSrc; //!< Corresponding adjacancy entry at source node.
AdjElement *m_adjTgt; //!< Corresponding adjacancy entry at target node.
int m_id; // The (unique) index of the node.
//! Constructs an edge element (\a src,\a tgt).
/**
* @param src is the source node of the edge.
* @param tgt is the target node of the edge.
* @param adjSrc is the corresponding adjacency entry at source node.
* @param adjTgt is the corresponding adjacency entry at target node.
* @param id is the index of the edge.
*/
EdgeElement(node src, node tgt, AdjElement *adjSrc, AdjElement *adjTgt, int id) :
m_src(src), m_tgt(tgt), m_adjSrc(adjSrc), m_adjTgt(adjTgt), m_id(id) { }
//! Constructs an edge element (\a src,\a tgt).
/**
* @param src is the source node of the edge.
* @param tgt is the target node of the edge.
* @param id is the index of the edge.
*/
EdgeElement(node src, node tgt, int id) :
m_src(src), m_tgt(tgt), m_id(id) { }
public:
//! Returns the index of the edge.
int index() const { return m_id; }
//! Returns the source node of the edge.
node source() const { return m_src; }
//! Returns the target node of the edge.
node target() const { return m_tgt; }
//! Returns the corresponding adjacancy entry at source node.
adjEntry adjSource() const { return m_adjSrc; }
//! Returns the corresponding adjacancy entry at target node.
adjEntry adjTarget() const { return m_adjTgt; }
//! Returns the adjacent node different from \a v.
node opposite(node v) const { return (v == m_src) ? m_tgt : m_src; }
// Returns true iff the edge is a self-loop (source node = target node).
bool isSelfLoop() const { return m_src == m_tgt; }
//! Returns the successor in the list of all edges.
edge succ() const { return (edge)m_next; }
//! Returns the predecessor in the list of all edges.
edge pred() const { return (edge)m_prev; }
#ifdef OGDF_DEBUG
//! Returns the graph containing this node (debug only).
const Graph *graphOf() const { return m_src->graphOf(); }
#endif
//! Returns true iff \a v is incident to the edge.
bool isIncident(node v) const { return v == m_src || v == m_tgt; }
//! Returns the common node of the edge and \a e. Returns NULL if the two edges are not adjacent.
node commonNode(edge e) const { return (m_src==e->m_src || m_src==e->m_tgt) ? m_src : ((m_tgt==e->m_src || m_tgt==e->m_tgt) ? m_tgt: 0); }
OGDF_NEW_DELETE
}; // class EdgeElement
#ifdef OGDF_DEBUG
inline const Graph *AdjElement::graphOf() const {
return m_node->graphOf();
}
#endif
template<>inline bool doDestruction(const node *) { return false; }
template<>inline bool doDestruction(const edge *) { return false; }
template<>inline bool doDestruction(const adjEntry *) { return false; }
class NodeArrayBase;
class EdgeArrayBase;
class AdjEntryArrayBase;
template class NodeArray;
template class EdgeArray;
template class AdjEntryArray;
class OGDF_EXPORT GraphObserver;
//---------------------------------------------------------
// iteration macros
//---------------------------------------------------------
//! Iteration over all nodes \a v of graph \a G.
#define forall_nodes(v,G) for((v)=(G).firstNode(); (v); (v)=(v)->succ())
//! Iteration over all nodes \a v of graph \a G in reverse order.
#define forall_rev_nodes(v,G) for((v)=(G).lastNode(); (v); (v)=(v)->pred())
//! Iteration over all edges \a e of graph \a G.
#define forall_edges(e,G) for((e)=(G).firstEdge(); (e); (e)=(e)->succ())
//! Iteration over all edges \a e of graph \a G in reverse order.
#define forall_rev_edges(e,G) for((e)=(G).lastEdge(); (e); (e)=(e)->pred())
//! Iteration over all adjacency list entries \a adj of node \a v.
#define forall_adj(adj,v) for((adj)=(v)->firstAdj(); (adj); (adj)=(adj)->succ())
//! Iteration over all adjacency list entries \a adj of node \a v in reverse order.
#define forall_rev_adj(adj,v) for((adj)=(v)->lastAdj(); (adj); (adj)=(adj)->pred())
//! Iteration over all adjacent edges \a e of node \a v.
#define forall_adj_edges(e,v)\
for(ogdf::adjEntry ogdf_loop_var=(v)->firstAdj();\
ogdf::test_forall_adj_edges(ogdf_loop_var,(e));\
ogdf_loop_var=ogdf_loop_var->succ())
//! Data type for general directed graphs (adjacency list representation).
/**
* Iteration
* Besides the usage of iteration macros defined in Graph_d.h, the following
* code is recommended for further iteration tasks.
*
* - Iteration over all outgoing edges \a e of node \a v:
* \code
* forall_adj_edges(e,v)
* if(e->source() != v) continue;
* \endcode
*
*
- Iteration over all ingoing edges \a e of node \a v:
* \code
* forall_adj_edges(e,v)
* if(e->target() != v) continue;
* \endcode
*
*
- Iteration over all nodes \a x reachable by an outgoing edge \a e
* of node \a v (without self-loops):
* \code
* forall_adj_edges(e,v)
* if ((x = e->target()) == v) continue;
* \endcode
*
*
- Iteration over all nodes \a x reachable by an outgoing edge \a e
* of node \a v (with self-loops):
* \code
* forall_adj_edges(e,v) {
* if (e->source() != v) continue;
* x = e->target();
* }
* \endcode
*
*
- Iteration over all nodes \a x reachable by an ingoing edge \a e
* of node \a v (without self-loops):
* \code
* forall_adj_edges(e,v)
* if ((x = e->source()) == v) continue;
* \endcode
*
*
- Iteration over all nodes \a x reachable by an ingoing edge \a e
* of node \a v (with self-loops):
* \code
* forall_adj_edges(e,v) {
* if (e->target() != v) continue;
* x = e->source();
* }
* \endcode
*
*/
class OGDF_EXPORT Graph
{
GraphList m_nodes; //!< The list of all nodes.
GraphList m_edges; //!< The list of all edges.
int m_nNodes; //!< The number of nodes in the graph.
int m_nEdges; //!< The number of edges in the graph.
int m_nodeIdCount; //!< The Index that will be assigned to the next created node.
int m_edgeIdCount; //!< The Index that will be assigned to the next created edge.
int m_nodeArrayTableSize; //!< The current table size of node arrays associated with this graph.
int m_edgeArrayTableSize; //!< The current table size of edge arrays associated with this graph.
mutable ListPure m_regNodeArrays; //!< The registered node arrays.
mutable ListPure m_regEdgeArrays; //!< The registered edge arrays.
mutable ListPure m_regAdjArrays; //!< The registered adjEntry arrays.
mutable ListPure m_regStructures; //!< The registered graph structures.
GraphList m_hiddenEdges; //!< The list of hidden edges.
public:
//
// enumerations
//
//! The type of edges (only used in derived classes).
enum EdgeType {
association = 0,
generalization = 1,
dependency = 2
}; // should be more flexible, standard, dissect, expand
//! The type of nodes.
enum NodeType {
vertex,
dummy,
generalizationMerger,
generalizationExpander,
highDegreeExpander,
lowDegreeExpander,
associationClass
};
//! Constructs an empty graph.
Graph();
//! Constructs a graph that is a copy of \a G.
/**
* The constructor assures that the adjacency lists of nodes in the
* constructed graph are in the same order as the adjacency lists in \a G.
* This is in particular important when dealing with embedded graphs.
*
* @param G is the graph that will be copied.
*/
Graph(const Graph &G);
//! Destructor.
virtual ~Graph();
/**
* @name Access methods
*/
//@{
//! Returns true iff the graph is empty, i.e., contains no nodes.
bool empty() const { return m_nNodes == 0; }
//! Returns the number of nodes in the graph.
int numberOfNodes() const { return m_nNodes; }
//! Returns the number of edges in the graph.
int numberOfEdges() const { return m_nEdges; }
//! Returns the largest used node index.
int maxNodeIndex() const { return m_nodeIdCount-1; }
//! Returns the largest used edge index.
int maxEdgeIndex() const { return m_edgeIdCount-1; }
//! Returns the largest used adjEntry index.
int maxAdjEntryIndex() const { return (m_edgeIdCount<<1)-1; }
//! Returns the table size of node arrays associated with this graph.
int nodeArrayTableSize() const { return m_nodeArrayTableSize; }
//! Returns the table size of edge arrays associated with this graph.
int edgeArrayTableSize() const { return m_edgeArrayTableSize; }
//! Returns the table size of adjEntry arrays associated with this graph.
int adjEntryArrayTableSize() const { return m_edgeArrayTableSize << 1; }
//! Returns the first node in the list of all nodes.
node firstNode() const { return m_nodes.begin (); }
//! Returns the last node in the list of all nodes.
node lastNode () const { return m_nodes.rbegin(); }
//! Returns the first edge in the list of all edges.
edge firstEdge() const { return m_edges.begin (); }
//! Returns the last edge in the list of all edges.
edge lastEdge () const { return m_edges.rbegin(); }
//! Returns a randomly chosen node.
node chooseNode() const;
//! Returns a randomly chosen edge.
edge chooseEdge() const;
//! Returns a list with all nodes of the graph.
/**
* @tparam NODELIST is the type of node list, which is returned.
* @param nodes is assigned the list of all nodes.
*/
template
void allNodes(NODELIST &nodes) const {
nodes.clear();
for (node v = m_nodes.begin(); v; v = v->succ())
nodes.pushBack(v);
}
//! Returns a list with all edges of the graph.
/**
* @tparam EDGELIST is the type of edge list, which is returned.
* @param edges is assigned the list of all edges.
*/
template
void allEdges(EDGELIST &edges) const {
edges.clear();
for (edge e = m_edges.begin(); e; e = e->succ())
edges.pushBack(e);
}
//! Returns a list with all edges adjacent to node \a v.
/**
* @tparam EDGELIST is the type of edge list, which is returned.
* @param v is the node whose incident edges are queried.
* @param edges is assigned the list of all edges incident to \a v
* (including incoming and outcoming edges).
*/
template
void adjEdges(node v, EDGELIST &edges) const {
edges.clear();
edge e;
forall_adj_edges(e,v)
edges.pushBack(e);
}
//! Returns a list with all entries in the adjacency list of node \a v.
/**
* @tparam ADJLIST is the type of adjacency entry list, which is returned.
* @param v is the node whose adjacency entries are queried.
* @param entries is assigned the list of all adjacency entries in the adjacency list of \a v.
*/
template
void adjEntries(node v, ADJLIST &entries) const {
entries.clear();
adjEntry adj;
forall_adj(adj,v)
entries.pushBack(adj);
}
//! Returns a list with all incoming edges of node \a v.
/**
* @tparam EDGELIST is the type of edge list, which is returned.
* @param v is the node whose incident edges are queried.
* @param edges is assigned the list of all incoming edges incident to \a v.
*/
template
void inEdges(node v, EDGELIST &edges) const {
edges.clear();
edge e;
forall_adj_edges(e,v)
if (e->target() == v) edges.pushBack(e);
}
//! Returns a list with all outgoing edges of node \a v.
/**
* @tparam EDGELIST is the type of edge list, which is returned.
* @param v is the node whose incident edges are queried.
* @param edges is assigned the list of all outgoing edges incident to \a v.
*/
template
void outEdges(node v, EDGELIST &edges) const {
edges.clear();
edge e;
forall_adj_edges(e,v)
if (e->source() == v) edges.pushBack(e);
}
//@}
/**
* @name Creation of new nodes and edges
*/
//@{
//! Creates a new node and returns it.
node newNode();
//! Creates a new node with predefined index and returns it.
/**
* \pre \a index is currently not the index of any other node in the graph.
*
* \attention Passing a node index that is already in use results in an inconsistent
* data structure. Only use this method if you know what you're doing!
*
* @param index is the index that will be assigned to the newly created node.
* @return the newly created node.
*/
node newNode(int index);
//! Creates a new edge (\a v,\a w) and returns it.
/**
* @param v is the source node of the newly created edge.
* @param w is the target node of the newly created edge.
* @return the newly created edge.
*/
edge newEdge(node v, node w);
//! Creates a new edge (\a v,\a w) with predefined index and returns it.
/**
* \pre \a index is currently not the index of any other edge in the graph.
*
* \attention Passing an edge index that is already in use results in an inconsistent
* data structure. Only use this method if you know what you're doing!
*
* @param v is the source node of the newly created edge.
* @param w is the target node of the newly created edge.
* @param index is the index that will be assigned to the newly created edge.
* @return the newly created edge.
*/
edge newEdge(node v, node w, int index);
//! Creates a new edge at predefined positions in the adjacency lists.
/**
* Let \a v be the node whose adjacency list contains \a adjSrc,
* and \a w the node whose adjacency list contains \a adjTgt. Then,
* the created edge is (\a v,\a w).
*
* @param adjSrc is the adjacency entry after which the new edge is inserted
* in the adjacency list of \a v.
* @param adjTgt is the adjacency entry after which the new edge is inserted
* in the adjacency list of \a w.
* @param dir specifies if the edge is inserted before or after the given
* adjacency entries.
* @return the newly created edge.
*/
edge newEdge(adjEntry adjSrc, adjEntry adjTgt, Direction dir = ogdf::after);
//! Creates a new edge at predefined positions in the adjacency lists.
/**
* Let \a w be the node whose adjacency list contains \a adjTgt. Then,
* the created edge is (\a v,\a w).
*
* @param v is the source node of the new edge; the edge is added at the end
* of the adjacency list of \a v.
* @param adjTgt is the adjacency entry after which the new edge is inserted
* in the adjacency list of \a w.
* @return the newly created edge.
*/
edge newEdge(node v, adjEntry adjTgt);
//! Creates a new edge at predefined positions in the adjacency lists.
/**
* Let \a v be the node whose adjacency list contains \a adjSrc. Then,
* the created edge is (\a v,\a w).
*
* @param adjSrc is the adjacency entry after which the new edge is inserted
* in the adjacency list of \a v.
* @param w is the source node of the new edge; the edge is added at the end
* of the adjacency list of \a w.
* @return the newly created edge.
*/
edge newEdge(adjEntry adjSrc, node w);
//@}
/**
* @name Removing nodes and edges
*/
//@{
//! Removes node \a v and all incident edges from the graph.
/**
* @param v is the node that will be deleted.
*/
void delNode(node v);
//! Removes edge \a e from the graph.
/**
* @param e is the egde that will be deleted.
*/
void delEdge(edge e);
//! Removes all nodes and all edges from the graph.
void clear();
//@}
/**
* @name Hiding edges
* These methods are used for temporarily hiding edges. Edges are removed from the
* list of all edges and their corresponding adfjacency entries from the repsective
* adjacency lists, but the edge objects themselves are not destroyed; hiddenedges
* can later be reactivated with restoreEdge().
*/
//@{
//! Hides the edge \a e.
/**
* The edge \a e is removed from the list of all edges and adjacency lists of nodes, but
* not deleted; \a e can be restored by calling restoreEdge(e).
*
* \attention If an edge is hidden, its source and target node may not be deleted!
*
* @param e is the edge that will be hidden.
*/
void hideEdge(edge e);
//! Restores a hidden edge \a e.
/**
* \pre \a e is currently hidden and its source and target have not been removed!
*
* @param e is the hidden edge that will be restored.
*/
void restoreEdge(edge e);
//! Restores all hidden edges.
void restoreAllEdges();
/**
* @name Advanced modification methods
*/
//@{
//! Splits edge \a e into two edges introducing a new node.
/**
* Let \a e=(\a v,\a w). Then, the resulting two edges are \a e=(\a v,\a u)
* and \a e'=(\a u,\a w), where \a u is a new node.
*
* \note The edge \a e is modified by this operation.
*
* @param e is the edge to be split.
* @return The edge \a e'.
*/
virtual edge split(edge e);
//! Undoes a split operation.
/**
* Removes node \a u by joining the two edges adjacent to \a u. The
* outgoing edge of \a u is removed and the incoming edge \a e is reused
*
* \pre \a u has exactly one incoming and one outgoing edge, and
* none of them is a self-loop.
*
* @param u is the node to be unsplit.
* @return The edge \a e.
*/
void unsplit(node u);
//! Undoes a split operation.
/**
* For two edges \a eIn = (\a x,\a u) and \a eOut = (\a u,\a y), removes
* node \a u by joining \a eIn and \a eOut. Edge \a eOut is removed and
* \a eIn is reused.
*
* \pre \a eIn and \a eOut are the only edges incident with \a u and
* none of them is a self-loop.
*
* @param eIn is the (only) incoming edge of \a u.
* @param eOut is the (only) outgoing edge of \a u.
*/
virtual void unsplit(edge eIn, edge eOut);
//! Splits a node while preserving the order of adjacency entries.
/**
* This method splits a node \a v into two nodes \a vl and \a vr. Node
* \a vl receives all adjacent edges of \a v from \a adjStartLeft until
* the edge preceding \a adjStartRight, and \a vr the remaining nodes
* (thus \a adjStartRight is the first edge that goes to \a vr). The
* order of adjacency entries is preserved. Additionally, a new edge
* (\a vl,\a vr) is created, such that this edge is inserted before
* \a adjStartLeft and \a adjStartRight in the the adjacency lists of
* \a vl and \a vr.
*
* Node \a v is modified to become node \a vl, and node \a vr is returned.
* This method is useful when modifying combinatorial embeddings.
*
* @param adjStartLeft is the first entry that goes to the left node.
* @param adjStartRight is the first entry that goes to the right node.
* @return the newly created node.
*/
node splitNode(adjEntry adjStartLeft, adjEntry adjStartRight);
//! Contracts edge \a e while preserving the order of adjacency entries.
/**
* @param e is the edge to be contracted.
* @return the endpoint of \a e to which all edges have been moved.
*/
node contract(edge e);
//! Moves edge \a e to a different adjacency list.
/**
* The source adjacency entry of \a e is moved to the adjacency list containing
* \a adjSrc and is inserted before or after \a adjSrc, and its target adjacency entry
* to the adjacency list containing \a adjTgt and is inserted before or after
* \a adjTgt; e is afterwards an edge from owner(\a adjSrc) to owner(\a adjTgt).
*
* @param e is the edge to be moved.
* @param adjSrc is the adjaceny entry before or after which the source adjacency entry
* of \a e will be inserted.
* @param dirSrc specifies if the source adjacency entry of \a e will be inserted before or after \a adjSrc.
* @param adjTgt is the adjaceny entry before or after which the target adjacency entry
* of \a e will be inserted.
* @param dirTgt specifies if the target adjacency entry of \a e will be inserted before or after \a adjTgt.
*/
void move(edge e, adjEntry adjSrc, Direction dirSrc,
adjEntry adjTgt, Direction dirTgt);
//! Moves the target node of edge \a e to node \a w.
/**
* If \a e=(\a v,\a u) before, then \a e=(\a v,\a w) afterwards.
*
* @param e is the edge whose target node is moved.
* @param w is the new target node of \a e.
*/
void moveTarget(edge e, node w);
//! Moves the target node of edge \a e to a specific position in an adjacency list.
/**
* Let \a w be the node containing \a adjTgt. If \a e=(\a v,\a u) before, then \a e=(\a v,\a w) afterwards.
* Inserts the adjacency entry before or after \a adjTgt according to \a dir.
*
* @param e is the edge whose target node is moved.
* @param adjTgt is the adjacency entry before or after which the target adjacency entry of \a e is inserted.
* @param dir specifies if the target adjacency entry of \a e is inserted before or after \a adjTgt.
*/
void moveTarget(edge e, adjEntry adjTgt, Direction dir);
//! Moves the source node of edge \a e to node \a w.
/**
* If \a e=(\a v,\a u) before, then \a e=(\a w,\a u) afterwards.
*
* @param e is the edge whose source node is moved.
* @param w is the new source node of \a e.
*/
void moveSource(edge e, node w);
//! Moves the source node of edge \a e to a specific position in an adjacency list.
/**
* Let \a w be the node containing \a adjSrc. If \a e=(\a v,\a u) before, then \a e=(\a w,\a u) afterwards.
* Inserts the adjacency entry before or after \a adjSrc according to \a dir.
*
* @param e is the edge whose source node is moved.
* @param adjSrc is the adjacency entry before or after which the source adjacency entry of \a e is inserted.
* @param dir specifies if the source adjacency entry of \a e is inserted before or after \a adjSrc.
*/
void moveSource(edge e, adjEntry adjSrc, Direction dir);
//! Searches and returns an edge connecting nodes \a v and \a w.
/**
* @param v is the source node of the edge to be searched.
* @param w is the target node of the edge to be searched.
* @return an edge (\ v,\a w) if such an edge exists, 0 otherwise.
*/
edge searchEdge (node v, node w) const;
//! Reverses the edge \a e, i.e., exchanges source and target node.
/**
* @param e is the edge to be reveresed.
*/
void reverseEdge(edge e);
//! Reverses all edges in the graph.
void reverseAllEdges();
//! Collapses all nodes in the list \a nodes to the first node in the list.
/**
* Parallel edges are removed.
*
* @tparam NODELIST is the type of input node list.
* @param nodes is the list of nodes that will be collapsed. This list will be empty after the call.
*/
template
void collaps(NODELIST &nodes){
node v = nodes.popFrontRet();
while (!nodes.empty())
{
node w = nodes.popFrontRet();
adjEntry adj = w->firstAdj();
while (adj !=0)
{
adjEntry succ = adj->succ();
edge e = adj->theEdge();
if (e->source() == v || e->target() == v)
delEdge(e);
else if (e->source() == w)
moveSource(e,v);
else
moveTarget(e,v);
adj = succ;
}
delNode(w);
}
}
//! Sorts the adjacency list of node \a v according to \a newOrder.
/**
* \pre \a newOrder contains exactly the adjacency entries of \a v!
*
* @tparam ADJ_ENTRY_LIST is the type of the input adjacency entry list.
* @param v is the node whose adjacency list will be sorted.
* @param newOrder is the list of adjacency entries of \a v in the new order.
*/
template
void sort(node v, const ADJ_ENTRY_LIST &newOrder) {
#ifdef OGDF_DEBUG
typename ADJ_ENTRY_LIST::const_iterator it;
for(it = newOrder.begin(); it.valid() ; ++it) {
OGDF_ASSERT((*it)->theNode() == v);
}
#endif
v->m_adjEdges.sort(newOrder);
}
//! Reverses the adjacency list of \a v.
/**
* @param v is the node whose adjacency list will be reveresed.
*/
void reverseAdjEdges(node v) {
v->m_adjEdges.reverse();
}
//! Moves adjacency entry \a adjMove before or after \a adjPos.
/**
* \pre \a adjMove and adjAfter are distinct entries in the same adjacency list.
*
* @param adjMove is an entry in the adjacency list of a node in this graph.
* @param adjPos is an entry in the same adjacency list as \a adjMove.
* @param dir specifies if \a adjMove is moved before or after \a adjPos.
*/
void moveAdj(adjEntry adjMove, Direction dir, adjEntry adjPos) {
OGDF_ASSERT(adjMove->graphOf() == this && adjPos->graphOf() == this);
OGDF_ASSERT(adjMove != 0 && adjPos != 0);
GraphList &adjList = adjMove->m_node->m_adjEdges;
adjList.move(adjMove, adjList, adjPos, dir);
}
//! Moves adjacency entry \a adjMove after \a adjAfter.
/**
* \pre \a adjMove and \a adjAfter are distinct entries in the same adjacency list.
*
* @param adjMove is an entry in the adjacency list of a node in this graph.
* @param adjAfter is an entry in the same adjacency list as \a adjMove.
*/
void moveAdjAfter(adjEntry adjMove, adjEntry adjAfter) {
OGDF_ASSERT(adjMove->graphOf() == this && adjAfter->graphOf() == this);
OGDF_ASSERT(adjMove != 0 && adjAfter != 0);
adjMove->m_node->m_adjEdges.moveAfter(adjMove,adjAfter);
}
//! Moves adjacency entry \a adjMove before \a adjBefore.
/**
* \pre \a adjMove and \a adjBefore are distinct entries in the same adjacency list.
*
* @param adjMove is an entry in the adjacency list of a node in this graph.
* @param adjBefore is an entry in the same adjacency list as \a adjMove.
*/
void moveAdjBefore(adjEntry adjMove, adjEntry adjBefore) {
OGDF_ASSERT(adjMove->graphOf() == this && adjBefore->graphOf() == this);
OGDF_ASSERT(adjMove != 0 && adjBefore != 0);
adjMove->m_node->m_adjEdges.moveBefore(adjMove,adjBefore);
}
//! Reverses all adjacency lists.
void reverseAdjEdges();
//! Exchanges two entries in an adjacency list.
/**
* \pre \a adj1 and \a adj2 must be belong to the same adjacency list.
*
* @param adj1 the first adjacency entry to be swapped.
* @param adj2 the secomd adjacency entry to be swapped.
*/
void swapAdjEdges(adjEntry adj1, adjEntry adj2) {
OGDF_ASSERT(adj1->theNode() == adj2->theNode());
OGDF_ASSERT(adj1->graphOf() == this);
adj1->theNode()->m_adjEdges.swap(adj1,adj2);
}
//@}
/**
* @name Input and output
*/
//@{
//! Reads a graph in GML format from file \a fileName.
/**
* @param fileName is the name of the input file.
* @return true if successful, false otherwise.
*/
bool readGML(const char *fileName);
//! Reads a graph in GML format from input stream \a is.
/**
* @param is is the input file stream.
* @return true if successful, false otherwise.
*/
bool readGML(istream &is);
//! Writes the graph in GML format to file \a fileName.
/**
* @param fileName is the name of the output file.
*/
void writeGML(const char *fileName) const;
//! Writes the graph in GML format to output stream \a os.
/**
* @param os is the output file stream.
* @return true if successful, false otherwise.
*/
void writeGML(ostream &os) const;
//! Reads a graph in LEDA format from file \a fileName.
/**
* @param fileName is the name of the input file.
* @return true if successful, false otherwise.
*/
bool readLEDAGraph(const char *fileName);
//! Read a graph in LEDA format from input stream \a is.
/**
* @param is is the input file stream.
* @return true if successful, false otherwise.
*/
bool readLEDAGraph(istream &is);
//@}
/**
* @name Miscellaneous
*/
//@{
//! Returns the genus of the graph's embedding.
/**
* The genus of a graph is defined as follows. Let \f$G\f$ be a graph
* with \f$m\f$ edges, \f$n\f$ nodes, \f$c\f$ connected components, \f$nz\f$
* isolated vertices, and \f$fc\f$ face cycles. Then,
* \f[
* genus(G) = (m/2 + 2c - n -nz -fc)/2
* \f]
*
* @return the genus of the graph's current embedding; if this is 0, then the graph is planarly embedded.
*/
int genus() const;
//! Returns true iff the graph represents a combinatorial embedding.
/**
* @return true if the current embedding (given by the adjacency lists) represents a combinatorial embedding, false otherwise.
*/
bool representsCombEmbedding() const {
return (genus() == 0);
}
//! Checks the consistency of the data structure.
/**
* \remark This method is meant for debugging purposes only.
*
* @return true if everything is ok, false if the data structure is inconsistent.
*/
bool consistencyCheck() const;
//@}
/**
* @name Registering arrays and observers
* These methods are used by various graph array types like NodeArray or EdgeArray.
* There should be no need to use them directly in user code.
*/
//@{
//! Registers a node array.
/**
* \remark This method is automatically called by node arrays; it should not be called manually.
*
* @param pNodeArray is a pointer to the node array's base; this node array must be associated with this graph.
* @return an iterator pointing to the entry for the registered node array in the list of registered node arrays.
* This iterator is required for unregistering the node array again.
*/
ListIterator registerArray(NodeArrayBase *pNodeArray) const;
//! Registers an edge array.
/**
* \remark This method is automatically called by edge arrays; it should not be called manually.
*
* @param pEdgeArray is a pointer to the edge array's base; this edge array must be associated with this graph.
* @return an iterator pointing to the entry for the registered edge array in the list of registered edge arrays.
* This iterator is required for unregistering the edge array again.
*/
ListIterator registerArray(EdgeArrayBase *pEdgeArray) const;
//! Registers an adjEntry array.
/**
* \remark This method is automatically called by adjacency entry arrays; it should not be called manually.
*
* @param pAdjArray is a pointer to the adjacency entry array's base; this adjacency entry array must be
* associated with this graph.
* @return an iterator pointing to the entry for the registered adjacency entry array in the list of registered
* adjacency entry arrays. This iterator is required for unregistering the adjacency entry array again.
*/
ListIterator registerArray(AdjEntryArrayBase *pAdjArray) const;
//! Registers a graph observer (e.g. a ClusterGraph).
/**
* @param pStructure is a pointer to the graph observer that shall be registered; this graph observer must be
* associated with this graph.
* @return an iterator pointing to the entry for the registered graph observer in the list of registered
* graph observers. This iterator is required for unregistering the graph observer again.
*/
ListIterator registerStructure(GraphObserver *pStructure) const;
//! Unregisters a node array.
/**
* @param it is an iterator pointing to the entry in the list of registered node arrays for the node array to
* be unregistered.
*/
void unregisterArray(ListIterator it) const;
//! Unregisters an edge array.
/**
* @param it is an iterator pointing to the entry in the list of registered edge arrays for the edge array to
* be unregistered.
*/
void unregisterArray(ListIterator it) const;
//! unregisters an adjEntry array.
/**
* @param it is an iterator pointing to the entry in the list of registered adjacency entry arrays for the
* adjacency entry array to be unregistered.
*/
void unregisterArray(ListIterator it) const;
//! Unregisters a graph observer.
/**
* @param it is an iterator pointing to the entry in the list of registered graph observers for the graph
* observer to be unregistered.
*/
void unregisterStructure(ListIterator it) const;
//! Resets the edge id count to \a maxId.
/**
* The next edge will get edge id \a maxId+1. Use this function with caution!
* It is provided as an efficient way to reduce the edge id count. The Graph class
* increments the edge id count whenever an edge is created; free edge ids resulting
* from removing edges are not reused (there is not something like a freelist).
*
* This function is , e.g., useful, when a lot of edges has been added and
* all these edges are removed again (without creating other new edges
* meanwile). Then, it is safe to reduce the edge id count to the value it had
* before, cf. the following code snippet:
* \code
* int oldIdCount = G.maxEdgeIndex();
* Create some edges
* ...
* Remove all these edges again
* G.resetEdgeIdCount(oldIdCount);
* \endcode
*
* Reducing the edge id count will reduce the memory consumption of edge arrays
* associated with the graph.
*
* \pre -1 \f$\leq\f$ \a maxId \f$\leq\f$ maximal edge id in the graph.
*
* @param maxId is an upper bound of the edge ids in the graph.
*/
void resetEdgeIdCount(int maxId);
//@}
/**
* @name Operators
*/
//@{
//! Assignment operator.
/**
* The assignment operature assures that the adjacency lists of nodes in the
* constructed graph are in the same order as the adjacency lists in \a G.
* This is in particular important when dealing with embedded graphs.
*
* @param G is the graph to be copied.
* @return this graph.
*/
Graph &operator=(const Graph &G);
OGDF_MALLOC_NEW_DELETE
//@}
public:
//! Returns the smallest power of 2 which is >= 2^\a start and > \a idCount.
static int nextPower2(int start, int idCount);
protected:
void construct(const Graph &G, NodeArray &mapNode,
EdgeArray &mapEdge);
void assign(const Graph &G, NodeArray &mapNode,
EdgeArray &mapEdge);
//! Constructs a copy of the subgraph of \a G induced by \a nodes.
/**
* This method preserves the order in the adjacency lists, i.e., if
* \a G is embedded, its embedding induces the embedding of the copy.
*/
void constructInitByNodes(
const Graph &G,
const List &nodes,
NodeArray &mapNode,
EdgeArray &mapEdge);
void constructInitByActiveNodes(
const List &nodes,
const NodeArray &activeNodes,
NodeArray &mapNode,
EdgeArray &mapEdge);
private:
void copy(const Graph &G, NodeArray &mapNode,
EdgeArray &mapEdge);
void copy(const Graph &G);
edge createEdgeElement(node v, node w, adjEntry adjSrc, adjEntry adjTgt);
node pureNewNode();
// moves adjacency entry to node w
void moveAdj(adjEntry adj, node w);
void reinitArrays();
void reinitStructures();
void resetAdjEntryIndex(int newIndex, int oldIndex);
bool readToEndOfLine(istream &is);
}; // class Graph
//! Bucket function using the index of an edge's source node as bucket.
class OGDF_EXPORT BucketSourceIndex : public BucketFunc {
public:
//! Returns source index of \a e.
int getBucket(const edge &e) { return e->source()->index(); }
};
//! Bucket function using the index of an edge's target node as bucket.
class OGDF_EXPORT BucketTargetIndex : public BucketFunc {
public:
//! Returns target index of \a e.
int getBucket(const edge &e) { return e->target()->index(); }
};
} //namespace
#endif