Search code examples
c#graph-theoryadjacency-listclique-problem

Random adjacency list generator

I am currently working on developing an application to find the maximum clique in a graph for my final year project. I have most the project complete and am just starting to test the application.

The application currently uses an adjacency list as an input and I was wondering if anyone knew of an adjacency list random generator, so I can test my application?

Many thanks

Solution

  • This problem is much easier to address if you think about the graphs in terms of adjacency matrices rather than adjacency lists. A graph with m vertices can be represented by an m by m matrix where each edge is 0 if it is absent, or 1 if it is present.

    For a directed graph, all elements are required, but for an undirected graph, you'll need a upper triangular matrix.

    Once you've got the adjacency matrix, you can easily convert it to adjacency lists.