|
Open Graph Drawing Framework |
v. 2023.09 (Elderberry)
|
|
|
Go to the documentation of this file.
55 template<
typename TWeight>
60 std::string& error)
override {
62 error =
"The graph is not simple";
66 error =
"The stretch must be >= 1.0";
77 if (G.numberOfNodes() == 0) {
91 GC.
insert(ccsInfo, c, nodeMap, edgeMap);
111 int64_t timeLeft = max(
getTimeLeft(),
static_cast<int64_t
>(0));
123 (*m_inSpanner)[eOrig] =
true;
static const long edgeIntWeight
Corresponds to edge attribute intWeight(edge).
The namespace for all OGDF objects.
Stores additional attributes of a graph (like layout information).
Declaration of class GraphAttributes which extends a Graph by additional attributes.
bool isTimelimitEnabled()
Includes declaration of graph class.
Implementation of an k-spanner approximation algorithm from Berman et al.
Info structure for maintaining connected components.
GraphCopySimple * m_spanner
void assertTimeLeft()
Assert, that time is left.
Copies of graphs with mapping between nodes and edges.
Wrapper around SpannerBerman: For each component of the graph, the algorithm will be called.
void setOriginalGraph(const Graph *G) override
Re-initializes the copy using G (which might be null), but does not create any nodes or edges.
bool directed() const
Returns if the graph is directed.
const Graph & constGraph() const
Returns a reference to the associated graph.
Basic module for spanner algorithms.
void setTimelimit(int64_t milliseconds)
Sets the timelimit for the algorithm in milliseconds.
Decralation of GraphElement and GraphList classes.
virtual SpannerModule< TWeight >::ReturnType execute() override
Executes the core algorithm.
Declaration of graph copy classes.
RegisteredArray for nodes, edges and adjEntries of a graph.
Data type for general directed graphs (adjacency list representation).
Interface for spanner algorithms.
void addAttributes(long attr)
Enables attributes specified by attr and allocates required memory.
Approximation algorithm for calculating spanners.
std::pair< int, int > insert(const NI &nodesBegin, const NI &nodesEnd, const EI &edgesBegin, const EI &edgesEnd, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap)
Inserts a copy of a given subgraph into this graph.
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
const GraphAttributes * m_GA
virtual ReturnType call(const GraphAttributes &GA, double stretch, GraphCopySimple &spanner, EdgeArray< bool > &inSpanner)
Executes the algorithm.
Class for the representation of edges.
int intWeight(edge e) const
Returns the (integer) weight of edge e.
static const long edgeDoubleWeight
Corresponds to edge attribute doubleWeight(edge).
double doubleWeight(edge e) const
Returns the (real number) weight of edge e.
virtual bool preconditionsOk(const GraphAttributes &GA, double stretch, std::string &error) override
int numberOfCCs() const
Returns the number of connected components.
ReturnType
The return type of a module.
edge newEdge(edge eOrig)
Creates a new edge in the graph copy with original edge eOrig.
bool isSimple(const Graph &G)
Returns true iff G contains neither self-loops nor parallel edges.
Declaration of simple graph algorithms.
bool has(long attr) const
Returns true iff all attributes in attr are available.
const Graph & original() const
Returns a reference to the original graph.
RegisteredArray for edges of a graph, specialized for EdgeArray<edge>.