Skip to content

chu_liu_edmonds

allennlp.nn.chu_liu_edmonds

[SOURCE]


decode_mst

def decode_mst(
    energy: numpy.ndarray,
    length: int,
    has_labels: bool = True
) -> Tuple[numpy.ndarray, numpy.ndarray]

Note: Counter to typical intuition, this function decodes the maximum spanning tree.

Decode the optimal MST tree with the Chu-Liu-Edmonds algorithm for maximum spanning arborescences on graphs.

Parameters

  • energy : numpy.ndarray
    A tensor with shape (num_labels, timesteps, timesteps) containing the energy of each edge. If has_labels is False, the tensor should have shape (timesteps, timesteps) instead.
  • length : int
    The length of this sequence, as the energy may have come from a padded batch.
  • has_labels : bool, optional (default = True)
    Whether the graph has labels or not.

chu_liu_edmonds

def chu_liu_edmonds(
    length: int,
    score_matrix: numpy.ndarray,
    current_nodes: List[bool],
    final_edges: Dict[int, int],
    old_input: numpy.ndarray,
    old_output: numpy.ndarray,
    representatives: List[Set[int]]
)

Applies the chu-liu-edmonds algorithm recursively to a graph with edge weights defined by score_matrix.

Note that this function operates in place, so variables will be modified.

Parameters

  • length : int
    The number of nodes.
  • score_matrix : numpy.ndarray
    The score matrix representing the scores for pairs of nodes.
  • current_nodes : List[bool]
    The nodes which are representatives in the graph. A representative at it's most basic represents a node, but as the algorithm progresses, individual nodes will represent collapsed cycles in the graph.
  • final_edges : Dict[int, int]
    An empty dictionary which will be populated with the nodes which are connected in the maximum spanning tree.
  • old_input : numpy.ndarray
  • old_output : numpy.ndarray
  • representatives : List[Set[int]]
    A list containing the nodes that a particular node is representing at this iteration in the graph.

Returns

  • Nothing - all variables are modified in place.