Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Undirected Graphs #29

Open
daniel-j-h opened this issue Jul 26, 2021 · 2 comments
Open

Undirected Graphs #29

daniel-j-h opened this issue Jul 26, 2021 · 2 comments

Comments

@daniel-j-h
Copy link
Member

We should provide an undirected graph abstraction. At the moment the csr graph is directed.

For use what we have and turn it into an undirected graph, we'll need

then we can a forward and a reverse graph.

Or better: have one directed graph and for all (s,t) also store (t, s). Then have bitsets for what is a forward/reverse edge.
@daniel-j-h
Copy link
Member Author

Here is the dense bitset we can use for forward / backward edge flags

https://github.com/tinygraph/tinygraph/blob/a34e9facb1406ff2dabf7bf1db9112d06120d85a/tinygraph/tinygraph-bitset.h

@daniel-j-h
Copy link
Member Author

We just added a reversible graph copy feature

tinygraph/tinygraph/tinygraph.h

Line 82 in c68edc5

tinygraph_s tinygraph_copy_reversed(tinygraph_s graph);

We can now get a graph with edges reversed easily, the use case is as follows

  1. User constructs a regular graph
  2. User creates a reverse copy of the graph
  3. User can now traverse both graphs manually

This is a great step forward; ideally we'd have a proper undirected graph abstraction where the user has a single object at hand and does not have to know about a forward and backward graph, which makes combined traversal hard and quite a manual process. That's why I'm leaving this ticket open.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@daniel-j-h