FreeCAD

1
/***************************************************************************
2
 *   Copyright (c) 2002 Jürgen Riegel <juergen.riegel@web.de>              *
3
 *                                                                         *
4
 *   This file is part of the FreeCAD CAx development system.              *
5
 *                                                                         *
6
 *   This library is free software; you can redistribute it and/or         *
7
 *   modify it under the terms of the GNU Library General Public           *
8
 *   License as published by the Free Software Foundation; either          *
9
 *   version 2 of the License, or (at your option) any later version.      *
10
 *                                                                         *
11
 *   This library  is distributed in the hope that it will be useful,      *
12
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
13
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
14
 *   GNU Library General Public License for more details.                  *
15
 *                                                                         *
16
 *   You should have received a copy of the GNU Library General Public     *
17
 *   License along with this library; see the file COPYING.LIB. If not,    *
18
 *   write to the Free Software Foundation, Inc., 59 Temple Place,         *
19
 *   Suite 330, Boston, MA  02111-1307, USA                                *
20
 *                                                                         *
21
 ***************************************************************************/
22

23
#include "PreCompiled.h"
24

25
#include <boost/graph/graphviz.hpp>
26
#include <random>
27

28
#include "Application.h"
29
#include "Document.h"
30
#include "private/DocumentP.h"
31
#include "DocumentObject.h"
32
#include "ExpressionParser.h"
33
#include "GeoFeatureGroupExtension.h"
34
#include "Origin.h"
35
#include "OriginGroupExtension.h"
36
#include "ObjectIdentifier.h"
37

38
using namespace App;
39
using namespace boost;
40

41
void Document::writeDependencyGraphViz(std::ostream &out)
42
{
43
    //  // caching vertex to DocObject
44
    //std::map<Vertex,DocumentObject*> VertexMap;
45
    //for(std::map<DocumentObject*,Vertex>::const_iterator It1= _DepConMap.begin();It1 != _DepConMap.end(); ++It1)
46
    //  VertexMap[It1->second] = It1->first;
47

48
    out << "digraph G {" << std::endl;
49
    out << "\tordering=out;" << std::endl;
50
    out << "\tnode [shape = box];" << std::endl;
51

52
    for (const auto &It : d->objectMap) {
53
        out << "\t" << It.first << ";" << std::endl;
54
        std::vector<DocumentObject*> OutList = It.second->getOutList();
55
        for (const auto &It2 : OutList) {
56
            if (It2) {
57
                out << "\t" << It.first << "->" << It2->getNameInDocument() << ";" << std::endl;
58
            }
59
        }
60
    }
61

62
    /*
63
    graph_traits<DependencyList>::edge_iterator ei, ei_end;
64
    for (tie(ei,ei_end) = edges(_DepList); ei != ei_end; ++ei)
65
      out << "\t"
66
          << VertexMap[source(*ei, _DepList)]->getNameInDocument()
67
          << " -> "
68
          << VertexMap[target(*ei, _DepList)]->getNameInDocument()
69
          << ";" << endl;
70
    */
71
    out << "}" << std::endl;
72
}
73

74
void Document::exportGraphviz(std::ostream& out) const
75
{
76
    /* Type defs for a graph with graphviz attributes */
77
    using GraphvizAttributes = std::map<std::string, std::string>;
78
    using Graph = boost::subgraph< adjacency_list<vecS, vecS, directedS,
79
                  property<vertex_attribute_t, GraphvizAttributes>,
80
                  property<edge_index_t, int, property<edge_attribute_t, GraphvizAttributes> >,
81
                  property<graph_name_t, std::string,
82
                  property<graph_graph_attribute_t,  GraphvizAttributes,
83
                  property<graph_vertex_attribute_t, GraphvizAttributes,
84
                  property<graph_edge_attribute_t,   GraphvizAttributes>
85
                  > > > > >;
86

87
    /**
88
     * @brief The GraphCreator class
89
     *
90
     * This class creates the dependency graph for a document.
91
     *
92
     */
93

94
    class GraphCreator {
95
    public:
96

97
        explicit GraphCreator(struct DocumentP* _d) : d(_d), seed(std::random_device()()), distribution(0,255) {
98
            build();
99
        }
100

101
        const Graph & getGraph() const { return DepList; }
102

103
    private:
104

105
        void build() {
106
            // Set attribute(s) for main graph
107
            get_property(DepList, graph_graph_attribute)["compound"] = "true";
108

109
            addSubgraphs();
110
            buildAdjacencyList();
111
            addEdges();
112
            markCycles();
113
            markOutOfScopeLinks();
114
        }
115

116
        /**
117
         * @brief getId returns a canonical string for a DocumentObject.
118
         * @param docObj Document object to get an ID from
119
         * @return A string
120
         */
121

122
        std::string getId(const DocumentObject * docObj) {
123
            return std::string((docObj)->getDocument()->getName()) + "#" + docObj->getNameInDocument();
124
        }
125

126
        /**
127
         * @brief getId returns a canonical string for an ObjectIdentifier;
128
         * @param path
129
         * @return A string
130
         */
131

132
        std::string getId(const ObjectIdentifier & path) {
133
            DocumentObject * docObj = path.getDocumentObject();
134
            if (!docObj)
135
                return {};
136

137
            return std::string((docObj)->getDocument()->getName()) + "#" + docObj->getNameInDocument() + "." + path.getPropertyName() + path.getSubPathStr();
138
        }
139

140
        std::string getClusterName(const DocumentObject * docObj) const {
141
            return std::string("cluster") + docObj->getNameInDocument();
142
        }
143

144
        void setGraphLabel(Graph& g, const DocumentObject* obj) const {
145
            std::string name(obj->getNameInDocument());
146
            std::string label(obj->Label.getValue());
147
            if (name == label)
148
                get_property(g, graph_graph_attribute)["label"] = name;
149
            else
150
                get_property(g, graph_graph_attribute)["label"] = name + "&#92;n(" + label + ")";
151
        }
152

153
        /**
154
         * @brief setGraphAttributes Set graph attributes on a subgraph for a DocumentObject node.
155
         * @param obj DocumentObject
156
         */
157

158
        void setGraphAttributes(const DocumentObject * obj) {
159
            assert(GraphList.find(obj) != GraphList.end());
160
            get_property(*GraphList[obj], graph_name) = getClusterName(obj);
161

162
            get_property(*GraphList[obj], graph_graph_attribute)["bgcolor"] = "#e0e0e0";
163

164
            get_property(*GraphList[obj], graph_graph_attribute)["style"] = "rounded,filled";
165
            setGraphLabel(*GraphList[obj], obj);
166
        }
167

168
        /**
169
         * @brief setPropertyVertexAttributes Set vertex attributes for a Property node in a graph.
170
         * @param g Graph
171
         * @param vertex Property node
172
         * @param name Name of node
173
         */
174

175
        void setPropertyVertexAttributes(Graph & g, Vertex vertex, const std::string & name) {
176
            get(vertex_attribute, g)[vertex]["label"] = name;
177
            get(vertex_attribute, g)[vertex]["shape"] = "box";
178
            get(vertex_attribute, g)[vertex]["style"] = "dashed";
179
            get(vertex_attribute, g)[vertex]["fontsize"] = "8pt";
180
        }
181

182
        /**
183
         * @brief addExpressionSubgraphIfNeeded Add a subgraph to the main graph if it is needed, i.e. there are defined at least one
184
         * expression in the document object, or other objects are referencing properties in it.
185
         * @param obj DocumentObject to assess.
186
         * @param CSSubgraphs Boolean if the GeoFeatureGroups are created as subgraphs
187
         */
188

189
        void addExpressionSubgraphIfNeeded(DocumentObject * obj, bool CSsubgraphs) {
190

191
            auto expressions = obj->ExpressionEngine.getExpressions();
192

193
            if (!expressions.empty()) {
194

195
                Graph* graph = nullptr;
196
                graph = &DepList;
197
                if (CSsubgraphs) {
198
                    auto group = GeoFeatureGroupExtension::getGroupOfObject(obj);
199
                    if (group) {
200
                        auto it = GraphList.find(group);
201
                        if (it != GraphList.end())
202
                            graph = it->second;
203
                    }
204
                }
205

206
                // If documentObject has an expression, create a subgraph for it
207
                if (graph && !GraphList[obj]) {
208
                    GraphList[obj] = &graph->create_subgraph();
209
                    setGraphAttributes(obj);
210
                }
211

212
                // Create subgraphs for all document objects that it depends on; it will depend on some property there
213
                for (const auto &expr : expressions) {
214
                    std::map<ObjectIdentifier, bool> deps;
215

216
                    expr.second->getIdentifiers(deps);
217

218
                    for (const auto &dep : deps) {
219
                        if (dep.second)
220
                            continue;
221
                        DocumentObject * o = dep.first.getDocumentObject();
222

223
                        // Doesn't exist already?
224
                        if (o && !GraphList[o]) {
225

226
                            if (CSsubgraphs) {
227
                                auto group = GeoFeatureGroupExtension::getGroupOfObject(o);
228
                                auto graph2 = group ? GraphList[group] : &DepList;
229
                                if (graph2) {
230
                                    GraphList[o] = &graph2->create_subgraph();
231
                                    setGraphAttributes(o);
232
                                }
233
                            }
234
                            else if (graph) {
235
                                GraphList[o] = &graph->create_subgraph();
236
                                setGraphAttributes(o);
237
                            }
238
                        }
239
                    }
240
                }
241
            }
242
        }
243

244
        /**
245
         * @brief add Add @docObj to the graph, including all expressions (and dependencies) it includes.
246
         * @param docObj The document object to add.
247
         * @param name Name of node.
248
         */
249

250
        void add(DocumentObject *docObj, const std::string &name, const std::string &label, bool CSSubgraphs)
251
        {
252

253
            //don't add objects twice
254
            if (std::find(objects.begin(), objects.end(), docObj) != objects.end())
255
                return;
256

257
            //find the correct graph to add the vertex to. Check first expression graphs, afterwards
258
            //the parent CS and origin graphs
259
            Graph *sgraph = GraphList[docObj];
260
            if (CSSubgraphs) {
261
                if (!sgraph) {
262
                    auto group = GeoFeatureGroupExtension::getGroupOfObject(docObj);
263
                    if (group) {
264
                        if (docObj->isDerivedFrom(App::OriginFeature::getClassTypeId()))
265
                            sgraph = GraphList[group->getExtensionByType<OriginGroupExtension>()->Origin.getValue()];
266
                        else
267
                            sgraph = GraphList[group];
268
                    }
269
                }
270
                if (!sgraph) {
271
                    if (docObj->isDerivedFrom(OriginFeature::getClassTypeId()))
272
                        sgraph = GraphList[static_cast<OriginFeature *>(docObj)->getOrigin()];
273
                }
274
            }
275
            if (!sgraph)
276
                sgraph = &DepList;
277

278
            // Keep a list of all added document objects.
279
            objects.insert(docObj);
280

281
            // Add vertex to graph. Track global and local index
282
            LocalVertexList[getId(docObj)] = add_vertex(*sgraph);
283
            GlobalVertexList[getId(docObj)] = vertex_no++;
284

285
            // If node is in main graph, style it with rounded corners. If not, make it invisible.
286
            if (!GraphList[docObj]) {
287
                get(vertex_attribute, *sgraph)[LocalVertexList[getId(docObj)]]["style"] = "filled";
288
                get(vertex_attribute, *sgraph)[LocalVertexList[getId(docObj)]]["shape"] = "Mrecord";
289
                // Set node label
290
                if (name == label)
291
                    get(vertex_attribute, *sgraph)[LocalVertexList[getId(docObj)]]["label"] = name;
292
                else
293
                    get(vertex_attribute, *sgraph)[LocalVertexList[getId(docObj)]]["label"] = name + "&#92;n(" + label + ")";
294
            }
295
            else {
296
                get(vertex_attribute, *sgraph)[LocalVertexList[getId(docObj)]]["style"] = "invis";
297
                get(vertex_attribute, *sgraph)[LocalVertexList[getId(docObj)]]["fixedsize"] = "true";
298
                get(vertex_attribute, *sgraph)[LocalVertexList[getId(docObj)]]["width"] = "0";
299
                get(vertex_attribute, *sgraph)[LocalVertexList[getId(docObj)]]["height"] = "0";
300
            }
301

302
            // Add expressions and its dependencies
303
            auto expressions{docObj->ExpressionEngine.getExpressions()};
304
            for (const auto &expr : expressions) {
305
                auto found = std::as_const(GlobalVertexList).find(getId(expr.first));
306
                if (found == GlobalVertexList.end()) {
307
                    int vid = LocalVertexList[getId(expr.first)] = add_vertex(*sgraph);
308
                    GlobalVertexList[getId(expr.first)] = vertex_no++;
309
                    setPropertyVertexAttributes(*sgraph, vid, expr.first.toString());
310
                }
311
            }
312

313
            // Add all dependencies
314
            for (const auto &expression : expressions) {
315
                // Get dependencies
316
                std::map<ObjectIdentifier, bool> deps;
317
                expression.second->getIdentifiers(deps);
318

319
                // Create subgraphs for all documentobjects that it depends on; it will depend on some property there
320
                for (const auto &dep : deps) {
321
                    if (dep.second) {
322
                        continue;
323
                    }
324
                    DocumentObject *depObjDoc = dep.first.getDocumentObject();
325
                    auto found = GlobalVertexList.find(getId(dep.first));
326

327
                    if (found == GlobalVertexList.end()) {
328
                        Graph *depSgraph = GraphList[depObjDoc] ? GraphList[depObjDoc] : &DepList;
329

330
                        LocalVertexList[getId(dep.first)] = add_vertex(*depSgraph);
331
                        GlobalVertexList[getId(dep.first)] = vertex_no++;
332
                        setPropertyVertexAttributes(*depSgraph, LocalVertexList[getId(dep.first)], dep.first.getPropertyName() + dep.first.getSubPathStr());
333
                    }
334
                }
335
            }
336
        }
337

338
        void recursiveCSSubgraphs(DocumentObject* cs, DocumentObject* parent) {
339

340
            auto graph = parent ? GraphList[parent] : &DepList;
341
            // check if the value for the key 'parent' is null
342
            if (!graph)
343
                return;
344
            auto& sub = graph->create_subgraph();
345
            GraphList[cs] = &sub;
346
            get_property(sub, graph_name) = getClusterName(cs);
347

348
            //build random color string
349
            std::stringstream stream;
350
            stream << "#" << std::setfill('0') << std::setw(2)<< std::hex << distribution(seed)
351
                   << std::setfill('0') << std::setw(2)<< std::hex << distribution(seed)
352
                   << std::setfill('0') << std::setw(2)<< std::hex << distribution(seed) << 80;
353
            std::string result(stream.str());
354

355
            get_property(sub, graph_graph_attribute)["bgcolor"] = result;
356
            get_property(sub, graph_graph_attribute)["style"] = "rounded,filled";
357
            setGraphLabel(sub, cs);
358

359
            for(auto obj : cs->getOutList()) {
360
                if (obj->hasExtension(GeoFeatureGroupExtension::getExtensionClassTypeId())) {
361
                    // in case of dependencies loops check if obj is already part of the
362
                    // map to avoid infinite recursions
363
                    auto it = GraphList.find(obj);
364
                    if (it == GraphList.end())
365
                        recursiveCSSubgraphs(obj, cs);
366
                }
367
            }
368

369
            //setup the origin if available
370
            if(cs->hasExtension(App::OriginGroupExtension::getExtensionClassTypeId())) {
371
                auto origin = cs->getExtensionByType<OriginGroupExtension>()->Origin.getValue();
372
                if (!origin) {
373
                    std::cerr << "Origin feature not found" << std::endl;
374
                    return;
375
                }
376
                auto& osub = sub.create_subgraph();
377
                GraphList[origin] = &osub;
378
                get_property(osub, graph_name) = getClusterName(origin);
379
                get_property(osub, graph_graph_attribute)["bgcolor"] = "none";
380
                setGraphLabel(osub, origin);
381
            }
382
        }
383

384
        void addSubgraphs() {
385

386
            ParameterGrp::handle depGrp = App::GetApplication().GetParameterGroupByPath("User parameter:BaseApp/Preferences/DependencyGraph");
387
            bool CSSubgraphs = depGrp->GetBool("GeoFeatureSubgraphs", true);
388

389
            if(CSSubgraphs) {
390
                //first build up the coordinate system subgraphs
391
                for (auto objectIt : d->objectArray) {
392
                    // do not require an empty inlist (#0003465: Groups breaking dependency graph)
393
                    // App::Origin now has the GeoFeatureGroupExtension but it should not move its
394
                    // group symbol outside its parent
395
                    if (!objectIt->isDerivedFrom(Origin::getClassTypeId()) &&
396
                         objectIt->hasExtension(GeoFeatureGroupExtension::getExtensionClassTypeId()))
397
                        recursiveCSSubgraphs(objectIt, nullptr);
398
                }
399
            }
400

401
            // Internal document objects
402
            for (const auto & It : d->objectMap)
403
                addExpressionSubgraphIfNeeded(It.second, CSSubgraphs);
404

405
            // Add external document objects
406
            for (const auto & it : d->objectMap) {
407
                std::vector<DocumentObject*> OutList = it.second->getOutList();
408
                for (auto obj : OutList) {
409
                    if (obj) {
410
                        std::map<std::string,Vertex>::const_iterator item = GlobalVertexList.find(getId(obj));
411

412
                        if (item == GlobalVertexList.end())
413
                            addExpressionSubgraphIfNeeded(obj, CSSubgraphs);
414
                    }
415
                }
416
            }
417

418
        }
419

420
        // Filling up the adjacency List
421
        void buildAdjacencyList() {
422

423
            ParameterGrp::handle depGrp = App::GetApplication().GetParameterGroupByPath("User parameter:BaseApp/Preferences/DependencyGraph");
424
            bool CSSubgraphs = depGrp->GetBool("GeoFeatureSubgraphs", true);
425

426
            // Add internal document objects
427
            for (const auto & It : d->objectMap)
428
                add(It.second, It.second->getNameInDocument(), It.second->Label.getValue(), CSSubgraphs);
429

430
            // Add external document objects
431
            for (const auto & It : d->objectMap) {
432
                std::vector<DocumentObject*> OutList = It.second->getOutList();
433
                for (auto obj : OutList) {
434
                    if (obj) {
435
                        std::map<std::string,Vertex>::const_iterator item = GlobalVertexList.find(getId(obj));
436

437
                        if (item == GlobalVertexList.end())
438
                            add(obj,
439
                                std::string(obj->getDocument()->getName()) + "#" + obj->getNameInDocument(),
440
                                std::string(obj->getDocument()->getName()) + "#" + obj->Label.getValue(),
441
                                CSSubgraphs);
442
                    }
443
                }
444
            }
445
        }
446

447
        void addEdges() {
448
            // Get edge properties for main graph
449
            const boost::property_map<Graph, boost::edge_attribute_t>::type& edgeAttrMap = boost::get(boost::edge_attribute, DepList);
450

451
            // Track edges between document objects connected by expression dependencies
452
            std::set<std::pair<const DocumentObject*, const DocumentObject*> > existingEdges;
453

454
            // Add edges between properties
455
            for (const auto &docObj : objects) {
456

457
                // Add expressions and its dependencies
458
                auto expressions = docObj->ExpressionEngine.getExpressions();
459
                for (const auto &expr : expressions) {
460
                    std::map<ObjectIdentifier, bool> deps;
461
                    expr.second->getIdentifiers(deps);
462

463
                    // Create subgraphs for all documentobjects that it depends on; it will depend on some property there
464
                    for (const auto &dep : deps) {
465
                        if (dep.second)
466
                            continue;
467
                        DocumentObject * depObjDoc = dep.first.getDocumentObject();
468
                        Edge edge;
469
                        bool inserted;
470

471
                        tie(edge, inserted) = add_edge(GlobalVertexList[getId(expr.first)], GlobalVertexList[getId(dep.first)], DepList);
472

473
                        // Add this edge to the set of all expression generated edges
474
                        existingEdges.insert(std::make_pair(docObj, depObjDoc));
475

476
                        // Edges between properties should be a bit smaller, and dashed
477
                        edgeAttrMap[edge]["arrowsize"] = "0.5";
478
                        edgeAttrMap[edge]["style"] = "dashed";
479
                    }
480
                }
481
            }
482

483
            ParameterGrp::handle depGrp = App::GetApplication().GetParameterGroupByPath("User parameter:BaseApp/Preferences/DependencyGraph");
484
            bool omitGeoFeatureGroups = depGrp->GetBool("GeoFeatureSubgraphs", true);
485

486
            // Add edges between document objects
487
            for (const auto & It : d->objectMap) {
488

489
                if(omitGeoFeatureGroups) {
490
                    //coordinate systems are represented by subgraphs
491
                    if(It.second->hasExtension(GeoFeatureGroupExtension::getExtensionClassTypeId()))
492
                        continue;
493

494
                    //as well as origins
495
                    if(It.second->isDerivedFrom(Origin::getClassTypeId()))
496
                        continue;
497
                }
498

499
                std::map<DocumentObject*, int> dups;
500
                std::vector<DocumentObject*> OutList = It.second->getOutList();
501
                const DocumentObject * docObj = It.second;
502

503
                for (auto obj : OutList) {
504
                    if (obj) {
505

506
                        // Count duplicate edges
507
                        bool inserted = edge(GlobalVertexList[getId(docObj)], GlobalVertexList[getId(obj)], DepList).second;
508
                        if (inserted) {
509
                            dups[obj]++;
510
                            continue;
511
                        }
512

513
                        // Skip edge if an expression edge already exists
514
                        if (existingEdges.find(std::make_pair(docObj, obj)) != existingEdges.end())
515
                            continue;
516

517
                        // Add edge
518

519
                        Edge edge;
520

521
                        tie(edge, inserted) = add_edge(GlobalVertexList[getId(docObj)], GlobalVertexList[getId(obj)], DepList);
522

523
                        // Set properties to make arrows go between subgraphs if needed
524
                        if (GraphList[docObj])
525
                            edgeAttrMap[edge]["ltail"] = getClusterName(docObj);
526
                        if (GraphList[obj])
527
                            edgeAttrMap[edge]["lhead"] = getClusterName(obj);
528
                    }
529
                }
530

531
                // Set labels for duplicate edges
532
                for (const auto & dup : dups) {
533
                    Edge e(edge(GlobalVertexList[getId(It.second)], GlobalVertexList[getId(dup.first)], DepList).first);
534
                    std::stringstream s;
535
                    s << " " << (dup.second + 1) << "x";
536
                    edgeAttrMap[e]["label"] = s.str();
537
                }
538
            }
539
        }
540

541
        using EdgeMap = std::unordered_multimap<Vertex, Edge>;
542

543
        void removeEdges(EdgeMap & in_edges,
544
                         EdgeMap & out_edges,
545
                         std::pair<EdgeMap::iterator, EdgeMap::iterator > i_pair,
546
                         std::function<Vertex (const Edge&)> select_vertex) {
547
            auto i = i_pair.first;
548

549
            while (i != i_pair.second) {
550
                // Remove from in edges in other nodes
551
                auto in_i_pair = in_edges.equal_range(select_vertex(i->second));
552
                auto in_i = in_i_pair.first;
553

554
                while (in_i != in_i_pair.second) {
555
                    if (in_i->second == i->second)
556
                        in_i = in_edges.erase(in_i);
557
                    else
558
                        ++in_i;
559
                }
560

561
                // Remove node from out_edges
562
                i = out_edges.erase(i);
563
            }
564
        }
565

566
#if defined(__clang__)
567
#elif defined (__GNUC__)
568
# pragma GCC diagnostic push
569
# pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
570
#endif
571

572
        void markCycles() {
573
            bool changed = true;
574
            std::unordered_set<Vertex> in_use;
575
            EdgeMap in_edges;
576
            EdgeMap out_edges;
577

578
            // Add all vertices to the in_use set
579
            graph_traits<Graph>::vertex_iterator vi, vi_end;
580
            tie(vi, vi_end) = vertices(DepList);
581
            for (; vi != vi_end; ++vi)
582
                in_use.insert(*vi);
583

584
            // Add all edges to the in_edges and out_edges multimaps
585
            graph_traits<Graph>::edge_iterator ei, ei_end;
586
            tie(ei, ei_end) = edges(DepList);
587
            for (; ei != ei_end; ++ei) {
588
                in_edges.insert(std::make_pair(target(*ei, DepList), *ei));
589
                out_edges.insert(std::make_pair(source(*ei, DepList), *ei));
590
            }
591

592
            // Go through dependency graph and remove nodes with either no input or output
593
            // A normal DAG without any cycles will get all its edges removed.
594
            // If one or more cycles exist in the graph, there will remain nodes with
595
            // both in and out edges.
596

597
            while (changed) {
598
                auto uvi = in_use.begin();
599
                auto uvi_end = in_use.end();
600

601
                // Flag that no changes has occurred so far. If the loop goes through
602
                // without this flag being set to true, we are done.
603
                changed = false;
604

605
                while (uvi != uvi_end) {
606
                    auto i_in_deg_pair = in_edges.equal_range(*uvi);
607
                    auto i_out_deg_pair = out_edges.equal_range(*uvi);
608

609
                    if (i_in_deg_pair.first == in_edges.end() && i_out_deg_pair.first == out_edges.end()) {
610
                        uvi = in_use.erase(uvi);
611
                        continue;
612
                    }
613

614
                    // Remove out edges of nodes that don't have a single edge in
615
                    if (i_in_deg_pair.first == in_edges.end()) {
616
                        removeEdges(in_edges, out_edges, i_out_deg_pair, [&](Edge e) { return target(e, DepList); });
617
                        changed = true;
618
                        i_out_deg_pair = out_edges.equal_range(*uvi);
619
                    }
620

621
                    // Remove in edges of nodes that don't have a single edge out
622
                    if (i_out_deg_pair.first == out_edges.end()) {
623
                        removeEdges(out_edges, in_edges, i_in_deg_pair, [&](Edge e) { return source(e, DepList); });
624
                        changed = true;
625
                    }
626

627
                    ++uvi;
628
                }
629
            }
630

631
            // Update colors in graph
632
            const boost::property_map<Graph, boost::edge_attribute_t>::type& edgeAttrMap = boost::get(boost::edge_attribute, DepList);
633
            for (auto ei : out_edges)
634
                edgeAttrMap[ei.second]["color"] = "red";
635
        }
636

637
#if defined(__clang__)
638
#elif defined (__GNUC__)
639
# pragma GCC diagnostic pop
640
#endif
641

642
        void markOutOfScopeLinks() {
643
            const boost::property_map<Graph, boost::edge_attribute_t>::type& edgeAttrMap = boost::get(boost::edge_attribute, DepList);
644

645
            for( auto obj : objects) {
646

647
                std::vector<App::DocumentObject*> invalids;
648
                GeoFeatureGroupExtension::getInvalidLinkObjects(obj, invalids);
649
                //isLinkValid returns true for non-link properties
650
                for(auto linkedObj : invalids) {
651

652
                    auto res = edge(GlobalVertexList[getId(obj)], GlobalVertexList[getId(linkedObj)], DepList);
653
                    if(res.second)
654
                        edgeAttrMap[res.first]["color"] = "orange";
655
                }
656
            }
657
        }
658

659
        const struct DocumentP* d;
660
        Graph DepList;
661
        int vertex_no{0};
662
        std::map<std::string, Vertex> LocalVertexList;
663
        std::map<std::string, Vertex> GlobalVertexList;
664
        std::set<const DocumentObject*> objects;
665
        std::map<const DocumentObject*, Graph*> GraphList;
666
        //random color generation
667
        std::mt19937 seed;
668
        std::uniform_int_distribution<int> distribution;
669
    };
670

671
    GraphCreator g(d);
672

673
    boost::write_graphviz(out, g.getGraph());
674
}
675