Note in Advance: This is for a personal project, it is not homework related.

Basically I need a java class which will take a 2-d array of numbers
and output a java graphics component with a graph drawn representing
the nodes and vertexes. The class should also colour the vertexes
different colours depending on the value of the number for that
position.

To clarify:

 a b c d e
a- 1 0 1 2
b1 - 1 1 0
c1 0 - 1 2
d0 1 2 - 1
e1 1 1 1 -

So if a (top row) and e (side) was 1 you might colour it red, if it
was 0 you might colour it blue (the actual colours arent important but
commenting would be appreciated so I can modify as necessary).

Finally the links between nodes should be uni-directional (That is
they should ideally contain arrows (a double headed arrow for a vertex
thats bi-directional).

I know this is relatively trivial but I need it to support up to 400
nodes and around 20,000 vertexes maximum and I cant find a suitable
algorithm for drawing it nicely....

Feel free to query if you want clarification, I could accept a
solution less perfect (needs to be able to draw 100 nodes minimum and
support 1000 vertexes minimum) but more would be better.

---

Clarification of Question by michael248-ga on 29 Sep 2006 15:29 PDT

Something which just occured to me (it would be ideal if each node was
created as a sub-component so I can add MouseOver, MouseAction events
etc).

---

Clarification of Question by michael248-ga on 29 Sep 2006 15:40 PDT

Incidentally the solution can be part of a library if necessary - im a
competent java programmer (I just struggle with graphics) also it
doesnt matter if the solution calls an external application with the
provision that the external application must be free for individual
use.

---

Clarification of Question by michael248-ga on 01 Oct 2006 11:01 PDT

Ok, since this doesnt seem to have received a lot of interest as is, I
would be willing to accept an answer with a link to an algorithm in
java and I will handle the drawing myself.

Please ask for clarification before submitting the answer so we can
agree on whats necessary.

---

Clarification of Question by michael248-ga on 05 Oct 2006 07:48 PDT

Ok you have it pretty much spot on, I see your point about the
arrowheads so would happily dump that as an idea (and therefore you
could assume the adjacency matrix was symmetrical but the lines would
still need to be coloured differently depending on value).

I'll add a picture in a little bit and to get someone interested i've
increased the question value to $200.00

---

Clarification of Question by michael248-ga on 05 Oct 2006 07:55 PDT

Just to clarify because I think some people may be heading along the
right lines: Its important that the algorithm outputs a nice looking
graph in the sense that as few vertixes as possible should cross over
(this is the part I have problems with).

---

Clarification of Question by michael248-ga on 05 Oct 2006 08:03 PDT

Ok since I have increased the price to $200 the drawing part of the
task is mandatory - that is, the algorithm with a java implementation
will be all that is accepted - use of libraries is still acceptable.

---

Request for Question Clarification by theta-ga on 05 Oct 2006 08:37 PDT

Hi michael248-ga,
   I have started work on a sample app to meet your requirements. I
just needed some clarifications and further information from you:
     - Is having each node as a sub-component so that we can add
MouseOver, MouseAction events a hard requirement? This may turn out to
be way more complicated than necessary, and with 20000 vertices and
400 nodes on screen, I doubt that it would be really useful.
     - I am planning on utilising an external library for this task
and providing the output graph as a JPanel. Would that be ok?

Thanks,
Theta-ga
:)

---

Clarification of Question by michael248-ga on 05 Oct 2006 09:40 PDT

Having the nodes as separate components is a hard requirement - I
appreciate that when theres a lot of nodes the usefulness of it will
diminish but initially the graph will only be representing (say 20
nodes) and being able to access information by clicking on the nodes
will be important....

Outputting as a Jpanel and using an external library is fine - please
make sure the library is free for personal use and the source files
for the library will be required so I can make modifications as
necessary.

---

Request for Question Clarification by theta-ga on 05 Oct 2006 21:31 PDT

Hi michael248-ga,
  I'll try to get an initial sample app up and running over the
weekend, and then we can take it from there.
  Is their a particular collection or data structure you intend to use
to provide the input data?
Regards,
Theta-ga

---

Clarification of Question by michael248-ga on 06 Oct 2006 00:42 PDT

Hey

I just planned to use a 2 dimensional int array - so int[x][y], if you
would prefer someother data collection then let me know and i'll use
that instead - pretty indifferent either way.... Thanks :)

---

Request for Question Clarification by theta-ga on 06 Oct 2006 01:44 PDT

I just wanted to know if you would be using a particular data
structure to pass in the vertices names or colors with the connection
data (for e.g., which colors do the numbers 0 and 1 signify)?
Also, from the sample connection grid you have provided, it would
appear that all the vertices are *always* connected to each other. If
this is not the case, then we could use the number 0 to indicate no
connection, and the other numbers to denote a connection and the
color.
Another point is that the grid would actually specify the color of the
edge connecting two vertices. So how will the color of the actual
vertex be decided?

Thanks,
Theta-ga
:)

---

Clarification of Question by michael248-ga on 06 Oct 2006 02:49 PDT

These are all good points.

Initially I wasnt intending to change the colour of the nodes but this
could be very useful. I think I'll create a data class which will have
the name of the vertex, the colour of the node (as a coded 0,1,2,3 etc
- set these colours to whatever you want and I can change them), and
then inside this data class will be an int array with the connection
values to other nodes (again 0 will be no connection, 1,2,3, etc
various colours - set them to whatever you want).

I'll put the data class I intend to use up in a couple of hours and
I'll send all the data as an array of these objects.

Hope this doesnt complicate things too much.

---

Clarification of Question by michael248-ga on 06 Oct 2006 13:43 PDT

theta - just done some searching and think this software would be
perfect (im still willing to pay for a nice java integration, however
if your code is adequate by itself then please feel free to ignore):

http://www.aisee.com

---

Request for Question Clarification by theta-ga on 09 Oct 2006 13:55 PDT

Hi michael248-ga,
  I was planning to use the Java Universal Network/Graph Framework
(JUNG) for the task at hand. It is a free, open source library, that
supports creating large graphs, multiple configurable layout
algorithms, and (with some effort) mouse events for the edges and
vertices. In short, I think it will meet all your current
requirements. [see http://jung.sourceforge.net/ ]
  If you still want me to explore the use of aiSee with the view of
integrating it with java, I will be glad to do so.

Regards,
Theta-ga
:)

---

Clarification of Question by michael248-ga on 10 Oct 2006 08:26 PDT

If your happy with it then im happy with it. :)

---

Clarification of Question by michael248-ga on 23 Oct 2006 02:22 PDT

theta-ga: just wondered how this was coming along? Its not immediately
pressing but theres been no action for the past 10 days and just
wondering if your still working on it?

---

Request for Question Clarification by theta-ga on 24 Oct 2006 17:42 PDT

Hi michael248-ga,
  I was shifting houses last week, and so could not devote any time to
this. I'm working on it now, and plan to post the final code by
tomorrow. Given below are the assumptions and feature requests I am
working with, based on your previous clarifications and comments:
   - Code compatibility: J2SE 1.4
   - Vertices and Edges will be coloured
   - Edge arrows are not required/do not matter
   - I have created a data class that encapsulates all the information
required for one vertex(name, color and array of edges). A list of
this vertex data class objects is provided whenever a graph needs to
be created.
   - Notification of mouse events for the graph.

Regards,
Theta-ga
:)

---

Clarification of Question by michael248-ga on 25 Oct 2006 01:03 PDT

Yup thats all fine.

Michael

Hi michael248-ga,
  I have uploaded a demo application which shows how the jung library
can be utilised to meed your needs. You can download the code from:
http://rapidshare.com/files/752229/graphDemo.zip.html


BUILDING THE CODE
-----------------
  The zip file contains the source java files, as well as the jar
dependencies for the code.
  Commandline for building the code:
       javac *.java -cp
".\jars\jung-1.7.4.jar;.\jars\commons-collections-3.2.jar;.\jars\colt.jar"
-source 1.4

  Commandline for running the code
       java -cp ".;.\jars\jung-1.7.4.jar;.\jars\commons-collections-3.2.jar;.\jars\colt.jar"
ColoredGraphDemo


About the demo
--------------
  The demo creates a window which contains a combobox and a panel
displaying a randomly generated graph. You can select a layout
algorithm from the combobox, and the displayed graph is redisplayed
with the selected layout algorithm.
  This way you can see which layout algorithm best suits your needs,
and use that in your code.

The JUNG library
----------------

Details on the JUNG(Java Universal Network/Graph Framework) library
can be found at [http://jung.sourceforge.net/index.html]
The library provides a number of classes to allow you to configure the
generated graph to your liking.
It provides a Graph class, which contains a set of Vertex and Edge
objects. There are multiple types of Graphs provided (directed,
undirected, sparse, etc.) and each of these have their corresponding
types of Vertex and Edge classes. The demo code uses an
UndirectedSparseGraph.
The VisualizationViewer class is a JPanel which is used to display the
graph, and can be configured to capture mouse events on the graph as
well as allow the user to interact with it.
The VisualizationViewer utilizes the PluggableRenderer classto
actually render the graph. The PluggableRenderer is very extensible
and can be used to specify custom methods for rendering, coloring, and
labelling the vertices and edges.

To see what can be done with the library, see the examples code and
images available at:http://jung.sourceforge.net/applet/index.html and
http://jung.sourceforge.net/pmwiki/index.php/Main/ImageGallery

You can find the Jung API documentation at:
http://jung.sourceforge.net/doc/api/index.html
Download the library from: http://jung.sourceforge.net/download.html


Explaination of the code
------------------------
The code contains the following classes:
  - ColoredGraphDemo: The main class. Responsible for setting up the
app window and displaying the graph.
  - VertexInfo: This is the data class which stores information about
one vertex and the edges associated with it. It stores the label for
the vertex, its color index, and the int array representing the edges
and their colour.
  - PopupGraphMousePlugin: This is a custom class which is used to
react to mouse events on the graph. Right now it just detects whether
the user has right clicked on a vertex or an edge, and displays the
corresponding popup menu on the screen.
  - GraphVisualizer: This is the class you can use in your code to
work with the Jung library. It contains the method to create a graph
from a list of vertexinfo objects. It also contains custom methods for
rendering the vertices and the edges in the specified color.

The code contains relevant comments and should be easy to follow. For
your reference, I am including the GraphVisualizer code below:
---------------- GraphVisualizer.java -------------------
import edu.uci.ics.jung.exceptions.ConstraintViolationException;
import edu.uci.ics.jung.graph.Edge;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.Vertex;
import edu.uci.ics.jung.graph.decorators.AbstractEdgePaintFunction;
import edu.uci.ics.jung.graph.decorators.StringLabeller;
import edu.uci.ics.jung.graph.decorators.VertexPaintFunction;
import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge;
import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph;
import edu.uci.ics.jung.graph.impl.UndirectedSparseVertex;
import edu.uci.ics.jung.utils.PredicateUtils;
import edu.uci.ics.jung.utils.UserData;
import edu.uci.ics.jung.visualization.*;
import edu.uci.ics.jung.visualization.control.PluggableGraphMouse;
import org.apache.commons.collections.Predicate;

import java.awt.*;
import java.lang.reflect.Constructor;
import java.util.ArrayList;
import java.util.List;

class GraphVisualizer
{
    private static final String COLOR_KEY = "color";
    private static final String LABEL_KEY = "label";

    protected static Graph jungGraph;
    protected static VisualizationViewer graphVisualizationViewer;
    private static StringLabeller vertexLabeller;

    // creates a graph from the list of vertices provided
    // Also creates and initializes the Visualization for the graph
    // returns a JPanel containing the rendered graph
    public VisualizationViewer GetGraphVisualization(List nodes, List colorPalette)
    {
        jungGraph = createJungGraph(nodes, colorPalette);

        // Set the rendering properties for the graph visualization
        final PluggableRenderer pluggableRenderer = new PluggableRenderer();
        pluggableRenderer.setVertexPaintFunction(new CustomVertexPaintFunction());
        pluggableRenderer.setEdgePaintFunction(new CustomEdgePaintFunction());
        pluggableRenderer.setVertexStringer(vertexLabeller);
        graphVisualizationViewer = new VisualizationViewer(new FRLayout(jungGraph),
                                     pluggableRenderer);

        // Specify a picker used to determine whether the user has selected
        // an edge or a vertex
        graphVisualizationViewer.setPickSupport(new ShapePickSupport());

        // Add mouse support to the graph Viewer so we can listen to the
        // relevant mouse events for the graph
        PluggableGraphMouse gm = new PluggableGraphMouse();
        graphVisualizationViewer.setGraphMouse(gm);
        gm.add(new PopupGraphMousePlugin());   // our custom menu display

        return graphVisualizationViewer;
    }

    // called whenever the user selects a layout class from the combobox
    // Responsible for setting the layout to the instance of the selected class.
    public void ChangeGraphLayout(Class lay)
    {
        try
        {
            Constructor constructor = lay.getConstructor(new Class[]{Graph.class});
            Object o = constructor.newInstance(new Object[]{jungGraph});
            Layout l = (Layout) o;
            graphVisualizationViewer.stop();
            graphVisualizationViewer.setGraphLayout(l);
            graphVisualizationViewer.restart();
            graphVisualizationViewer.stop(); // put in to stop the layout algo from
                                            // iteratively updating
the visualization
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }
    }

    // Creates vertices and edges from the list of vertexinfos
    // and adds them to the graph
    private Graph createJungGraph(List vertexInfoList, List palette)
    {
        final int vertexCount = vertexInfoList.size();
        Graph graph = new UndirectedSparseGraph();
        List vertexList = new ArrayList(vertexCount);

        // Add all the vertices to the graph first
        // we need to do this because we cant add edges to a graph
        // unless all the vertices involve have been added to the graph
        for (int i = 0; i < vertexCount; i++)
        {
            vertexList.add(new UndirectedSparseVertex());
            graph.addVertex((Vertex) vertexList.get(i));
        }

        // Create a StringLabeller that we will use to add labels to every vertex
        vertexLabeller = StringLabeller.getLabeller(graph, LABEL_KEY);

        for (int i = 0; i < vertexCount; ++i)
        {
            VertexInfo vertexInfo = (VertexInfo) vertexInfoList.get(i);
            UndirectedSparseVertex vertex = (UndirectedSparseVertex)
vertexList.get(i);

            // Store color information inside the vertex
            vertex.addUserDatum(COLOR_KEY, getColor(palette,
vertexInfo.color), UserData.CLONE);

            try
            {
                // add the label to the vertex
                vertexLabeller.setLabel(vertex, vertexInfo.label);
            } catch (StringLabeller.UniqueLabelException e)
            {
                e.printStackTrace();
            }
            // add all the edges for this vertex
            for (int j = 0; j < vertexInfo.edges.length; j++)
            {
                int connectedNodeValue = vertexInfo.edges[j];
                if (connectedNodeValue != 0)
                {
                    UndirectedSparseEdge edge = new
UndirectedSparseEdge(vertex, (UndirectedSparseVertex)
vertexList.get(j));
                    edge.addUserDatum(COLOR_KEY, getColor(palette,
connectedNodeValue), UserData.CLONE);
                    try
                    {
                        graph.addEdge(edge);
                    } catch (ConstraintViolationException e)
                    {
                        // Incase an edge already exists between the two vertices
                        // an exception will be thrown
                        e.printStackTrace();
                        final Predicate predicate = e.getViolatedConstraint();
                        PredicateUtils.evaluateNestedPredicates(predicate, edge);
                    }
                }
            }
        }

        return graph;
    }

    // Selects the specified colr from the palette provided
    // returns black in case of any error
    private Color getColor(List palette, int colorIndex)
    {
        Color defaultColor = Color.black;
        if (colorIndex < 0 || colorIndex >= palette.size())
        {
            return defaultColor;
        }
        Color color = (Color) palette.get(colorIndex);
        if (color == null)
        {
            return defaultColor;
        }

        return color;
    }

    // Custom method provided to a PluggableRenderer
    // Used to paint an edge with the user specified color
    public static class CustomEdgePaintFunction extends AbstractEdgePaintFunction
    {
        public Paint getDrawPaint(Edge e)
        {
            return (Color) e.getUserDatum(COLOR_KEY);
        }
    }


    // Custom method provided to a PluggableRenderer
    // Used to draw and fill a vertex with the user specified color
    public static class CustomVertexPaintFunction implements VertexPaintFunction
    {
        public Paint getFillPaint(Vertex vertex)
        {
            return (Color) vertex.getUserDatum(COLOR_KEY);
        }

        public Paint getDrawPaint(Vertex vertex)
        {
            return (Color) vertex.getUserDatum(COLOR_KEY);
        }
    }
}
---------------- End of GraphVisualizer.java -------------------

=================================================================

Hope this helps!
Play with the code, and if you need any clarifications, just ask!

Regards,
Theta-ga
:)

I seriously doubt I'd be able to help, but it may clarify your problem
much better for people who are likely to be able to help if you maybe
did a quick and dirty mock-up of what a general graphical output of
the algorithm should look like. Just throw something together in Paint
or whatever based on the 2D array example you already gave. I really
think it might get more people interested, and maybe even get someone
thinking they can do it.

It may actually be clear enough already but I don't quite get what you
want, so maybe a general idea of example output would be good. Just a
thought.

So the matrix you want to read is the adjacency matrix which indicates
that in your case nodes (or vertices) a and e are connected by an
edge? Depending on the number at (a,e) you want to color the vertex a
certain way?
If you want to draw up to 400 nodes with 20000 edges it does not make
any sense to add arrowheads since you won't be able to see anything
anyways. If I understand you correctly I might me able to help. Let me
know.