Array List Graph

[Oxfam_Reject]

Hey, I'm trying to create a graph which will later be used to make some sort of pagerank program, but at the moment I'm stuck on the basics.
"write a class called Graph that encapsulates
a suitable graph data structure and methods for operating on it (given that the number of nodes
and edges will potentially be very large). Include methods in your class which load and storegraphs to and from an ASCII text file."

I have decided to create an array list with all the nodes, then add a link by adding an arraylist to that particular node with the names of the other nodes it links to,i.e 1:2,3
2:1
3:4,1
4:2,3,1
But i dont know how to add an array list to the node?

this is my code so far:


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


public class pagerank {

public ArrayList<String> biggraph = new ArrayList<String>();
//public LinkedList<String>[] links;
public static void main(String[] args) {
new pagerank().read("pagerank.txt");
}


public void read(String filename) {

BufferedReader bufferedReader = null;
try {
bufferedReader = new BufferedReader(new FileReader(filename));
String nextline = new String("");
String currentline = null;
while ((currentline = bufferedReader.readLine()) != null) {
nextline = currentline;
String[] part = new String[1];
part = nextline.split(" ");
graph(part[0], part[1]);
//System.out.println(part[0]);
//System.out.println(part[1]);
}
bufferedReader.close();
}catch (Exception e){
System.err.println("Error: " + e.getMessage());

}
}

public void graph(String from, String into){
addVertex(from);
addVertex(into);
addLink(from, into);
//checks to see if from exists, if not add
//checks to see if into exists, if not add
//checks to see if edge exists within from's linked list, if not add
}

public void addVertex(String name){
//if biggraph does not contain name, add to big graph, create linked list for it
//Boolean found = false;
Iterator<String> iter = this.biggraph.iterator();
String currItem = "";
while ( iter.hasNext() == true ) {
currItem = iter.next();

if (currItem == name) {
return;
}
}
biggraph.add(name);
return;
}

public void addLink(String from, String into){
//search for from in biggraph, add element to its linked list
Iterator<String> iter = this.biggraph.iterator();
String currItem = "";
int i = 0;
while ( iter.hasNext() == true ) {
currItem = iter.next();
i++;
if (currItem == from) {
/*PROBLEM HERE! LINE BELOW!*/
biggraph[i] = new ArrayList<String>();
}


//check to see if linked list exists
//add linked list to from
//check to see if element exists
//add new element, into
}
}
}

[JosAH]

If you are representing the vertexes (nodes) of the graph as Strings why not use a Map<String, ...> where the key is the name of the vertex and the value is a collection of Strings again, representing the vertexes that can be reached from a certain vertex. To complete the map: Map<String, Set<String>>. I represent the 'to vertexes' as a Set of Strings. It's up to you to interpret this map as a directed graph or an undirected graph. The Map and the Set can do the searching for you so you don't need to iterate over it anymore. Adding a vertex is easy:

Map<String, Set<String>> graph= new Map<String, Set<String>>();
...
public boolean addVertex(String name) {
   if (graph.containsKey(name)) return false;
   graph.put(name, null);
   return true;
}

Adding a vertex isn't much more difficult:

public boolean addEdge(String from, String to) {
   addVertex(from);
   addVertext(to);
   Set<String> edges= graph.get(from);
   if (edges == null)
      graph.put(from, edges= new Set<String>());
   if (edges.contains(to)) return null;
   edges.add(to);
   return true;
}

kind regards,

Jos

[Oxfam_Reject]

Thanks. I posted this question on three forums and you came up with the best answer! It seems to work, no doubt I'll experience more problems later on, so I'll be back for your help soon :)

[Fubarable]

Thanks. I posted this question on three forums and you came up with the best answer! It seems to work, no doubt I'll experience more problems later on, so I'll be back for your help soon :)

Please be sure to notify the other forums that your question is solved. Also, if you cross-post, please notify all threads of the same question of the cross-posts so folks don't waste time and energy duplicating effort for a problem that's already solved elsewhere. Thank you for your cooperation.

[Oxfam_Reject]

And that time has come.

I now need to search the graph and have it print out which nodes each of the nodes links too. I can get this:

{product=[help], help=null, index=[product, help, support], support=[help]}

to print, that is when i input the file:
index product
index support
index help
product help
support help

But how do you reference the different values separately in a Map.
As in, to print

node { name } links to nodes { name },{ name }

Also, i changed the map bit at the start to say this, or it came up with an error:

public Map<String, Set<String>> biggraph = new HashMap<String, Set<String>>();

Thanks.