Java Glossary : graph

Java definitions: 0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

You are here : home : Java Glossary : G words : graph.

graph

To most people when they hear the word graph they think of a traditional x-y graph with ordinate and abscissa. There are packages for creating such graphs, along with bar graphs, such as:

Batik - SVG Toolkit ¤ JasperReports ¤ JCharts ¤ JClass Chart by Quest, née Sitraka, née KL Group, ¤ JFreeChart ¤ JFreeReport ¤ JGraph ¤ JMSL ¤ Ptolemy Plot ¤ Quadbase ExpressChart ¤ SAS/GRAPH

However, when computer scientists use the term graph, they are usually thinking in term of nodes and their connections called edges. Trees and linked lists are a special types of graph. The edges can be unidirectional, (called directed) or bidirectional (called Hamilton). The connections can contain loops back to where you started (cyclic), or not (acyclic). They can have several pieces not connected to each other (disconnected) or may be all in one piece (connected). Many mathematical algorithms are conceptualised in terms of painting the connections between the different nodes to put them into different categories, e.g. red-black trees. Colouring a graph does not mean creating an x-y graph in many colours for a Powerpoint presentation. That should be enough to get you started researching this fascinating branch of mathematics.

The most common ways to represent graphs are by numbering the nodes and edges between them:

Connection matrix: boolean array of size NxN, where N is number of nodes. Entry [x,y] is true if there is an edge between nodes x and y. Consumes a lot of space when N is large, but quick for checking existence of edges between given nodes. You can compress it using a BitSet.
Edge list: a list of pairs. (i.e. Edge class with fields x and y), if (x,y) is present, there is an edge between nodes x and y. If you have unconnected nodes, you need a separate list of nodes. The most space-efficient representation for sparse connections, but slow for lookups.
Connectivity list: for each node, you have an ArrayList of all the nodes which are directly connected to it by an edge. This is still fairly space-efficient and nearly as fast for lookups as the matrix (possibly faster when doing a traversal since you always iterate over the list of nodes connected to the current one anyway.)

BFO ¤ Comparison of charting packages ¤ NIST glossary ¤ SVG

home	Canadian Mind Products
	mindprod.com IP:[24.87.56.253]
	Your IP:[80.134.30.163]
	You are visitor number 2040.
	Please send errors, omissions and suggestions
	to improve this page to Roedy Green.
	You can get a fresh copy of this page from:	or possibly from your local J: drive mirror:
	http://mindprod.com/jgloss/graph.html	J:\mindprod\jgloss\graph.html