MacRumors Forums Java graph work problems

 Jan 15, 2007, 11:58 AM #1 CSJoe macrumors newbie   Join Date: Jan 2007 Java graph work problems Having a spot of bother getting my head round this baby. Any suggestions? You should use Hierholzers Algorithm to find the Euler tour The program should be started with the command: java -classpath \\raptor\files\packages\java\repository;. EulerGraph For example: java -classpath \\raptor\files\packages\java\repository;. EulerGraph graph.adj You should load in a graph file, which simply contains a list of edges, edges are pairs of nodes labels (arbitrary alphanumeric strings) separated by a colon, For example graph.adj might contain: 10:15 15:27 27:10 You should output a file named after the input file name with an additional .euler extension. This should contain either the text FAIL if there is no tour or a list [Node1, Node2, ..., NodeX, Node1] which describes a Euler Tour in the given graph. The list must be surrounded by square brackets and the nodes must be divided by commas. For example graph.adj.euler might contain: [10, 15, 27, 10] or [15, 10, 27, 15] Because there are many possible Euler tours in a given Eulerian graph, any one of the possible trails is acceptable. No other text should be present in the output file. You should generate your own set of test data to check that your program works, including large Eulerian graphs (so that the sub trails are present) and non Eulerian graphs, empty graphs and minimal graphs. The prj.graph package contains the three classes package pjr.graph; import java.util.*; import java.io.*; /** * This is a graph containing nodes and edges. *

* The graph can be used for both directed and undirected graphs. * The current interpretation of undirected edges in the * algorithms is being able to traverse a single edge in either * direction. This is reflected in the graph and edge access functions, * which provide for this form of undirected access. *

* Consistency of the graph takes several forms: * all nodes and edges attach to items in the graph; * unique nodes and edges in the collections (no duplicate objects); * edges having a connection at each end; and * edge to and from corresponding to node to and from. *

* Consistency is maintained through the operations in graph, so * that its not possible to add an edge without the nodes being * in the graph. * Also, the node delete removes any connecting edges from the graph *

* It contains some additional fields for helping when writing algorithms, the * boolean {@link #visited}, a flag for indicating that a node has been traversed * and the list {@link #path} for indicating some sort of route to the * node, which also allows a test (null) to see if the node has been visited. *

* It contains an additional field for helping when writing algorithms, the * boolean {@link #visited}, a flag for indicating that an edge has been traversed * * @see Graph * @see Node * @author Peter Rodgers */ public class Edge { /** Source node. Must be assigned.*/ private Node from; /** Target node. Must be assigned.*/ private Node to; /** Optional label.*/ private String label = ""; /** Optional weight value.*/ private double weight = 0.0; /** This flag can be set if the edge has been traversed during a graph algorithm. */ private boolean visited = false; /** * Pass the two nodes that the edge connects with to this constructor. * It creates an edge between the two nodes. */ public Edge(Node inFrom, Node inTo) { setFromTo(inFrom, inTo); } /** * Constructor initialising label. * It creates an edge between the two nodes. */ public Edge(Node inFrom, Node inTo, String inLabel) { setFromTo(inFrom, inTo); setLabel(inLabel); } /** * Constructor initialising weight. * It creates an edge between the two nodes. */ public Edge(Node inFrom, Node inTo, double inWeight) { setFromTo(inFrom, inTo); setWeight(inWeight); } /** * Constructor initialising label and weight. * It creates an edge between the two nodes. */ public Edge(Node inFrom, Node inTo, String inLabel, double inWeight) { setFromTo(inFrom, inTo); setLabel(inLabel); setWeight(inWeight); } /** Trival accessor. */ public Node getFrom() {return from;} /** Trival accessor. */ public Node getTo() {return to;} /** Trival accessor. */ public String getLabel() {return label;} /** Trival accessor. */ public double getWeight() {return weight;} /** Trival accessor. */ public boolean getVisited() {return visited;} /** Trivial modifier. */ public void setLabel(String inLabel) {label = inLabel;} /** Trivial modifier. */ public void setWeight(double inWeight) {weight = inWeight;} /** Trivial modifier. */ public void setVisited(boolean inVisited) {visited = inVisited;} /** find out if the edge connects to the same node at each end. */ public boolean selfSourcing() { if(from == to) { return(true); } return(false); } /** * Gives the other end of the edge to the argument node. * @return the node at the other end of the edge, or null if the passed node is not connected to the edge */ public Node getOppositeEnd(Node n) { Node ret = null; if (getFrom() == n) { ret = getTo(); } if (getTo() == n) { ret = getFrom(); } return(ret); } /** * Sets or moves both ends of the edge. * @return the success of the operation, if fail, then the old state * should be preserved. */ public boolean setFromTo(Node inFrom, Node inTo) { Node oldFrom=from; if(!setFrom(inFrom)) { return(false); }; if(!setTo(inTo)) { setFrom(oldFrom); return(false); }; return(true); } /** * Sets or moves the source of the edge. Accounts for the * redundant data in the node. Also deals with nulls, either * currently attached to edges, or passed to this method. * @return the success of the operation. */ public boolean setFrom(Node inFrom) { if(from != null) { if(!from.removeEdgeFrom(this)) { return(false); } } if(inFrom != null) { inFrom.addEdgeFrom(this); } from = inFrom; return(true); } /** * Sets or moves the target of the edge. Accounts for the * redundant data in the node. Also deals with nulls, either * currently attached to edges, or passed to this method. * @return the success of the operation. */ public boolean setTo(Node inTo) { if(to != null) { if(!to.removeEdgeTo(this)) { return(false); } } if(inTo != null) { inTo.addEdgeTo(this); } to = inTo; return(true); } /** * This method reverses the ends of the edge. It also works for undirected edges, * reversing the from and to values, although in this case no difference should * be apparent. */ public void reverse() { Node oldFrom = from; setFrom(to); setTo(oldFrom); } /** * Checks that the connecting nodes have consistent redundant data. Used principally * by {@link Graph#consistent}. */ public boolean consistent(Graph g) { if(!getFrom().getEdgesFrom().contains(this)) { return(false); } if(!getTo().getEdgesTo().contains(this)) { return(false); } if(!g.getNodes().contains(getFrom())) { return(false); } if(!g.getNodes().contains(getTo())) { return(false); } return(true); } /** Gives the connecting nodes strings in a pair, plus the edge label and weight. */ public String toString() { return("("+getFrom()+":"+getTo()+","+getLabel()+","+getWeight()+")"); } } Long winded i know but I would appreciate the help 0

 MacRumors Forums