BALL 1.5.0
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Protected Attributes | List of all members
BALL::GRAPH::UndoEliminateOperation< UndirectedGraph > Class Template Reference

#include <BALL/DATATYPE/GRAPH/graphAlgorithms.h>

Public Types

typedef boost::graph_traits< UndirectedGraph >::vertex_descriptor VertexType
 
typedef boost::graph_traits< UndirectedGraph >::edge_descriptor EdgeType
 
typedef boost::graph_traits< UndirectedGraph >::adjacency_iterator NeighbourIterator
 
typedef boost::property_traits< typenameboost::property_map< UndirectedGraph, boost::vertex_all_t >::type >::value_type VertexProperties
 
typedef boost::property_traits< typenameboost::property_map< UndirectedGraph, boost::edge_all_t >::type >::value_type EdgeProperties
 

Public Member Functions

 UndoEliminateOperation (UndirectedGraph &graph, VertexType const &a)
 
VertexTypegetEliminatedVertex ()
 
VertexType undo ()
 
std::vector< std::pair< int, int > > & getEdges ()
 
std::vector< EdgeProperties > & getEdgeProperties ()
 
std::vector< int > & getNeighbours ()
 

Protected Attributes

UndirectedGraph * graph
 
VertexType vertex
 
VertexProperties vertex_properties_
 
std::vector< std::pair< int, int > > edges_
 
std::vector< EdgePropertiesedge_properties_
 
std::vector< int > neighbours_
 
bool applied
 

Detailed Description

template<class UndirectedGraph>
class BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >

Elimination means: remove a vertex v from graph and build a clique with the neighbourhood of v. Sometimes it's usefull to reverse this operation. This class remembers the changes of an elimination and provide an undo-operation. It's important, that you can only undo an elimination, if the graph wasn't changed after the elimination operation. Currently, there is no check if this condition is fulfilled. Since undo may change pointers into the graph (depending on the underlying graph structure), the user has to hand a pointer to a map from old vertex pointers to new vertex pointers.

Definition at line 214 of file graphAlgorithms.h.

Member Typedef Documentation

◆ EdgeProperties

template<class UndirectedGraph >
typedef boost::property_traits<typenameboost::property_map<UndirectedGraph,boost::edge_all_t>::type>::value_type BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::EdgeProperties

Definition at line 224 of file graphAlgorithms.h.

◆ EdgeType

template<class UndirectedGraph >
typedef boost::graph_traits<UndirectedGraph>::edge_descriptor BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::EdgeType

Definition at line 218 of file graphAlgorithms.h.

◆ NeighbourIterator

template<class UndirectedGraph >
typedef boost::graph_traits<UndirectedGraph>::adjacency_iterator BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::NeighbourIterator

Definition at line 219 of file graphAlgorithms.h.

◆ VertexProperties

template<class UndirectedGraph >
typedef boost::property_traits<typenameboost::property_map<UndirectedGraph,boost::vertex_all_t>::type>::value_type BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::VertexProperties

Definition at line 222 of file graphAlgorithms.h.

◆ VertexType

template<class UndirectedGraph >
typedef boost::graph_traits<UndirectedGraph>::vertex_descriptor BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::VertexType

Definition at line 217 of file graphAlgorithms.h.

Constructor & Destructor Documentation

◆ UndoEliminateOperation()

template<class UndirectedGraph >
BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::UndoEliminateOperation ( UndirectedGraph &  graph,
VertexType const &  a 
)

Eliminate vertex a in undirectedGraph and remember the changes.

Definition at line 258 of file graphAlgorithms.h.

Member Function Documentation

◆ getEdgeProperties()

template<class UndirectedGraph >
std::vector< EdgeProperties > & BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::getEdgeProperties ( )
inline

Definition at line 244 of file graphAlgorithms.h.

◆ getEdges()

template<class UndirectedGraph >
std::vector< std::pair< int, int > > & BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::getEdges ( )
inline

Definition at line 243 of file graphAlgorithms.h.

◆ getEliminatedVertex()

template<class UndirectedGraph >
UndoEliminateOperation< UndirectedGraph >::VertexType & BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::getEliminatedVertex ( )

returns the eliminated vertex

Definition at line 270 of file graphAlgorithms.h.

◆ getNeighbours()

template<class UndirectedGraph >
std::vector< int > & BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::getNeighbours ( )
inline

Definition at line 245 of file graphAlgorithms.h.

◆ undo()

template<class UndirectedGraph >
UndoEliminateOperation< UndirectedGraph >::VertexType BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::undo ( )

reverse this operation. It's important that you can reverse this operation only if the graph is in the same state as immediately after the elimination. Furthermore you should call this method only one time! Currently there is no check if this conditions are fulfilled.

Definition at line 276 of file graphAlgorithms.h.

Member Data Documentation

◆ applied

template<class UndirectedGraph >
bool BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::applied
protected

Definition at line 254 of file graphAlgorithms.h.

◆ edge_properties_

template<class UndirectedGraph >
std::vector<EdgeProperties> BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::edge_properties_
protected

Definition at line 252 of file graphAlgorithms.h.

◆ edges_

template<class UndirectedGraph >
std::vector<std::pair<int, int> > BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::edges_
protected

Definition at line 251 of file graphAlgorithms.h.

◆ graph

template<class UndirectedGraph >
UndirectedGraph* BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::graph
protected

Definition at line 248 of file graphAlgorithms.h.

◆ neighbours_

template<class UndirectedGraph >
std::vector<int> BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::neighbours_
protected

Definition at line 253 of file graphAlgorithms.h.

◆ vertex

template<class UndirectedGraph >
VertexType BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::vertex
protected

Definition at line 249 of file graphAlgorithms.h.

◆ vertex_properties_

template<class UndirectedGraph >
VertexProperties BALL::GRAPH::UndoEliminateOperation< UndirectedGraph >::vertex_properties_
protected

Definition at line 250 of file graphAlgorithms.h.