ext/OGDF/src/simultaneous/SimDrawCreator.cpp

   1 /*
   2  * $Revision: 2554 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 11:39:38 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Offers variety of possible SimDraw creations.
  11  *
  12  * \author Michael Schulz and Daniel Lueckerath
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43 #include <ogdf/simultaneous/SimDrawCreator.h>
  44 #include <ogdf/basic/graph_generators.h>
  45
  46 namespace ogdf {
  47
  48 //*************************************************************
  49 //sets all edgeSubGraph values to zero
  50 //
  51 void SimDrawCreator::clearESG()
  52 {
  53         edge e;
  54         forall_edges(e,*m_G)
  55                 m_GA->subGraphBits(e) = 0;
  56
  57 }//end clearESG
  58
  59
  60 //*************************************************************
  61 //gives each edge in m_G a random edgeSubGraph value
  62 //works with two graphs
  63 void SimDrawCreator::randomESG2(int doubleESGProbability)
  64 {
  65         OGDF_ASSERT( doubleESGProbability <= 100 );
  66         OGDF_ASSERT( doubleESGProbability >= 0 );
  67
  68         clearESG();
  69
  70         edge e;
  71         forall_edges(e,*m_G)
  72         {
  73                 //all edges have a chance of doubleESGProbability (in percent)
  74                 //to belong to both input graphs
  75                 int doubleESGRandom = rand() % 100;
  76                 if(doubleESGRandom < doubleESGProbability)
  77                 {
  78                         m_GA->addSubGraph(e, 0);
  79                         m_GA->addSubGraph(e, 1);
  80                 }
  81                 else
  82                 {
  83                         // all edges, which do not belong to both input graphs
  84                         // have a 50/50 chance to belong to graph 0 or to graph 1
  85                         int singleESGRandom = rand() % 2;
  86                         m_GA->addSubGraph(e, singleESGRandom);
  87                 }
  88         }
  89
  90 }//end randomESG2
  91
  92
  93 //*************************************************************
  94 //gives each edge in m_G a random edgeSubGraph value
  95 //works with three graphs
  96 void SimDrawCreator::randomESG3(int doubleESGProbability, int tripleESGProbability)
  97 {
  98         OGDF_ASSERT( doubleESGProbability + tripleESGProbability <= 100 );
  99         OGDF_ASSERT( doubleESGProbability >= 0 );
 100         OGDF_ASSERT( tripleESGProbability >= 0 );
 101
 102         clearESG();
 103
 104         edge e;
 105         forall_edges(e,*m_G)
 106         {
 107                 /*All edges have a chance of tripleESGProbability (in percent)
 108                 to belong to all three graphs.*/
 109                 int multipleESGRandom = rand() % 100;
 110                 if(multipleESGRandom < doubleESGProbability + tripleESGProbability)
 111                 {
 112                         m_GA->addSubGraph(e,0);
 113                         m_GA->addSubGraph(e,1);
 114                         m_GA->addSubGraph(e,2);
 115
 116                         /*Furthermore, all edges have a chance of doubleESGProbability
 117                         to belong to two of three graphs.*/
 118                         if(multipleESGRandom >= tripleESGProbability)
 119                         {
 120                                 int removeESGRandom = rand() % 3;
 121                                 m_GA->removeSubGraph(e, removeESGRandom);
 122                         }
 123                 }
 124                 else
 125                 {
 126                         //all edges, which do not belong to two or three graphs
 127                         //have a 33 percent chance to belong to one of the three graphs.
 128                         int singleESGRandom = rand() % 3;
 129                         m_GA->addSubGraph(e, singleESGRandom);
 130                 }
 131         }
 132
 133 }//end randomESG3
 134
 135
 136 //*************************************************************
 137 //gives each edge a random edgeSubgraph value
 138 //works with graphNumber number of graphs
 139 void SimDrawCreator::randomESG(int graphNumber)
 140 {
 141         OGDF_ASSERT( 0 < graphNumber && graphNumber < 32 );
 142
 143         int max = (int)pow((double)2,graphNumber+1)-1;
 144         edge e;
 145         forall_edges(e,*m_G)
 146         {
 147                 int randomESGValue = 1 + rand() % max;
 148                 m_GA->subGraphBits(e) = randomESGValue;
 149         }
 150
 151 }//end randomESG
 152
 153
 154 //*************************************************************
 155 //
 156 //
 157 void SimDrawCreator::createRandom(int numberOfNodes,
 158         int numberOfEdges,
 159         int numberOfBasicGraphs)
 160 {
 161         OGDF_ASSERT( 0 < numberOfBasicGraphs && numberOfBasicGraphs < 32 );
 162         randomSimpleGraph(*m_G, numberOfNodes, numberOfEdges);
 163         randomESG(numberOfBasicGraphs);
 164
 165 }//end createRandom
 166
 167
 168 } // end namespace ogdf