Package edu.ucsb.cs.scaffold.services

Class ConceptGraphService

java.lang.Object

edu.ucsb.cs.scaffold.services.ConceptGraphService

@Service
public class ConceptGraphService
extends Object

Graph algorithms for the prerequisite structure of a course's top-level concepts (subconcepts have no position in this graph). Prerequisite edges only ever connect top-level concepts, so every method here operates on that subgraph.

reset(java.util.List<edu.ucsb.cs.scaffold.entity.Concept>, java.util.List<edu.ucsb.cs.scaffold.entity.ConceptEdge>) is the analysis run by POST /api/course/scaffold/reset: it detects cycles (flagging their edges rather than processing them further), removes edges that are redundant given the graph's transitive structure, ranks concepts by longest path from a root, and lays out each level's x,y position. It is a pure function of its inputs — no repository access — so the controller owns loading input and persisting the result.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final record	ConceptGraphService.Position
static final record	ConceptGraphService.ResetResult

Field Summary

Fields

Modifier and Type	Field	Description
static final String	CYCLE_EDGE_COLOR
static final List<String>	LEVEL_COLORS
static final int	MIN_HORIZONTAL_SEPARATION
static final int	VERTICAL_LEVEL_SEPARATION

Constructor Summary

Constructors

Constructor	Description
ConceptGraphService()

Method Summary

Modifier and Type	Method	Description
String	colorForLevel(int level)	The color assigned to a top-level concept at the given longest-path level (1-based).
ConceptGraphService.ResetResult	reset(List<Concept> topLevelConcepts, List<ConceptEdge> edges)	Runs the full scaffold reset analysis: cycle detection, transitive reduction, longest-path leveling, and layout.
ConceptGraphService.ResetResult	reset(List<Concept> topLevelConcepts, List<ConceptEdge> edges, Map<Long,Integer> priorXByConceptId)	Like reset(List, List), but sorts each level by the given prior x values instead of each concept's own x column.
boolean	wouldCreateCycle(List<ConceptEdge> existingEdges, Long sourceId, Long targetId)	True if adding an edge sourceId -> targetId would create a cycle, i.e. targetId can already reach sourceId via existingEdges.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

LEVEL_COLORS

public static final List<String> LEVEL_COLORS

CYCLE_EDGE_COLOR

public static final String CYCLE_EDGE_COLOR

See Also:

• Constant Field Values

MIN_HORIZONTAL_SEPARATION

public static final int MIN_HORIZONTAL_SEPARATION

See Also:

• Constant Field Values

VERTICAL_LEVEL_SEPARATION

public static final int VERTICAL_LEVEL_SEPARATION

See Also:

• Constant Field Values

Constructor Details

ConceptGraphService

public ConceptGraphService()

Method Details

colorForLevel

public String colorForLevel(int level)

The color assigned to a top-level concept at the given longest-path level (1-based).

wouldCreateCycle

public boolean wouldCreateCycle(List<ConceptEdge> existingEdges,
 Long sourceId,
 Long targetId)

True if adding an edge sourceId -> targetId would create a cycle, i.e. targetId can already reach sourceId via existingEdges. Used to reject new prerequisite edges at creation time, before a cycle can ever be persisted.

reset

public ConceptGraphService.ResetResult reset(List<Concept> topLevelConcepts,
 List<ConceptEdge> edges)

Runs the full scaffold reset analysis: cycle detection, transitive reduction, longest-path leveling, and layout. Does not mutate concepts or edges or read/write any repository; the caller applies ConceptGraphService.ResetResult to persistent entities.

Parameters:

topLevelConcepts - every top-level concept in the course (used for their id/x, to sort and lay out concepts with no edges at all, and as the node set for the graph algorithms)

edges - every prerequisite edge in the course

reset

public ConceptGraphService.ResetResult reset(List<Concept> topLevelConcepts,
 List<ConceptEdge> edges,
 Map<Long,Integer> priorXByConceptId)

Like reset(List, List), but sorts each level by the given prior x values instead of each concept's own x column. Used by the controller to sort by the requesting user's private, unsaved drag positions where they exist, falling back to the concept's persisted x otherwise — see POST /api/course/scaffold/reset.