Logic and if statement Question

Question

Suppose that we are given a graph, in which V is the set of vertices and Edge(x, y) is a predicate which tells us that vertices x and y are connected by an edge. Assume that there are no self-looping edges which connect a vertex to itself, and also assume that the graph is undirected, so that if Edge(x, y) is true, then Edge(y, x) must also be true. The graph will be used to represents a map, in which the vertices are cities and edges are highways between cities.

Suppose that we say that a city is a ”big city” if it’s connected to three or more other cities by a highway. Write a definition for a new predicate, Isolated(x), which tells us that x is not a big city, and there is no read that we can take from x which can lead us (directly or indirectly) to a big city. If we pass through five different cities until we eventually reach a big city, then x is not isolated, but if there’s no way to ever reach a big city, then it is isolated.

Note: it is legal, but not necessary, to define yet another predicate to help define Isolated(x). Hint: it may be necessary to use a recursive definition.

Answer 1

Hey there,

Due to Wyzant's character restriction, I will include mostly code.

The idea is we will loop through each edge contained in a given vertex's neighbors. We will see if each vertex the edge is pointing TO is a big city. If it is, we will return false (it is not isolated). Otherwise, we will return true if the counter exceeds 5 and no big city was found.

class Graph

{

private List<Vertex> adjacencyList;

public Graph()

{

adjacencyList = new List<Vertex>();

}

public bool IsBigCity(Vertex city)

{

// ADD UP NUMBER OF HIGHWAYS (EDGES)

int counter = 0;

foreach (Edge element in city.Neighbors)

{

counter += 1;

}

return counter >= 3;

}

public bool Isolated(Vertex city)

{

// ITERATE THROUGH HIGHWAYS (EDGES)

int counter = 0;

foreach (Edge element in city.Neighbors)

{

if (counter < 5 && IsBigCity(element.To) == true)

{

return false;

}

counter += 1;

}

return false;

}

}

Here is the Vertex and Edge class:

class Vertex

{

private string data;

private LinkedList<Edge> neighbors;

public Vertex(string data)

{

neighbors = new LinkedList<Edge>();

this.data = data;

}

public string Data { get => data; }

public LinkedList<Edge> Neighbors { get => neighbors; }

}

class Edge

{

private Vertex from;

private Vertex to;

private int weight;

public Edge(Vertex from, Vertex to, int weight)

{

this.from = from;

this.to = to;

this.weight = weight;

}

public Vertex To { get => to; }

public int Weight { get => weight; }

}