Weighted Directed Graphs - Eishaaya/GMRDataStructuresTest GitHub Wiki

Applications:

Weighted and directed graphs are significantly more versatile than unweighted and undirected graphs. They allow computer scientists to model many of the networks in the real world: GPS maps, social networks, language structure, etc.

In our code example we have three classes for a weighted graph. The new class that is being added is an Edge class which will help us define direction within our graph. We will be making a small change in our class however. Instead of doing a public get and a private set for the list of vertices, we will now use an IReadOnlyList. An IReadOnlyList will allow anyone to reference the list without adding or removing any elements in our collection.

public class Edge<T>
{
    public Vertex<T> StartingPoint { get; set; }
    public Vertex<T> EndingPoint { get; set; }
    public float Distance { get; set; }

    public Edge(Vertex<T> startingPoint, Vertex<T> endingPoint, float distance) {...}
}

public class Vertex<T>
{
    public T Value { get; set; }
    public List<Edge<T>> Neighbors { get; set; }

    public int NeighborCount => Neighbors.Count;

    public Vertex(T value) {...}
}

public class Graph<T>
{
    private List<Vertex<T>> vertices;
    
    public IReadOnlyList<Vertex<T>> Vertices => vertices;
    public IReadOnlyList<Edges<T>> Edges { get {...} }

    public int VertexCount => vertices.Count;

    public Graph() {...}
}

• Check if the vertex is null, contains any neighbors, and does not exist within our list. If none of these are true, add it to the list.

• If the vertex exists within the graph, remove all the edges where the vertex is the ending point, remove the vertex from the list, and return true. If it does not exist within the graph return false.

• Check if both of the vertices are null, check if they both exist in the list, and check that the same edge does not already exist. If none of these are true, create the edge where a is the starting point and b is the ending point.

• Check if both of the vertices are not null and that the edge with starting point a and ending point b exists to be able to remove the edge between the two vertices.

• Create an int variable equal to -1. Then loop through all the vertices and check if the value equals to any of the vertices. If so set the int variable to that index and break out of the loop. If the int is -1 then return null else return the vertex at that index.

• Check if both of the vertices are not null and that the edge with the starting point a and ending point b exists to return the edge.

If you have tried this assignment and either are still stuck or have finished and would like to see how it has been implemented see this link DirectedGraphExample

• Using Depth-First or Breadth-First search find a path from one given vertex to another. Compare the cost of the path between the two search functions.

• Take a look at our implementation if you are stuck.
  • Directed Weighted Graph C#
  • Directed Weighted Graph C++

<-- Previous | Next -->