gephi / gephi/graphstore

No O(1) way to read parallel-edge count/index from an Edge, needed for rendering

Open
#297 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
93
Forks
34
Avg merge
18h 53m
Merged PRs (30d)
13

Description

## Summary

Gephi's rendering engine cannot draw parallel edges (multiple edges between the same pair of nodes) correctly. To draw them as distinct, non-overlapping curves/arcs, the renderer needs to know, for each edge: how many parallel edges exist between its two endpoints, and which one of those this particular edge is (an index it can use to offset/space the curve).

Today, `Graph` only exposes `getEdges(node1, node2)` / `getEdges(node1, node2, type)`, which return an `EdgeIterable` that must be iterated (and counted) to learn the multiplicity, and there is no way at all to learn an edge's position within that set. Gephi already iterates every edge once, in parallel across threads, to build its render objects, so this lookup needs to be cheap and safe to call concurrently from many threads for every edge — an O(1), thread-safe read is required; anything that re-walks or re-counts the parallel set per edge (O(k) per edge, O(E·k) overall) is a non-starter at render time.

## Why it matters

- Parallel edges currently overlap visually in Gephi with no way to distinguish them.
- There's no supported way for a renderer (or any API consumer) to answer "how many edges are there between these two nodes" or "where does this edge fall among them" without manually collecting and counting `getEdges(node1, node2)` for every edge, every frame — which defeats the purpose of the existing single-pass parallel iteration the renderer already does.
- This is purely a missing-capability gap, not a bug: `isEnableParallelEdgesSameType()` (`ConfigurationImpl.java`) already allows creating parallel edges; there's just no efficient way to introspect them once created.

## Proposed API changes

Two new read accessors on `Edge` (`src/main/java/org/gephi/graph/api/Edge.java`), analogous in spirit to existing edge accessors like `isSelfLoop()` / `isMutual()`:

```java
/**
* Returns the number of edges (including this one) that share this edge's
* source and target node pair.
*


* Returns 1 if this edge has no parallel edges.
*
* @return the parallel edge count
*/
public int getParallelEdgeCount();

/**
* Returns this edge's index among the edges that share its source and
* target node pair.
*


* The value is in {@code [0, getParallelEdgeCount() - 1]}. Returns 0 if
* this edge has no parallel edges.
*
* @return the parallel edge index
*/
public int getParallelEdgeIndex();
```

Open questions to settle during design/implementation (explicitly out of scope for this issue):

- Whether "parallel" is scoped per edge type or across all types between the pair (existing `getEdges(node1, node2)` vs `getEdges(node1, node2, type)` suggests both may be wanted).
- Whether index assignment is stable across removals or may be reassigned (e.g. via swap-on-remove) as long as it stays contiguous.
- Whether a corresponding `Graph.getEdgeCount(node1, node2[, type])` convenience method is also warranted, independent of a specific `Edge` instance.

## Scope / risk

- Purely additive to the public `Edge` API; no existing method signatures change.
- Affects `EdgeStore`/`EdgeImpl` internals to maintain the new values incrementally, but that's an implementation concern for a follow-up PR, not this issue.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with src/main/java/org/gephi/graph/api/Edge.java and the existing Graph.getEdges(node1, node2[, type]) accessors. Then inspect the mentioned EdgeStore and EdgeImpl internals, settling the parallel-edge scope and index behavior before implementation. Done means the additive reads are O(1), thread-safe, and expose contiguous count and index values.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
backend-api-design
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.