Question

I'm writing a Java program to develop a graph representation. One of the functions that I need to build is to return the weight of a vertex that is adjacent to another vertex but I don't know how to write the code to test two different weights.

import java.util.*;

/**
* A representation of a graph.
* Assumes that we do not have negative cost edges in the graph.
*/
public class MyGraph implements Graph {
private Collection myVertices; // the vertices in this graph private Collection myEdges; // the edges in this graph /** * Creates a MyGraph object with the given collection of vertices * and the given collection of edges. * * @param v a collection of the vertices in this graph * @param e a collection of the edges in this graph */ public MyGraph(Collection v, Collection e) { myVertices = v; myEdges = e; } public MyGraph() { } /** * Return the collection of vertices of this graph * * @return the vertices as a collection (which is anything iterable) */ public Collection vertices() { return myVertices; } /** * Return the collection of edges of this graph * * @return the edges as a collection (which is anything iterable) */ public Collection edges() { return myEdges; } /** * Return a collection of vertices adjacent to a given vertex v. * i.e., the set of all vertices w where edges v -> w exist in the graph. * Return an empty collection if there are no adjacent vertices. * * @param v one of the vertices in the graph * @return an iterable collection of vertices adjacent to v in the graph * @throws IllegalArgumentException if v does not exist. * */ public Collection adjacentVertices(Vertex v) { Set result = new HashSet(); if (!myVertices.contains(v)) { throw new IllegalArgumentException("Vertex does not exist"); } result.addAll(outNeighbors(v)); result.addAll(inNeighbors(v)); return result; } /** * Return a collection of vertices that are reachable from a given vertex v. * A vertex is reachable if a path exists from v to the other vertex. * * @param v one of the vertices in the graph * @return an iterable collection of vertices that are reachable from v in the graph */ public Collection reachableVertices(Vertex v) { Set result = new HashSet(); Set frontier = new HashSet(); Set nextFrontier = new HashSet(); // a vertex is reachable to itself (path length 0) result.add(v); frontier.add(v); while (!frontier.isEmpty()) { Iterator itr = frontier.iterator(); // start at level 0, get all level 1 nodes // union the nodes into the result set // build up level 1 while (itr.hasNext()) { Vertex current = (Vertex) itr.next(); Set outNodes = outNeighbors(current); // remove all outneighbors we've already visited outNodes.removeAll(result); nextFrontier.addAll(outNodes); outNodes.clear(); } result.addAll(nextFrontier); frontier.clear(); frontier.addAll(nextFrontier); nextFrontier.clear(); } return result; } /** * Returns a topological sorting of the vertices in the graph. * * @return an ordered list of vertices in topological sort order */ public List topologicalSort() { return null; } /** * Test whether vertex b is adjacent to vertex a (i.e. a -> b) in a directed graph. * Assumes that we do not have negative cost edges in the graph. * * @param a one vertex * @param b another vertex * @return cost of edge if there is a directed edge from a to b in the graph, * return -1 otherwise. * @throws IllegalArgumentException if a or b do not exist. */ public int isAdjacent(Vertex a, Vertex b) { if (!myVertices.contains(a) || !myVertices.contains(b)) { throw new IllegalArgumentException("Vertex a or b does not exist"); } // Test that the weight of the first edge is equal to the second edge return -1; }

Answer 1

@e.mccormick

Answer 2

The function that I'm having a problem with is the isAdjacent which should return the weight if two vertices are adjacent or a -1 if they are not.

Answer 3

In general, you would test them one at a time and store them then do whatever is needed to average or add them as needed. Obviously the first ting it needs to call is the adjacency test because if that fails, skip the rest.

Answer 4

I don't know how I can access the weight class member to compare the two vertices if they are adjacent or not

Answer 5

So you don't have a way to calculate the weight?

Answer 6

There is no need to add or average... my instructor just wants to me test if two vertices are adjacent and return the weight if they are or a -1

Answer 7

I'm storing weight as a class variable in the Vertex class

Answer 8

Sorry Edge class

Answer 9

/**
* Representation of a directed graph edge.
*/
public class Edge {
public final Vertex from;
public final Vertex to;
public final int w;

Answer 10

OK, then what is the problem in getting it?

Answer 11

The problem is I'm not sure how to write the test

Answer 12

Well, the test is if they are adjacent, right?

Answer 13

Correct

Answer 14

You have something that returns a list of adjacent things, right?

Answer 15

Or collection, so be more precise...

Answer 16

I was thinking something like if(outNeighbors(a) == outNeighbors(b) // they are adjacent but that doesn't look right

Answer 17

/** * Return a collection of vertices adjacent to a given vertex v.
* i.e., the set of all vertices w where edges v -> w exist in the graph.

That one is the key.

Answer 18

Yeah, I use a Set or a HashSet

Answer 19

I was looking at that function to determine how I would need to write the test and then i get stuck when I'm trying to access the weight variable in the Edge class

Answer 20

Well, if you have vertex v and collection c of all vertexes next to v, then if vertex w exists in collection c then w is next to v.

Answer 21

if (adjacentVertices(a).equals(adjacentVertices(b)))

Answer 22

That is how I started but I know I need to compare the weights and not just the vertices

Answer 23

ou don't need to:

"return the weight of a vertex that is adjacent to another vertex"

Answer 24

The if it is adjacent just determines if you return the weight or -1.

Answer 25

If I'm understanding how a graph works... to check if two vertices are adjacent, they would be on opposite ends and have the same weight

Answer 26

This is my diagram I am using to write the program.

Answer 27

Umm... the weight does not need to match. They are on opposite ends of an edge.

Answer 28

What is meant by this line? * @return cost of edge if there is a directed edge from a to b in the graph,
* return -1 otherwise.

Answer 29

I thought cost of edge was weight...

Answer 30

No clue.

Answer 31

I'm trying to figure out what I need to return in the function and what I'm testing.

Answer 32

What you are testing is what is stated:
return the weight of a vertex that is adjacent to another vertex

It says you need to see if they are adjacent. That is what you are testing. It also says what to return. The weight of it, but only if it is adjacent.

Answer 33

My if statement was correct. I need to create a new collection to hold the result and then return the result with the weight if they are adjacent

Answer 34

Why would you return a collection? The instructions are to return the weight. In what you showed, the weight was an int.

Answer 35

Well, I can only access the weight through the Edge class and my function does not use Edge but Vertex

Answer 36

public int isAdjacent(Vertex a, Vertex b) {

if (!myVertices.contains(a) || !myVertices.contains(b)) {
throw new IllegalArgumentException("Vertex a or b does not exist");
}

// Test that the weight of the first edge is equal to the second edge
if (adjacentVertices(a).equals(adjacentVertices(b)))
return -1;

}

Answer 37

// Test that the vertices are adjacent, if they are return the weight, or -1
if (adjacentVertices(a).equals(adjacentVertices(b))) {

} else {
return -1;
}
}

Answer 38

Inside the if statement, I'm not sure how to return the weight

Answer 39

The adjacentVertices functions returns a collection of the vertices that are adjacent to the given vertex

Answer 40

Well, has anything you have studied defined how you are suposed to assign a vertex weight. There is more that one way to do so...

Answer 41

I defined the vertex weight for my graph object in the constructor

Answer 42

ublic class GraphTester {
public static void main(String[] args) {
System.out.println("This is the graph tester.");

Vertex v1 = new Vertex("A");
Vertex v2 = new Vertex("B");
Vertex v3 = new Vertex("C");
Vertex v4 = new Vertex("D");

Set<Vertex> nodes = new HashSet<Vertex>();
nodes.add(v1);
nodes.add(v2);
nodes.add(v3);
nodes.add(v4);

Edge e1 = new Edge(v1, v2, 1); // A to B
Edge e2 = new Edge(v1, v3, 2); // A to C
Edge e3 = new Edge(v2, v3, 5); // B to C
Edge e4 = new Edge(v2, v4, 6); // B to D
Edge e5 = new Edge(v3, v4, 8); // C to D

Set<Edge> edges = new HashSet<Edge>();

edges.add(e1);
edges.add(e2);
edges.add(e3);
edges.add(e4);
edges.add(e5);

Graph g = new MyGraph(nodes, edges);

Answer 43

Ok... so you do have the vertex weight stored somewhere.

Answer 44

That is my graph tester class

Answer 45

I don't see a vertex weight in there.

Answer 46

It is stored as the third parameter to the constructor

Answer 47

That is the edge weight. Edge weight is not vertex weight.

Answer 48

Oh we don't have a vertex weight. We just defined edge weight, as far as I know

Answer 49

Well, it is asking for the vertex weight... vertex weight can be set, computed, etc. So unless you have some defined way to figure out the vertex weight I do not see a way to return it.

Answer 50

/**
* Test whether vertex b is adjacent to vertex a (i.e. a -> b) in a directed graph.
* Assumes that we do not have negative cost edges in the graph.
*
* @param a one vertex
* @param b another vertex
* @return cost of edge if there is a directed edge from a to b in the graph,
* return -1 otherwise.
* @throws IllegalArgumentException if a or b do not exist.
*/

Answer 51

Here, this is a short example of vertex weights:
http://reference.wolfram.com/language/ref/VertexWeight.html

Answer 52

I may be wrong but it sounds like my instructor wants the edge weight...

Answer 53

Well, you have said two different things:

"I'm writing a Java program to develop a graph representation. One of the functions that I need to build is to return the weight of a vertex that is adjacent to another vertex but I don't know how to write the code to test two different weights."

That says vertex weight.

"The function that I'm having a problem with is the isAdjacent which should return the weight if two vertices are adjacent or a -1 if they are not."

That is some undefined weight. So I am not even sure which is correct.

Answer 54

Yeah, I should be more clear. My instructor wrote the classes for Graph, Vertex, Edge, and MyGraph. He left the rest of the implementation for the graph functions up to me. In the function adjacentVertices, I think what he is asking is that if the two vertexes are adjacent to each other, return the weight but if they are not, return -1.

Answer 55

OK, so where you mistyped was at the start and the only weight that need concern us is the egde weight.

Answer 56

Yes, that is right.

Answer 57

That is why I was confused when you brought up vertex weight because we haven't discussed that in class and only looked at edge weight.

Answer 58

OK. So first you need to find if they are adjacent, if they are not, return -1. If they are, then you need to find which edge they make and return the weight of that edge.

Answer 59

Ok, so to return if they are adjacent, I would write a test like if (adjacentVertices(a).equals(adjacentVertices(b)) // they are equal so return the weight, otherwise return -1

Answer 60

I understand how to test if they are adjacent now, but I'm not sure how to find which edge out of the vertices

Answer 61

Well, you don't need all the adjacent ones to match. You only need to see if adjacentVertices(a) contains b.

Answer 62

So the correct way to test would actually be if adjacentVertices(a).contains(adjacentVertices(b))

Answer 63

no. You do not need the adjacent vertices of b at all. You just need to know if adjacentVertices(a).contains(b).

Answer 64

Isn't that what I wrote with the contains?

Answer 65

No. You tested too much.

Answer 66

I'm testing for the adjacent vertices of a AND b

Answer 67

No. You only want to know if a is adjacent to b. Not if a and b share all adjacencies.

Answer 68

if (adjacentVertices(a).contains(b)) // the two are adjacent

Answer 69

when I find that a is adjacent to b, now I need to find out what edge that is and return the weight

Answer 70

Yes.

Answer 71

And your else is to return -1.

Answer 72

So you may want to write a sepeate method for finding what edge is defined by two verticies.

Answer 73

Ok, I don't have a method for that just a method to return the edges of all vertices. That is why I am not completely sure how to write the code right now.

Answer 74

Yes, well, sadly you will need to cycle through the edges, since that is what is stored, and on any edge with one vertex concerned, see if it has the other.

Answer 75

public Set<Edge> edgeInVertices(Edge a, Edge b) and I will use a foreach loop to cycle through the edges

Answer 76

Would either of these methods work for what I'm trying to do?

// When provided with a vertex called v
// It should return a set of all the "incoming"
// neighbor vertexes of v
public Set<Vertex> inNeighbors(Vertex v) {
Set<Vertex> result = new HashSet<Vertex>();
for (Edge e : myEdges) {
if (e.to.equals(v)) {
// This is an "in-neighbor"
result.add(e.from);
}
}

return result;
}

public Set<Vertex> outNeighbors(Vertex v) {
Set<Vertex> result = new HashSet<Vertex>();
for (Edge e : myEdges) {
if (e.from.equals(v)) {
// This is an "in-neighbor"
result.add(e.to);
}
}

return result;
}

Answer 77

public Set<Edge> edgeNeighbors(Vertex a, Vertex b) {
Set<Edge> result = new HashSet<Edge>();

for (Edge edge: myEdges) {
if (myEdges(a).equals(myEdges(b)) {
result.add(edge.to);
}
}
}

Answer 78

Am I even on the right track? @e.mccormick

Answer 79

Well, since you have a test set, why not see if it gives you the results you would expect.

Answer 80

I would be asking my instructor for help but he is in the hospital so I really appreciate you taking the time to help me with this program. I'm also pretty rusty at Java.

Answer 81

Well, you showed a valid test set. That is a really good tool. You can just use it to test some valid and invalid pairs and see if you get what you expect.