Graph Drawing Toolkit

An object-oriented C++ library for handling and drawing graphs

---

rm3_dire_graph.h

Go to the documentation of this file.

/*******************************************************************************
+
+  rm3_dire_graph.h
+
+  This file is part of GDToolkit. It can be 
+  used free of charge in academic research and teaching. 
+  Any direct or indirect commercial use of this software is illegal 
+  without a written authorization of
+  the Dipartimento di Informatica e Automazione
+  Universita' di Roma Tre, Roma, ITALIA
+  
+
+  All rights reserved.
+ 
*******************************************************************************/


#ifndef RM3_DIRE_GRAPH_H
#define RM3_DIRE_GRAPH_H

#if !defined(ROOT_INCL_ID)
#define ROOT_INCL_ID 34004
#endif

#include <GDT/rm3_undi_graph.h>
#include <GDT/gdtnode_pq.h>

        /*
        SOURCEFILE rm3_dire_graph.h
        To be defined.
        */

//-----------------------------------------------------------------------------
// dire_graph:
//      base class for all directed embedded graphs
//
// W.Didimo, A.Leonforte (1996)
//-----------------------------------------------------------------------------

        class GDT_NONSTANDARD_DECL
dire_graph
        : public undi_graph
        {
        private:
                // -----------------
                // private variables
                // -----------------
                // empty
                
                
                // ---------------
                // private methods
                // ---------------
                
                void local_new  ();      // create a new set of pointers for the not-inherited class-part
                void local_del  ();      // delete all the not-inherited class-part
                void local_renew();      // utility function : just local_del(), then local_new()
                void local_init ();      // init the not-inherited class-part

                void make_undirected (); // hides undesired inherited method
        

        public:

                /*
                CATEGORY constructors_destructors
                Constructors and Destructors
                */
        
                
                        
                dire_graph
                        (
                        );                                                      

                
                        
                dire_graph
                        (
                        const undi_graph&
                        );
                        
                /*
                CATEGORY opeartors
                Operators.
                */
                        
                
                        
                        dire_graph&
                operator=
                        (
                        const undi_graph&
                        );              

                

                /*
                CATEGORY access
                Access operations
                */
                                                                                                
                
                        
                        gdtnode 
                find_source
                        (
                        );                                      
                        
                
                        
                        gdtnode 
                find_sink
                        (
                        );
                        
                
                        
                        void 
                find_shortest_path                                      
                        (
                        gdtnode s, 
                        gdt::gdtedge_array<int>&  length, 
                        gdt::gdtnode_array<int>&  distance, 
                        gdt::gdtnode_array<gdtedge>& pred_edge
                        );
                                                
                
                        
                        void 
                find_longest_path                                
                        (
                        gdtnode s, 
                        gdt::gdtedge_array<int>&  length, 
                        gdt::gdtnode_array<int>&  distance, 
                        gdt::gdtnode_array<gdtedge>& pred_edge
                        );
                        
                
                        
                        void 
                find_path_with_minimum_switches 
                        (
                        gdtnode s, 
                        gdt::gdtnode_array<int>&  switches, 
                        gdt::gdtnode_array<gdtedge>& pred_edge, 
                        visit_direction_type dir
                        );
                        
                
                        
                        void 
                find_path_with_minimum_switches 
                        (
                        gdtnode s, 
                        gdtnode t, 
                        gdt::gdtnode_array<int>&  switches, 
                        gdt::gdtnode_array<gdtedge>& pred_edge
                        );                                                                              
                        
                
                        
                        void 
                Dijkstra 
                        (
                        gdtnode s, 
                        gdt::gdtedge_array<int>&  length, 
                        gdt::gdtnode_array<int>&  distance, 
                        gdt::gdtnode_array<gdtedge>& pred_edge
                        );                                      
                        
                
                        
                        gdt::gdtlist<gdtedge> 
                simple_DFS 
                        (
                        gdtnode v, 
                        gdt::gdtnode_array<bool>& reached, 
                        gdt::gdtnode_array<gdtedge>& father, 
                        gdt::gdtlist<gdtnode>&    order, 
                        visit_direction_type dt = OUTGOING
                        );              
                                                
                
                        
                        bool 
                is_acyclic 
                        (
                        );                                                                                      
                
                        
                        gdt::gdtlist<gdtedge>
                make_acyclic
                        (
                        );
                
                        
                        bool 
                topological_sort 
                        (
                        gdtnode v, 
                        gdt::gdtnode_array<bool>& reached, 
                        gdt::gdtlist<gdtnode>& order
                        );                                              
                
                /*
                CATEGORY update
                Update operations
                */

                
                        
                        gdtedge
                new_edge
                        (
                        gdtnode v1,
                        gdtnode v2,
                        int new_id=AUTO_ID
                        );
                        
                
                        
                        gdtedge 
                new_edge 
                        (
                        gdtnode v1,
                        gdtedge e1,
                        gdtnode v2,
                        int new_id=AUTO_ID,
                        int dir=gdt::after
                        );



                        gdtedge
                new_edge
                        (
                        gdtnode v1,
                        gdtnode v2,
                        gdtedge e2,
                        int new_id=AUTO_ID,
                        int dir=gdt::after
                        );



                        gdtedge
                new_edge
                        (
                        gdtnode v,
                        gdtedge ev,
                        gdtnode w,
                        gdtedge ew,
                        int new_id=AUTO_ID,
                        int dir=gdt::after
                        );
                                                                                                                        
                
                        
                        void 
                clear 
                        (
                        );                                                                                                                                              
                
                        
                        void
                steal_from 
                        (
                        undi_graph& ug
                        );                                      
        };                                                                                      
        
                                                                                                

#endif

---