0

I am trying to find an appropriate data structure for representing available navigations between a game's screens.

  • Using a linked list, a node can only have one node after it : inappropriate.

  • Using a tree seems up to the job as nodes can have many children nodes but it's inconsistent in the sense that a supposedly children item Options can have a parent Title as a children. Also how am I supposed to represent the infinite sequence of the case Title -> Race -> Title -> Race ... without endlessly repeating it in my tree ? Still, this is the best structure I found to accomplish the job.

Here is an example of the possible sequences :

  1. Title
    • Options
    • Race
  2. Options
    • Title
    • Race
  3. Race
    • Options
    • Title

Do you know whether a tree is the way to go or if there's a better structure for this job ?


Edit:

There is a great library for creating graphs for C#/WPF : http://graphsharp.codeplex.com/

It uses http://quickgraph.codeplex.com/ internally.

Here's a small example :

enter image description here

Code-behind:

using System.Collections.Generic;
using System.Windows;
using GraphSharp.Controls;
using QuickGraph;

namespace WpfApplication15graph
{
    internal class ScreenVertex
    {
        public string Hello { get; set; }
    }

    internal class ScreenEdge : Edge<ScreenVertex>
    {
        public ScreenEdge(ScreenVertex source, ScreenVertex target)
            : base(source, target)
        {
        }
    }

    internal class ScreenLayout : GraphLayout<ScreenVertex, ScreenEdge, ScreenGraph>
    {
    }

    internal class ScreenGraph : BidirectionalGraph<ScreenVertex, ScreenEdge>
    {
    }

    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
            Loaded += MainWindow_Loaded;
        }

        private void MainWindow_Loaded(object sender, RoutedEventArgs e)
        {
            // build graph
            var screenGraph = new ScreenGraph();
            var screenVertex1 = new ScreenVertex {Hello = "1"};
            var screenVertex2 = new ScreenVertex {Hello = "2"};
            var screenVertex3 = new ScreenVertex {Hello = "3"};
            screenGraph.AddVertex(screenVertex1);
            screenGraph.AddVertex(screenVertex2);
            screenGraph.AddVertex(screenVertex3);
            screenGraph.AddEdge(new ScreenEdge(screenVertex1, screenVertex2));
            screenGraph.AddEdge(new ScreenEdge(screenVertex2, screenVertex1));
            screenGraph.AddEdge(new ScreenEdge(screenVertex1, screenVertex3));
            screenGraph.AddEdge(new ScreenEdge(screenVertex3, screenVertex1));
            screenGraph.AddEdge(new ScreenEdge(screenVertex3, screenVertex2));
            ScreenLayout.Graph = screenGraph;

            // get connections for a particular vertex
            IEnumerable<ScreenEdge> inEdges = screenGraph.InEdges(screenVertex3);
            IEnumerable<ScreenEdge> outEdges = screenGraph.OutEdges(screenVertex3);
        }
    }
}

XAML :

<Window x:Class="WpfApplication15graph.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:controls="clr-namespace:WPFExtensions.Controls;assembly=WPFExtensions"
        xmlns:controls1="clr-namespace:GraphSharp.Controls;assembly=GraphSharp.Controls"
        xmlns:wpfApplication15Graph="clr-namespace:WpfApplication15graph"
        Title="MainWindow"
        Width="525"
        Height="350">
    <Window.Resources>
        <DataTemplate x:Key="SvTemplate" DataType="wpfApplication15Graph:ScreenVertex">
            <Grid>
                <TextBlock Text="{Binding Hello}" />
            </Grid>
        </DataTemplate>
        <Style TargetType="controls1:VertexControl">
            <Style.Setters>
                <Setter Property="Template">
                    <Setter.Value>
                        <ControlTemplate TargetType="controls1:VertexControl">
                            <Border CornerRadius="5" Width="50" Height="50" Background="LightBlue">
                                <ContentPresenter Content="{TemplateBinding Vertex}"
                                                  ContentTemplate="{DynamicResource SvTemplate}" />
                            </Border>
                        </ControlTemplate>
                    </Setter.Value>
                </Setter>
            </Style.Setters>
        </Style>
    </Window.Resources>
    <Grid>
        <controls:ZoomControl>
            <wpfApplication15Graph:ScreenLayout x:Name="ScreenLayout"
                                                HighlightAlgorithmType="Simple"
                                                LayoutAlgorithmType="Circular"
                                                OverlapRemovalAlgorithmType="FSA" />
        </controls:ZoomControl>
    </Grid>
</Window>
  • 2
    Are you looking for a Directed Graph? – Dan Pichelman Nov 13 '13 at 19:04
  • I think so, thank you ! Can you add your comment as an answer so I can mark it as it ? – Aybe Nov 13 '13 at 19:10
4

You may want to consider a Directed Graph.

It's similar to a tree, but with fewer restrictions. You just have nodes with one-way links between them. You can make the structure as clean/well-organized/neat/messy/chaotic as you wish.

Be careful if your menu system becomes complicated - DGs can get messy.

  • I've been using it previously but totally forgot about its existence, thanks ! – Aybe Nov 13 '13 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.