Java how to represent graphs

Question

I m implementing some algorithms to teach myself about graphs and how to work with them  What would you recommend is the best way to do that in Java  I was thinking something like this   public class Vertex        private ArrayList lt Vertex gt  outnodes    Adjacency list  if I wanted to support edge weight  this would be a hash map         methods to manipulate outnodes    public class Graph       private ArrayList lt Vertex gt  nodes        algorithms on graphs     But I basically just made this up  Is there a better way   Also  I want it to be able to support variations on vanilla graphs like digraphs  weighted edges  multigraphs  etc

User · Answer

class Graph lt E gt        private List lt Vertex lt E gt  gt  vertices       private static class Vertex lt E gt            E elem          List lt Vertex lt E gt  gt  neighbors

User · Answer

Adjacency List implementation of Graph is appropriate for solving most of the graph related problems   Java implementation of the same is here on my blog

User · Answer

Take a look at the http   jung sourceforge net doc index html graph library  You can still practice implementing your own algorithms  maybe breadth-first or depth-first search to start   but you don t need to worry about creating the graph structure

User · Answer

Time ago I had the same problem and did my own implementation  What I suggest you is to implement another class  Edge  Then  a Vertex will have a List of Edge   public class Edge       private Node a  b      private directionEnum direction         AB  BA or both     private int weight              It worked for me  But maybe is so simple  There is this library that maybe can help you if you look into its code  http   jgrapht sourceforge net

User · Answer

Why not keep things simple and use an adjacency matrix or an adjacency list

User · Answer

When learning algorithms  the programming language  Java  should not be considered in deciding the representation  Each problem could benefit from a unique representation  and moreover designing it can add a bit of learning  Solve the problem first without relying on a particular language  then the representation for any particular language will flow naturally   Of course  general representations and libraries are useful in real-world applications  But some of them could benefit from some customization as well  Use the other answers to know the different techniques available  but consider customization when appropriate

User · Answer

Each node is named uniquely and knows who it is connected to  The List of connections allows for a Node to be connected to an arbitrary number of other nodes   public class Node       public String name      public List lt Edge gt  connections      Each connection is directed  has a start and an end  and is weighted   public class Edge       public Node start      public Node end      public double weight      A graph is just your collection of nodes  Instead of List lt Node gt  consider Map lt String  Node gt  for fast lookup by name   public class Graph       List lt Node gt  nodes

User · Answer

A simple representation written by  Robert Sedgwick  and  Kevin Wayne  is available at http   algs4 cs princeton edu 41graph Graph java html Explanation copied from the above page   The Graph class represents an undirected graph of vertices named 0 through V - 1  It supports the following two primary operations  add an edge to the graph  iterate over all of the vertices adjacent to a vertex  It also provides methods for returning the number of vertices V and the number of edges E  Parallel edges and self-loops are permitted  By convention  a self-loop v-v appears in the adjacency list of v twice and contributes two to the degree of v  This implementation uses an adjacency-lists representation  which is a vertex-indexed array of Bag objects  All operations take constant time  in the worst case  except iterating over the vertices adjacent to a given vertex  which takes time proportional to the number of such vertices

User · Answer

class Vertex       private String name      private int score     for path algos     private boolean visited     for path algos     List lt Edge gt  connections     class Edge       private String vertex1Name     same as Vertex name     private String vertex2Name      private int length     class Graph       private List lt Edge gt  edges

User · Answer

If you need weighted edges and multigraphs  you might want to add another class Edge   I would also recommend using generics to allow specifying which sub-class of Vertex and Edge are currently used  For example   public class Graph lt V extends Vertex gt    List lt V gt  vertices          When it comes to implementing graph algorithms  you could also define interfaces for your graph classes on which the algorithms can operate  so that you can play around with different implementations of the actual graph representation  For example  simple graphs that are well-connected might be better implemented by an adjacency matrix  sparser graphs might be represented by adjacency lists - it all depends     BTW Building such structures efficiently can be quite challenging  so maybe you could give us some more details on what kind of job you would want to use them for  For more complex tasks I would suggest you have a look at the various Java graph libraries  to get some inspiration

User · Answer

I d recommend graphviz highly when you get to the point where you want to render your graphs   And its companions  take a look at Laszlo Szathmary s GraphViz class  along with notugly xls

User · Answer

Even at the time of this question  over 3 years ago  Sage  which is completely free  existed and was pretty good at graph theory   But  in 2012 it is about the best graph theory tool there is   Thus  Sage already has a huge amount of graph theory material built in  including other free and open source stuff that is out there   So  simply messing around with various things to learn more is easy as no programming is required   And  if you are interested in the programming part as well  first Sage is open source so you can see any code that already exists   And  second  you can re-program any function you want if you really want to practice  or you can be the first to program something that does not already exist   In the latter case  you can even submit that new functionality and make Sage better for all other users   At this time  this answer may not be that useful to the OP  since it has been 3 years   but hopefully it is useful to any one else who sees this question in the future

[java] Java: how to represent graphs?

Examples related to java

Examples related to graph