graph.java

sifi-0.1.6.tar.gz 出自http://www.ifi.unizh.ch/ikm/SINUS/firewall/ 一个linux的防火墙工具。

/* ----------------------------------------------------------------------
   The SINUS Firewall -- a TCP/IP packet filter for Linux

   Written within the SINUS project at the University of Zurich,
   SWITCH, Telekurs Payserv AG, ETH Zurich.
   originally based on the sf Firewall Software (C) 1996 by Robert
   Muchsel and Roland Schmid.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

   SINUS Firewall resources:
   SINUS Homepage: http://www.ifi.unizh.ch/ikm/SINUS/
   Firewall Homepage: http://www.ifi.unizh.ch/ikm/SINUS/firewall.html
   Frequently asked questions: http://www.ifi.unizh.ch/ikm/SINUS/sf_faq.html
   Mailing list for comments, questions, bug reports: [e-mail]
   ----------------------------------------------------------------------  */



package sfclasses;

import java.util.*;
import java.io.*;
import java.awt.*;

/**
 * This class implements a graph datastructure.
 * @version 1.0 29 Nov 1996
 * @author Roland E. Schmid
 */

public class Graph implements Persistent {

  /**
   * @return true iff the graph does not contain any vertices
   */
  public boolean isEmpty() {
    return Vertices.isEmpty();
  }

  /**
   * @return number of vertices in the graph
   */
  public int NumberOfVertices() {
    return Vertices.size();
  }

  /**
   * Search a vertex in the graph
   * @param V the object to search 
   * @return true if the object is a vertex in the graph
   */
  public boolean searchVertex(Object V) {
    return Vertices.contains(V);
  }
    
  /**
   * Search an edge in the graph
   * @param V1 first vertex
   * @param V2 second vertex
   * @return true if V1 and V2 are adjacent
   */
  public boolean searchEdge(Object V1, Object V2) {
    int V1index = Vertices.lastIndexOf(V1);
    if (V1index == -1) 
      return false;
    return ((Vector)(AdjLists.elementAt(V1index))).contains(V2);
  }

  /**
   * Search an edge in the graph and return its color.
   * @param V1 first vertex
   * @param V2 second vertex
   * @return Object's color if V1 and V2 are adjacent, null otherwise
   */
  public Color getEdgeColor(Object V1, Object V2) {
    int V1index = Vertices.lastIndexOf(V1);
    if (V1index == -1) {
      return null;
		}
		Vector v = (Vector)(AdjLists.elementAt(V1index));
		int V2Index = v.lastIndexOf(V2);
    if (V2Index == -1) {
			return null;
		}
		try {
			v = (Vector)(ColLists.elementAt(V1index));
			return ((EdgeColor)v.elementAt(V2Index)).getColor();
		}
		catch (ArrayIndexOutOfBoundsException e) {
			System.out.println("ArrayIndexOutOfBoundsException in getEdgeColor");
			return null;
		}
  }

  /**
   * Set the color of an already existing edge.
   * @param V1 first vertex
   * @param V2 second vertex
   * @return true if succsessful, false otherwise
   */
  public boolean setEdgeColor(Object V1, Object V2, Color col) {
    if ((!Vertices.contains(V1)) || (!Vertices.contains(V2)))
      return false;
    Vector al = (Vector)(AdjLists.elementAt(Vertices.lastIndexOf(V1)));
    Vector cl = (Vector)(ColLists.elementAt(Vertices.lastIndexOf(V1)));
    if (!al.contains(V2))
			return false;
		else 
      cl.setElementAt(new EdgeColor(col), al.lastIndexOf(V2));

    al = (Vector)(AdjLists.elementAt(Vertices.lastIndexOf(V2)));
    cl = (Vector)(ColLists.elementAt(Vertices.lastIndexOf(V2)));
    if (!al.contains(V1))
			return false;
		else
      cl.setElementAt(new EdgeColor(col), al.lastIndexOf(V1));
		return true;
  }

  /**
   * Insert a vertex in graph
   * @param V object to insert
   */
  public void insertVertex(Object V) {
    if (!Vertices.contains(V)) {
      Vertices.addElement(V);
      Vector al = new Vector(3,3);
      AdjLists.addElement(al);
			Vector cl = new Vector(3,3);
			ColLists.addElement(cl);
    }
  }

  /**
   * Insert an edge in graph
   * @param V1 first vertex
   * @param V2 second vertex
   */
  public void insertEdge(Object V1, Object V2) {
    if ((!Vertices.contains(V1)) || (!Vertices.contains(V2)))
      return;
    Vector al = (Vector)(AdjLists.elementAt(Vertices.lastIndexOf(V1)));
    if (!al.contains(V2))
      al.addElement(V2);
    al = (Vector)(AdjLists.elementAt(Vertices.lastIndexOf(V2)));
    if (!al.contains(V1))
      al.addElement(V1);
  }

  /**
   * Insert an edge in graph
   * @param V1 first vertex
   * @param V2 second vertex
   * @param col color of edge
   */
  public void insertEdge(Object V1, Object V2, Color col) {
    if ((!Vertices.contains(V1)) || (!Vertices.contains(V2)))
      return;
		int vIndex = Vertices.lastIndexOf(V1);
    Vector al = (Vector)(AdjLists.elementAt(vIndex));
    Vector cl = (Vector)(ColLists.elementAt(vIndex));
    if (!al.contains(V2)) {
      al.addElement(V2);
      cl.addElement(new EdgeColor(col));
		}

    al = (Vector)(AdjLists.elementAt(Vertices.lastIndexOf(V2)));
    cl = (Vector)(ColLists.elementAt(Vertices.lastIndexOf(V2)));
    if (!al.contains(V1)) {
      al.addElement(V1);
      cl.addElement(new EdgeColor(col));
		}
  }

  /**
   * Delete a vertex
   * @param V vertex to delete
   */
  public void deleteVertex(Object V) {
    int index = Vertices.lastIndexOf(V);
    if (index == -1)
      return;
    Vertices.removeElementAt(index);
    AdjLists.removeElementAt(index);
    ColLists.removeElementAt(index);
    Enumeration listenum = AdjLists.elements();
    while (listenum.hasMoreElements()) {
      Vector al = (Vector)listenum.nextElement();
      al.removeElement(V);
    }
    listenum = ColLists.elements();
    while (listenum.hasMoreElements()) {
      Vector al = (Vector)listenum.nextElement();
      al.removeElement(V);
    }
  }

  /**
   * Delete an edge
   * @param V1 first vertex
   * @param V2 second vertex
   */
  public void deleteEdge(Object V1, Object V2) {
    if ((!Vertices.contains(V1)) || (!Vertices.contains(V2)))
      return;
		int vIndex = Vertices.lastIndexOf(V1);
    Vector list = (Vector)(AdjLists.elementAt(vIndex));
    list.removeElement(V2);
    list = (Vector)(ColLists.elementAt(vIndex));
    list.removeElement(V2);
		vIndex = Vertices.lastIndexOf(V2);
    list = (Vector)(AdjLists.elementAt(vIndex));
    list.removeElement(V1);
    list = (Vector)(ColLists.elementAt(vIndex));
    list.removeElement(V1);
  }

  /**
   * @param V vertex
   * @return enumeration of all neighbors of vertex V
   */
  public Enumeration findNeighbors(Object V) {
    return new GraphEnumeration(Vertices, AdjLists, V);
  }

  /**
   * @return an enumeration of all vertices in graph
   */
  public Enumeration getAllVertices() {
    return new GraphEnumeration(Vertices, AdjLists);
  }

  /**
   * @return an enumeration of all edges in graph
   * @see Edge
   */
  public Enumeration getAllEdges() {
    return new EdgeEnumeration(Vertices, AdjLists);
  }

  /**
   * override Object.toString()
   * @return string describing the graph
   */
  public String toString() {
    String str = new String("number of vertices: "+Vertices.size());
    Vector al;
    for (int i=0; i < Vertices.size(); i++) {
      str += "\n  "+i+" "+Vertices.elementAt(i)+"\n     Neighbors:";
      al = (Vector)AdjLists.elementAt(i);
      for (int j=0; j < al.size(); j++)
        str += " "+Vertices.lastIndexOf(al.elementAt(j));
    }  
    return str;
  }

  // Persistence
  /**
   * Write object data to a persistent output stream
   * @param ps Stream
   * @see PersistentOutputStream
   */
  public void write(PersistentOutputStream ps) {
    ps.writePersistentVector("vertices=", Vertices);
    for (int i = 0; i < Vertices.size(); i++)
      ps.writePersistentVector("adjlist=", (Vector)AdjLists.elementAt(i));
		try {
      for (int j = 0; j < Vertices.size(); j++)
        ps.writePersistentVector("collist=", (Vector)ColLists.elementAt(j));
			
		}
		catch (ArrayIndexOutOfBoundsException e) {
			System.out.println("ArrayOutOfBoundsException in Graph Persistence");	
		}
		
  }

  /**
   * Read object data from a persistent input stream
   * @param ps Stream
   * @see PersistentInputStream
   */
  public void read(PersistentInputStream ps) throws java.io.IOException {
    Vertices = ps.readPersistentVector("vertices=");
    for (int i = 0; i < Vertices.size(); i++)
      AdjLists.addElement(ps.readPersistentVector("adjlist="));
    for (int i = 0; i < Vertices.size(); i++)
      ColLists.addElement(ps.readPersistentVector("collist="));
  }


  // private data
  private Vector Vertices = new Vector(10, 5);
  private Vector AdjLists = new Vector(10, 5);
  private Vector ColLists = new Vector(10, 5);
  protected boolean isConsistent = true;

}

// EdgeColor
class EdgeColor
	implements Persistent { 
	

	EdgeColor() {
		color = 0;
	}

	EdgeColor(Color col) {
		color = col.getRGB();
	}

	public void setColor(Color col) {
		color = col.getRGB();
	}

	public Color getColor() {
		return new Color(color);
	}


	// Persistent methods
	public void write(PersistentOutputStream ps) {
		ps.writeInt("color=", color);
	}

	public void read(PersistentInputStream ps) throws java.io.IOException {
		color = ps.readInt("color=");
	}

	int color;
	
} // EdgeColor


// Enumeration of all vertices
class GraphEnumeration
	implements Enumeration {

  // constructors
  public GraphEnumeration(Vector Vertices, Vector AdjLists) {
    selectedVertices = Vertices.elements();
  }

  public GraphEnumeration(Vector Vertices, Vector AdjLists, Object Neighbor) {
    int index = Vertices.lastIndexOf(Neighbor);
    if (index == -1)
      NeighborAvailable = false;
    else 
      selectedVertices = ((Vector)(AdjLists.elementAt(index))).elements();
  }

  // public instance methods
  public boolean hasMoreElements() {
    if (NeighborAvailable)
      return selectedVertices.hasMoreElements();
    else
      return false;
  }

  public Object nextElement() {
    if (NeighborAvailable)
      return selectedVertices.nextElement();
    else
      throw new NoSuchElementException();
  }

  // private data
  private Enumeration selectedVertices;
  private boolean NeighborAvailable = true;
}

// Enumeration of all edges
class EdgeEnumeration
	implements Enumeration {

  // constructor
  public EdgeEnumeration(Vector Vertices, Vector AdjLists) {
    Edge e;
    for (int i = 0; i < Vertices.size(); i++) {
      Vector al = (Vector)AdjLists.elementAt(i);
      for (int j = 0; j < al.size(); j++) {
        Object o = al.elementAt(j);
        if (Vertices.lastIndexOf(o) > i) { // insert each edge only once
          e = new Edge(Vertices.elementAt(i), o);
          Edges.addElement(e);
        }
      }
    }
    EdgeEnum = Edges.elements();
  }

  // public instance methods
  public boolean hasMoreElements() {
    return EdgeEnum.hasMoreElements();
  }

  public Object nextElement() {
    return EdgeEnum.nextElement();
  }

  // private data
  private Vector Edges = new Vector(20,10);
  private Enumeration EdgeEnum;
}