Package ca.uqac.lif.cep.graphviz

Class Graph

java.lang.Object
ca.uqac.lif.cep.graphviz.Graph
public class Graph extends Object
Simple representation of a directed graph.
Author:
Sylvain Hallé

  • Field Details

    • m_edges

      protected final Map<Integer,Set<Graph.Edge>> m_edges
      A collection of directed edges in this graph. Edges are indexed by source node to facilitate lookup.

    • m_vertexLabels

      protected final Map<Integer,String> m_vertexLabels
      A map associating vertex IDs to labels.

    • m_vertexIds

      protected final Map<String,Integer> m_vertexIds
      A map associating labels to vertex IDs.

    • m_inWeights

      protected final Map<Integer,Float> m_inWeights
      A map associating vertices to the sum of the weights on its incoming edges. Since edges are stored by source vertex, computing the input degree would require looping through every source vertex to look for a destination vertex, which would be very costly. The alternative is to update a separate map of the input degrees as the graph is manipulated.

    • m_vertexCounter

      protected int m_vertexCounter
      A counter for giving unique numbers to vertices.

    • m_incrementWeights

      protected boolean m_incrementWeights
      Whether to increment the weights or to replace the weight of an edge with a new value.

  • Constructor Details

    • Graph

      public Graph()
      Creates a new empty graph

    • Graph

      public Graph(Graph g)
      Creates a new graph by copying another graph.
      Parameters:
      g - The graph to copy

  • Method Details

    • incrementWeight

      public Graph incrementWeight(boolean b)
      Sets whether to increment the weights or to replace the weight of an edge with a new value
      Parameters:
      b - Set to true to increment weights, false to replace
      Returns:
      This graph

    • add

      public Graph add(String source, String destination, float weight)

    • add

      public Graph add(int source, int destination, float weight)

    • add

      public Graph add(Graph.Edge e)
      Adds an edge to the graph
      Parameters:
      e - The edge
      Returns:
      This graph

    • getEdge

      public Graph.Edge getEdge(int source, int destination)
      Finds the edge with given source and destination vertices
      Parameters:
      source - The source vertex
      destination - The destination vertex
      Returns:
      The edge, or null if no edge could be found

    • getInWeight

      public float getInWeight(String vertex)
      Returns the input weight of a vertex by designating a vertex label.
      Parameters:
      vertex - The vertex label
      Returns:
      The input weight, or -1 if the vertex does not exist

    • getInWeight

      public float getInWeight(int vertex)
      Returns the input weight of a vertex
      Parameters:
      vertex - The vertex
      Returns:
      The input weight, or -1 if the vertex does not exist

    • getOutWeight

      public float getOutWeight(int vertex)
      Returns the output weight of a vertex
      Parameters:
      vertex - The vertex
      Returns:
      The output weight, or 0 if the vertex does not exist

    • incrementWeight

      public Graph incrementWeight(String source, String destination, Number weight_increment)
      Increments the weight of an edge in the graph, by designating it with the labels of the source and destination vertices. If the edge does not exist, a new edge is created and its weight is set to weight_increment. Note that this method assumes that each vertex in the graph has a different label in order to be used.
      Parameters:
      source - The label of the source vertex
      destination - The label of the destination vertex
      weight_increment - The amount to add to the edge's weight
      Returns:
      This graph

    • incrementWeight

      public Graph incrementWeight(int source, int destination, Number weight_increment)
      Increments the weight of an edge in the graph. If the edge does not exist, a new edge is created and its weight is set to weight_increment.
      Parameters:
      source - The source vertex
      destination - The destination vertex
      weight_increment - The amount to add to the edge's weight
      Returns:
      This graph

    • toDot

      public String toDot()
      Outputs the graph in DOT format
      Returns:
      A DOT string

    • renderEdge

      public String renderEdge(Graph.Edge e)
      Renders an edge. Override this method to customize the rendering.
      Parameters:
      e - The edge to render
      Returns:
      The label

    • renderVertex

      public String renderVertex(String vertex)
      Renders a vertex. Override this method to customize the rendering.
      Parameters:
      vertex - The string corresponding to the vertex to render
      Returns:
      The Graphviz string that goes between the brackets

    • formatWeight

      protected static String formatWeight(float w)
      Removes decimals if number is an integer
      Parameters:
      w - The number
      Returns:
      A formatted string for that number

    • duplicate

      public Graph duplicate()
      Creates a deep copy of the graph.
      Returns:
      A copy of the graph

    • duplicate

      public Graph duplicate(boolean with_state)
      Creates a deep copy of the graph.
      Parameters:
      with_state - Has no effect
      Returns:
      A copy of the graph

    • clear

      public void clear()
      Clears the contents of the graph.