(u,v) (v,u) problem in adjList

[Lindsey Joseph]

So I read about the "reverse graph" and I was wondering if when we
load the graph, we can create a separate graph that is undirected.
Meaning, we would create another ArrayList with GraphNodes (in our
case) where these graph nodes, rather than having an incoming and
outgoing field for edges, would just have a list of edge to be used in
maxst(). Is this allowed even though it will affect our loading time
significantly?

Also, could the" reverse graph" be explained in more detail? In
addition, some of the TA's said you could hash on the fly in order to
see if (u,v) also has a valid (v,u)? How would this be implemented?

Lindsey

[Robert Escriva]

I would suggest your adjacency list datastructure be implemented
something like:

[ (A, [B, C], [D, E]),
(B, [], [A]),
(C, [D], [A]),
(D, [A], [C])
(E, [A], [])
]

Notice how each vertex in parens () has two lists. One for outgoing
edges, and one for incoming edges.

This comes from graph:

A B
A C
C D
D A
E A

You now have access to the incoming and outgoing edges of each vertex.
I do not recommend keeping an undirected graph next to the other graph.

-Robert

[Lindsey Joseph]

That is exactly what I have, however, I don't understand how to
implement MST in log time if we have to check to see if if the both
edges exist, so wouldn't you have to search through the incoming and
outgoing edges which would be O(n) time? How can you make it log time?

[Teddy Ni]

Are you asking about log time retrieval out of a priority queue?

Teddy

[Nikos Karampatziakis]

I think the question is about finding if two vertices u and v are
connected both as u->v and v->u. One way to do this is to use binary
search.

-Nikos

[Robert Escriva]

I believe the original question is about merging u-v and v-u to make the
sum. OP, if this is not the case, let me know and I'll answer any other
question instead.

Here's how I merge incoming and outgoing edges:

m = hashmap from (int, int) to int

for each vertex:
for each incoming edge from, to, weight:
if from < to:
add (from, to) -> weight to hashmap (making sure to account
for the possibility that it exists).
else:
add (to, from) -> weight in the same way as the above.
do the same for the outgoing edges of the vertex

Convert m to a sorted array.

-Robert

[Shane Jarvie]

How do you create a hashmap that takes in a pair(int, int) as its key?
I cannot figure out how to create it. I tried

Hashmap<(Integer,Integer),Integer> = new Hashmap<(Integer,Integer),
Integer>();

but java seems to not like that.

On May 7, 4:21 pm, Robert Escriva <escr...@cs.cornell.edu> wrote:
> I believe the original question is about merging u-v and v-u to make the
> sum.  OP, if this is not the case, let me know and I'll answer any other
> question instead.
>
> Here's how I merge incoming and outgoing edges:
>
> m = hashmap from (int, int) to int
>
> for each vertex:
>     for each incoming edge from, to, weight:
>         if from < to:
>             add (from, to) -> weight to hashmap (making sure to account
>             for the possibility that it exists).
>         else:
>             add (to, from) -> weight in the same way as the above.
>     do the same for the outgoing edges of the vertex
>
> Convert m to a sorted array.
>
> -Robert
>
>
>
>
>
>
>
> On Sat, May 07, 2011 at 03:56:20PM -0400, Nikos Karampatziakis wrote:
> > I think the question is about finding if two vertices u and v are
> > connected both as u->v and v->u. One way to do this is to use binary
> > search.
>
> > -Nikos
>
> > On Sat, May 7, 2011 at 3:37 PM, Teddy Ni <tn...@cornell.edu> wrote:
> > > Are you asking about log time retrieval out of a priority queue?
>
> > > Teddy
>

[Shane Jarvie]

I tried creating a seperate class Pair, which takes in the (from,to)
integer pair, and used that as my key. But when I try to create pairs
in the form (to,from), the map does not recongize them even if the map
does contain a (from,to) that is equal to my (to,from). Is it an issue
with hashcodes?

[Nikos Karampatziakis]

On Sat, May 7, 2011 at 11:06 PM, Shane Jarvie <shane....@gmail.com> wrote:
> I tried creating a seperate class Pair, which takes in the (from,to)
> integer pair, and used that as my key. But when I try to create pairs
> in the form (to,from), the map does not recongize them even if the map
> does contain a (from,to) that is equal to my (to,from). Is it an issue
> with hashcodes?
>

hashcode() and equals() need to be implemented appropriately for the pair.

-Nikos

[Joshua Hagins]

Also, you could just use an array of two integers as the key...