Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

SpannerBermanDisconnected.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/Graph.h>
36 #include <ogdf/basic/GraphCopy.h>
37 #include <ogdf/basic/GraphList.h>
41 
42 #include <algorithm>
43 #include <cstdint>
44 #include <string>
45 
46 namespace ogdf {
47 
55 template<typename TWeight>
56 class SpannerBermanDisconnected : public SpannerModule<TWeight> {
57 public:
59  virtual bool preconditionsOk(const GraphAttributes& GA, double stretch,
60  std::string& error) override {
61  if (!isSimple(GA.constGraph())) {
62  error = "The graph is not simple";
63  return false;
64  }
65  if (stretch < 1.0) {
66  error = "The stretch must be >= 1.0";
67  return false;
68  }
69  return true;
70  }
71 
72 private:
74  virtual typename SpannerModule<TWeight>::ReturnType execute() override {
75  const Graph& G = m_GA->constGraph();
76 
77  if (G.numberOfNodes() == 0) {
79  }
80 
81  Graph::CCsInfo ccsInfo(G);
82  SpannerBerman<TWeight> spannerBerman;
83 
84  for (int c = 0; c < ccsInfo.numberOfCCs(); c++) {
86 
87  GraphCopySimple GC;
88  GC.setOriginalGraph(G);
89  NodeArray<node> nodeMap(G, nullptr);
90  EdgeArray<edge> edgeMap(G, nullptr);
91  GC.insert(ccsInfo, c, nodeMap, edgeMap);
92 
93  GraphCopySimple spanner(GC);
94  EdgeArray<bool> inSpanner;
95  GraphAttributes GCA(GC, 0);
96  GCA.directed() = m_GA->directed();
99  for (edge e : GC.edges) {
100  GCA.intWeight(e) = m_GA->intWeight(GC.original(e));
101  }
102  }
105  for (edge e : GC.edges) {
106  GCA.doubleWeight(e) = m_GA->doubleWeight(GC.original(e));
107  }
108  }
109 
110  if (isTimelimitEnabled()) {
111  int64_t timeLeft = max(getTimeLeft(), static_cast<int64_t>(0));
112  spannerBerman.setTimelimit(timeLeft);
113  }
115  spannerBerman.call(GCA, m_stretch, spanner, inSpanner);
117  return r;
118  }
119 
120  // copy used edges to m_spanner and m_inSpanner
121  for (edge e : spanner.edges) {
122  edge eOrig = GC.original(spanner.original(e));
123  (*m_inSpanner)[eOrig] = true;
124  m_spanner->newEdge(eOrig);
125  }
126  }
127 
129  }
130 
139 };
140 
141 }
ogdf::GraphAttributes::edgeIntWeight
static const long edgeIntWeight
Corresponds to edge attribute intWeight(edge).
Definition: GraphAttributes.h:125
ogdf
The namespace for all OGDF objects.
Definition: multilevelmixer.cpp:39
ogdf::GraphAttributes
Stores additional attributes of a graph (like layout information).
Definition: GraphAttributes.h:72
GraphAttributes.h
Declaration of class GraphAttributes which extends a Graph by additional attributes.
ogdf::SpannerModule::isTimelimitEnabled
bool isTimelimitEnabled()
Definition: SpannerModule.h:167
Graph.h
Includes declaration of graph class.
SpannerBerman.h
Implementation of an k-spanner approximation algorithm from Berman et al.
ogdf::Graph::CCsInfo
Info structure for maintaining connected components.
Definition: Graph_d.h:1908
ogdf::SpannerModule::m_spanner
GraphCopySimple * m_spanner
Definition: SpannerModule.h:136
ogdf::SpannerModule::assertTimeLeft
void assertTimeLeft()
Assert, that time is left.
Definition: SpannerModule.h:178
ogdf::GraphCopySimple
Copies of graphs with mapping between nodes and edges.
Definition: GraphCopy.h:261
ogdf::SpannerBermanDisconnected
Wrapper around SpannerBerman: For each component of the graph, the algorithm will be called.
Definition: SpannerBermanDisconnected.h:56
ogdf::GraphCopySimple::setOriginalGraph
void setOriginalGraph(const Graph *G) override
Re-initializes the copy using G (which might be null), but does not create any nodes or edges.
ogdf::GraphAttributes::directed
bool directed() const
Returns if the graph is directed.
Definition: GraphAttributes.h:232
ogdf::GraphAttributes::constGraph
const Graph & constGraph() const
Returns a reference to the associated graph.
Definition: GraphAttributes.h:223
SpannerModule.h
Basic module for spanner algorithms.
ogdf::SpannerModule::setTimelimit
void setTimelimit(int64_t milliseconds)
Sets the timelimit for the algorithm in milliseconds.
Definition: SpannerModule.h:126
r
int r[]
Definition: hierarchical-ranking.cpp:13
ogdf::SpannerModule::getTimeLeft
int64_t getTimeLeft()
Definition: SpannerModule.h:172
GraphList.h
Decralation of GraphElement and GraphList classes.
ogdf::SpannerBermanDisconnected::execute
virtual SpannerModule< TWeight >::ReturnType execute() override
Executes the core algorithm.
Definition: SpannerBermanDisconnected.h:74
GraphCopy.h
Declaration of graph copy classes.
ogdf::SpannerModule::m_stretch
double m_stretch
Definition: SpannerModule.h:135
ogdf::internal::GraphRegisteredArray
RegisteredArray for nodes, edges and adjEntries of a graph.
Definition: Graph_d.h:658
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:869
ogdf::SpannerModule
Interface for spanner algorithms.
Definition: SpannerModule.h:63
ogdf::GraphAttributes::addAttributes
void addAttributes(long attr)
Enables attributes specified by attr and allocates required memory.
ogdf::SpannerBerman
Approximation algorithm for calculating spanners.
Definition: SpannerBerman.h:89
ogdf::Graph::insert
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.
Definition: InducedSubgraph.h:102
ogdf::Graph::edges
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition: Graph_d.h:935
ogdf::SpannerModule::m_GA
const GraphAttributes * m_GA
Definition: SpannerModule.h:134
ogdf::SpannerModule::call
virtual ReturnType call(const GraphAttributes &GA, double stretch, GraphCopySimple &spanner, EdgeArray< bool > &inSpanner)
Executes the algorithm.
Definition: SpannerModule.h:92
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:363
ogdf::GraphAttributes::intWeight
int intWeight(edge e) const
Returns the (integer) weight of edge e.
Definition: GraphAttributes.h:774
ogdf::GraphAttributes::edgeDoubleWeight
static const long edgeDoubleWeight
Corresponds to edge attribute doubleWeight(edge).
Definition: GraphAttributes.h:128
ogdf::GraphAttributes::doubleWeight
double doubleWeight(edge e) const
Returns the (real number) weight of edge e.
Definition: GraphAttributes.h:792
ogdf::SpannerBermanDisconnected::preconditionsOk
virtual bool preconditionsOk(const GraphAttributes &GA, double stretch, std::string &error) override
Definition: SpannerBermanDisconnected.h:59
ogdf::Graph::CCsInfo::numberOfCCs
int numberOfCCs() const
Returns the number of connected components.
Definition: Graph_d.h:1928
ogdf::Module::ReturnType
ReturnType
The return type of a module.
Definition: Module.h:52
ogdf::GraphCopySimple::newEdge
edge newEdge(edge eOrig)
Creates a new edge in the graph copy with original edge eOrig.
Definition: GraphCopy.h:321
ogdf::isSimple
bool isSimple(const Graph &G)
Returns true iff G contains neither self-loops nor parallel edges.
Definition: simple_graph_alg.h:402
simple_graph_alg.h
Declaration of simple graph algorithms.
ogdf::GraphAttributes::has
bool has(long attr) const
Returns true iff all attributes in attr are available.
Definition: GraphAttributes.h:200
ogdf::GraphCopyBase::original
const Graph & original() const
Returns a reference to the original graph.
Definition: GraphCopy.h:105
ogdf::internal::EdgeArrayBase2
RegisteredArray for edges of a graph, specialized for EdgeArray<edge>.
Definition: Graph_d.h:716