Access an element in an adjacency list

[TheUnknown]

Is there a better way of finding an element's position in an adjacency list of a graph than storing its position and then comparing the whole array to find it?(pairs are already used)

 

I have a weighted graph and lets say I know that from A I can go to B and has a cost of 5.I used a 2d vector of pairs to store this.

 

Ex:

 

A: B-5,C-6,D-7 (explanation : A goes to B with a cost of 5 , it also goes to C with a cost of 6 etc...)

B: G-6 ,W-6

H: V-5

 

A goes to B , B goes to G and W.

What I want to do is find a way to access the memory of B without having to store it in a temporary array.Which means that I will need to search it every time to find it.

 

Any ideas?

 

EDIT-This isn't homework exercise by the way.

[Ciccioo]

what type of value is A?

you could make it so that everyone of your N nodes is identified by a numeric ID ranging from 0 to N-1

so your adjaciency array would be an array of lists, where adjaciency[X] would be the adj list for the node X

[TheUnknown]

what type of value is A?

you could make it so that everyone of your N nodes is identified by a numeric ID ranging from 0 to N-1

so your adjaciency array would be an array of lists, where adjaciency[X] would be the adj list for the node X

The real problem has numeric values to be honest.But they are not in order and they  are random  ( >100 )

 

EDIT-Plus its a vector.Not a simple array with 100 rows

 

I'll just assign the position of the node in an array and I'll search for it every time.Pretty lame for a programmer but it works...

[Ciccioo]

The real problem has numeric values to be honest.But they are not in order and they  are random  ( >100 )

you could use a dictionary / hashmap / associative array, if your language provides a library for it

[MrSuperb]

Is there a better way of finding an element's position in an adjacency list of a graph than storing its position and then comparing the whole array to find it?(pairs are already used)

 

I don't quite get what you are asking for (yet).

 

what element's 'position'?

what is the problem with storing the data in a adjacency matrix?

[Ciccioo]

EDIT-Plus its a vector.Not a simple array with 100 rows

Vectors exist because they're easier to manage than arrays, right?

Again, take a look at dictionaries

[wolfsinner]

I might have read your problem wrong, but here's a suggestion that might help you out.
A simple way is to store your graph as a set of lists of arcs. Many times an adjacency matrix is not efficient and if I understood your problem correctly, this is one of those times.
 
A rough example of what I mean follows.

class Arc {	private int cost;	private Node otherNode;	//constructors and getters}

 
Where Node is something along the lines of:

class Node {	private String name; //A, B, C, ...	//any other properties	private Arc [] edges;	//whatever code you need}

This way you can chain access to all of the nodes connected to the one you start with. Slight memory overhead but more efficient.

[SSL]

That's the tradeoff of an adjacency matrix vs adjacency list. Consider the time complexity of the operations that you will perform the most and pick the implementation that provides the most efficiency.

[TheUnknown]

I don't quite get what you are asking for (yet).

 

what element's 'position'?

what is the problem with storing the data in a adjacency matrix?

I want to know the element's position.adjacency matrix takes too much memory.

 

That's the tradeoff of an adjacency matrix vs adjacency list. Consider the time complexity of the operations that you will perform the most and pick the implementation that provides the most efficiency.

Adjacency matrix takes a lot of memory.The graph is huge and storing it in an adjacency matrix will feel unnecessary physical memory space

 

Vectors exist because they're easier to manage than arrays, right?

Again, take a look at dictionaries

Vectors are dynamic containers that store data.They give you the ability to access,manipulate or change the stored elements dynamically.I think they only exist in C/C++ and Java(not sure for Java though)

[TheUnknown]

I might have read your problem wrong, but here's a suggestion that might help you out.

A simple way is to store your graph as a set of lists of arcs. Many times an adjacency matrix is not efficient and if I understood your problem correctly, this is one of those times.

 

A rough example of what I mean follows.

*snip*

 

Where Node is something along the lines of:

*snip*

This way you can chain access to all of the nodes connected to the one you start with. Slight memory overhead but more efficient.

 

Storing the graph is not really my problem.I stored the graph using 2D vectors of pairs(you don't really care about pairs though)

So lets say the map(2d vector) looks like this

 

Vmap[0][0]: 5 Vmap[0][1] : 6

Vmap[1][0]:  8 Vmap[1][1]: 10

 

So lets say Vmap[0] is my a node.That node goes to 5 and 6.My problem is to find the position of the node 5 (Vmap[0][0]) in the array.So lets say its position is like Vmap[2].Somebody suggest me to use the actual value (5) as the position it self( ex Vmap[5]) but in my case the numbers are way more complex and can't be used to link to an address in the array.

 

[Midnight]

Just use a set, either C++ STL set or Java TreeSet or HashSet.

That's the problem with lists, right? You can't find stuff randomly due to the lack of keys or indices.

 

Vectors are dynamic containers that store data.They give you the ability to access,manipulate or change the stored elements dynamically.I think they only exist in C/C++ and Java(not sure for Java though)

ALL data structures should have the ability to access or change elements dynamically. It's not just vectors. The problem is the speed and memory usage.  Also, vectors, or arrayLists, exists for a LOT of languages. Java has two variants, Vector and ArrayList.

[MrSuperb]

Adjacency matrix takes a lot of memory.The graph is huge and storing it in an adjacency matrix will feel unnecessary physical memory space

 

how huge?

________

 

So you have a 2D vector. (e.g. vec[j])

vec essentially is another vector/list of nodes that haven an edge/arc to the node i

j is just an index for the connected node, but doesn't actually refer to the node j

Is this correct so far?

does i refer to an actual node or is it just an arbitrary index?

do you delete/add nodes/edges or why do you use a vector?

 

Now you want to get what?

a) the index j of a node in the vector vec[j]

or

b) the index i of a node in the vector vec[i]

 

???

 

maybe you can give a minimal example of you data structure in c++

[Midnight]

Storing the graph is not really my problem.I stored the graph using 2D vectors of pairs(you don't really care about pairs though)

So lets say the map(2d vector) looks like this

 

Vmap[0][0]: 5 Vmap[0][1] : 6

Vmap[1][0]:  8 Vmap[1][1]: 10

 

So lets say Vmap[0] is my a node.That node goes to 5 and 6.My problem is to find the position of the node 5 (Vmap[0][0]) in the array.So lets say its position is like Vmap[2].Somebody suggest me to use the actual value (5) as the position it self( ex Vmap[5]) but in my case the numbers are way more complex and can't be used to link to an address in the array.

 

 

That's not how adjacency lists work. If Vmap[0] is your A node, then I assume Vmap[1] is your B node, etc. If that's the case, then Vmap[0][0] DOES NOT go to 5, nor Vmap[0][1] to 6. The cost of going from 0 to 0 is 5 and 0 to 1 to 6.

 

You're not making any sense at all.

[MrSuperb]

You're not making any sense at all.

 

lol .... at least i am not the only one ...

[SSL]

So use a map of some sort to store the adjacency lists. Simple.

[TheUnknown]

That's not how adjacency lists work. If Vmap[0] is your A node, then I assume Vmap[1] is your B node, etc. If that's the case, then Vmap[0][0] DOES NOT go to 5, nor Vmap[0][1] to 6. The cost of going from 0 to 0 is 5 and 0 to 1 to 6.

 

You're not making any sense at all.

2D vector of pairs:

 

0: 6-62 7-68 2-98

1: 6-13 6-25 6-37 3-27 3-19 1-17

2: 5-13 5-25 5-37 2-27 2-19

3:

 

Are you satisfied?Now please stop feeling this thread with useless replies. 0 is a node 6 is the weight and 62 is the node that goes to.

 

[Midnight]

2D vector of pairs:

 

0: 6-62 7-68 2-98

1: 6-13 6-25 6-37 3-27 3-19 1-17

2: 5-13 5-25 5-37 2-27 2-19

3:

 

Are you satisfied?Now please stop feeling this thread with useless replies. 0 is a node 6 is the weight and 62 is the node that goes to.

 

 

Yeah, I'm satisfied. I don't know why you need to be so irate though.

 

Then it's easy. You find a node by vector's index. Done.

[TheUnknown]

Yeah, I'm satisfied. I don't know why you need to be so irate though.

 

Then it's easy. You find a node by vector's index. Done.

 

I am not irate.The fact is that I asked something else and you ppl are answering something else...

 

[MrSuperb]

2D vector of pairs:

 

0: 6-62 7-68 2-98

1: 6-13 6-25 6-37 3-27 3-19 1-17

2: 5-13 5-25 5-37 2-27 2-19

3:

 

Are you satisfied?Now please stop feeling this thread with useless replies. 0 is a node 6 is the weight and 62 is the node that goes to.

 

 

 

ok, so now you want to know the index/position of let us say the edge 7-68 in the 0: vector? (i.e. 1)

That is not possible.

[TheUnknown]

ok, so now you want to know the index/position of let us say the edge 7-68 in the 0: vector? (i.e. 1)

That is not possible.

 

Ik ,I am using a temporary vector to store there index/position.

[Midnight]

I am not irate.The fact is that I asked something else and you ppl are answering something else...

 

 

Because your first explanation doesn't make sense and nobody else seemed to know what you're asking.

[Midnight]

Ik ,I am using a temporary vector to store there index/position.

 

And why is this important, may I ask?

[SSL]

Is there some reason that the map solution won't work? Map the node label to an adjacency list? I mean, that is the question at hand here, right?

[wolfsinner]

Storing the graph is not really my problem.I stored the graph using 2D vectors of pairs(you don't really care about pairs though)

So lets say the map(2d vector) looks like this

 

Vmap[0][0]: 5 Vmap[0][1] : 6

Vmap[1][0]:  8 Vmap[1][1]: 10

 

So lets say Vmap[0] is my a node.That node goes to 5 and 6.My problem is to find the position of the node 5 (Vmap[0][0]) in the array.So lets say its position is like Vmap[2].Somebody suggest me to use the actual value (5) as the position it self( ex Vmap[5]) but in my case the numbers are way more complex and can't be used to link to an address in the array.

 

 

Instead of storing 5, store a reference to the node (its corresponding array in Vmap) and not its value. Ideally you would store it in a more meaningful way though (like the one I suggested), but if it absolutely must be done this way, then that's how you'd do it.

 

Alternatively (and this is not a great idea), an hash table will allow you to index your data on a more complex "id".

 

I strongly suggest making it more meaningful though (like storing lists of arcs to nodes, and storing data pertaining to a node in its own structure). There's only so much you can represent with a single value.