resonance 1.0.1
Loading...
Searching...
No Matches
netflow.h File Reference

Go to the source code of this file.

Classes

struct  netflow_edge
 One edge in the adjacency list of a U vertex. More...
struct  netflow_u_vertex
 One vertex of the U set. More...
struct  netflow_graph
 The U set and its adjacency lists. More...
struct  netflow_v_side
 The V set. More...

Enumerations

enum  { NETFLOW_MAX_VERTICES = 2500 }
 Bipartite matching from the netflow package. More...

Functions

void Init_U (struct netflow_graph *graph)
 Clear every adjacency list and mate of a graph, and its U count.
void Init_V (struct netflow_v_side *side)
 Clear every mate of a V set, and its V count.
void AddEdge (int u, int v, struct netflow_graph *graph, struct netflow_v_side *side)
 Add an edge from a U vertex to a V vertex.
void Match (struct netflow_graph *graph, struct netflow_v_side *side)
 Find a maximum matching of graph against side.

Enumeration Type Documentation

◆ anonymous enum

anonymous enum

Bipartite matching from the netflow package.

The package is vendored into the image, which its diagnostics establish ("Inconsistent matching between %d(U) and %d(V)" and "matching NOT maximum; augm. path:"). This header declares only the part that Rnd::Mesh::AssignFlatVerts() uses, with the layouts that routine and the four entry points below read and write. The type names are inferred.

Both vertex sets are numbered from 1, and a mate of 0 means unmatched. Capacity of each vertex set, including the unused entry 0.

Enumerator
NETFLOW_MAX_VERTICES 

Function Documentation

◆ Init_U()

void Init_U ( struct netflow_graph * graph)

Clear every adjacency list and mate of a graph, and its U count.

Parameters
graphThe graph to clear.
Ghidra address:
NTSC-U/C: 0x005e6508
Ghidra address:
PAL: 0x006286f0

◆ Init_V()

void Init_V ( struct netflow_v_side * side)

Clear every mate of a V set, and its V count.

Parameters
sideThe V set to clear.
Ghidra address:
NTSC-U/C: 0x005e64e8
Ghidra address:
PAL: 0x006286d0

◆ AddEdge()

void AddEdge ( int u,
int v,
struct netflow_graph * graph,
struct netflow_v_side * side )

Add an edge from a U vertex to a V vertex.

Prepends the edge to the adjacency list of u. The routine also allocates a second record for the reverse direction, stores u in it, and links it nowhere; side is not read.

Parameters
uThe U vertex, from 1.
vThe V vertex, from 1.
graphThe graph that owns u.
sideThe V set.
Ghidra address:
NTSC-U/C: 0x005e6538
Ghidra address:
PAL: 0x00628720

◆ Match()

void Match ( struct netflow_graph * graph,
struct netflow_v_side * side )

Find a maximum matching of graph against side.

Seeds a greedy matching, reports its size, and then grows it along augmenting paths. The result is left in the mate members of both sets.

Parameters
graphThe U set and its edges.
sideThe V set.
Ghidra address:
NTSC-U/C: 0x00569bf0
Ghidra address:
PAL: 0x005aa0b8