Results 1 to 5 of 5
  1. #1
    Oxfam_Reject is offline Member
    Join Date
    Dec 2010
    Posts
    3
    Rep Power
    0

    Unhappy Array List Graph

    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
    }
    }
    }

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,000
    Blog Entries
    7
    Rep Power
    20

    Default

    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:

    Java Code:
    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:

    Java Code:
    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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Oxfam_Reject is offline Member
    Join Date
    Dec 2010
    Posts
    3
    Rep Power
    0

    Default

    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 :)

  4. #4
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

    Default

    Quote Originally Posted by Oxfam_Reject View Post
    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.

  5. #5
    Oxfam_Reject is offline Member
    Join Date
    Dec 2010
    Posts
    3
    Rep Power
    0

    Default

    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:
    Java Code:
    {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
    Java Code:
    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:
    Java Code:
    public Map<String, Set<String>> biggraph = new HashMap<String, Set<String>>();
    Thanks.
    Last edited by Oxfam_Reject; 12-28-2010 at 12:32 AM.

Similar Threads

  1. Replies: 2
    Last Post: 09-06-2010, 01:03 AM
  2. Drawing 3d graph from array table
    By Mekonom in forum Java 2D
    Replies: 3
    Last Post: 12-26-2009, 09:42 AM
  3. Array List help
    By Weejee37 in forum New To Java
    Replies: 4
    Last Post: 10-27-2009, 12:32 AM
  4. array list help
    By dorno83 in forum New To Java
    Replies: 9
    Last Post: 11-07-2008, 09:56 AM
  5. using an Array list
    By toad in forum New To Java
    Replies: 1
    Last Post: 11-18-2007, 09:08 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •