CODEWITHSUNDEEP
javagraphgraph-theorydirected-graph
xiao
xiao

Reputation: 1758

What is the most efficient way to store a non-directed graph?

As the title says.. What is the most efficient way to store a connected graph in java?

For example lets say I have multiple locations connecting to each other in various ways and I have to traverse through the graph to see if it's connected.. any help/comment would be helpful thanks!

Upvotes: 1

Views: 4170

Answers (5)

CurtainDog
CurtainDog

Reputation: 3205

Am I missing something? The data is already a graph, just serialize it.For the question as written talk of matrices is completely premature.

Upvotes: 0

darioo
darioo

Reputation: 47183

Using an incidence or adjacency matrix will do the trick.

If you use an adjacency matrix, a sparse matrix might be efficient to use, if you have a lot of nodes. Colt provides a sparse matrix implementation. Info taken from this SO post.

Also, I've used JUNG sucessfully before, so you might want to take a peek under the hood to see how they've implemented directed graphs.

Upvotes: 1

Assaf
Assaf

Reputation: 1346

For lookup efficiency - use a boolean matrix (true if there is an arc connecting the nodes, false if there isn't). For memory efficiency define one of your object properties as a (dynamic) list of objects its pointing to. Note the latter will only help if you have a LOT of nodes in your graph.

Upvotes: 0

Péter Török
Péter Török

Reputation: 116266

One often used representation is a matrix (two dimensional array) indexed by all the nodes in the graph, where M[i,j] == true if there is a directed edge from node i to j. A variation on the theme is to store the length / weight of the edge between the two nodes (where a missing edge may be represented by the value -1).

Upvotes: 5

Jean-Bernard Pellerin
Jean-Bernard Pellerin

Reputation: 12670

use an adjacency matrix without the symmetry, thereby representing direction instead of simple adjacency.

Upvotes: 1

Related Questions