contrib/psg/src/peersim/graph/GraphIO.java

   1 /*
   2  * Copyright (c) 2003-2005 The BISON Project
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU Lesser General Public License version 2 as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU Lesser General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Lesser General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16  *
  17  */
  18
  19 package peersim.graph;
  20
  21 import java.util.*;
  22 import java.io.*;
  23
  24 /**
  25 * Implements static methods to load and write graphs.
  26 */
  27 public class GraphIO {
  28 private GraphIO() {}
  29
  30
  31 // ================== public static methods =========================
  32 // ==================================================================
  33
  34
  35 /**
  36 * Prints graph in edge list format. Each line contains exactly two
  37 * node IDs separated by whitespace.
  38 */
  39 public static void writeEdgeList( Graph g, PrintStream out ) {
  40
  41         for(int i=0; i<g.size(); ++i)
  42         {
  43                 Iterator it=g.getNeighbours(i).iterator();
  44                 while(it.hasNext())
  45                 {
  46                         out.println(i+" "+it.next());
  47                 }
  48         }
  49 }
  50
  51 // ------------------------------------------------------------------
  52
  53 /**
  54 * Prints graph in neighbor list format. Each line starts with the
  55 * id of a node followed by the ids of its neighbors separated by space.
  56 */
  57 public static void writeNeighborList( Graph g, PrintStream out ) {
  58
  59         out.println("# "+g.size());
  60
  61         for(int i=0; i<g.size(); ++i)
  62         {
  63                 out.print(i+" ");
  64                 Iterator it=g.getNeighbours(i).iterator();
  65                 while(it.hasNext())
  66                 {
  67                         out.print(it.next()+" ");
  68                 }
  69                 out.println();
  70         }
  71 }
  72
  73 // ------------------------------------------------------------------
  74
  75 /**
  76 * Saves the given graph to
  77 * the given stream in DOT format. Good for the graphviz package.
  78 */
  79 public static void writeDOT( Graph g, PrintStream out ) {
  80
  81         out.println((g.directed()?"digraph":"graph")+" {");
  82
  83         for(int i=0; i<g.size(); ++i)
  84         {
  85                 Iterator<Integer> it=g.getNeighbours(i).iterator();
  86                 while(it.hasNext())
  87                 {
  88                         final int j = it.next();
  89                         if(g.directed())
  90                                 out.println(i+" -> "+j+";");
  91                         else if( i<=j )
  92                                 out.println(i+" -- "+j+";");
  93                 }
  94         }
  95
  96         out.println("}");
  97 }
  98
  99 // ------------------------------------------------------------------
 100
 101 /**
 102 * Saves the given graph to
 103 * the given stream in GML format.
 104 */
 105 public static void writeGML( Graph g, PrintStream out ) {
 106
 107         out.println("graph [ directed "+(g.directed()?"1":"0"));
 108
 109         for(int i=0; i<g.size(); ++i)
 110                 out.println("node [ id "+i+" ]");
 111
 112         for(int i=0; i<g.size(); ++i)
 113         {
 114                 Iterator it=g.getNeighbours(i).iterator();
 115                 while(it.hasNext())
 116                 {
 117                         out.println(
 118                                 "edge [ source "+i+" target "+it.next()+" ]");
 119                 }
 120         }
 121
 122         out.println("]");
 123 }
 124
 125 // --------------------------------------------------------------------
 126
 127 /**
 128 * Saves the given graph to
 129 * the given stream to be read by NETMETER. It should be ok also for Pajek.
 130 */
 131 public static void writeNetmeter( Graph g, PrintStream out ) {
 132
 133         out.println("*Vertices "+g.size());
 134         for(int i=0; i<g.size(); ++i)
 135                 out.println((i+1)+" \""+(i+1)+"\"");
 136
 137         out.println("*Arcs");
 138         for(int i=0; i<g.size(); ++i)
 139         {
 140                 Iterator it=g.getNeighbours(i).iterator();
 141                 while(it.hasNext())
 142                 {
 143                         out.println((i+1)+" "+
 144                                 (((Integer)it.next()).intValue()+1)+" 1");
 145                 }
 146         }
 147         out.println("*Edges");
 148 }
 149
 150 // --------------------------------------------------------------------
 151
 152 /**
 153 * Saves the given graph to
 154 * the given stream in UCINET DL nodelist format.
 155 */
 156 public static void writeUCINET_DL( Graph g, PrintStream out ) {
 157
 158         out.println("DL\nN="+g.size()+"\nFORMAT=NODELIST\nDATA:");
 159
 160         for(int i=0; i<g.size(); ++i)
 161         {
 162                 out.print(" " + (i+1));
 163                 Iterator it=g.getNeighbours(i).iterator();
 164                 while(it.hasNext())
 165                 {
 166                         out.print(" "+(((Integer)it.next()).intValue()+1));
 167                 }
 168                 out.println();
 169         }
 170         out.println();
 171 }
 172
 173 // --------------------------------------------------------------------
 174
 175 /**
 176 * Saves the given graph to
 177 * the given stream in UCINET DL matrix format.
 178 */
 179 public static void writeUCINET_DLMatrix( Graph g, PrintStream out ) {
 180
 181         out.println("DL\nN="+g.size()+"\nDATA:");
 182
 183         for(int i=0; i<g.size(); ++i)
 184         {
 185                 BitSet bs = new BitSet(g.size());
 186                 Iterator it=g.getNeighbours(i).iterator();
 187                 while(it.hasNext())
 188                 {
 189                         bs.set( ((Integer)it.next()).intValue() );
 190                 }
 191                 for(int j=0; j<g.size(); ++j)
 192                 {
 193                         out.print(bs.get(j)?" 1":" 0");
 194                 }
 195                 out.println();
 196         }
 197         out.println();
 198 }
 199
 200 // --------------------------------------------------------------------
 201
 202 /**
 203 * Saves the given graph to
 204 * the given stream in Chaco format. We need to output the number of edges
 205 * so they have to be counted first which might not be very efficient.
 206 * Note that this format is designed for undirected graphs only.
 207 */
 208 public static void writeChaco( Graph g, PrintStream out ) {
 209
 210         if( g.directed() ) System.err.println(
 211                 "warning: you're saving a directed graph in Chaco format");
 212
 213         long edges = 0;
 214         for(int i=0; i<g.size(); ++i) edges += g.getNeighbours(i).size();
 215
 216         out.println( g.size() + " " + edges/2 );
 217
 218         for(int i=0; i<g.size(); ++i)
 219         {
 220                 Iterator it=g.getNeighbours(i).iterator();
 221                 while(it.hasNext())
 222                 {
 223                         out.print((((Integer)it.next()).intValue()+1)+" ");
 224                 }
 225                 out.println();
 226         }
 227
 228         out.println();
 229 }
 230
 231 // -------------------------------------------------------------------
 232
 233 /**
 234 * Read a graph in newscast graph format.
 235 * The format depends on mode, the parameter.
 236 * The file begins with the three byte latin 1 coded "NCG" string followed
 237 * by the int MODE which is the
 238 * given parameter. The formats are the following as a function of mode:
 239 * <ul>
 240 * <li> 1: Begins with cacheSize in binary format (int), followed by the
 241 *     numberOfNodes (int), and then a continuous series of exactly
 242 *     numberOfNodes records, where a record describes a node's
 243 *     neighbours and their timestamps.
 244 *     A record is a series of exactly cacheSize (int,long) pairs where
 245 *     the int is the node id, and the long is the timestamp.
 246 *     Node id-s start from 1. Node id 0 means no node and used if the parent
 247 *     node has less that cacheSize nodes.</li>
 248 * </ul>
 249 * @param file Filename to read
 250 * @param direction If 0, the original directionality is preserved, if 1,
 251 * than each edge is reversed, if 2 then directionality is dropped and the
 252 * returned graph will be undirected.
 253 */
 254 public static Graph readNewscastGraph( String file, int direction )
 255 throws IOException {
 256
 257         NeighbourListGraph gr = new NeighbourListGraph( direction != 2 );
 258         FileInputStream fis = new FileInputStream(file);
 259         DataInputStream dis = new DataInputStream(fis);
 260
 261         dis.readByte();
 262         dis.readByte();
 263         dis.readByte();
 264
 265         final int MODE = dis.readInt();
 266         if( MODE != 1 ) throw new IOException("Unknown mode "+MODE);
 267
 268         final int CACHESIZE = dis.readInt();
 269         final int GRAPHSIZE = dis.readInt();
 270
 271 //System.out.println("header: "+MODE+" "+CACHESIZE+" "+GRAPHSIZE);
 272
 273         for(int i=1; i<=GRAPHSIZE; ++i)
 274         {
 275                 int iind = gr.addNode(i);
 276
 277                 for(int j=0; j<CACHESIZE; ++j)
 278                 {
 279                         int a = dis.readInt();
 280                         dis.readLong();
 281
 282                         int agentIndex = gr.addNode(a);
 283                         if( direction == 0 ) gr.setEdge(iind,agentIndex);
 284                         else gr.setEdge(agentIndex,iind);
 285                 }
 286         }
 287
 288         dis.close();
 289
 290         return gr;
 291 }
 292
 293
 294 }
 295