logo
down
shadow

How to represent an undirected weighted graph in java


How to represent an undirected weighted graph in java

Content Index :

How to represent an undirected weighted graph in java
Tag : java , By : Nick
Date : January 11 2021, 05:14 PM

I wish did fix the issue. There are many different way to represent vertices, edges and a graph. Here is an over-simplified one:
Define a directional Edge :
class Edge {

    private Vertex to; 
    private int weight;

    public Edge(Vertex to, int weight) {
        super();
        this.to = to;
        this.weight = weight;
    }

    Vertex getTo() {
        return to;
    }

    int getWeight() {
        return weight;
    }   

    //todo override hashCode()
}
class Vertex { 

    private String label;
    private Set<Edge> edges; //collection of edges to neighbors 

    public Vertex(String pageObject) {
        this.label = pageObject;
        edges = new HashSet<>();
    }

    String getLabel() {
        return label;
    }

    boolean addEdge(Edge edge){
        return edges.add(edge);
    }

    List<Edge> getEdges() {
        return new ArrayList<>(edges);
    }

    //todo override hashCode()
}
class Graph{

    private Set<Vertex> vertices; //collection of all verices 

    public Graph() {
        vertices = new HashSet<>();
    } 

    List<Vertex> getVertices() {
        return new ArrayList<>(vertices);
    }   

    boolean addVertex(Vertex vertex){
        return vertices.add(vertex);
    }
}
public static void main(String[] args) {

    Graph graph = new Graph();

    //construct vertices 
    Vertex v1 = new Vertex("1"); 
    Vertex v2 = new Vertex("2"); 
    Vertex v3 = new Vertex("3");
    Vertex v4 = new Vertex("4");
    Vertex v5 = new Vertex("5");

    //to make the graph un directed use the same weight 
    //both ways 
    v1.addEdge(new Edge(v2, 1)); //connect v1 v2 
    v2.addEdge(new Edge(v1, 1));   

    v2.addEdge(new Edge(v3, 2)); //connect v2 v3
    v3.addEdge(new Edge(v2, 2));

    v2.addEdge(new Edge(v4, 3)); //connect v2 v4
    v4.addEdge(new Edge(v2, 3));

    v4.addEdge(new Edge(v5, 1)); //connect v4 v5
    v5.addEdge(new Edge(v4, 1));

     graph.addVertex(v1); graph.addVertex(v2); graph.addVertex(v3);
     graph.addVertex(v4); graph.addVertex(v5);  
}

Comments
No Comments Right Now !

Boards Message :
You Must Login Or Sign Up to Add Your Comments .

Share : facebook icon twitter icon

What are some ways I can represent a weighted, directed graph in Java?


Tag : java , By : Randoa
Date : March 29 2020, 07:55 AM
To fix the issue you can do The answer depends a lot on the algorithms that you are planning to apply to your graphs.
There are two common ways to represent a graph - an adjacency list and an adjacency matrix. In your case, and adjacency matrix is a square array of integers representing weights. Your representation uses an adjacency list.

How to represent given adjacency matrix as undirected weighted graph in matlab?


Tag : matlab , By : Ricardo
Date : March 29 2020, 07:55 AM
Hope this helps To get only one edge between each vertex, you only want a triangular matrix.
If you try something like this:
table1 = (table2 + table2') - triu((table2 + table2')) 
table1 =
     0     0     0     0     0
     4     0     0     0     0
     5     6     0     0     0
     2     3     4     0     0
     8     6     7     5     0

bg = biograph(table1,[],'ShowArrows','off','ShowWeights','on');
h = view(bg);

Floyd Warshall (all-pairs shortest paths) on weighted undirected graph - Boost Graph


Tag : cpp , By : gcomstock
Date : March 29 2020, 07:55 AM
wish of those help I figured (with the help of the inter-webs) that I need to use boost::get(boost::edge_weight, g) to directly supply an undirected weighted graph to floyd warshall. The following code compiles and works (here is a figure of the graph for the example below)
#include <iostream>
#include <boost/graph/undirected_graph.hpp>
#include <boost/graph/exterior_property.hpp>
#include <boost/graph/floyd_warshall_shortest.hpp>

// type for weight/distance on each edge
typedef double t_weight;

// define the graph type
typedef boost::property<boost::edge_weight_t, t_weight> EdgeWeightProperty;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, 
                              boost::no_property, EdgeWeightProperty> Graph;

typedef boost::property_map<Graph, boost::edge_weight_t>::type WeightMap;

// Declare a matrix type and its corresponding property map that
// will contain the distances between each pair of vertices.
typedef boost::exterior_vertex_property<Graph, t_weight> DistanceProperty;
typedef DistanceProperty::matrix_type DistanceMatrix;
typedef DistanceProperty::matrix_map_type DistanceMatrixMap;


int main()
{
  Graph g;

  const int num_edges = 11;

  // define edges
  int edges[] = { 1,     2,
                  1,     3,
                  1,     4,
                  2,     5,
                  3,     4,
                  3,     6,
                  4,     5,
                  4,     6,
                  4,     7,
                  5,     7,
                  6,     7 };

  // define the weight on edges
  t_weight weight[] = {  4,
                        10,
                         3,
                         1,
                        12,
                        20,
                         6,
                         3,
                         0,
                         3,
                         9 };

  // iterate over all edges and insert them in the graph
  for (std::size_t k = 0; k < num_edges; ++k)
    boost::add_edge(edges[k*2]-1, edges[k*2+1]-1, weight[k], g);

  WeightMap weight_pmap = boost::get(boost::edge_weight, g);

  // set the distance matrix to receive the floyd warshall output
  DistanceMatrix distances(num_vertices(g));
  DistanceMatrixMap dm(distances, g);

  // find all pairs shortest paths
  bool valid = floyd_warshall_all_pairs_shortest_paths(g, dm, 
                                            boost::weight_map(weight_pmap));

  // check if there no negative cycles
  if (!valid) {
    std::cerr << "Error - Negative cycle in matrix" << std::endl;
    return -1;
  }

  // print upper triangular part of the distance matrix
  std::cout << "Distance matrix: " << std::endl;
  for (std::size_t i = 0; i < num_vertices(g); ++i) {
    for (std::size_t j = i; j < num_vertices(g); ++j) {
      std::cout << "From vertex " << i+1 << " to " << j+1 << " : ";
      if(distances[i][j] == std::numeric_limits<t_weight>::max())
        std::cout << "inf" << std::endl;
      else
        std::cout << distances[i][j] << std::endl;
    }
    std::cout << std::endl;
  }

  return 0;
}

How to write a toString method for a weighted undirected graph in java?


Tag : java , By : Gilmar Souza Jr.
Date : March 29 2020, 07:55 AM
I wish this help you Your definition of the method V() is recursive and probably is going into an infinite loop. You probably want it to be:
public int V(){
    return V;
}

What way I can represent a weighted, directed graph in Java?


Tag : java , By : Topher Cyll
Date : March 29 2020, 07:55 AM
I hope this helps . I need a method that would traverse the graph by operating on adjacency, returning the total weight of path. I'm not sure how to go about adding weight in the method "public double getPathWeight(List path)". Also, possibly I have the feeling that my public void addEdge method might contain some errors, so if I could get some pointers on that method as well, it would help me out tremendously completing my graph. My graph is written in terms of a generic VertexType parameter. And I am operating on an adjacency list data structure. , To keep it simple, I'd like you to ponder upon somethings:
public void addEdge(VertexType v1, VertexType v2, double weight) {
    adjacency.computeIfAbsent(v1, v -> new HashMap<>()).put(v2,weight);
}
public double getPathWeight(List<VertexType> path) throws GraphPathException {
    VertexType previousVertex = path.get(0);

    double resultWeight = 0.0;
    for (int i = 1; i < path.size(); i++) {
        VertexType currentVertex = path.get(i);
        Map<VertexType, Double> adjacencyForPreviousVertex = adjacency.get(previousVertex);
        if (adjacencyForPreviousVertex == null) {
            throw new GraphPathException("Vertex " + previousVertex + " don't exist in graph");
        }
        Double currentEdgeWeight = adjacencyForPreviousVertex.get(currentVertex);
        if (currentEdgeWeight == null) {
            throw new GraphPathException(currentVertex + "Vertex don't exist as an adjacent Vertex of " + previousVertex);
        }
        resultWeight += currentEdgeWeight;
        previousVertex = currentVertex;
    }
    return resultWeight;
}
Related Posts Related QUESTIONS :
  • How to Inject Dependencies into a Servlet Filter with Spring Boot Filter Registration Bean?
  • Thrift types as a Generic
  • Effective algorithm to random 4 unique integers less than a big max such as 100_000
  • Combining or and negation in Java regex?
  • Unable to instantiate default tuplizer Exception
  • Multi-tenant migration to work with quarkus
  • Ignite persisting a Set: Cannot find metadata for object with compact footer
  • Maven cannot resolve Jacob dependency using eclipse
  • testcontainers oracle database container starts before database user is created
  • Launching two spring boot apps in integration test
  • Is there a way to add a HashMap's value that is a integer array into a ArrayList?
  • Is there any way that I can get a parameter in paintComponent?
  • Empty stack with one recursive method and one iterative method
  • What's the behavior of onBackpressureBuffer in RxJava2
  • Java regex can only use 1 quantifier in a lookback (need 2)
  • How to fix error in native query : it is showing syntax error near or at
  • How to retrieve nested object from a document and display it in FirestoreRecyclerOptions?
  • Why not use ListIterator for full LinkedList Operation?
  • Android Webview EvaluateJavascript sometimes does not return a response
  • Matcher java doesn't work but regex seems to be good
  • Finding dimensions of a .gif file
  • Java Number format how to change +/- sign to custom text
  • Entity partially saved when using JOINED inheritance strategy and setting spring.jpa.properties.hibernate.jdbc.batch_siz
  • Stored Procedure in Java Spring Boot Project returns null as Output
  • How to solve org.hibernate.MappingException which is causing due to inheriting a class
  • Clean Archtecture. Understanding of scheme
  • Processing 3 triangle not showing in Javafx 8 Window tab
  • How to specify a sequence-based generated value in Hibernate 5 via legacy mapping
  • Spring-boot application not getting auto-deployed on startup
  • How to only pass strings that the user select
  • Is there a way to SELECT using "GREATEST(field1, field2)" where field1 and field2 are aggregate sums in the sa
  • How to handle JSON objects wrapped into one JSON object with retrofit2?
  • Configure Hazelcast CPSubsystem Retries Timeout
  • how to use onBindViewHolder with multiple items in android RecyclerView
  • No ParameterResolver registered for parameter in BeforeAll method
  • Finding the path in a graph with the least casualties according to the lanchester square law
  • MongoWriteException when inserting into Mongodb with composite custom _id
  • Fetch Oracle procedure metadata with Java when multiple procedure signatures
  • Value modification of key-pair in HashMap and impact for a HashCode
  • Migration from solrj to spring-data-solr
  • How to check if you're still connected to the database with jpa
  • Use Date type in the graphql scheme
  • Split and add the string based on length
  • Is "main" method of spring boot application required when deploy as war
  • Getting the average within specific numbers in an array
  • how to use izpack to make my jar application to installer?
  • What is meant by src in Java Eclipse?
  • Create a mirrored linked list in Java
  • Examples of good JPA Java Desktop Application
  • Translate Java to Python -- signing strings with PEM certificate files
  • Algorithm Analysis tool for java
  • Java serial comm API - what does inputstream.read() return if a timeout occurs?
  • How do I make a background thread in Java that allows the main application to exit completely? This works in Linux, but
  • How to add an image dynamically at runtime in java
  • Java App on Mac asking for allow network connections everytime
  • Best actively maintained Java XMPP Library?
  • Multi-Threaded Application - Help with some pseudo code!
  • Scoping a StringBuilder inside a for loop
  • How to specify hash algorithm when updating LDAP via Java?
  • Class not found exception (org.apache.openjpa.enhance.PersistenceCapable) thrown in a client of WLS 10
  • shadow
    Privacy Policy - Terms - Contact Us © scrbit.com