fork(1) download
copy 
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.io.BufferedOutputStream;
  4. import java.io.BufferedInputStream;
  5. import java.io.FileInputStream;
  6. import java.io.FileOutputStream;
  7. import java.io.InputStream;
  8. import java.io.IOException;
  9. import java.io.ObjectInput;
  10. import java.io.ObjectInputStream;
  11. import java.io.ObjectOutput;
  12. import java.io.ObjectOutputStream;
  13. import java.io.ObjectStreamField;
  14. import java.io.OutputStream;
  15. import java.io.Serializable;
  16. /**
  17.  * Represents a graph comprised of collection of nodes,
  18.  * a collection of edges, and an indicator as to
  19.  * whether or not the graph is directed.
  20.  */
  21. public class Graph implements Serializable {
  22.     /**
  23.      * Serialization version indicator used to determine if
  24.      * a file is compatible with this class.
  25.      */
  26.     private static final long serialVersionUID = 1038001L;
  27.     /** Default state save/restore file name. */
  28.     public static String SERIAL_FILENAME = "graph.ser";
  29.     /** Ensure serialization of necessary fields. */
  30.     private static final ObjectStreamField[] serialPersistentFields
  31.                  = { new ObjectStreamField("isDirected", Boolean.class),
  32.                      new ObjectStreamField("nodes", List.class),
  33.                      new ObjectStreamField("edges", List.class) };
  34.  
  35.     /**
  36.      * The list of nodes in this graph.
  37.      * Each node is represented by a Node object.
  38.      * @serial
  39.      */
  40.     private List<Node> nodes = new ArrayList<Node>();
  41.  
  42.     /**
  43.      * The list of edges in this graph.
  44.      * Each edge is represented by an Edge object.
  45.      * @serial
  46.      */
  47.     private List<Edge> edges = new ArrayList<Edge>();
  48.  
  49.     /**
  50.      * Indicator of directedness of this graph;
  51.      * true = directed, false = undirected
  52.      * @serial
  53.      */
  54.     private Boolean isDirected = new Boolean(false);
  55.  
  56.     /**
  57.      * Construct an undirected graph with no nodes or edges.
  58.      */
  59.     public Graph() { }
  60.  
  61.     /**
  62.      * Construct an undirected graph with nodes only, no edges.
  63.      * Performs no error checking.
  64.      * @param nodeLabels a list of String objects to be used as node labels
  65.      */
  66.     public Graph(List<String> nodeLabels) {
  67.         for (String label : nodeLabels) {
  68.             this.nodes.add(new Node(label, null));
  69.         }
  70.     }
  71.  
  72.     /**
  73.      * Construct a simple undirected, unweighted graph.
  74.      * Performs no error checking.
  75.      * @param nodeLabels a list of String objects to be used as node labels
  76.      * @param edgeList a list of edges where each edge is specified as a
  77.      *        list of two strings representing the start-node-label and
  78.      *        end-node-label in that order.
  79.      */
  80.     public Graph(List<String> nodeLabels, List<List<String>> edgeList, Boolean simple) {
  81.         this(nodeLabels);
  82.         for (List<String> edge : edgeList) {
  83.             this.edges.add(new Edge(edge.get(0), edge.get(1), false, null, null));
  84.         }
  85.     }
  86.  
  87.     /**
  88.      * Construct a general graph.
  89.      * Performs no error checking.
  90.      * @param nodeLabels a list of String objects to be used as node labels
  91.      * @param nodeCosts a list of Integer objects to be used as cost of each node in nodeLabels
  92.      * @param directed true if this is a directed graph; false otherwise
  93.      * @param edgeList a list of edges where each edge is specified as a
  94.      *        list of Strings representing
  95.      *        <start-node-label,end-node-label,directedness,edge-label,edge-weight>;
  96.      *        edge-label and edge-weight may be null.
  97.      */
  98.     public Graph(List<String> nodeLabels,
  99.                  List<Integer> nodeCosts,
  100.                  Boolean directed,
  101.                  List<List<String>> edgeList) {
  102.         for (int i = 0; i < nodeLabels.size(); i++) {
  103.             this.nodes.add(new Node(nodeLabels.get(i), nodeCosts.get(i)));
  104.         }
  105.         this.isDirected = directed;
  106.         for (List<String> edge : edgeList) {
  107.             this.edges.add(new Edge(edge.get(0),
  108.                                     edge.get(1),
  109.                                     Boolean.valueOf(edge.get(2)),
  110.                                     edge.get(3),
  111.                                     Integer.valueOf(edge.get(4))));
  112.         }
  113.     }
  114.  
  115.     /**
  116.      * Retrieve nodes as list of labels.
  117.      * @return list of labels of nodes in this graph
  118.      */
  119.     public List<String> getNodeNamesAsStrings() {
  120.         List<String> labels = new ArrayList<String>();
  121.         for (Node n : this.nodes) {
  122.             labels.add(n.getLabel());
  123.         }
  124.         return labels;
  125.     }
  126.  
  127.  
  128.     /**
  129.      * Retrieve nodes as list of pairs of Strings.
  130.      * The first element is the node label, the second is the associated cost.
  131.      * @return list of labels of nodes in this graph
  132.      */
  133.     public List<List<String>> getNodesAsStrings() {
  134.         List<List<String>> nodeStrings = new ArrayList<List<String>>();
  135.         for (Node n : this.nodes) {
  136.             List<String> nodePair = new ArrayList<String>();
  137.             nodePair.add(n.getLabel());
  138.             nodePair.add(n.getCost().toString());
  139.             nodeStrings.add(nodePair);
  140.         }
  141.         return nodeStrings;
  142.     }
  143.  
  144.     /**
  145.      * Retrieve edges as list of lists of five Strings:
  146.      * two node labels, an indicator of directedness,
  147.      * a label, and a weight.
  148.      * If a directed edge, the first of the pair of nodes represents
  149.      * the start node while the second represents the end node.
  150.      * If a directed edge, the indicator is "true"; 
  151.      * otherwise the indicator is "false".
  152.      * If the edge has no label, it will be shown as "null".
  153.      * If the edge has a weight, it will be given as an integer string;
  154.      * otherwise it will be shown as "null".
  155.      * @return list of edges in this graph
  156.      */
  157.     public List<List<String>> getEdgesAsStrings () {
  158.         List<List<String>> edgeList = new ArrayList<List<String>>();
  159.         for (Edge e : this.edges) {
  160.             List<String> oneEdge = new ArrayList<String>();
  161.             oneEdge.add(e.getStartNode());
  162.             oneEdge.add(e.getEndNode());
  163.             oneEdge.add(e.isDirected().toString());
  164.             oneEdge.add("" + e.getLabel());
  165.             oneEdge.add("" + e.getWeight());
  166.             edgeList.add(oneEdge);
  167.         }
  168.         return edgeList;           
  169.     }
  170.  
  171.     /**
  172.      * Disclose if graph is directed or undirected.
  173.      * @return true if graph is directed; false otherwise
  174.      */
  175.     public Boolean isDirected() { return this.isDirected; }
  176.  
  177.     /**
  178.      * Simple string representation of graph.
  179.      * @return a string that shows the nodes and edges of this graph
  180.      */
  181.     @Override
  182.     public String toString() {
  183.         return "GRAPH: " + 
  184.         (isDirected ? "Directed" : "Undirected") +
  185.         "\n " +
  186.         "Nodes(" + nodes + ")\n " +
  187.         "Edges(" + edges + ")";
  188.     }
  189.  
  190.     @Override public boolean equals(Object o) {
  191.         if ( this == o ) return true;
  192.         if ( !(o instanceof Graph) ) return false;
  193.         Graph that = (Graph)o;
  194.         return
  195.             (this.nodes.equals(that.nodes)) &&
  196.             (this.edges.equals(that.edges)) &&
  197.             (this.isDirected.equals(that.isDirected));
  198.     }
  199.  
  200.     @Override public int hashCode() {
  201.         return
  202.         17 + 
  203.         ((this.nodes == null) ? 0 : this.nodes.hashCode()) +
  204.         ((this.edges  == null) ? 0 : this.edges.hashCode()) +
  205.         ((this.isDirected == null) ? 0 : this.isDirected.hashCode());
  206.     }
  207.  
  208.     /**
  209.      * Save the state of this graph.
  210.      * @param graphFileName the name of the file into which to save,
  211.      *        or null to use default file name. 
  212.      */
  213.     public void saveGraph(String graphFileName) {
  214.         if (graphFileName == null) graphFileName = Graph.SERIAL_FILENAME;
  215.         // Serialize the graph.
  216.         try {
  217.             OutputStream file = new FileOutputStream(graphFileName);
  218.             OutputStream buffer = new BufferedOutputStream(file);
  219.             ObjectOutput output = new ObjectOutputStream(buffer);
  220.             try { output.writeObject(this); }
  221.             finally { output.close(); }
  222.         }
  223.         catch (IOException ex) {
  224.             System.err.println("Unsuccessful save. " + ex);
  225.         }
  226.  
  227.         // Attempt to deserialize the graph as verification.
  228.         try {
  229.             InputStream file = new FileInputStream(graphFileName);
  230.             InputStream buffer = new BufferedInputStream(file);
  231.             ObjectInput input = new ObjectInputStream (buffer);
  232.             try {
  233.  
  234.                 @SuppressWarnings("unchecked") // Accommodate type erasure.
  235.                 Graph restored = null;
  236.                 restored = (Graph)input.readObject();
  237.                 // Simple check that deserialized data matches original.
  238.                 if (!this.toString().equals(restored.toString()))
  239.                     System.err.println("[1] State restore did not match save!");
  240.                 if (!this.equals(restored))
  241.                     System.err.println("[2] State restore did not match save!");
  242.             }
  243.             finally { input.close(); }
  244.         }
  245.         catch (ClassNotFoundException ex) {
  246.             System.err.println(
  247.                 "Unsuccessful deserialization: Class not found. " + ex);
  248.         }
  249.         catch (IOException ex) {
  250.             System.err.println("Unsuccessful deserialization: " + ex);
  251.         }
  252.     }
  253.  
  254.     /**
  255.      * Reload this graph.
  256.      * @param graphFileName the name of the file with serialized graph,
  257.      *        or null to use default file name. 
  258.      */
  259.     public void restoreGraph(String graphFileName) {
  260.         if (graphFileName == null) graphFileName = Graph.SERIAL_FILENAME;
  261.         Graph restored = null;
  262.         try {
  263.             InputStream file = new FileInputStream(graphFileName);
  264.             InputStream buffer = new BufferedInputStream(file);
  265.             ObjectInput input = new ObjectInputStream (buffer);
  266.             try {
  267.                 @SuppressWarnings("unchecked") // Accommodate type erasure.
  268.                 Graph retrieved = (Graph)input.readObject();
  269.                 restored = retrieved;
  270.             }
  271.             finally {
  272.                 input.close();
  273.             }
  274.         }
  275.         catch (ClassNotFoundException ex) {
  276.             System.err.println(
  277.                 "Unsuccessful deserialization: Class not found. " + ex);
  278.         }
  279.         catch (IOException ex) {
  280.             System.err.println("Unsuccessful deserialization: " + ex);
  281.         }
  282.         if (restored == null) {
  283.             System.err.println("Unsuccessful deserialization: restored == null");
  284.         } else {
  285.             this.nodes = restored.nodes;
  286.             this.edges = restored.edges;
  287.             this.isDirected = restored.isDirected;
  288.         }
  289.     }
  290.  
  291.     /**
  292.      * Node representation is comprised of a
  293.      * String label and an Integer cost.
  294.      * If cost is null, this node is not part of
  295.      * a graph whose nodes have a cost attribute.
  296.      */
  297.     private class Node implements Serializable  {
  298.         private String label;
  299.         private Integer cost;
  300.         /**
  301.          * Construct a node with attributes as
  302.          * specified by the parameters.
  303.          * @param nodeLabel the label associated with this node
  304.          * @param nodeCost the cost or weight associated with this node
  305.          */
  306.         Node(String nodeLabel, Integer nodeCost) {
  307.             this.label = nodeLabel;
  308.             this.cost = nodeCost;
  309.         }
  310.  
  311.         String getLabel() { return this.label; }
  312.  
  313.         Integer getCost() { return this.cost; }
  314.  
  315.         @Override public String toString() { return this.label; }
  316.  
  317.         /**
  318.          * Equals predicate helper method.
  319.          * @param x first object for comparison
  320.          * @param y second object for comparison
  321.          * @return true if both objects are null or
  322.          *         objects' native equals method returns true;
  323.          *         false otherwise
  324.          */
  325.         private boolean closeEnough(Object x, Object y) {
  326.             if (x == y) return true;
  327.             if (x == null || y == null) return false;
  328.             return x.equals(y);
  329.         }
  330.  
  331.         @Override public boolean equals(Object o) {
  332.             if ( this == o ) return true;
  333.             if ( !(o instanceof Node) ) return false;
  334.             Node that = (Node)o;
  335.             return
  336.             closeEnough(this.label, that.label) &&
  337.             closeEnough(this.cost, that.cost);
  338.         }
  339.  
  340.         @Override public int hashCode() {
  341.             return
  342.             29 + 
  343.             ((this.label == null) ? 0 : this.label.hashCode()) +
  344.             ((this.cost  == null) ? 0 : this.cost.hashCode());
  345.         }
  346.     }
  347.  
  348.     /**
  349.      * Edge representation is comprised of two String
  350.      * node labels, a Boolean indicator of directedness,
  351.      * an optional Integer weight, and an optional
  352.      * String edge label.
  353.      * Nodes are referred to as start and end even
  354.      * if that distinction is not meaningful (as for
  355.      * undirected edges).
  356.      * If weight is null, this edge is not part of
  357.      * a graph whose edges have a weight attribute.
  358.      */
  359.     private class Edge implements Serializable  {
  360.         private String start;
  361.         private String end;
  362.         private Boolean directed;
  363.         private String label;
  364.         private Integer weight;
  365.  
  366.         /**
  367.          * Construct an edge with attributes as
  368.          * specified by the parameters.
  369.          * @param startNode the label of the start node
  370.          * @param endNode the label of the end node
  371.          * @param isDirected true if a directed edge; false otherwise
  372.          * @param edgeLabel the label of this edge (null if none)
  373.          * @param edgeWeight the integer weight of this edge (null if none)
  374.          */
  375.         Edge(String startNode, String endNode, Boolean isDirected,
  376.              String edgeLabel, Integer edgeWeight) {
  377.             this.start = startNode;
  378.             this.end = endNode;
  379.             this.directed = isDirected;
  380.             this.label = edgeLabel;
  381.             this.weight = edgeWeight;
  382.         }
  383.  
  384.         String getStartNode() { return this.start; }
  385.  
  386.         String getEndNode() { return this.end; }
  387.  
  388.         Boolean isDirected() { return this.directed; }
  389.  
  390.         String getLabel() { return this.label; }
  391.  
  392.         Integer getWeight() { return this.weight; }
  393.  
  394.         @Override public String toString() {
  395.             return "<" + this.start + "," + this.end + "," + 
  396.                    this.directed + "," + this.label + "," + this.weight + ">";
  397.         }
  398.  
  399.         /**
  400.          * Equals predicate helper method.
  401.          * @param x first object for comparison
  402.          * @param y second object for comparison
  403.          * @return true if both objects are null or
  404.          *         objects' native equals method returns true;
  405.          *         false otherwise
  406.          */
  407.         boolean closeEnough(Object x, Object y) {
  408.             if (x == y) return true;
  409.             if (x == null || y == null) return false;
  410.             return x.equals(y);
  411.         }
  412.  
  413.         @Override public boolean equals(Object o) {
  414.             if ( this == o ) return true;
  415.             if ( !(o instanceof Edge) ) return false;
  416.             Edge that = (Edge)o;
  417.             return
  418.             closeEnough(this.start, that.start) &&
  419.             closeEnough(this.end, that.end) &&
  420.             closeEnough(this.directed, that.directed) &&
  421.             closeEnough(this.label, that.label) &&
  422.             closeEnough(this.weight, that.weight);
  423.         }
  424.  
  425.         @Override public int hashCode() {
  426.             return
  427.             37 + 
  428.             ((this.start    == null) ? 0 : this.start.hashCode()) +
  429.             ((this.end      == null) ? 0 : this.end.hashCode()) +
  430.             ((this.directed == null) ? 0 : this.directed.hashCode()) +
  431.             ((this.label    == null) ? 0 : this.label.hashCode()) +
  432.             ((this.weight   == null) ? 0 : this.weight.hashCode());
  433.         }
  434.     }
  435. }
  436.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5lE7JL
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!