Package com.pnfsoftware.jeb.util.graph

Class Digraph

java.lang.Object
com.pnfsoftware.jeb.util.graph.Digraph
public class Digraph extends Object
A directed graph object, cyclic or acyclic. Self-loops (x>x) are also allowed. Duplicate edges are not allowed, e.g. if an edge x>y exists, another edge x>y cannot be added (a way to represent this information is to specify an edge weight).

  • Constructor Details

    • Digraph

      public Digraph()
      Create an empty directed graph.

  • Method Details

    • create

      public static Digraph create()
      Create an empty directed graph.
      Returns:
      an empty directed graph

    • copyOfVertices

      public List<Digraph.V> copyOfVertices()
      Create a copy of the graph vertices.
      Returns:
      cloned vertices in index order

    • copyOfEdges

      public List<Digraph.E> copyOfEdges()
      Create a copy of the graph edges.
      Returns:
      cloned edges in edge insertion order

    • getVertexCount

      public int getVertexCount()
      Get the number of vertices.
      Returns:
      the vertex count

    • getVertices

      public List<Digraph.V> getVertices()
      Get the graph vertices.
      Returns:
      the internal vertex list in index order

    • getVertex

      public Digraph.V getVertex(int id)
      Get a vertex by id.
      Parameters:
      id - vertex id
      Returns:
      the vertex, or null if no vertex has this id

    • getVertexByIndex

      public Digraph.V getVertexByIndex(int index)
      Get a vertex by index.
      Parameters:
      index - vertex index
      Returns:
      the vertex at that index

    • getVertexLabel

      public String getVertexLabel(int id)
      Get a vertex label by vertex id.
      Parameters:
      id - vertex id
      Returns:
      the vertex label, or null if none was assigned

    • setVertexLabel

      public void setVertexLabel(int id, String label)
      Set a vertex label by vertex id.
      Parameters:
      id - vertex id
      label - vertex label, or null to clear it

    • setVertexLabels

      public void setVertexLabels(Object... idLabels)
      Set multiple vertex labels.

      Arguments are read as Integer, String pairs. Pairs whose values do not match those types are ignored.

      Parameters:
      idLabels - alternating vertex ids and labels

    • removeVertex

      public void removeVertex(Digraph.V v, boolean reconnectEdges)
      Remove a vertex and all incident edges.
      Parameters:
      v - vertex to remove
      reconnectEdges - true to connect each predecessor of the removed vertex to each of its successors

    • getEdgeCount

      public int getEdgeCount()
      Get the number of edges.
      Returns:
      the edge count

    • getEdges

      public List<Digraph.E> getEdges()
      Get the graph edges.
      Returns:
      the internal edge list in insertion order

    • getEdge

      public Digraph.E getEdge(int index)
      Get an edge by index.
      Parameters:
      index - edge index
      Returns:
      the edge at that index

    • removeEdge

      public void removeEdge(Digraph.E e)
      Remove an edge.
      Parameters:
      e - edge to remove

    • removeEdge

      public void removeEdge(int index)
      Remove an edge by index.
      Parameters:
      index - edge index

    • getEdge

      public Digraph.E getEdge(int srcId, int dstId)
      Get an edge by source and destination vertex ids.
      Parameters:
      srcId - source vertex id
      dstId - destination vertex id
      Returns:
      the edge, or null if no such edge exists

    • v

      public Digraph v(int id, Double weight, String label)
      Add a vertex to this graph.
      Parameters:
      id - vertex id
      weight - optional vertex weight
      label - optional vertex label
      Returns:
      this graph

    • v

      public Digraph v(int id, Double weight)
      Add a vertex to this graph.
      Parameters:
      id - vertex id
      weight - optional vertex weight
      Returns:
      this graph

    • v

      public Digraph v(int id)
      Add a vertex to this graph.
      Parameters:
      id - vertex id
      Returns:
      this graph

    • e

      public Digraph e(int srcId, int dstId, Double weight)
      Add an edge to this graph, creating missing endpoint vertices if needed.
      Parameters:
      srcId - source vertex id
      dstId - destination vertex id
      weight - optional edge weight
      Returns:
      this graph

    • e

      public Digraph e(int srcId, int dstId)
      Add an unweighted edge to this graph, creating missing endpoint vertices if needed.
      Parameters:
      srcId - source vertex id
      dstId - destination vertex id
      Returns:
      this graph

    • done

      public Digraph done()
      Verify the graph after an initial build step.
      Returns:
      this graph

    • resetEdgeBetweennessScores

      public void resetEdgeBetweennessScores()
      Reset edge-betweenness and vertex centrality scores to zero.

    • computeEdgeBetweenness

      public List<Integer> computeEdgeBetweenness()
      Compute the edge-betweenness score of all edges of the graph using Girvan-Newman. The scores are available through Digraph.E.getEdgeBetweennessScore().
      Returns:
      a list of edge indexes ordered by descending order of edge-betweenness score; e.g., if the first element of the list is 2, it means that the third registered edge (getEdge(2)) is the one with the highest EB score

    • getEdgeIndexesByDescendingBetweenness

      public List<Integer> getEdgeIndexesByDescendingBetweenness()
      Get edge indexes ordered by descending edge-betweenness score.
      Returns:
      a list of edge indexes ordered by descending score

    • getVertexIndexesByDescendingCentrality

      public List<Integer> getVertexIndexesByDescendingCentrality()
      Get vertex indexes ordered by descending vertex centrality score.
      Returns:
      a list of vertex indexes ordered by descending score

    • isWeaklyConnected

      public boolean isWeaklyConnected()
      Determine if this directed graph is weakly connected, that is, if the corresponding undirected graph is connected.
      Returns:
      true if all vertices belong to a single weakly connected component

    • getWeaklyConnectedComponents

      public List<Digraph> getWeaklyConnectedComponents()
      Split this graph into weakly connected components.
      Returns:
      weakly connected component subgraphs; if this graph is already weakly connected, the returned list contains this graph

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • isAdjacent

      public boolean isAdjacent(Digraph.V from, Digraph.V to)
      Determine whether two vertices are directly connected by an edge.
      Parameters:
      from - source vertex
      to - destination vertex
      Returns:
      true if an edge exists from from to to

    • canReach

      public boolean canReach(Digraph.V from, Digraph.V to)
      Determine whether a vertex can reach another vertex by following directed edges.
      Parameters:
      from - source vertex
      to - destination vertex
      Returns:
      true if to is reachable from from

    • getReachableVertices

      public Set<Integer> getReachableVertices(int fromId)
      Get all vertices reachable from a vertex.
      Parameters:
      fromId - source vertex id
      Returns:
      ids of vertices reachable from the source vertex

    • load

      public static Digraph load(File file) throws IOException
      Load a graph from a text file.
      Parameters:
      file - graph definition file
      Returns:
      the loaded graph
      Throws:
      IOException - if the file cannot be read