Simplify.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>
#include <ogdf/cluster/sync_plan/SyncPlan.h>
 
#include <functional>
#include <iosfwd>
 
namespace ogdf {
class EdgeSet;
} // namespace ogdf
 
namespace ogdf::pc_tree {
class NodePCRotation;
} // namespace ogdf::pc_tree
 
namespace ogdf::sync_plan {
 
class SyncPlanComponents;
 
namespace internal {
 
struct SimplifyMapping {
    adjEntry u2_adj, u_adj, v2_adj;
    List<adjEntry> v_adj;
 
    explicit SimplifyMapping(adjEntry u2Adj = nullptr, adjEntry uAdj = nullptr,
            adjEntry vAdj = nullptr, adjEntry v2Adj = nullptr);
 
    friend std::ostream& operator<<(std::ostream& os, const SimplifyMapping& mapping);
};
 
struct FrozenSimplifyMapping {
    int u2_adj, u_adj, v2_adj;
    List<int> v_adj;
 
    explicit FrozenSimplifyMapping(int u2Adj = -1, int uAdj = -1, int vAdj = -1, int v2Adj = -1);
 
    friend std::ostream& operator<<(std::ostream& os, const FrozenSimplifyMapping& mapping);
};
 
class UndoSimplify : public SyncPlan::UndoOperation {
    int u2_idx, u_idx, v_idx, v2_idx;
    SList<FrozenSimplifyMapping> bij;
 
public:
    UndoSimplify(const List<SimplifyMapping>& in_bij, node u2, node u, node v, node v2 = nullptr);
 
    void undo(SyncPlan& pq) override;
 
    std::ostream& print(std::ostream& os) const override;
};
 
int findCycles(Graph& G, node u, const std::function<adjEntry(adjEntry)>& mapping,
        List<List<adjEntry>>& cycles, std::ostream& log);
 
adjEntry continueNodeDFS(Graph& G, adjEntry u_adj, node v, EdgeSet& visited,
        List<adjEntry>& dfs_stack);
 
adjEntry startNodeDFS(Graph& G, adjEntry u_adj, node v, EdgeSet& visited, List<adjEntry>& dfs_stack);
 
int exhaustiveNodeDFS(Graph& G, adjEntry u_adj, node v, EdgeSet& visited, List<adjEntry>& out);
 
#ifdef OGDF_DEBUG
 
bool compareWithExhaustiveNodeDFS(Graph& G, adjEntry u_adj, node v, const EdgeSet& visited,
        const List<adjEntry>& found);
 
void validatePartnerPCTree(const NodePCRotation* u_pc, const NodePCRotation* v_pc);
 
bool validateCollectedAdjs(node v, node u, List<SimplifyMapping>& bij_list, EdgeSet& visited,
        SyncPlanComponents& components);
 
#endif
 
}
}